筆試數(shù)據(jù)結(jié)構(gòu)與算法

1、第1章基本數(shù)據(jù)結(jié)構(gòu)與算法,主講：曾慶尚煙臺大學(xué)文經(jīng)學(xué)院電子系,,,二級ACCESS—數(shù)據(jù)庫基礎(chǔ)知識,本章的重要性,2007年4月-2010年9月共8次計算機等級考試涉及到本章內(nèi)容的題目有40題，平均每次接近10分，因此本章還是很重要的。本章在考試中只涉及筆試題目，上機不考。,,,二級ACCESS—數(shù)據(jù)訪問頁,關(guān)鍵考點,順序存儲與鏈?zhǔn)酱鎯Φ幕靖拍?棧、隊列的基本概念與基本操作 循環(huán)隊列元素個數(shù)的計算 算法時間、空間復(fù)雜度

2、的概念幾種查找與排序的比較次數(shù)二叉樹的遍歷二叉樹結(jié)點個數(shù)的計算,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,本章主要內(nèi)容,算法 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容 基本概念和術(shù)語 數(shù)據(jù)結(jié)構(gòu)類型 線性結(jié)構(gòu)和非線性結(jié)構(gòu) 順序存儲與鏈?zhǔn)酱鎯?線性表 棧和隊列 線性鏈表 樹與二叉樹 查找和排序 圖,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.1 算法,算法的基本概念 算法：解題方案的準(zhǔn)確而完整的描述。 算法的基本特征：是一組嚴(yán)謹(jǐn)?shù)囟x運算順序的規(guī)則

3、，每一個規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法不等于程序，程序不可能優(yōu)于算法。 基本特性 可行性：根據(jù)實際問題設(shè)計的算法，執(zhí)行得到滿意結(jié)果 確定性：每一步驟必須有明確定義，不允許有多義性。 有窮性：算法必須能在有限的時間內(nèi)做完。 擁有足夠的情報：輸入和輸出，方可執(zhí)行。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.1 算法,算法的基本要素 1.算法中對數(shù)據(jù)的運算和操作 算術(shù)運算：＋、－、×、÷等 邏

4、輯運算：>、=、<=、!=等 關(guān)系運算：and、or、not等 數(shù)據(jù)傳輸：w、r等 2.算法的控制結(jié)構(gòu) 算法中各操作之間的執(zhí)行順序 描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語言等 算法可以用順序、選擇、循環(huán)三種基本機構(gòu)組合而成。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.1 算法,算法設(shè)計基本方法 （1）列舉法：根據(jù)問題，列舉所有可能的情況，并用問題中給定的條件檢驗?zāi)男┦切枰模男┦遣恍枰摹?（2）

5、歸納法：通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。 （3）遞推：是指從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。 （4）遞歸：將問題逐層分解的過程。 （5）減半遞推技術(shù)： “減半”，是指將問題規(guī)模減半，而問題性質(zhì)不變； “遞推”，是指重復(fù)“減半”過程。 （6）回溯法：分析問題，找出一個解決總線索，然后沿著這個線索逐步試探。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.1 算法,算法的復(fù)雜度：時間復(fù)雜度、空間復(fù)雜度 （

6、P5）算法的時間復(fù)雜度 算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。 工作量用算法所執(zhí)行的基本運算次數(shù)來度量，而算法所執(zhí)行的基本運算次數(shù)是問題規(guī)模的函數(shù)，即 算法的工作量=f(n) 算法空間復(fù)雜度 算法空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。 存儲空間包括：①算法程序所占的空間、 ②輸入數(shù)據(jù)所占的空間、③算法執(zhí)行過程中所需要的額外空間。。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,3.2.1 數(shù)據(jù)結(jié)構(gòu)研究的

7、主要內(nèi)容,當(dāng)今計算機應(yīng)用的特點 所處理的數(shù)據(jù)量大且具有一定的關(guān)系； 對其操作不再是單純的數(shù)值計算，而更多地是需要對其進行組織、管理和檢索。 應(yīng)用舉例1——學(xué)籍檔案管理 假設(shè)一個學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表所示的學(xué)生信息。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,特點 每個學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號順序依次排列構(gòu)成一張表格； 表中每個學(xué)生的信息依據(jù)學(xué)號的大小存在著一種前后關(guān)系. 對它的操作通常是插入某個學(xué)生的信息，刪除某個

