全國計算機(jī)等級考試二級公共基礎(chǔ)知識課件版.ppt

2003.11.,全國計算機(jī)等級考試 二級公共基礎(chǔ)知識 (2),2004.2,.程序設(shè)計基本概念,1.1 計算機(jī)工作原理,通過工作原理了解，熟悉計算機(jī)內(nèi)部執(zhí)行功能的基本意義。為理解程序打下基礎(chǔ)，特別理解計算機(jī)是機(jī)器。,1.2 程序概念,什么是程序？ 指令的集合。（解釋指令） 通過硬件控制系統(tǒng)自動完成某一功能。 通過一系列代碼實(shí)現(xiàn)。,1.3 程序怎樣執(zhí)行？怎樣編寫？, 計算機(jī)本身僅能識別二進(jìn)制代碼“0”、“1”。 編程最直接、最低級的就是機(jī)器語言。 為解決機(jī)器語言難理解、記憶等問題。出現(xiàn)符號語言。 為使編程接近自然語言，出現(xiàn)高級語言。如C、PASCAL、FORTRAN, 為配合高級語言編程，出現(xiàn)了開發(fā)工具，提高效率、減輕勞動量。如VB、VC、PB、Dephi、VFP等。因此VFP不是編程語言。 不管什么形式編寫代碼，最終都應(yīng)將代碼翻譯成機(jī)器語言，這就是編譯程序的工作。不同的語言有不同的編譯器。 程序控制是一種邏輯控制。因此，嚴(yán)謹(jǐn)?shù)倪壿嬎季S是一個程序員必備的基本素質(zhì)。, 用程序?qū)崿F(xiàn)某一功能。有許多方法。具體用哪種完全取決于程序員個人的思維方式。因此，程序是腦力勞動的結(jié)晶，從某種意義上，編程又是一門藝術(shù)。 程序的特殊性決定了程序的復(fù)雜性，且與實(shí)現(xiàn)功能的復(fù)雜性密切相關(guān)成正比。因此為使復(fù)雜的、智力的編程工作規(guī)范化、科學(xué)化，便出現(xiàn)了各種編程設(shè)計方法。如結(jié)構(gòu)化編程方法、面向?qū)ο蟮某绦蛟O(shè)計方法等。, 不管用什么方法編程，不管編程者智力程度如何，不管采用什么樣的編程語言和方法，程序最終完成的功能穩(wěn)定、可靠、實(shí)用、易維護(hù)和安全等是程序的最終目標(biāo)，也是程序員的追求。 程序設(shè)計是一個復(fù)雜艱巨的過程。編寫代碼僅是程序設(shè)計的一部分。必須先有思想，再有方法，然后才是編寫代碼，且要經(jīng)過許多反復(fù)，不可急功近利。,1.4 程序設(shè)計語言或工具, 程序設(shè)計語言指的是用來編寫程序的語言。 人與計算機(jī)交流要使用語言，以便讓計算機(jī)工作，計算機(jī)也通過語言把結(jié)果告訴用計算機(jī)的人“人機(jī)對話”。 人與計算機(jī)交流的語言非平常人與人之間交流的語言，是專門的語言程序設(shè)計語言。, 程序設(shè)計語言是計算機(jī)系統(tǒng)軟件的重要組成部分。 執(zhí)行程序設(shè)計的語言有很多，可分高級語言和低級語言，區(qū)別在于接近自然語言的程度 高級語言一般與具體的計算機(jī)硬件無關(guān)，比較接近人類自然語言的語法習(xí)慣及數(shù)學(xué)表達(dá)形式。 用高級語言編寫的源程序不能被機(jī)器直接執(zhí)行，需通過編譯成解釋程序的翻譯才可被機(jī)器執(zhí)行（機(jī)器語言）。,2. 基本數(shù)據(jù)結(jié)構(gòu)與算法,2.1 算法,2.1.1 算法(algorithm)基本概念 對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。它是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。 算法具有有窮性、確定性、可行性、輸入和輸出（擁有足夠的情報）等個重要特性。,2.1.2 算法的基本要素 1、對數(shù)據(jù)對象的運(yùn)算和操作 算術(shù)運(yùn)算 邏輯運(yùn)算 關(guān)系運(yùn)算 數(shù)據(jù)傳輸 2、算法的控制結(jié)構(gòu) 算法中各操作之間的執(zhí)行順序 描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語言等 一個算法一般可以用順序、選擇、循環(huán)三種基本機(jī)構(gòu)組合而成。,2.1.3 算法設(shè)計基本方法 列舉法 歸納法 遞推 遞歸（以簡潔的形式設(shè)計和描述算法） 減半遞推技術(shù) 回溯法,2.2 算法復(fù)雜度,2.2.1 時間復(fù)雜度 依據(jù)算法算法編制的程序在計算機(jī)上運(yùn)行時所消耗的時間來度量。通常有事后統(tǒng)計法和事前分析估算法。 一個算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)）和原操作構(gòu)成的，算法時間取決于兩者的綜合效果。 算法中基本操作重復(fù)執(zhí)行次數(shù)n和算法執(zhí)行時間同步增長，稱作算法的時間復(fù)雜度。,2.2.2 算法的空間復(fù)雜度 一般是指執(zhí)行這個算法所需要的內(nèi)存空間 一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間 一個上機(jī)執(zhí)行的程序除了需要存儲空間來寄存本身所用指令、常數(shù)、變量和輸入數(shù)據(jù)外，也需要一些對數(shù)據(jù)進(jìn)行操作的工作單元和存儲一些為實(shí)現(xiàn)計算所需信息的輔助空間。,例題講解,算法的時間復(fù)雜度是指 A) 執(zhí)行算法程序所需要的時間 B) 算法程序的長度 C) 算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù) D) 算法程序中的指令條數(shù) 算法的基本特征是可行性、確定性、 【1】 和擁有足夠的情報。 算法的空間復(fù)雜度是指 A) 算法程序的長度 B) 算法程序中的指令條數(shù) C) 算法程序所占的存儲空間 D) 執(zhí)行過程中所需要的存儲空間 在計算機(jī)中，算法是指 A) 加工方法 B) 解題方案的準(zhǔn)確而完整的描述 C) 排序方法 D) 查詢方法,算法分析的目的是 A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 找出算法中輸入和輸出之間的關(guān)系 C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改進(jìn) 算法的工作量大小和實(shí)現(xiàn)算法所需的存儲單元多少分別稱為算法的 【1】 。,2.2 數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的定義 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的圖形表示 線性結(jié)構(gòu)與非線性結(jié)構(gòu),2.2.1 數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容,當(dāng)今計算機(jī)應(yīng)用的特點(diǎn)： 所處理的數(shù)據(jù)量大且具有一定的關(guān)系； 對其操作不再是單純的數(shù)值計算，而更多地是需要對其進(jìn)行組織、管理和檢索。 應(yīng)用舉例1學(xué)籍檔案管理 假設(shè)一個學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表1-1所示的學(xué)生信息。,特點(diǎn)： l 每個學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號順序依次排列構(gòu)成一張表格； l 表中每個學(xué)生的信息依據(jù)學(xué)號的大小存在著一種前后關(guān)系，這就是我們所說的線性結(jié)構(gòu)； l 對它的操作通常是插入某個學(xué)生的信息，刪除某個學(xué)生的信息，更新某個學(xué)生的信息，按條件檢索某個學(xué)生的信息等等。 應(yīng)用舉例2輸出n個對象的全排列 輸出n個對象的全排列可以使用下圖1-1所示的形式描述。,圖 1-1 3個對象的全排列過程,特點(diǎn)： l 在求解過程中，所處理的數(shù)據(jù)之間具有層次關(guān)系，這是我們所說的樹形結(jié)構(gòu)； l 對它的操作有：建立樹形結(jié)構(gòu)，輸出最低層結(jié)點(diǎn)內(nèi)容等等。 應(yīng)用舉例3制定教學(xué)計劃 在制定教學(xué)計劃時，需要考慮各門課程的開設(shè)順序。有些課程需要先導(dǎo)課程，有些課程則不需要，而有些課程又是其他課程的先導(dǎo)課程。比如，計算機(jī)專業(yè)課程的開設(shè)情況如下表1-2所示：,課程先后關(guān)系的圖形描形式：,圖 1-2 計算機(jī)專業(yè)必修課程開設(shè)先后關(guān)系,特點(diǎn) l 課程之間的先后關(guān)系用圖結(jié)構(gòu)描述； l 通過實(shí)施創(chuàng)建圖結(jié)構(gòu)，按要求將圖結(jié)構(gòu)中的頂點(diǎn)進(jìn)行線性排序。 結(jié)論： 數(shù)據(jù)結(jié)構(gòu)主要研究以下三個方面的問題： 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu) 對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運(yùn)算的一般方法的學(xué)科。,2.2.2 基本概念和術(shù)語,能輸入到計算機(jī)中 并能被計算機(jī)程序處理的 符號的集合。,整數(shù)(1,2)、實(shí)數(shù)(1.1,1.2) 字符串(Beijing)、 圖形、聲音。,2.2.2 基本概念和術(shù)語,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運(yùn)算的一般方法的學(xué)科。,2.2.2 基本概念和術(shù)語,計算機(jī)管理圖書問題 在圖書館里有各種卡片：有按書名編排的、 有按作者編排的、有按分類編排 如何將查詢圖書的這些信息存入計算機(jī)中 既要考慮查詢時間短，又要考慮節(jié)省空間,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運(yùn)算的一般方法的學(xué)科。,最簡單的辦法之一是建立一張表， 每一本書的信息在表中占一行，如,2.2.2 基本概念和術(shù)語,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運(yùn)算的一般方法的學(xué)科。,如何將0,1,2,3,4,5,6,7,8,9這10個數(shù)存放在 計算機(jī)中能最快地達(dá)到你所需要的目的？ 目的不同，最佳的存儲方方法就不同。 從大到小排列：9,8,7,6,5,4,3,2,1,0 輸出偶數(shù)：0,2,4,6,8,1,3,5,7,9,數(shù)據(jù)元素在 計算機(jī)中的表示,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運(yùn)算的一般方法的學(xué)科。,2.2.2 基本概念和術(shù)語,對數(shù)據(jù)結(jié)構(gòu)中的節(jié)點(diǎn)進(jìn)行 操作處理 (插入、刪除、修改、查找、排序),2.2.2 基本概念和術(shù)語,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運(yùn)算的一般方法的學(xué)科。,數(shù)據(jù)元素(Data Element),數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體。 有時一個數(shù)據(jù)元數(shù)可由若干數(shù)據(jù)項(xiàng)(Data Item)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。,數(shù)據(jù)元素亦稱節(jié)點(diǎn)或記錄。,數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）,有限個數(shù)據(jù)元素的集合,有限個節(jié)點(diǎn)間關(guān)系的集合,1數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A 順序存儲,B 鏈?zhǔn)酱鎯?線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個方面,數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）,線性結(jié)構(gòu),A , B , C , ，X ,Y , Z,學(xué) 生 成 績 表,線性表結(jié)點(diǎn)間是以線性關(guān)系聯(lián)結(jié),1數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A 順序存儲,B 鏈?zhǔn)酱鎯?線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個方面,數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）,樹形結(jié)構(gòu),全校學(xué)生檔案管理的組織方式,計算機(jī)程序管理系統(tǒng)也是典型的樹形結(jié)構(gòu),樹形結(jié)構(gòu) 結(jié)點(diǎn)間具有分層次的連接關(guān)系,1數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A 順序存儲,B 鏈?zhǔn)酱鎯?線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個方面,(亦稱物理結(jié)構(gòu)),D= 1 , 2 , 3 , 4 R=(1,2) , (1,3) , (1,4) , (2,3) (3,4) , (2,4) ,D= 1 , 2 , 3 R= (1,2) , (2,3) , (3,2) , (1,3) ,圖形結(jié)構(gòu)節(jié)點(diǎn)間的連結(jié)是任意的,1數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A 順序存儲,B 鏈?zhǔn)酱鎯?線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個方面,(亦稱物理結(jié)構(gòu)),元素n,元素i,元素2,元素1,Lo,Lo+m,Lo+(i-1)*m,Lo+（n-1)*m,存儲地址,存儲內(nèi)容,Loc(a)=Lo+（i-1)*m,順序存儲,每個元素所占用 的存儲單元個數(shù),元素n,元素i,元素2,元素1,存儲內(nèi)容,順序存儲結(jié)構(gòu)常用于線性數(shù)據(jù)結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里。,順序存儲結(jié)構(gòu)的三個弱點(diǎn)： 1.作插入或刪除操作時，需移動大量元數(shù)。 2.長度變化較大時，需按最大空間分配。 3.表的容量難以擴(kuò)充。,1數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A 順序存儲,B 鏈?zhǔn)酱鎯?線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個方面,(亦稱物理結(jié)構(gòu)),1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,鏈?zhǔn)酱鎯?每個節(jié)點(diǎn)都由兩部分組成：數(shù)據(jù)域和指針域。 數(shù)據(jù)域存放元素本身的數(shù)據(jù)， 指針域存放指針。 數(shù)據(jù)元素之間邏輯上的聯(lián)系由指針來體現(xiàn)。,1536,元素2,1400,元素1,1346,元素3,元素4,head,鏈?zhǔn)酱鎯?1345,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,鏈?zhǔn)酱鎯?1.比順序存儲結(jié)構(gòu)的存儲密度小 (每個節(jié)點(diǎn)都由數(shù)據(jù)域和指針愈組成)。 2.邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰。 3.插入、刪除靈活 (不必移動節(jié)點(diǎn)，只要改變節(jié)點(diǎn)中的指針)。,鏈接存儲結(jié)構(gòu)特點(diǎn)：,1數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A 順序存儲,B 鏈?zhǔn)酱鎯?線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個方面,(亦稱物理結(jié)構(gòu)),線性結(jié)構(gòu)和非線性結(jié)構(gòu),如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件： 有且只有一個根結(jié)點(diǎn)； 每一個結(jié)點(diǎn)最多有一個前件，也最多有一個后件 則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)（線性表）。 如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。,例題講解,鏈表不具有的特點(diǎn)是 A) 不必事先估計存儲空間 B) 可隨機(jī)訪問任一元素 C) 插入刪除不需要移動元素 D) 所需空間與線性表長度成正比 數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于 【1】 。 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的 A) 存儲結(jié)構(gòu) B) 物理結(jié)構(gòu) C) 邏輯結(jié)構(gòu) D) 物理和存儲結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和 【1】 兩大類。,順序存儲方法是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置 【2】 的存儲單元中。 數(shù)據(jù)處理的最小單位是 A) 數(shù)據(jù) B) 數(shù)據(jù)元素 C) 數(shù)據(jù)項(xiàng) D) 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)作為計算機(jī)的一門學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算，以及 A) 數(shù)據(jù)的存儲結(jié)構(gòu) B) 計算方法 C) 數(shù)據(jù)映象 D) 邏輯存儲 線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是 A) 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) B) 隨機(jī)存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) C) 隨機(jī)存取的存儲結(jié)構(gòu)、隨機(jī)存取的存儲結(jié)構(gòu) D) 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu),根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成 A) 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B) 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D) 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 【2】 以及對數(shù)據(jù)的操作運(yùn)算。 數(shù)據(jù)的基本單位是 【5】 。,下列敘述中，錯誤的是 A) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān) B) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān) C) 數(shù)據(jù)的存儲結(jié)構(gòu)在計算機(jī)中所占的空間不一定是連續(xù)的 D) 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)是指 A）數(shù)據(jù)所占的存儲空間 B）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示 C）數(shù)據(jù)在計算機(jī)中的順序存儲方式 D）存儲在外存中的數(shù)據(jù),2.3 線性表,2.3.1 線性表的定義 線性表是n個元素的有限序列，它們之間的關(guān)系可以排成一個線性序列： a1，a2， ，ai， ，an 其中n稱作表的長度，當(dāng)n=0時，稱作空表。,線性表的特點(diǎn)： 1.線性表中所有元素的性質(zhì)相同。 2.除第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素有且僅有一個前驅(qū)和一個后繼。第一個數(shù)據(jù)元素?zé)o前驅(qū)，最后一個數(shù)據(jù)元素?zé)o后繼。 3.數(shù)據(jù)元素在表中的位置只取決于它自身的序號。 在線性表上常用的運(yùn)算有： 初始化、求長度、取元素、修改、 前插、刪除、檢索、排序。,2.3.2 線性表的順序存儲結(jié)構(gòu)及其插入與刪除操作,特點(diǎn)： 1、線性表中數(shù)據(jù)元素類型一致，只有數(shù)據(jù)域，存儲空間利用率高。 2、所有元素所占的存儲空間是連續(xù)的 3、各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的 2. 做插入、刪除時需移動大量元素。 3. 空間估計不明時，按最大空間分配。,元素an,元素ai,元素a2,元素a1,b,b+m,b+(i-1)*m,b+(maxlen-1)*m,存儲地址,內(nèi)存狀態(tài),Loc(元素i)=b +（i-1)*m,順序存儲結(jié)構(gòu)示意圖(順序表)：,首地址 起始地址 基地址,每個元素所占用 的存儲單元個數(shù),0,1,i,線性表的順序存儲結(jié)構(gòu)可用VB語言中的一維數(shù)組來描述. Dim VM As integer; /*V是數(shù)組的名字，M是數(shù)組大小，假設(shè)數(shù)組中的元素是整型類型*/,第i個元素的ai存儲地址： Loc(ai)=Loc(a1)+(i-1)*m,V,V,Vi,Vm-1,a2,a1,an,ai+1,ai,0,1,i-1,i,n-1,1- 1插入運(yùn)算,ai-1,a2,a1,alength,ai+1,ai,x,x,Option Base 0 Function int insq( i As Integer，x As Integer , V( ) As Integer,M As Integer,） / *順序表插入函數(shù)*/ /*在線性表V中第i 個元素之前插入x，i 的合法值為 1 i n */ Dim n As Integer，j As Integer n=UBound(V) / *獲取表長*/ If n=M Then / *M是存儲空間的大小*/ print “overflown“ Exit Function End If If (in+1) Then print “i is error“ Exit Function /*i值不合法 */ Else for j=n To i Step -1 V(j)=V(j-1) /*插入位置后的元素依次右移*/ Next J V(j)=x /* 插入x */ End If End Function,注意數(shù)組元素從0開始,1- 2刪除運(yùn)算 Option Base o Function delsq( i As Integer ,V( ) As Integer） /*在線性表V中刪除第i 個元素*/ Dim n As Integer,j As Integer n=UBound(V) If in Then print “This element is not in the list“ Exit Function else For j=I To n V(j-1)=V(j) /*被刪除元素之后的元素左移*/ Next J End if End Function,插入算法的分析 假設(shè)線性表中含有n個數(shù)據(jù)元素，在進(jìn)行插入操作時，若假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數(shù)為：,刪除算法的分析 在進(jìn)行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數(shù)為： 分析結(jié)論 順序存儲結(jié)構(gòu)表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對其做插入或刪除操作時，這一點(diǎn)需要值得考慮。,例題講解,鏈表不具有的特點(diǎn)是 A) 不必事先估計存儲空間 B) 可隨機(jī)訪問任一元素 C) 插入刪除不需要移動元素 D) 所需空間與線性表長度成正比 順序存儲方法是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置 【2】 的存儲單元中。 長度為n的順序存儲線性表中，當(dāng)在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為 【1】 。,線性表L=(a1,a2,a3,ai，an)，下列說法正確的是 A) 每個元素都有一個直接前件和直接后件 B) 線性表中至少要有一個元素 C) 表中諸元素的排列順序必須是由小到大或由大到小 D) 除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件 線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是 A) 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) B) 隨機(jī)存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) C) 隨機(jī)存取的存儲結(jié)構(gòu)、隨機(jī)存取的存儲結(jié)構(gòu) D) 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu),根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成 A) 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B) 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D) 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 當(dāng)線性表采用順序存儲結(jié)構(gòu)實(shí)現(xiàn)存儲時，其主要特點(diǎn)是 【1】 。 線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址 A) 必須是連續(xù)的 B) 部分地址必須是連續(xù)的 C) 一定是不連續(xù)的 D) 連續(xù)不連續(xù)都可以,下列敘述中，錯誤的是 A) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān) B) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān) C) 數(shù)據(jù)的存儲結(jié)構(gòu)在計算機(jī)中所占的空間不一定是連續(xù)的 D) 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu),2.4 棧和隊(duì)列,2.4.1 棧和隊(duì)列的定義 棧和隊(duì)列是兩種特殊的線性表，它們是運(yùn)算時要受到某些限制的線性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。,2.4.1.1棧的定義 棧：限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表,此種結(jié)構(gòu)稱為后進(jìn)先出 設(shè)棧s=（a1，a2，. . . ,ai，. . . ，an）， 其中a1是棧底元素， an是棧頂元素。 棧頂（top)：允許插入和刪除的一端； 約定top始終指向新數(shù)據(jù)元素將存放的位置。 棧底（bottom):不允許插入和刪除的一端。,隊(duì)列的主要運(yùn)算,（1）設(shè)置一個空隊(duì)列； （2）插入一個新的隊(duì)尾元素，稱為進(jìn)隊(duì)； （3）刪除隊(duì)頭元素，稱為出隊(duì)； （4）讀取隊(duì)頭元素；,2.4.1.2 隊(duì)列的定義 定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表 。此種結(jié)構(gòu)稱為先進(jìn)先出（FIFO）表。,a1 , a2 , a3 , a4 , an-1 , an,隊(duì) 列 示 意 圖,隊(duì)頭,隊(duì)尾,2.4.2 棧的順序存儲結(jié)構(gòu)及其基本運(yùn)算,用順序存儲結(jié)構(gòu)表示的棧。 順序棧用一組連續(xù)的存儲單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組表示，設(shè)置一個簡單變量top指示棧頂位置，稱為棧頂指針，它始終指向待插入元素的位置。,基本運(yùn)算： 壓（進(jìn)）棧：PUSH 出棧：POP,隊(duì)空時， 令rear=front=-1，當(dāng)有新元素入隊(duì)時，尾指針加1，當(dāng)有元素出隊(duì)時，頭指針加1。故在非空隊(duì)列中，頭指針始終指向隊(duì)頭元素前一個位置，而尾指針始終指向隊(duì)尾元素的位置,2.4.3 隊(duì)列的順序存儲結(jié)構(gòu)及其基本運(yùn)算,例題講解,棧和隊(duì)列的共同特點(diǎn)是 A)都是先進(jìn)先出 B) 都是先進(jìn)后出 C) 只允許在端點(diǎn)處插入和刪除元素 D) 沒有共同點(diǎn) 如果進(jìn)棧序列為e1,e2,e3,e4，則可能的出棧序列是 A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2 D) 任意順序 一些重要的程序語言(如C語言和Pascal語言) 允許過程的遞歸調(diào)用。而實(shí)現(xiàn)遞歸調(diào)用中的存儲分配通常用 A) 棧 B) 堆 C) 數(shù)組 D) 鏈表,棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是 A) ABCED B) DCBEA C) DBCEA D) CDABE 棧通常采用的兩種存儲結(jié)構(gòu)是 A) 線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu) B) 散列方式和索引方式 C) 鏈表存儲結(jié)構(gòu)和數(shù)組 D) 線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu) 棧和隊(duì)列通常采用的存儲結(jié)構(gòu)是 【1】 。 下列數(shù)據(jù)結(jié)構(gòu)中，按先進(jìn)后出原則組織數(shù)據(jù)的是 A) 線性鏈表 B) 棧 C) 循環(huán)鏈表 D) 順序表,當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于隊(duì)頭指針時，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為 【2】 。 由兩個棧共享一個存儲空間的好處是 A) 減少存取時間，降低下溢發(fā)生的機(jī)率 B) 節(jié)省存儲空間，降低上溢發(fā)生的機(jī)率 C) 減少存取時間，降低上溢發(fā)生的機(jī)率 D) 節(jié)省存儲空間，降低下溢發(fā)生的機(jī)率 下列關(guān)于棧的敘述中正確的是 ）在棧中只能插入數(shù)據(jù) B）在棧中只能刪除數(shù)據(jù) C）棧是先進(jìn)先出的線性表 D）棧是后進(jìn)先出的線性表 下列關(guān)于隊(duì)列的敘述中正確的是 ）在隊(duì)列中只能插入數(shù)據(jù) B）在隊(duì)列中只能刪除數(shù)據(jù) C）隊(duì)列是先進(jìn)先出的線性表 D）隊(duì)列是后進(jìn)先出的線性表,2.5 鏈表,線性單鏈表 雙向鏈表 循環(huán)鏈表,結(jié)構(gòu)及其基本運(yùn)算,2.5.1 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu),將線性表的元素放到一個具有頭指針的鏈表中，鏈表中每個結(jié)點(diǎn)包含數(shù)據(jù)域和指針域。 數(shù)據(jù)域存放數(shù)據(jù)，指針域存放后繼結(jié)點(diǎn)的地址，最后一個結(jié)點(diǎn)的指針域?yàn)榭铡＿壿嬌舷噜彽臄?shù)據(jù)元素在內(nèi)存中的物理存儲空間不一定相鄰。,上圖的線性表為 ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG,線性鏈表表示法:,鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn),插入、刪除靈活方便，不需要移動結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中指針域的值即可。 適合于線性表是動態(tài)變化的,不進(jìn)行頻繁查找操作、但經(jīng)常進(jìn)行插入刪除時使用。 鏈表的查找只能從頭指針開始順序查找。,L,線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)可用C語言中的“結(jié)構(gòu)指針”來描述,帶頭結(jié)點(diǎn)的線性鏈表,data,next,typedef struct LNode int data; Struct LNode *next; JD;,P,P,單鏈表的插入運(yùn)算,S,在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn),P,P,L,單鏈表的插入運(yùn)算,S,單鏈表的插入運(yùn)算,void lbcr (JD *p, int x) / * 在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn) */ JD *s; /* 定義指向結(jié)點(diǎn)類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結(jié)點(diǎn) */ s-data=x; s-next=p-next; p-next=s; return OK; ,P,L,單鏈表的插入運(yùn)算,void lbcr (JD *p, int x) / * 在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn) */ JD *s; /* 定義指向結(jié)點(diǎn)類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結(jié)點(diǎn) */ s-data=x; s-next=p-next; p-next=s; return OK; ,P,L,單鏈表的插入運(yùn)算,void lbcr (JD *p, int x) / * 在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn) */ JD *s; /* 定義指向結(jié)點(diǎn)類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結(jié)點(diǎn) */ s-data=x; s-next=p-next; p-next=s; return OK; ,S,P,L,單鏈表的插入運(yùn)算,void lbcr (JD *p, int x) / * 在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn) */ JD *s; /* 定義指向結(jié)點(diǎn)類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結(jié)點(diǎn) */ s-data=x; s-next=p-next; p-next=s; return OK; ,S,P,L,單鏈表的插入運(yùn)算,void lbcr (JD *p, int x) / * 在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn) */ JD *s; /* 定義指向結(jié)點(diǎn)類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結(jié)點(diǎn) */ s-data=x; s-next=p-next; p-next=s; return OK; ,S,P,L,單鏈表的插入運(yùn)算,void lbcr (JD *p, int x) / * 在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn) */ JD *s; /* 定義指向結(jié)點(diǎn)類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結(jié)點(diǎn) */ s-data=x; s-next=p-next; p-next=s; return OK; ,void lbsc(JD *p) /* 刪除p指針指向結(jié)點(diǎn)的后一個結(jié)點(diǎn) */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向p的后繼結(jié)點(diǎn) */ p-next=q-next; /* 修改p結(jié)點(diǎn)的指針域 */ free(q); /* 刪除并釋放結(jié)點(diǎn) */ ,單鏈表的刪除運(yùn)算,L,p,void lbsc(JD *p) /* 刪除p指針指向結(jié)點(diǎn)的后一個結(jié)點(diǎn) */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向p的后繼結(jié)點(diǎn) */ p-next=q-next; /* 修改p結(jié)點(diǎn)的指針域 */ free(q); /* 刪除并釋放結(jié)點(diǎn) */ ,單鏈表的刪除運(yùn)算,L,p,void lbsc(JD *p) /* 刪除p指針指向結(jié)點(diǎn)的后一個結(jié)點(diǎn) */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向p的后繼結(jié)點(diǎn) */ p-next=q-next; /* 修改p結(jié)點(diǎn)的指針域 */ free(q); /* 刪除并釋放結(jié)點(diǎn) */ ,單鏈表的刪除運(yùn)算,q,L,p,q,void lbsc(JD *p) /*刪除p指針指向結(jié)點(diǎn)的后一個結(jié)點(diǎn) */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向p的后繼結(jié)點(diǎn) */ p-next=q-next; /* 修改p結(jié)點(diǎn)的指針域 */ free(q); /* 刪除并釋放結(jié)點(diǎn) */ ,單鏈表的刪除運(yùn)算,L,p,q,void lbsc(JD *p) /*刪除p指針指向結(jié)點(diǎn)的后一個結(jié)點(diǎn) */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向p的后繼結(jié)點(diǎn) */ p-next=q-next; /* 修改p結(jié)點(diǎn)的指針域 */ free(q); /* 刪除并釋放結(jié)點(diǎn) */ ,單鏈表的刪除運(yùn)算,L,p,void lbsc(JD *p) /*刪除p指針指向結(jié)點(diǎn)的后一個結(jié)點(diǎn) */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向p的后繼結(jié)點(diǎn) */ p-next=q-next; /* 修改p結(jié)點(diǎn)的指針域 */ free(q); /* 刪除并釋放結(jié)點(diǎn) */ ,單鏈表的刪除運(yùn)算,線性鏈表的查找操作： 設(shè)無表頭結(jié)點(diǎn)的線性鏈表的頭指針為h, 沿著鏈表的開始往后找結(jié)點(diǎn)x，若找到，則返回該結(jié)點(diǎn)在鏈表中的位置，否則返回空地址。 JD *lbcz (JD *h,int x) JD *p; p=h; while (p!=NULL ,2.5.2 循環(huán)鏈表: 首尾相接的鏈表。 將最后一個結(jié)點(diǎn)的空指針改為指向頭結(jié)點(diǎn)，從任一結(jié)點(diǎn)出發(fā)均可找到其它結(jié)點(diǎn)。,L,帶頭結(jié)點(diǎn)的單鏈表,L,循環(huán)單鏈表,2.5.3 雙向鏈表 在每個結(jié)點(diǎn)中設(shè)置兩個指針，一個指向后繼，一個指向前驅(qū)?？芍苯哟_定一個結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)。可提高效率。,data,next,before,線性表的應(yīng)用：應(yīng)用最廣的數(shù)據(jù)結(jié)構(gòu)。 高級語言中的數(shù)組； 計算機(jī)的文件系統(tǒng)； 計算機(jī)的目錄系統(tǒng)； 電話號碼查詢系統(tǒng)（可采用順序表或單鏈表結(jié)構(gòu)）； 各種事務(wù)處理（各種表格均采用順序表和線性鏈表結(jié)構(gòu)）,(1) L=P-link;,例題 對以下單鏈表分別執(zhí)行下列各程序段,并畫出結(jié)果示意圖.,(2) R-data=P-data;,(3) R-data=P-link-data;,(4) P-link-link-link-data=P-data;,(5) T=P; while(T!=NULL) T-data=(T-data)*2; T=T-link; ,(6) T=P; while(T-link!=NULL) T-data=(T-data)*2; T=T-link; ,(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;,(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;,P,(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;,P,10,(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;,P,10,(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;,P,10,(8) T=L; T-link=P-link; free(P);,(9) S-link=L;,如果 S-link= =L 則S所指向的結(jié)點(diǎn)為尾結(jié)點(diǎn).,例題講解,鏈表不具有的特點(diǎn)是 A) 不必事先估計存儲空間 B) 可隨機(jī)訪問任一元素 C) 插入刪除不需要移動元素 D) 所需空間與線性表長度成正比 用鏈表表示線性表的優(yōu)點(diǎn)是 A) 便于隨機(jī)存取 B) 花費(fèi)的存儲空間較順序存儲少 C) 便于插入和刪除操作 D) 數(shù)據(jù)元素的物理順序與邏輯順序相同 長度為n的順序存儲線性表中，當(dāng)在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為 【1】 。,線性表L=(a1,a2,a3,ai，an)，下列說法正確的是 A) 每個元素都有一個直接前件和直接后件 B) 線性表中至少要有一個元素 C) 表中諸元素的排列順序必須是由小到大或由大到小 D) 除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件 在單鏈表中，增加頭結(jié)點(diǎn)的目的是 A) 方便運(yùn)算的實(shí)現(xiàn) B) 使單鏈表至少有一個結(jié)點(diǎn) C) 標(biāo)識表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置 D) 說明單鏈表是線性表的鏈?zhǔn)酱鎯?shí)現(xiàn),非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向) ，滿足 A) p-next=NULL B) p=NULL C) p-next=head D) p=head 循環(huán)鏈表的主要優(yōu)點(diǎn)是 A) 不再需要頭指針了 B) 從表中任一結(jié)點(diǎn)出發(fā)都能訪問到整個鏈表 C) 在進(jìn)行插入、刪除運(yùn)算時，能更好的保證鏈表不斷開 D) 已知某個結(jié)點(diǎn)的位置后，能夠容易的找到它的直接前件,線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是 A) 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) B) 隨機(jī)存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) C) 隨機(jī)存取的存儲結(jié)構(gòu)、隨機(jī)存取的存儲結(jié)構(gòu) D) 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu) 當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于隊(duì)頭指針時，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為 【2】 。 用鏈表表示線性表的突出優(yōu)點(diǎn)是 【1】 。,2.6 樹,樹的基本概念 二叉樹的定義及其存儲結(jié)構(gòu) 二叉樹的前序、中序和后序遍歷,2.6.1 樹的定義 由一個或多個結(jié)點(diǎn)組成的有限集合。僅有一個根結(jié)點(diǎn)，結(jié)點(diǎn)間有明顯的層次結(jié)構(gòu)關(guān)系。,現(xiàn)實(shí)世界中，能用樹的結(jié)構(gòu)表示的例子： 學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。,介紹幾個概念： 結(jié)點(diǎn)（Node）：樹中的元素，包含數(shù)據(jù)項(xiàng)及若干指向其子樹的分支。 結(jié)點(diǎn)的度（Degree）：結(jié)點(diǎn)擁有的子樹數(shù)。 結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開始算起，根為第一層。 葉子（Leaf）：度為零的結(jié)點(diǎn)，也稱端結(jié)點(diǎn)。 孩子（Child）：結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。 兄弟（Sibling）：同一雙親的孩子。 雙親（Parent）：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)，稱為這些結(jié)點(diǎn)的雙親。 深度（Depth)： 樹中結(jié)點(diǎn)的最大層次數(shù)。 森林（Forest）：M棵互不相交的樹的集合。,2.6.2 二叉樹 （Binary Tree）,1 、二叉樹的定義及其性質(zhì) (1) 二叉樹的定義,二叉樹的五種基本形態(tài),二叉樹一種特殊的樹型結(jié)構(gòu)，特點(diǎn)是樹中每個結(jié)點(diǎn)只有兩棵子樹，且子樹有左右之分，次序不能顛倒。,因?yàn)闃涞拿總€結(jié)點(diǎn)的度不同，存儲困難，使對樹的處理算法很復(fù)雜。所以引出二叉樹的討論。,二叉數(shù)是n(n0)個結(jié)點(diǎn)的有限集合。它或?yàn)榭諗?shù)(n=0),或由一個根結(jié)點(diǎn)和兩棵分別稱為根的左子樹和右子樹的互不相交的二叉數(shù)組成。,特別要注意：二叉數(shù)不是樹的特殊情況。,a,a,b,b,兩棵不同的二叉數(shù),A、 二叉樹的第i層上至多有2 i-1（i 1）個結(jié)點(diǎn)。,(2) 二叉樹的基本性質(zhì),第三層上(i=3)，有23-1=4個節(jié)點(diǎn)。 第四層上(i=4)，有24-1=8個節(jié)點(diǎn)。,A、 二叉樹的第i層上至多有2 i-1（i 1）個結(jié)點(diǎn)。 B、 深度為h的二叉樹中至多含有2h-1個結(jié)點(diǎn)。,(2) 二叉樹的基本性質(zhì),此樹的深度h=4，共有24-1=15個節(jié)點(diǎn)。,A、 二叉樹的第i層上至多有2 i-1（i 1）個結(jié)點(diǎn)。 B、 深度為h的二叉樹中至多含有2h-1個結(jié)點(diǎn)。 C、 若在任意一棵二叉樹中，有n0個葉子結(jié)點(diǎn)， 有n2個度為2的結(jié)點(diǎn)，則：n0=n2+1,(2) 二叉樹的基本性質(zhì),n0=8 n2=7,（3）滿二叉樹,特點(diǎn)：每一層上都含有最大結(jié)點(diǎn)數(shù)。,（4）完全二叉樹,特點(diǎn)：除最后一層外，每一層都取最大結(jié)點(diǎn)數(shù)， 最后一層結(jié)點(diǎn)都集中在該層最左邊的若干位置。,（5）樹與二叉樹的區(qū)別,A樹的結(jié)點(diǎn)個數(shù)至少為1，而二叉樹的結(jié)點(diǎn)個數(shù)可以為0。 B樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，二叉樹結(jié)點(diǎn)最大度數(shù)為2。 C樹的結(jié)點(diǎn)無左、右之分，二叉樹的結(jié)點(diǎn)子樹有明確的左、右之分。,樹,二叉樹,2、二叉樹的存儲結(jié)構(gòu),(2) 鏈?zhǔn)酱鎯Y(jié)構(gòu),T16,若父結(jié)點(diǎn)在數(shù)組中i下標(biāo)處，其左孩子在2*i處，右孩子在2*i+1處。,(1) 順序存儲結(jié)構(gòu),(1) 順序存儲結(jié)構(gòu),2h-1=,24-1 = 15,用一組連續(xù)的存儲單元存放二叉樹的數(shù)據(jù)元素。結(jié)點(diǎn)在數(shù)組中的相對位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。,一般二叉樹必須按完全二叉樹的形式存儲，將造成存儲的浪費(fèi)。,2.6.3 二叉樹的遍歷 查找某個結(jié)點(diǎn)，或?qū)Χ鏄渲腥拷Y(jié)點(diǎn)進(jìn)行某種處理，就需要遍歷。 （1）遍歷定義及遍歷算法 遍歷是指按某條搜索路線尋訪樹中每個結(jié)點(diǎn)，且每個結(jié)點(diǎn)只被訪問一次。 按先左后右的原則，一般使用三種遍歷： 先序遍歷(D L R): 訪問根結(jié)點(diǎn)，按先序遍歷左子樹，按先序遍歷右子樹。 中序遍歷(L D R): 按中序遍歷左子樹，訪問根結(jié)點(diǎn)，按中序遍歷右子樹。 后序遍歷(L R D): 按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點(diǎn)。 二叉樹為空時，執(zhí)行空操作，即空二叉樹已遍歷完。,（2）遍歷算法,先序遍歷：D L R 中序遍歷：L D R 后序遍歷：L R D,A,D,B,C,T1,T2,T3,D L R,以先序遍歷D L R為例演示遍歷過程,ABDC,BDAC,DBCA,例題講解,已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是 A) acbed B) decab C) deabc D) cedba 已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為 A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHG 樹是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是 A) 有且只有1 B) 1或多于1 C) 0或1 D) 至少2,在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個數(shù)為 A) 32 B) 31 C) 16 D) 15 若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是 A) bdgcefha B) gdbecfha C) bdgaechf D) gdbehfca 在樹結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 【1】 。 下列敘述中正確的是 A) 線性表是線性結(jié)構(gòu) B) 棧與隊(duì)列是非線性結(jié)構(gòu) C) 線性鏈表是非線性結(jié)構(gòu) D) 二叉樹是線性結(jié)構(gòu),具有3個結(jié)點(diǎn)的二叉樹有 A) 2種形態(tài) B) 4種形態(tài) C) 7種形態(tài) D) 5種形態(tài) 設(shè)有下列二叉樹： 對此二叉樹前序遍歷的結(jié)果為 A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT,設(shè)一棵二叉樹中有3個葉子結(jié)點(diǎn)，有8個度為1的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為 A) 12 B) 13 C) 14 D) 15 設(shè)有下列二叉樹： 對此二叉樹的中序遍歷的結(jié)果為 A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA,設(shè)樹T的深度為4,其中度為1、2、3、4的結(jié)點(diǎn)個數(shù)分別為4、2、1、1。則T中的葉子結(jié)點(diǎn)數(shù)為 A）8 B）7 C）6 D）5 設(shè)一棵完全二叉樹共有700個結(jié)點(diǎn)，則該二叉樹中有（ ）個葉子結(jié)點(diǎn)。 在一個容量為15的循環(huán)隊(duì)列中，若頭指針front=6，尾指針rear=9，則該循環(huán)隊(duì)列中共有（ ）個元素。 設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為（ ）。,2.7 查找和排序,順序查找與二分查找算法 基本排序算法（交換類排序、選擇類排序、插入類排序）,2.7.1 查找,查找是在一個給定的數(shù)據(jù)結(jié)構(gòu)中，根據(jù)給定的條件查找滿足條件的結(jié)點(diǎn)。不同的數(shù)據(jù)結(jié)構(gòu)采用不同的查找方法。查找的效率直接影響數(shù)據(jù)處理的效率。 查找的結(jié)果： 查找成功：找到滿足條件的結(jié)點(diǎn) 查找失敗：找不到滿足條件的結(jié)點(diǎn)。,2.7.1.1 順序查找（線性查找）,查找過程： 對給定的一關(guān)鍵字K，從線性表的一端開始，逐個進(jìn)行記錄的關(guān)鍵字和K的比較，直到找到關(guān)鍵字等于K的記錄或到達(dá)表的另一端。 可以采用從前向后查，也可采用從后向前查的方法。 在平均情況下，大約要與表中一半以上元素進(jìn)行比較