8、學(xué)生的信息，更新某個學(xué)生的信息，按條件檢索某個學(xué)生的信息等等。,數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,應(yīng)用舉例2—制定教學(xué)計劃 在制定教學(xué)計劃時，需要考慮各門課程的開設(shè)順序。有些課程需要先導(dǎo)課程，有些則不需要;而有些課程又是其他課程的先導(dǎo)課程。比如，計算機專業(yè)課程的開設(shè)情況如下表所示：,數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容,特點 課程的先后關(guān)系用圖結(jié)構(gòu)描述； 通過實施創(chuàng)建圖結(jié)構(gòu)，

9、按要求將圖結(jié)構(gòu)中的頂點進行線性排序。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu)主要研究以下三個方面的問題(P7) 數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)集合中各元素的信息，及元素之間所固有的邏輯關(guān)系（前后件關(guān)系） 數(shù)據(jù)的存儲結(jié)構(gòu)：各數(shù)據(jù)元素在計算機中的存儲關(guān)系 對各種數(shù)據(jù)結(jié)構(gòu)進行的運算 主要目的是為了提高數(shù)據(jù)的效率。所謂提高數(shù)據(jù)處理的效率，主要包括兩個方面：一是提高數(shù)據(jù)處理的速度，二是盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計算機存儲空間。,數(shù)據(jù)結(jié)構(gòu)研究

10、的主要內(nèi)容,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學(xué)科。是相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,能輸入到計算機中 并能被計算機程序處理的 符號的集合。,整數(shù)(1,2)、實數(shù)(1.1,1.2) 字符串(Beijing)、 圖形、聲音。,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學(xué)科。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,計算

11、機管理圖書問題 圖書館里有各種卡片：有按書名編排的、有按作者編排的、有按分類編排。 如何將查詢圖書的這些信息存入計算機中既要考慮查詢時間短，又要考慮節(jié)省空間,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學(xué)科。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,最簡單的辦法之一是建立一張表，每一本書的信息在表中占一行，如,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的

12、學(xué)科。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,如何將0,1,2,3,4,5,6,7,8,9這10個數(shù)存放在 計算機中能最快地達(dá)到你所需要的目的？ 目的不同，最佳的存儲方方法就不同。 從大到小排列：9,8,7,6,5,4,3,2,1,0 輸出偶數(shù)：0,2,4,6,8,1,3,5,7,9,數(shù)據(jù)元素在 計算機中的表示,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學(xué)科。,1.2 數(shù)據(jù)結(jié)構(gòu)

13、的基本概念,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,對數(shù)據(jù)結(jié)構(gòu)中的節(jié)點進行操作處理 (插入、刪除、修改、查找、排序),數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學(xué)科。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)元素(Data Element) 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體。 有時一個數(shù)據(jù)元素可由若干數(shù)據(jù)項(Data Item)組成。數(shù)據(jù)項是數(shù)據(jù)的最小單位。,數(shù)據(jù)元素亦稱節(jié)點或記錄。,1.2 數(shù)

14、據(jù)結(jié)構(gòu)的基本概念,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）,有限個數(shù)據(jù)元素的集合,有限個節(jié)點間關(guān)系的集合,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,,,1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲結(jié)構(gòu),3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。,,,,,A．線性結(jié)構(gòu),B．非線性結(jié)構(gòu),A 順序存儲,B 鏈?zhǔn)酱鎯?線性表,棧,隊,樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個方面,數(shù)據(jù)結(jié)構(gòu)類型,,,基本數(shù)據(jù)結(jié)

15、構(gòu)與算法,線性結(jié)構(gòu)和非線性結(jié)構(gòu),線性結(jié)構(gòu)條件 （1）有且只有一個根結(jié)點； （2）每一個結(jié)點最多有一個前件，也最多有一個后件。 （3）首節(jié)點無前件，尾節(jié)點無后件。 非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu) 注意：在一個線性結(jié)構(gòu)中插入或刪除任何一個節(jié)點后還應(yīng)是線性結(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é)構(gòu) —結(jié)點間具有分層次的連接關(guān)系,線性結(jié)構(gòu)和非線性

16、結(jié)構(gòu),樹形結(jié)構(gòu),,,基本數(shù)據(jù)結(jié)構(gòu)與算法,線性結(jié)構(gòu)和非線性結(jié)構(gòu),圖形結(jié)構(gòu)：節(jié)點間的連接任意,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,順序存儲與鏈?zhǔn)酱鎯?順序存儲 常用于線性數(shù)據(jù)結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里。 三個弱點 插入或刪除操作時，需移動大量元數(shù)。 長度變化較大時，需按最大空間分配。 表的容量難以擴充,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,每個節(jié)點都由兩部分組成：數(shù)據(jù)域和指針域。 數(shù)據(jù)域：存放元素本身的數(shù)據(jù)， 指針域：存放

17、指針，體現(xiàn)數(shù)據(jù)元素之間的邏輯聯(lián)系,順序存儲與鏈?zhǔn)酱鎯?鏈接存儲結(jié)構(gòu)特點 比順序存儲結(jié)構(gòu)的存儲密度小 (每個節(jié)點都由數(shù)據(jù)域和指針愈組成)。 邏輯上相鄰的節(jié)點物理上不必相鄰。 插入、刪除靈活(不必移動節(jié)點，僅改變節(jié)點中的指針)。,鏈接存儲結(jié)構(gòu),,,基本數(shù)據(jù)結(jié)構(gòu)與算法,順序存儲與鏈?zhǔn)酱鎯?鏈?zhǔn)酱鎯Φ牡刂酚成浔?,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.3 線性表,線性表的基本概念 （P15） 線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決

18、于自己的序號，元素之間的相對位置是線性的。 非空線性表的結(jié)構(gòu)特征 有且只有一個根結(jié)點a1，它無前件；有且只有一個終端結(jié)點an，它無后件； 除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一個前件，也有且只有一個后件。結(jié)點個數(shù)n稱為線性表的長度，當(dāng)n=0時，稱為空表。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,在線性表上常用的運算有 初始化、求長度、取元素、修改、插入、刪除、檢索、排序。 線性表的插入操作 （P17） 在線性表L中第i個數(shù)據(jù)元素之

19、前插入數(shù)據(jù)元素e 檢查插入要求的有關(guān)參數(shù)的合理性 把原來第n個數(shù)據(jù)元素至第i個元素（共n-i+1)依次后移一個數(shù)組元素的位置。 把新數(shù)據(jù)元素放在第i個位置上 修正線性表的數(shù)據(jù)元素個數(shù)。 線性表中含有n個數(shù)據(jù)元素，在進行插入操作時，若假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數(shù)為：n/2,1.3 線性表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,線性表的插入操作（時間復(fù)雜度O(n)）,1.3 線性表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,線性

20、表的刪除操作（時間復(fù)雜度O(n)）（P18）,1.3 線性表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.4 棧和隊列（P19）,棧和隊列是兩種運算時要受到某些特殊限制的線性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。 棧：限定只能在表的一端進行插入和刪除的特殊的線性表,此種結(jié)構(gòu)稱為后進先出。 設(shè)棧s=（a1，a2，…,ai，…，an） 其中a1是棧底元素， an是棧頂元素。 棧頂（top)：允許插入和刪除的一端； 約定top始終指向新數(shù)據(jù)元素將存放

21、的位置。 棧底（bottom):不允許插入和刪除的一端。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,隊列的主要運算 設(shè)置一個空隊列； 插入一個新的隊尾（rear）元素，稱為進隊； 刪除隊頭（front）元素，稱為出隊； 讀取隊頭元素；,,,a1 , a2 , a3 , a4 , ………… an-1 , an,,,,,隊頭,隊尾,1.4 棧和隊列,隊列：限

22、定只能在表的一端進行插入，在表的另一端進行刪除的線性表。此種結(jié)構(gòu)稱為先進先出（FIFO）表。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,,1.4 棧和隊列,隊列的主要運算 隊空時，令rear=front=0; 元素個數(shù)＝rear-front 當(dāng)有新元素入隊時，尾指針加1，當(dāng)有元素出隊時，頭指針加1。故在非空隊列中，頭指針始終指向隊頭元素前一個位置，而尾指針始終指向隊尾元素的位置,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,循環(huán)隊列元素個數(shù)=(rear-front+n

23、) mod n,,,a1 , a2 , a3 , a4 , ………… an-1 , an,,,,,隊頭,隊尾,1.4 棧和隊列,循環(huán)隊列：首尾相接的隊列，邏輯上形成一個環(huán)狀。,,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.5 線性鏈表（P24）,線性表順序存儲結(jié)構(gòu)的特點 簡單、方便，要求數(shù)據(jù)元素依次存放在連續(xù)的存儲單元中，從而利用數(shù)據(jù)元素的存

24、儲順序表示相應(yīng)的邏輯順序，這種存儲方式屬于靜態(tài)存儲形式。 暴露的問題 在做插入或刪除元素的操作時，會產(chǎn)生大量的數(shù)據(jù)元素移動； 對于長度變化較大的線性表，要一次性地分配足夠的存儲空間，但這些空間常常又得不到充分的利用； 線性表的容量難以擴充。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,將線性表的元素放到一個具有頭指針的鏈表中，鏈表中每個結(jié)點包含數(shù)據(jù)域和指針域。   數(shù)據(jù)域存放數(shù)據(jù)，指針域存放后繼結(jié)點的地址，最后一個結(jié)點的指針域為空。

25、邏輯上相鄰的數(shù)據(jù)元素在內(nèi)存中的物理存儲空間不一定相鄰。 線性鏈表分為：單鏈表、雙鏈表、循環(huán)鏈表,1.5 線性鏈表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,單鏈表：每個結(jié)點只有一個指針域，由該指針只能找到其后件結(jié)點。,1.5 線性鏈表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.5 線性鏈表,線性鏈表的計算 在指定節(jié)點前插入一個元素(不必移動節(jié)點，僅改變節(jié)點中的指針，且不會出現(xiàn)“上溢”現(xiàn)象) 刪除指定節(jié)點(不必移動節(jié)點，僅改變節(jié)點中的指針) 合并兩

26、個線性鏈表 逆轉(zhuǎn)線性鏈表 復(fù)制線性鏈表 線性鏈表排序 線性鏈表查找,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,,,P,P,,,,單鏈表的插入運算：在節(jié)點a之后插入一新節(jié)點,,S,,1.5 線性鏈表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,,L,,,,,,,p,,,,,,,,單鏈表的刪除運算：刪除節(jié)點ai,1.5 線性鏈表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,循環(huán)鏈表: 首尾相接的鏈表 （P30） 循環(huán)鏈表是表中最后一個結(jié)點的指針非空，而是指向頭結(jié)點，使鏈表

27、構(gòu)成環(huán)狀。 特點： 2、增加了頭結(jié)點，使得任何時候循環(huán)鏈表中至少有一個結(jié)點。 1、從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點，提高查找效率。,1.5 線性鏈表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,雙向鏈表：在每個結(jié)點中設(shè)置兩個指針，一個指向后繼，一個指向前驅(qū)。可直接確定一個結(jié)點的前驅(qū)和后繼結(jié)點。可提高效率。,1.5 線性鏈表,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.5 線性鏈表,線性鏈表的特點 插入、刪除節(jié)點方便(不必移動節(jié)點，僅改變節(jié)

28、點中的指針) 只能順序存?。ú檎抑荒軓念^指針開始），不能隨即存取。 適應(yīng)于數(shù)據(jù)的動態(tài)變化,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,樹的定義：由一個或多個結(jié)點組成的有限集合。僅有一個根結(jié)點，結(jié)點間有明顯的層次結(jié)構(gòu)關(guān)系。,,,,現(xiàn)實世界中，能用樹的結(jié)構(gòu)表示：學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。,1.6 樹與二叉樹,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,樹的基本概念： 結(jié)點（Node）：樹中的元素 結(jié)點的度（Degree）：結(jié)點擁有的子樹數(shù)。

29、結(jié)點的層次：從根結(jié)點開始算起，根為第一層。 葉子（Leaf）：度為零的結(jié)點，也稱端結(jié)點。 孩子（Child）：結(jié)點子樹的根稱為該結(jié)點的孩子結(jié)點。 兄弟（Sibling）：同一雙親的孩子。 雙親（Parent）：孩子結(jié)點的上層結(jié)點，稱為其的雙親。 深度（Depth)： 樹中結(jié)點的最大層次數(shù)。 森林（Forest）：M棵互不相交的樹的集合。,1.6 樹與二叉樹（P31）,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,二叉樹（Binary Tree

30、）的定義(P34),二叉樹的五種基本形態(tài),因為樹的每個結(jié)點的度不同，存儲困難，使對樹的處理算法很復(fù)雜。所以引出二叉樹的理論。,1.6 樹與二叉樹,二叉樹一種特殊的樹型結(jié)構(gòu)，特點是樹中每個結(jié)點只有兩棵子樹，且子樹有左右之分，次序不能顛倒。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,滿二叉樹 （P35）,特點：所有分支結(jié)點都存在左右子樹，且所有葉子結(jié)點都在同一層上。,1.6 樹與二叉樹,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,完全二叉樹 （P35）,特點：除最后一層外，

31、每一層都取最大結(jié)點數(shù)，最后一層結(jié)點都集中在該層最左邊的若干位置。,1.6 樹與二叉樹,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,A、二叉樹的第i層上至多有2k-1（k ?1）個結(jié)點。 B、深度為h的二叉樹中至多含有2m-1個結(jié)點。 C、若在任意一棵二叉樹中，有n0個葉子結(jié)點（度為0），有n2個度為2的結(jié)點，則：n0=n2+1 D、具有n個結(jié)點的完全二叉樹的深度為[log2n]+1，其中 [log2n]表示log2n 的整數(shù)部分。,二叉樹的基本性質(zhì)

32、（P34）,1.6 樹與二叉樹,第三層 (i=3)，有23-1=4個節(jié)點 深度h=4，共有24-1=15個節(jié)點 n0=8,n2=7,n0=n2+1 15個節(jié)點，深度=[log215]+1=4,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,E、設(shè)完全二叉樹共有n個結(jié)點，如從根結(jié)點開始，按層序（每一層從左到右）用自然數(shù)1,2,…,n給結(jié)點進行編號，則對于編號為k（k=1,2,…,n）的結(jié)點有以下結(jié)論： ①若k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k&

33、gt;1，則該結(jié)點的父結(jié)點的編號為INT(k/2)。 ②若2k≤n，則結(jié)點k的左子結(jié)點編號為2k；否則該結(jié)點無左子結(jié)點（顯然也沒有右子結(jié)點）。 ③若2k+1≤n，則結(jié)點k的右子結(jié)點編號為2k+1；否則該結(jié)點無右子結(jié)點。,二叉樹的基本性質(zhì),1.6 樹與二叉樹,例如結(jié)點6，其父結(jié)點為3，左子結(jié)點為12，左子結(jié)點為13,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.6 樹與二叉樹,二叉樹的存儲結(jié)構(gòu) (P36)順序存儲結(jié)構(gòu) 鏈?zhǔn)酱鎯Y(jié)構(gòu) 順序存儲結(jié)

34、構(gòu) （不需掌握）用一組連續(xù)的存儲單元存放二叉樹的數(shù)據(jù)元素。結(jié)點在數(shù)組中的相對位置蘊含著結(jié)點之間的關(guān)系。 用數(shù)組存儲時，若父結(jié)點在數(shù)組中i下標(biāo)處，其左孩子在2*i處，右孩子在2*i+1處。 順序存儲二叉樹必須按完全二叉樹的形式存儲，將造成存儲的浪費。,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,二叉樹的順序存儲結(jié)構(gòu)（不需掌握）,,,T[16],2h-1=,24-1 = 15,1.6 樹與二叉樹,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.6 樹與二叉樹,二叉樹鏈?zhǔn)?/p>

35、存儲結(jié)構(gòu)（不需掌握） 在順序存儲結(jié)構(gòu)中，對于非完全二叉樹，需要將空缺的位置用特定的符號填補，若空缺結(jié)點較多，勢必造成空間利用率的下降。在這種情況下，就應(yīng)該考慮使用鏈?zhǔn)酱鎯Y(jié)構(gòu)。常見的二叉樹結(jié)點結(jié)構(gòu)如下所示：,A,B,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,1.6 樹與二叉樹,二叉樹的鏈接存儲結(jié)構(gòu)（不需掌握）,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,二叉樹的遍歷（P38） 遍歷是指按某條搜索路線尋訪樹中每個結(jié)點，且每個結(jié)點只被訪問一次。 按

36、先左后右的原則，一般使用三種遍歷： 前序遍歷(D L R): 訪問根結(jié)點，按先序遍歷左子樹，按先序遍歷右子樹。 中序遍歷(L D R): 按中序遍歷左子樹，訪問根結(jié)點，按中序遍歷右子樹。 后序遍歷(L R D): 按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點。 二叉樹為空時，執(zhí)行空操作，即空二叉樹已遍歷完。,1.6 樹與二叉樹,,,基本數(shù)據(jù)結(jié)構(gòu)與

37、算法,遍歷算法,先序遍歷：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,1.6 樹與二叉樹,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,查找：在一個給定的數(shù)據(jù)結(jié)構(gòu)中，根據(jù)給定的條件找到滿足條件的結(jié)點。不同的數(shù)據(jù)結(jié)構(gòu)采用不同的查找方法。查找的效率直接影響數(shù)據(jù)處理的效率。 平

38、均查找長度：查找過程中比較的次數(shù) 查找的結(jié)果 查找成功：找到滿足條件的結(jié)點 查找失?。赫也坏綕M足條件的結(jié)點。,1.7 查找技術(shù)（P39）,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,順序查找（線性查找） 對給定的一關(guān)鍵字K，從線性表的一端開始，逐個進行記錄的關(guān)鍵字和K的比較，直到找到關(guān)鍵字等于K的記錄或到達(dá)表的另一端。 可以采用從前向后查，也可采用從后向前查的方法。 在平均情況下，大約要與表中一半以上元素進行比較，效率較低。平均查找長

39、度=(n+1)/2。 時間復(fù)雜度＝O(n) 在下面兩種情況下只能采取順序查找： 線性表為無序表（元素排列是無序的）； 即使是有序線性表，但采用的是鏈?zhǔn)酱鎯Y(jié)構(gòu)。,1.7 查找技術(shù)（P39）,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,折半查找（二分法查找）,思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。 前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進行。 分三種情況： 若中間項的值等于x,則說明已查到。 若

40、x小于中間項的值，則在線性表的前半部分查找； 若x大于中間項的值，則在線性表的后半部分查找。 特點：比順序查找方法效率高。最壞的情況下，需要比較 log2n次。,1.7 查找技術(shù)（P39）,折半查找（二分法查找）算法,假設(shè)查找表存放在數(shù)組a的a[1]～a[n]中，且升序，查找關(guān)鍵字值為k。折半查找的主要步驟為： （1）置初始查找范圍：low=1，high=n; （2）求查找范圍中間項：mid=(low+high)/2 （3

41、）將指定的關(guān)鍵字值k與中間項a[mid].key比較。 若相等，查找成功，找到的數(shù)據(jù)元素為此時mid 指向的位置； 若小于，查找范圍的低端數(shù)據(jù)元素指針low不變，高端數(shù)據(jù)元素指針high更新為mid-1; 若大于，查找范圍的高端數(shù)據(jù)元素指針high不變，低端數(shù)據(jù)元素指針low更新為mid+1; （4）重復(fù)步驟（2）、（3）直到查找成功或查找范圍空（low>high），即查找失敗為止。 （5）

42、如果查找成功，返回找到元素的存放位置，即當(dāng)前的中間項位置指針mid；否則返回查找失敗標(biāo)志。,查找23和79的過程如下圖：9元素,mid=(low+high)/2不進位取整,( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37

43、, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55,

44、 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79,

45、 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),,,基本數(shù)據(jù)結(jié)構(gòu)與算法,排序的功能：將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排成一個按關(guān)鍵字有序的序列。 排序過程的組成步驟 1、首先比較兩個關(guān)鍵字的大小； 2、然后將記錄從一個位置移動到

46、另一個位置。,1.8 排序技術(shù)（P40）,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,,交換排序的特點在于交換，有冒泡和快速排序兩種。 冒泡排序（起泡排序） 思想：小的浮起，大的沉底。從左端開始比較。 第一趟：第1個與第2個比較，大則交換；第2個與第3個比較，大則交換，…關(guān)鍵字最大的記錄交換到最后一個位置上； 第二趟：對前n-1個記錄進行同樣的操作，關(guān)鍵字次大的記錄交換到第n-1個位置上； 依次類推，則完成排序。

47、 正序：時間復(fù)雜度為O(n) 逆序：時間復(fù)雜度為O(n2) 排序n個記錄的文件最多需要n-1趟冒泡排序。,1.8.1 交換類排序法（P40）,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,第 六 趟 排 序 后,第 五 趟 排 序 后,第 四 趟 排 序 后,第 三 趟 排 序 后,第 二 趟 排 序 后,第 一 趟 排 序 后,初 始 關(guān) 鍵 字,,,,,1.8.1 交換類

48、排序法—示例,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,該算法適合于n 較小的情況，時間復(fù)雜度為O(n2).,待排元素序列：[53] 27 36 15 69 42 第一次排序： [27 53] 36 15 69 42 第二次排序： [27 36 53] 15 69 42 第三次排序： [15 27 36 53] 69 42 第四次排序：

49、 [15 27 36 53 69] 42 第五次排序： [15 27 36 42 53 69] 直接插入排序示例,對于有n個數(shù)據(jù)元素的待排序列，插入操作要進行n-1次,,1.8.2 直接插入排序（P42）,從數(shù)組的第2號元素開始，順序取出后續(xù)元素，并將該元素插入到其左端已排好序數(shù)組的適當(dāng)位置。需比較n(n-1)/2次,,,基本數(shù)據(jù)

50、結(jié)構(gòu)與算法,例：有6個記錄，前5 個已排序的基礎(chǔ)上，對第6個記錄排序。 [ 15 27 36 53 69 ] 42 ? low ?mid ? high [ 15 27 36 53 69 ] 42 ?low ? hi

51、gh ?mid [ 15 27 36 53 69 ] 42 ?high ?low [ 15 27 36 42 53 69 ]

52、,,(high<low ，查找結(jié)束，插入位置為low 或high+1 ),( 42>36 ),( 42<53 ),折半插入排序,折半插入排序在尋找插入位置時，不是逐個比較而是利用折半查找的原理尋找插入位置 。待排序元素越多，改進效果越明顯。,思想：首先從1～n個元素中選出關(guān)鍵字最小的記錄交換到第一個位置上。然后再從第2 個到第n個元素中選出次小的記錄交換到第二個位置上，依次類推。 時間復(fù)雜度為O(n2)，最壞情況下

53、需要比較 n(n-1)/2次 適用于待排序元素較少的情況。,1.8.3 簡單選擇排序（P44）,初態(tài),8 3 9 1 6,8 3 9 1 6,8 3 9 1 6,8 3 9 1 6,1 3

54、 9 8 6,1 3 9 8 6,1 3 9 8 6,,,,基本數(shù)據(jù)結(jié)構(gòu)與算法,,各種排序法比較,,,二級ACCESS—查詢,過關(guān)練習(xí),,【2010.9】(1) 下列敘述中正確的是【 】A) 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)所需要的存儲空間是相同的B) 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)所需要的

55、存儲空間一般要多于順序存儲結(jié)構(gòu)C) 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)所需要的存儲空間一般要少于順序存儲結(jié)構(gòu) D) 上述三種說法都不對【2010.9】(2)下列敘述中正確的是【 】A）在棧中，棧中元素隨棧底指針與棧頂指針的變化而動態(tài)變化B）在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動態(tài)變化C）在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態(tài)變化 D）上述三種說法都不對,√,√

56、,,,二級ACCESS—查詢,過關(guān)練習(xí),,【2010.9】(3)一個棧的初始狀態(tài)為空。首先將元素5,4,3,2,1依次入棧，然后退棧一次，再將元素A,B,C,D依次入棧，之后將所有元素全部退棧，則所有元素退棧（包括中間退棧的元素)的順序為【 】?！?【2010.9】(4)在長度為n的線性表中，尋找最大項至少需要比較【 】次?！?010.9】(5)一棵二叉樹

57、有10個度為1的結(jié)點，7個度為2的結(jié)點，則該二義樹共有【 】個結(jié)點。,1DCBA2345,1,25,,,二級ACCESS—查詢,過關(guān)練習(xí),,【2010.3】(6)下列敘述中正確的是【 】　　A)對長度為n的有序鏈表進行查找，最壞情況下需要的比較次數(shù)為n　　B)對長度為n的有序鏈表進行對分查找，最壞情況下需要的比較次數(shù)為(n/2)　　C)對長度為n的有序鏈表進行對分查找，最壞情況下需要的比較次數(shù)為(lo

58、g2n)　　D)對長度為n的有序鏈表進行對分查找，最壞情況下需要的比較次數(shù)為(n log2n)【2010.3】(7)算法的時間復(fù)雜度是指【 】　　A)算法的執(zhí)行時間　　B)算法所處理的數(shù)據(jù)量　　C)算法程序中的語句或指令條數(shù)　　D)算法在執(zhí)行過程中所需要的基本運算次數(shù),√,√,,,二級ACCESS—查詢,過關(guān)練習(xí),,【2010.3】(8)一個隊列的初始狀態(tài)為空。現(xiàn)將元素A,B,C,D,E,F,5,4,3,2,1依次入

59、隊，然后再依次退隊，則元素退隊的順序為【 】?！?010.3】(9)設(shè)某循環(huán)隊列的容量為50，如果頭指針front=45(指向隊頭元素的前一位置)，尾指針rear=10(指向隊尾元素)，則該循環(huán)隊列中共有【 】 個元素。【2010.3】(10)設(shè)二叉樹如下：對該二叉樹進行后序遍歷的結(jié)果為【

60、 】 。,A,B,C,D,E,F,5,4,3,2,1,15,EDBGHFCA,,,二級ACCESS—查詢,過關(guān)練習(xí),,【2009.9】(11) 下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是【 】 A）循環(huán)隊列　　 B）帶鏈隊列　　 C）二叉樹　　 D）帶鏈棧【2009.9】(12)下列數(shù)據(jù)結(jié)果中，能夠按照“先進后出”原則存取數(shù)據(jù)的是【 】A）循環(huán)隊列　　B）?！　）隊列

61、　　D）二叉樹【2009.9】(13) 對于循環(huán)隊列，下列敘述中正確的是【 】Ａ）隊頭指針是固定不變的 Ｂ）隊頭指針一定大于隊尾指針Ｃ）隊頭指針一定小于隊尾指針Ｄ）隊頭指針可以大于隊尾指針，也可以小于隊尾指針,√,√,√,,,二級ACCESS—查詢,過關(guān)練習(xí),,【2009.9】（14）算法的空間復(fù)雜度是指【 】 Ａ）算法在執(zhí)行過程中所需要的計算機存儲空間　　Ｂ）算法所處理的數(shù)據(jù)量　?。茫┧惴ǔ?/p>

62、序中的語句或指令條數(shù)　?。模┧惴ㄔ趫?zhí)行過程中所需要的臨時工作單元數(shù)【2009.9】（15）某二叉樹由5個度為2的結(jié)點以及3個度為1的結(jié)點，則該二叉樹中共有 【 】 個結(jié)點。,14,√,,,二級ACCESS—查詢,過關(guān)練習(xí),,【2009.3】(16)下面敘述中正確的是【 】 A）棧是“先進先出”的線性表 B）隊列是“先進后出”的線性表 C）循環(huán)隊列是非線性結(jié)構(gòu) D）有序線性表既可以采用順

63、序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)【2009.3】(17)支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是【 】 A）棧 B）樹 C）隊列 D）二叉樹,√,√,,,二級ACCESS—查詢,過關(guān)練習(xí),,【2009.3】(18)某二叉樹有5個度為2的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)是【 C 】 A）10 B） 8 C）6

64、 D）4【2009.3】(19)下列排序方法中，最壞情況下比較次數(shù)最少的是【 D 】 A）冒泡排序 B）簡單選擇排序 C）直接插入排序 D）堆排序【2009.3】（20）假如用一個長度為50的數(shù)組（數(shù)組元素的下標(biāo)從0到49）作為棧的存儲空間，棧底指針bottom指向棧底元素，棧頂指針top指向棧頂元素，如果bottom=49,top=30（數(shù)組下標(biāo)）