1、計算機二級考試公共基礎之計算機二級考試公共基礎之數據結構與算法數據結構與算法14 算法與算法分析算法與算法分析算法與算法分析一一 算法的概念算法的概念 算法是對特定問題求解步驟的一種描述算法是對特定問題求解步驟的一種描述 算法的基本特征：算法的基本特征：1 1）可行性可行性：組成算法的操作必須能夠在計算機上實現。：組成算法的操作必須能夠在計算機上實現。2 2）確定性確定性：算法的每一步操作必須清晰無二義性。：算法的每一步操作必須清晰無二義性。3 3）有窮性有窮性：算法必須在有限步內結束；：算法必須在有限步內結束；4 4）有足夠的情報有足夠的情報：0 0個或多個輸入；個或多個輸入；1 1個或多個

2、輸出；個或多個輸出； 算法描述的方法很多，如自然語言、框圖、類算法描述的方法很多，如自然語言、框圖、類C C等等例例: : 求兩個正整數求兩個正整數 m m，n n 中的最大數中的最大數MAXMAX的算法的算法 （1 1）若若 m n m n 則則 max=mmax=m （2 2）若若 m = n m = n 則則 max=nmax=n 程序程序=算法算法+數據結構數據結構1、正確性正確性： (1) 沒有語法錯誤； (2) 對于幾組輸入數據能夠得出滿足要求的結果； (3) 對于精心選擇的典型而苛刻的幾組輸入數據能夠得到滿足要求的結果。 (4) 對于一切合法的輸入數據都能產生滿足要求的結果。 2

3、、可讀性：可讀性：便于閱讀、理解、調試、修改；3、健壯性：健壯性：對不合法的輸入能作出正確的反映與處理；4、高效性：高效性：執行時間短（時間復雜度時間復雜度）、 需求存儲空間省（空間復雜度空間復雜度）評價算法標準評價算法標準1 時間復雜度時間復雜度T（n） 以求解問題的基本操作的以求解問題的基本操作的執行次數執行次數作為算法時間的度量。作為算法時間的度量。算法與算法分析算法與算法分析O（n3） 稱為矩陣相乘算法時間復雜度；稱為矩陣相乘算法時間復雜度；O（n3）表示矩陣相乘算法執行時間與）表示矩陣相乘算法執行時間與n3成正比成正比, 即即O（n3）與）與n3 同一數量級；同一數量級； 例：例：n

4、 階矩陣相乘的算法階矩陣相乘的算法For ( i = 1; i=n; i+ ) For (j = 1; j=n; j+ ) c i j = 0 ; For (k = 1; k= n; k+ ) c i j += a i k * b k j 乘法乘法 加法加法執行次數均為執行次數均為 n3 矩陣相乘的基本運算：乘法矩陣相乘的基本運算：乘法 加法；加法；數據結構中常用的時間復雜度頻率計數有數據結構中常用的時間復雜度頻率計數有7個：個： O(1) 常數型常數型 O(n)線性型線性型 O(n2)平方型平方型 O(n3)立方型立方型 O(2n)指數型指數型 O(log2n)對數型對數型 O(nlog2n

5、)二維型二維型2 算法空間復雜度算法空間復雜度 用執行算法所需的用執行算法所需的內存空間的大小內存空間的大小作為算法所需空間的度量。作為算法所需空間的度量。 設執行算法所需的內存空間是問題規模設執行算法所需的內存空間是問題規模n的某個函數的某個函數g(n),則算法空間復雜則算法空間復雜度記作：度記作： S（n）= O(g(n)表示算法內存空間的增長率表示算法內存空間的增長率與與g(n) 的增長率相同的增長率相同例計算例計算 解法解法1 先計算先計算x 的冪的冪, 存于存于power 中中,再分別乘以相應的系數再分別乘以相應的系數 # define N 100 float evaluate (f

6、loat coef , float x , int n ) float powerN, f; int i; for (power 0=1, i = 1; i=n; i+ ) poweri=x*poweri-1; for (f = 0, i=0; ideta=a; q-next=p- next; p- next =q;headheadzyxp pyxzp pheadheada q q插入操作功能：在線性鏈表的第插入操作功能：在線性鏈表的第i個元素結點之前插入一個個元素結點之前插入一個新元素結點新元素結點e； 插入操作圖示：插入前插入后 ai-1aia2a1ai+1nanheadheadai-1a

7、ia2a1ai+1naneheadhead 4）刪除結點刪除結點q=p-next; p- next =q- next; free(q);headheadzyxq qyxzq qheadheadp pp p刪除前刪除后ai-1aia2a1ai+1nanheadheadai-1aia2a1ai+1nanheadp pp pq qq q線性鏈表小結線性鏈表小結線性鏈表是線性表的一種鏈式存儲結構 線性鏈表的特點 1 通過保存直接后繼元素的存儲位置來表示 數據元素之間的邏輯關系； 2 插入、刪除操作通過修改結點的指針實現； 3 不能隨機存取元素；1 循環鏈表的概念循環鏈表的概念 循環鏈表的特點是將線性鏈

8、表的最后一個結點的指循環鏈表的特點是將線性鏈表的最后一個結點的指針指向鏈表的第一個結點（首尾相連的單鏈表）針指向鏈表的第一個結點（首尾相連的單鏈表）2 循環鏈表圖示循環鏈表圖示循環鏈表循環鏈表(a)非空表 （b）空表headheadheadheada1an循環鏈表循環鏈表說明在解決某些實際問題時循環鏈表可能要比線性鏈表在解決某些實際問題時循環鏈表可能要比線性鏈表方便些。如將一個鏈表鏈在另一個鏈表的后面；方便些。如將一個鏈表鏈在另一個鏈表的后面； 對循環鏈表，有時不給出頭指針，而是給出尾指針對循環鏈表，有時不給出頭指針，而是給出尾指針a aa1ana-next給出尾指針的循環鏈表雙向鏈表雙向鏈表

9、 循環單鏈表，雖然從任一結點出發沿著指針鏈能找到其前循環單鏈表，雖然從任一結點出發沿著指針鏈能找到其前件，但時間耗費是件，但時間耗費是O(n) 。如果希望從表中快速確定某一個結點。如果希望從表中快速確定某一個結點的前件，另一個解決方法是在鏈表的每個結點里再增加一個指的前件，另一個解決方法是在鏈表的每個結點里再增加一個指向其前件的指針域向其前件的指針域prior。 這樣形成的鏈表中就有兩條方向不這樣形成的鏈表中就有兩條方向不同的鏈，稱為雙向鏈表。同的鏈，稱為雙向鏈表。線性表小結線性表小結 線性表的順序存儲結構線性表的順序存儲結構順序表，順序表， 鏈式存儲結構鏈式存儲結構-線性鏈表線性鏈表,循環鏈

10、表循環鏈表, 雙向鏈雙向鏈表表.不同的存儲結構，線性表的同一操作的算不同的存儲結構，線性表的同一操作的算法是不同的法是不同的:在順序存儲結構下，線性表的插入、刪除在順序存儲結構下，線性表的插入、刪除操作，通過移動元素實現操作，通過移動元素實現;在線性鏈表存儲結構下，線性表的插入、在線性鏈表存儲結構下，線性表的插入、刪除操作，通過修改指針實現。刪除操作，通過修改指針實現。2 棧棧 棧是限定僅能在表尾一端進行插入、刪除操作棧是限定僅能在表尾一端進行插入、刪除操作的線性表的線性表（a1, a2, . , ai -1, ai , ai+1, , an ）插入刪除2.1棧的概念棧的概念一一 什么是棧什么

11、是棧?將表中允許進行插入、刪除操作的一端稱為將表中允許進行插入、刪除操作的一端稱為棧頂棧頂(Top)，棧頂的當前位置是動態變化的，由一個棧頂指針指示其位置。棧頂的當前位置是動態變化的，由一個棧頂指針指示其位置。表的另一端稱為棧底表的另一端稱為棧底(Bottom)。當棧中沒有元素時稱為空棧。當棧中沒有元素時稱為空棧。棧的插入操作稱為棧的插入操作稱為進棧或入棧進棧或入棧，刪除操作稱為，刪除操作稱為出棧或退棧出棧或退棧。 棧棧 ana2a1進棧出棧棧頂棧底進棧出棧(a) 棧的示意圖(b) 鐵路調序棧的表示棧的示意圖棧的示意圖出棧出棧進棧進棧棧的特點棧的特點后進先出后進先出第一個進棧的元素在棧底，第一

12、個進棧的元素在棧底，最后一個進棧的元素在棧頂，最后一個進棧的元素在棧頂，第一個出棧的元素為棧頂元素，第一個出棧的元素為棧頂元素，最后一個出棧的元素為棧底元素最后一個出棧的元素為棧底元素棧棧頂頂棧棧底底ana2a1 小小 結結 1 棧是限定僅能在表尾一端進行插入、棧是限定僅能在表尾一端進行插入、 刪除操作的線性表；刪除操作的線性表； 2 棧的元素具有后進先出的特點；棧的元素具有后進先出的特點； 3 棧頂元素的位置由一個稱為棧頂指針的棧頂元素的位置由一個稱為棧頂指針的 變量指示，變量指示， 進棧、出棧操作要修改棧頂指針；進棧、出棧操作要修改棧頂指針； 2 棧棧3 隊列隊列3.1 隊列的概念隊列的概

13、念一一 什么是隊列什么是隊列隊列是限定僅能在表頭進行刪除，表尾進行插入的線性表隊列是限定僅能在表頭進行刪除，表尾進行插入的線性表（a1, a2, . , ai -1, ai , ai+1, , an ）插入插入刪除刪除3 隊列隊列 a a1 1 a a2 2 a a3 3 a an n入隊列入隊列隊隊頭頭隊隊尾尾出隊列出隊列隊隊 列列 的的 示示 意意 圖圖隊列的特點隊列的特點先進先出先進先出第一個入隊的元素在隊頭，第一個入隊的元素在隊頭，最后一個入隊的元素在隊尾，最后一個入隊的元素在隊尾，第一個出隊的元素為隊頭元素，第一個出隊的元素為隊頭元素，最后一個出隊的元素為隊尾元素最后一個出隊的元素為

14、隊尾元素rearrearfrontfrontJ1rearrearfrontfrontJ2（a)a)空隊列空隊列(b)J1,J2(b)J1,J2相繼相繼入隊列入隊列(c)J1(c)J1出隊出隊(d)J3,J4, J5(d)J3,J4, J5和和J6J6相繼入隊之后相繼入隊之后,J2,J2出隊出隊rearrearfrontfront0 01 12 23 34 45 5rearrearfrontfrontJ5J4J3front,rearfront,rear為整為整數數 又有又有J7入隊入隊, 怎么辦？怎么辦？J2J63 . 循環隊列循環隊列frontfrontrearJ6J6J4J4J5J53 12

15、4 05rearrear54 03 12frontfrontJ6J6J7J7J8J8J9J9J4J4J5J5frontfrontrearrear54 03 12(b)(b)隊空隊空(a)(a)隊滿隊滿J7J7rearrear判分隊空、隊滿方法：判分隊空、隊滿方法：1）另設一個標志）另設一個標志S以區分隊空、隊滿。以區分隊空、隊滿。2）S=0 隊空：隊空： front=rear; S=1 隊滿：隊滿： front=rear;或少用一個空間或少用一個空間Real+1=front 為滿為滿frontfront54 03 12J6J6J7J7J8J8J4J4J5J5（c c）rearrear入隊操作入

16、隊操作 ：將元素將元素 x 插入隊尾插入隊尾 frontfrontrearrear54 03 12J1J1J3J3J2J2x xfrontfrontrearrear54 03 12J1J1J3J3J2J2元素元素 x x 入隊前入隊前元素元素 x x 入隊后入隊后出隊操作出隊操作 ：刪除隊頭：刪除隊頭元素；元素； frontfrontrearrear54 03 12J1J1J3J3J2J2出隊操作前出隊操作前frontfrontrearrear54 03 12J1J1J3J3J2J2出隊操作后出隊操作后 小小 結結 1 隊列是限定僅能在表尾一端進行插入，表頭隊列是限定僅能在表尾一端進行插入，表

17、頭一端刪除一端刪除 操作的線性表；操作的線性表； 2 隊列中的元素具有先進先出的特點；隊列中的元素具有先進先出的特點； 3 隊頭、隊尾元素的位置分別由稱為隊頭指針隊頭、隊尾元素的位置分別由稱為隊頭指針和隊尾指針的變量指示，和隊尾指針的變量指示， 4 入隊操作要修改隊尾指針，出隊操作要修改入隊操作要修改隊尾指針，出隊操作要修改隊頭指針；隊頭指針； 數據存儲結構方面的考題數據存儲結構方面的考題 1：數據的存儲結構是指：數據的存儲結構是指 （ ）。）。A) 存儲在外存中的數據存儲在外存中的數據 B) 數據所占的存儲空間量數據所占的存儲空間量C) 數據在計算機中的順序存儲方式數據在計算機中的順序存儲方

18、式 D) 數據的邏輯結構在計算機中的表示數據的邏輯結構在計算機中的表示2. 下列敘述中正確的是下列敘述中正確的是 （ ）。）。 A）棧是）棧是“先進先出先進先出”的線性表的線性表 B）隊列是）隊列是“先進后出先進后出”的線性表的線性表 C）循環隊列是非線性結構）循環隊列是非線性結構 D）有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構）有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構 3. 數據結構分為線性結構和非線性結構，帶鏈的隊列屬于（數據結構分為線性結構和非線性結構，帶鏈的隊列屬于（ ）。）。4. 下列數據結構中，屬于非線性結構的是（下列數據結構中，屬于非線性結構的是（

19、）。）。A）循環隊列）循環隊列 B) 帶鏈隊列帶鏈隊列C) 二叉樹二叉樹 D）帶鏈棧）帶鏈棧答案：答案：D。答案：答案：D。答案：線性結構。答案：線性結構。答案：答案：c5.下列敘述中正確的是（下列敘述中正確的是（ ）。）。 A）順序存儲結構的存儲一定是連續的，鏈式存儲結構的存儲空間不一）順序存儲結構的存儲一定是連續的，鏈式存儲結構的存儲空間不一定是連續的定是連續的 B）順序存儲結構只針對線性結構，鏈式存儲結構只針對非線性結構）順序存儲結構只針對線性結構，鏈式存儲結構只針對非線性結構 C）順序存儲結構能存儲有序表，鏈式存儲結構不能存儲有序表）順序存儲結構能存儲有序表，鏈式存儲結構不能存儲有序表

20、 D）鏈式存儲結構比順序存儲結構節省存儲空間）鏈式存儲結構比順序存儲結構節省存儲空間答案：答案：A。6.6.下列關于棧的敘述正確的是下列關于棧的敘述正確的是 （ ） A A）棧按）棧按“先進先出先進先出”組織數據組織數據 B)B)棧按棧按“先進后出先進后出”組織數據組織數據 C C）只能在棧底插入數據）只能在棧底插入數據 D D）不能刪除數據）不能刪除數據 答案：答案：B。7. 一個隊列的初始狀態為空。現將元素一個隊列的初始狀態為空。現將元素A，B，C，D，E，F，5，4，3，2，1依次入隊，然后再依次退隊，則元素退隊的順序為依次入隊，然后再依次退隊，則元素退隊的順序為 【1】 。（。（ ）

21、答案：答案：A，B，C，D，E，F，5，4，3，2，19. 設某循環隊列的容量為設某循環隊列的容量為50，如果頭指針，如果頭指針front=45(指向隊頭元素的前一指向隊頭元素的前一位置位置)，尾指針，尾指針rear=10(指向隊尾元素指向隊尾元素)，則該循環隊列中共有，則該循環隊列中共有 【2】 個個元素。元素。 （ ） 8.假設用一個長度為假設用一個長度為50的數組（數組元索的下標從的數組（數組元索的下標從0到到49）作為棧的存）作為棧的存儲空間，棧底指針儲空間，棧底指針bottom指間棧底元素，棧頂指針指間棧底元素，棧頂指針top指向棧頂元素，指向棧頂元素，如果如果bottom=49，t

22、op=30（數組下標），則棧中具有（數組下標），則棧中具有【 】個元素。個元素。 （2009年年3月）月） 答案：答案：19答案：答案：154 樹和二叉樹 1樹的定義樹的定義 樹是樹是n個結點的有限集合個結點的有限集合T，當，當n=0時，稱為空樹；當時，稱為空樹；當n0時，時，T滿足如下條件：在任一棵非空樹中：滿足如下條件：在任一棵非空樹中：（1）有且僅有一個稱為根的結點。）有且僅有一個稱為根的結點。（2）其余結點可分為）其余結點可分為M個互不相交的子集合，而且這些子集個互不相交的子集合，而且這些子集中的每一個本身又是一棵樹，也稱為根的子樹。中的每一個本身又是一棵樹，也稱為根的子樹。J JI

23、IA AC CB BD DH HG GF FE EK KL LM M2樹的實例樹的實例樹可表示具有分枝結構關系的對象樹可表示具有分枝結構關系的對象例例1家族族譜家族族譜 設某家庭有設某家庭有13個成員個成員A、B、C、D、E、F、G、H、I、J、K、L、M，他們之間的關系可用樹表示：，他們之間的關系可用樹表示：J JI IA AC CB BD DH HG GF FE EK KL LM M計算機中樹是常用的數據組織形式計算機中樹是常用的數據組織形式 盡管有些應用中數據元素之間并不存在分支結構關系，但盡管有些應用中數據元素之間并不存在分支結構關系，但為了便于管理和使用數據，將它們用樹的形式來組織。

24、為了便于管理和使用數據，將它們用樹的形式來組織。例例2 計算機的文件系統計算機的文件系統 不論是不論是DOS文件系統還是文件系統還是window文件系統，所有的文件都是用文件系統，所有的文件都是用樹的形式來組織的。樹的形式來組織的。文件夾文件夾1 1 文件夾文件夾n n 文件文件1 1 文件文件2 2文件夾文件夾11 11 文件夾文件夾12 12 文件文件11 11 文件文件1212C C盤盤3、樹的、樹的 基本術語基本術語 樹的結點：包含一個數據元素及若干指樹的結點：包含一個數據元素及若干指向子樹的分支；向子樹的分支；孩子結點：結點的子樹的根稱為該結點孩子結點：結點的子樹的根稱為該結點的孩子

25、，的孩子， B、C是是A的孩子；的孩子；雙親結點：雙親結點：B 結點是結點是A 結點的孩子，則結點的孩子，則A結點是結點是B 結點的雙親；結點的雙親；兄弟結點：同一雙親的孩子結點，兄弟結點：同一雙親的孩子結點， H、I、 J互為兄弟；互為兄弟；堂兄結點堂兄結點：同一層上結點，同一層上結點， E E、F F、G G、H H、I I、J J、互為堂兄弟；互為堂兄弟；J JI IA AC CB BD DH HG GF FE EK KL LM M3、樹的、樹的 基本術語基本術語結點的層次：根結點的層次定義為結點的層次：根結點的層次定義為1；根的孩子為第；根的孩子為第二層，依此類推；二層，依此類推；樹的

26、深度：樹的深度：樹中所有結點的層次的最大值樹中所有結點的層次的最大值結點的度：結點的度：結點子樹的個數結點子樹的個數樹的度：樹的度： 樹中結點度的最大值。樹中結點度的最大值。葉子結點葉子結點：度為：度為 0 的結點；的結點；分枝結點：分枝結點：度不為度不為0的結點；的結點；J JI IA AC CB BD DH HG GF FE EK KL LM M一一 二叉樹的概念二叉樹的概念1 1 二叉樹的定義二叉樹的定義二叉樹：二叉樹： 或為空樹，或由根及兩顆互不相交的左子樹、或為空樹，或由根及兩顆互不相交的左子樹、右子樹構成，并且左、右子樹本身也是二叉樹。右子樹構成，并且左、右子樹本身也是二叉樹。 A

27、 A F F G G E E D D C C B B一一 二叉樹的概念二叉樹的概念二叉樹說明說明1 1）二叉樹中每個結點最多有兩個子樹；）二叉樹中每個結點最多有兩個子樹；既：二叉樹每個結點度小于等于既：二叉樹每個結點度小于等于2;2;2 2）左、右子樹不能顛倒）左、右子樹不能顛倒有序樹有序樹; ;3 3）二叉樹是遞歸結構，在二叉樹的定義中又用到了二叉樹的）二叉樹是遞歸結構，在二叉樹的定義中又用到了二叉樹的概念概念; ; (a)(a)、(b)(b)是不同的二叉樹，是不同的二叉樹， (a)(a)的左子樹有四個結點的左子樹有四個結點，(b)(b)的左子樹有兩個結點的左子樹有兩個結點(a)(b) G

28、G E E D D C C B B A A F F G G E E D D C C B B F FA A 2 二叉樹的基本形態二叉樹的基本形態(a)空樹(b)只有根(c) 右子樹空(e) 左子樹空(d) 左、右子樹非空二、二、 二叉樹的性質二叉樹的性質 性質性質1: 在二叉樹的第在二叉樹的第i層上至多有層上至多有2i-1個結點個結點(i1)。 性質性質2: 深度為深度為k的二叉樹至多有的二叉樹至多有2k-1個結點（個結點（k1）。）。 性質性質3: 對任意一棵二叉樹對任意一棵二叉樹T，若葉結點數為，若葉結點數為n0，而其度為，而其度為2的結的結點數為點數為n2，則，則n0=n2+1。兩種特殊的

29、二叉樹兩種特殊的二叉樹滿二叉樹：深度為滿二叉樹：深度為k k的二叉樹，如有的二叉樹，如有2 2k k-1-1個結點則稱為滿二叉樹；個結點則稱為滿二叉樹； A A G G F F E E D D C C B B A A C C B BK=3的滿二叉樹K=2的滿二叉樹滿二叉樹的順序表示：滿二叉樹的順序表示： 從二叉樹的根開始，從二叉樹的根開始， 從上到下，從上到下， 從左到右，逐層進行編號（從左到右，逐層進行編號（1， 2， ， n）。例如圖（）。例如圖（a）所示的滿二叉樹的順序表示為）所示的滿二叉樹的順序表示為:(1， 2， 3， 4， 5， 6， 7， 8， 9， 10， 11， 12， 13

30、， 14， 15)。 891011 1213452136714158910111213452136714(a) 滿二叉樹(b) 完全二叉樹 完全二叉樹：完全二叉樹： 深度為深度為k，結點數為，結點數為n的二叉樹，如果其結點的二叉樹，如果其結點1n的位置序號分別與滿二叉樹的結點的位置序號分別與滿二叉樹的結點1n的位置序號的位置序號一一對應，則為完全二叉樹，一一對應，則為完全二叉樹， 如上圖如上圖 (b)所示。所示。 滿二叉樹必為完全二叉樹，滿二叉樹必為完全二叉樹， 而完全二叉樹不一而完全二叉樹不一定是滿二叉樹。定是滿二叉樹。 性質性質4：具有：具有n個結點的完全二叉樹的深度個結點的完全二叉樹的深

31、度為為log2n+1。 性質性質5: 對于有對于有n個結點的完全二叉樹，個結點的完全二叉樹， 按照從上到下、從按照從上到下、從左到右的順序對二叉樹中的所有結點從左到右的順序對二叉樹中的所有結點從1開始順序編號，開始順序編號， 則對則對于任意的序號為于任意的序號為i的結點有：的結點有： （1） 如如i=1，則序號為，則序號為i的結點是根結點，的結點是根結點， 無雙親結點；無雙親結點； 如如i1， 則序號為則序號為i的結點的雙親結點序號為的結點的雙親結點序號為i/2 （下取整） （2） 如如2in，則序號為，則序號為i的結點無左孩子；如的結點無左孩子；如2in，則序號，則序號為為i的結點的左孩子結

32、點的序號為的結點的左孩子結點的序號為2i。 （3） 如如2i1n，則序號為，則序號為i的結點無右孩子；如的結點無右孩子；如2i1n， 則序號為則序號為i的結點的右孩子結點的序號為的結點的右孩子結點的序號為2i1。 二叉樹二叉樹存儲結構存儲結構-二叉鏈表二叉鏈表 二叉鏈表中每個結點包含三個域：數據域、左指針域、右二叉鏈表中每個結點包含三個域：數據域、左指針域、右指針域指針域 A A F F E E D D C C B B二叉鏈表圖示二叉鏈表圖示 D D A A B B C C E E F F 若一個二叉樹含有若一個二叉樹含有n個結點，則它的二叉鏈表中必含有個結點，則它的二叉鏈表中必含有2n個指針

33、域，個指針域， 其中必有其中必有n+1個空的指針域。個空的指針域。 二、二叉樹的遍歷（必考）二、二叉樹的遍歷（必考）遍歷遍歷：按某種順序訪問二叉樹的每個結點，而且每個結點僅被按某種順序訪問二叉樹的每個結點，而且每個結點僅被訪問一次。訪問一次。訪問：含義很廣，可以是對結點的各種處理含義很廣，可以是對結點的各種處理，如修改結點數據，如修改結點數據、輸出結點數據。、輸出結點數據。 如何訪問二叉樹的每個結點， 而且每個結點僅被訪問一次？二叉樹的遍歷方法（必考）二叉樹的遍歷方法（必考） 二叉樹由根、左子樹、右子樹三部分組成 二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹令：L L：遍歷左子樹 T

34、：訪問根結點 R R：遍歷右子樹 約定先左后右,有三種遍歷方法： T L R L R前序遍歷、 L L T R R中序遍歷、 L R L R T后序遍歷。 A A F F G G E E D D C C B B 先序遍歷（T L L R R） 若二叉樹非空 （1）訪問根結點； （2）先序遍歷左子樹； （3）先序遍歷右子樹； 先序遍歷序列：A, ,B,D,B,D,E E,G,G,C C, ,F F例：先序遍歷右圖所示的二叉樹 （1）訪問根結點A （2）先序遍歷左子樹：即按 T L L R R 的順序遍歷左子樹 （3）先序遍歷右子樹：即按 T L L R R 的順序遍歷右子樹 A A F F G

35、G E E D D C C B B中序遍歷（L L T R R）若二叉樹非空（1）中序遍歷左子樹（2）訪問根結點（3）中序遍歷右子樹 中序遍歷序列： D,B,G,D,B,G,E E, ,A, ,C,FC,F例：中序遍歷右圖所示的二叉樹 （1）中序遍歷左子樹：即按 L L T R R 的順序遍歷左子樹 （2）訪問根結點A （3）中序遍歷右子樹：即按 L L T R R 的順序遍歷右子樹 A A F F G G E E D D C C B B后序遍歷（L L R R T）若二叉樹非空（1）后序遍歷左子樹（2）后序遍歷右子樹（3）訪問根結點 后序遍歷序列： D,G,D,G,E E,B,B,F,CF,

36、C, ,A例：后序遍歷右圖所示的二叉樹 （1）后序遍歷左子樹：即按 L L R R T 的順序遍歷左子樹 （2）后序遍歷右子樹：即按 L L R R T 的順序遍歷右子樹 （3）訪問根結點A A A F F G G E E D D C C B B 后序遍歷序列：a,b,c,d,-,a,b,c,d,-,* *,+,+,e,f,/e,f,/, ,-中序遍歷序列：a,+,b,a,+,b,* *,c,-,d,c,-,d,-, ,e,/,fe,/,f 例：例：中序遍歷、中序遍歷、后后序序遍歷下圖所示的二叉樹 e e d d c c b b f f a a + + * * / / - - - -例例:已知

37、一棵二叉樹前序遍歷和中序遍歷分別為已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和和DBGEACHF，則該二叉樹，則該二叉樹的后序遍歷為的后序遍歷為? A) GEDHFBCA B) DGEBHFCAC) ABCDEFGH D) ACBFEDHG B二叉樹1 1 二叉樹：二叉樹： 或為空樹，或由根及兩顆互不相交或為空樹，或由根及兩顆互不相交的左子樹、右子樹構成，并且左、右子樹本身的左子樹、右子樹構成，并且左、右子樹本身也是二叉樹；也是二叉樹； 2 2 二叉樹可以用鏈式結構存儲；二叉樹可以用鏈式結構存儲；遍歷：按某種搜索路徑訪問二叉樹的每個結點遍歷：按某種搜索路徑訪問二叉樹的每個結點，每個

38、結點僅被訪問一次。，每個結點僅被訪問一次。 3 3二叉樹的遍歷可以分解為：訪問根，遍歷二叉樹的遍歷可以分解為：訪問根，遍歷左子左子樹和樹和遍歷遍歷右子樹，常用的三種遍歷算法：右子樹，常用的三種遍歷算法：先序先序遍歷、中序遍歷、后序遍歷；遍歷、中序遍歷、后序遍歷；5 查找 5.1 查找的基本概念查找的基本概念 查找（列）表：由同一類型的數據元素（或記錄）構成的查找（列）表：由同一類型的數據元素（或記錄）構成的集合，集合， 可利用任意數據結構實現。可利用任意數據結構實現。 關鍵字：關鍵字：數據元素的某個（幾個）數據項的值。如果一個數據元素的某個（幾個）數據項的值。如果一個數據項可以數據項可以唯一標

39、識列表中的一個數據元素唯一標識列表中的一個數據元素， 則稱其為關鍵則稱其為關鍵字。字。 查找：查找： 根據給定的關鍵字值，在特定的查找（列）表中根據給定的關鍵字值，在特定的查找（列）表中確定一個其關鍵字與給定值相同的數據元素，并返回該數據元確定一個其關鍵字與給定值相同的數據元素，并返回該數據元素在列表中的位置。素在列表中的位置。若找到相應的數據元素，若找到相應的數據元素， 稱查找成功，否則稱查找失敗稱查找成功，否則稱查找失敗 52 線性表的查找線性表的查找5.2.1 順序查找順序查找-最簡單的查找方法順序查找的基本思想順序查找的基本思想 從表的一端開始，順序掃描線性表，從表的一端開始，順序掃描

40、線性表，依次將掃描到的依次將掃描到的結點關鍵字和待找的值相比較，若相等，則查找成功，若結點關鍵字和待找的值相比較，若相等，則查找成功，若整個表掃描完畢，仍末找到關鍵字等于的元素，則查找失整個表掃描完畢，仍末找到關鍵字等于的元素，則查找失敗。敗。 順序查找既適用于順序表，也適用于鏈表。若用順序表，順序查找既適用于順序表，也適用于鏈表。若用順序表，查找可從前往后掃描，也可從后往前掃描，但若采用單鏈表，查找可從前往后掃描，也可從后往前掃描，但若采用單鏈表，則只能從前往后掃描。另外，順序查找的表中元素可以是無則只能從前往后掃描。另外，順序查找的表中元素可以是無序的。序的。順序查找算法的性能。順序查找算

41、法的性能。假設列表長度為假設列表長度為n，那么查找第，那么查找第i個數據個數據元素時需進行元素時需進行n-i+1次比較，即次比較，即Ci=n-i+1。又假設查找每個數據。又假設查找每個數據元素的概率相等，即元素的概率相等，即Pi=1/n， 則順序查找算法的平均查找長度則順序查找算法的平均查找長度為：為： niniiniiininnCnCPASL111) 1(21) 1(11順序查找的特點順序查找的特點 順序查找的順序查找的優點是算法簡單優點是算法簡單，對查找表結構無任何，對查找表結構無任何要求，無論是用向量還是用鏈表來存放結點，也無論結要求，無論是用向量還是用鏈表來存放結點，也無論結點之間是否

42、按關鍵字有序或無序排，它都同樣適用。點之間是否按關鍵字有序或無序排，它都同樣適用。順序查找的缺點是順序查找的缺點是查找效率低查找效率低，當，當 n 較大時，不較大時，不宜采用順序查找宜采用順序查找。 5.2.2二分二分查找（折半查找）查找（折半查找）1.二分查找的基本思想二分查找的基本思想高效率的查找方法。要求表中元素按關鍵字有序高效率的查找方法。要求表中元素按關鍵字有序(升序或降序升序或降序)。假設表中元素為升序排列。假設表中元素為升序排列。二分查找的基本思想是：二分查找的基本思想是：首先將表首先將表中間位置記錄的關鍵字與查找關鍵字中間位置記錄的關鍵字與查找關鍵字比較，比較，如果兩者相等，則

43、查找成功；如果兩者相等，則查找成功；否則利用中間位置記錄否則利用中間位置記錄將表分成前、后兩個子表，將表分成前、后兩個子表， 如果中間位置記錄的關鍵字大于查找關鍵字，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查則進一步查找前一子表，否則進一步查找后一子表。找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。成功，或直到子表不存在為止，此時查找不成功。例如，假設給定有序表中關鍵字為：例如，假設給定有序表中關鍵字為：05,13,19,21,37,56,64,74,80,88,9

44、2，查找，查找K=21的情況：的情況： 05 13 19 21 37 56 64 74 80 88 92 low hig (a) 初初始始情情形形 0 1 2 3 4 5 6 7 8 9 10 05 13 19 21 37 56 64 74 80 88 92 low hig mid (b) 經經過過一一次次比比較較后后的的情情形形 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 05 13 19 21 37 56 64 74 80 88 92 (c ) 經經過過二二次次比比較較后后的的情情形形 (arraymid.key=19) low mid hi

45、g 圖圖 6-1 查查找找 K=21 的的示示意意圖圖 05 13 19 21 37 56 64 74 80 88 92 (d ) 經經過過三三次次比比較較后后的的情情形形 (arraymid.key=21) mid low hig 圖圖 6-1 查查找找 K=21 的的示示意意圖圖 (查查找找成成功功) 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 103.二分查找的性能分析 二分查找的過程可以用二叉樹來描述。把當前查找區間的二分查找的過程可以用二叉樹來描述。把當前查找區間的中點作為根結點，左子區間和右子區間分別作為根的左子中點作為根結點，左子區間和右

46、子區間分別作為根的左子樹和右子樹，左子區間和右子區間再按類似的方法，由此樹和右子樹，左子區間和右子區間再按類似的方法，由此得到的二叉樹稱為二分查找的判定樹。得到的二叉樹稱為二分查找的判定樹。例如，給定的關鍵字序列例如，給定的關鍵字序列05,13,19,21,37,56,64,74,80,88,92，的判定樹。的判定樹。 0 1 2 3 4 5 6 7 8 9 10 4 0 3 2 7 6 5 8 9 1 0 圖圖6 -3 具具 有有11 個個 關關 鍵鍵 字字 序序 列列 的的 二二 分分 查查 找找 判判 定定 樹樹 1 在長度為在長度為n n的有序線性表中進行二分查找。的有序線性表中進行二

47、分查找。最壞的情況下，需要的比較次數為最壞的情況下，需要的比較次數為 loglog2 2n n 6 排序 61 基本概念基本概念 6.1.1 排序定義排序定義 排序就是把一組記錄（元素）按照某個域的值的遞增或遞減的排序就是把一組記錄（元素）按照某個域的值的遞增或遞減的次序重新排列的過程。次序重新排列的過程。(按學號的遞增按學號的遞增)表7-1 學生檔案表學號學號姓名姓名年齡年齡性別性別99001王曉佳王曉佳18男男99002林一鵬林一鵬19男男99003謝寧謝寧17女女99004張麗娟張麗娟18女女99005周濤周濤20男男99006李小燕李小燕16女女為討論方便，我們直接將排序碼寫成一個一維

48、數組的形式，并且在沒有聲明的情形下，所有排序都按排序碼的值遞增排列。 排序排序 插入排序（直插排序、希爾排序）插入排序（直插排序、希爾排序） 交換排序（冒泡排序、快速排序）交換排序（冒泡排序、快速排序） 選擇排序選擇排序 （直選排序、堆排序）（直選排序、堆排序） 歸并排序（二路歸并排序）歸并排序（二路歸并排序） 62 插入排序插入排序 6.2.1直接插入排序1直接插入排序（Straight Insertion Sorting）基本思想：把基本思想：把n個待排序的元素看成一個有序表和一個無序表，個待排序的元素看成一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有開始時有序表中只

49、包含一個元素，無序表中包含有n-1個元素，個元素，排序過程中每次從無序表中取出第一個元素，把它的排序碼排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，將它插入到有序表中依次與有序表元素的排序碼進行比較，將它插入到有序表中的適當位置，使之成為新的有序表。的適當位置，使之成為新的有序表。例如，n=6，數組R的六個排序碼分別為：17，3，25，14，20，9。它的直接插入排序的執行過程如圖7-1所示。 0 1 2 3 4 5 初始狀態 (17 ) 3 25 14 20 9 第一次插入 (3 17 ) 25 14 20 9 第二次插入 (3 17 25 ) 14

50、20 9 第三次插入 (3 14 17 25 ) 20 9 第四次插入 (3 14 17 20 25 ) 9 第五次插入 (3 9 14 17 20 25) 圖 7-1 直接插入排序示例 3直接插入排序的效率分析直接插入排序的效率分析直接插入排序算法十分簡單。直接插入排序算法十分簡單。空間空間:只需要一個元素的輔助空間，用于元素的位置交換只需要一個元素的輔助空間，用于元素的位置交換。時間時間:外層循環要進行外層循環要進行n-1次插入，每次插入最少比較一次次插入，每次插入最少比較一次（正序），移動兩次；最多比較（正序），移動兩次；最多比較i次，移動次，移動i2次（逆序）次（逆序）（i=1，2，n

51、-1）。）。直接插入排序的時間復雜度為直接插入排序的時間復雜度為O（n2）。）。最壞情況比較最壞情況比較n(n-1)/26.2.2希爾排序希爾排序希爾排序希爾排序(縮小增量排序縮小增量排序):1959年由年由D.L.Shell提出來的。提出來的。基本思想：先將整個待排元素序列分割成若干個子序列（由基本思想：先將整個待排元素序列分割成若干個子序列（由 “增量增量”確定）分別進行直接插入排序，待整個序列中的元素確定）分別進行直接插入排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序

52、的情況下（接近最好排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的。情況），效率是很高的。例如，n=8，數組array 的八個元素分別為：91，67，35，62，29，72，46，57。下面用圖7-2給出希爾排序算法的執行過程。 91 67 35 62 29 72 46 57 初始狀態， setp=4 29 57 35 62 46 67 91 72 第二趟結果，step=1 29 35 46 57 62 67 72 91 第三趟結果 29 67 35 57 91 72 46 62 第一趟結果,step=2 圖 7-2 希爾排序算法的執行過程 希爾排序的效率分析希爾排序

53、的效率分析與增量有關，與增量有關，最壞情況，希爾排序的時間復雜性在最壞情況，希爾排序的時間復雜性在O（nlog2n）。）。63 交換排序交換排序6.3.1 冒泡排序冒泡排序基本思想:對待排序序列從后向前（從下標較大的元素開始），對待排序序列從后向前（從下標較大的元素開始），依次比較相鄰元素的排序碼，若發現逆序則交換，使排序碼依次比較相鄰元素的排序碼，若發現逆序則交換，使排序碼較小的元素逐漸從后部移向前部，就象水底下的氣泡一樣逐較小的元素逐漸從后部移向前部，就象水底下的氣泡一樣逐漸向上冒。漸向上冒。例如，例如，n=6，數組，數組R的六個排序碼分別為：的六個排序碼分別為：17，3，25，14，20

54、，9。下面用圖。下面用圖7-3給出冒泡排序算法的執行過程。給出冒泡排序算法的執行過程。 圖 7-3 冒泡排序示例 0 1 2 3 4 5 第一趟排序 3 (17 9 25 14 20) 第二趟排序 3 9 (17 14 25 20) 第三趟排序 3 9 14 (17 20 25) 第四趟排序 3 9 14 17 20 25 初始狀態 （17 3 25 14 20 9) 冒泡排序的效率分析冒泡排序的效率分析若待排序的元素為正序，則只需進行一趟排序，比較次數為若待排序的元素為正序，則只需進行一趟排序，比較次數為（n-1）次，移動元素次數為）次，移動元素次數為0；若待排序的元素為逆序，則需進行若待排

55、序的元素為逆序，則需進行n-1趟排序，比較次數為趟排序，比較次數為(n2-n)/2，移動次數為，移動次數為3(n2-n )/2，最壞情況比較最壞情況比較n(n-1)/2因此冒泡排序算法的時間復雜度為因此冒泡排序算法的時間復雜度為O（n2）。由于其中的元）。由于其中的元素移動較多，所以屬于內排序中速度較慢的一種。素移動較多，所以屬于內排序中速度較慢的一種。6.3.2 快速排序快速排序基本思想是：取待排序序列中的某個元素（一般第一個元素）基本思想是：取待排序序列中的某個元素（一般第一個元素）作為基準，通過一趟排序，將待排元素分為左右兩個子序列，作為基準，通過一趟排序，將待排元素分為左右兩個子序列，

56、左子序列元素的排序碼均小于或等于基準元素的排序碼，左子序列元素的排序碼均小于或等于基準元素的排序碼，右子序列的排序碼則大于基準元素的排序碼，右子序列的排序碼則大于基準元素的排序碼，然后分別對兩個子序列繼續進行然后分別對兩個子序列繼續進行快速快速排序，直至整個序列有序。排序，直至整個序列有序。元素的比較和交換是從兩端向中間進行的，排序碼較大的元素元素的比較和交換是從兩端向中間進行的，排序碼較大的元素一次就能夠交換到后面，排序碼較小的記錄一次就能夠交換到一次就能夠交換到后面，排序碼較小的記錄一次就能夠交換到前面，記錄每次移動的距離較遠，因而總的比較和移動次數較前面，記錄每次移動的距離較遠，因而總的

57、比較和移動次數較少。少。 例如，給定排序碼為：（46，55，13，42，94，05，17，70），具體劃分如圖7-4所示。 4 6 5 5 1 3 4 2 9 4 0 5 1 7 7 0 i j 4 6 5 5 1 3 4 2 9 4 0 5 1 7 7 0 i j 1 7 5 5 1 3 4 2 9 4 0 5 4 6 7 0 i j 1 7 4 6 1 3 4 2 9 4 0 5 5 5 7 0 i j 1 7 0 5 1 3 4 2 9 4 4 6 5 5 7 0 i j 1 7 0 5 1 3 4 2 9 4 4 6 5 5 7 0 i j 1 7 0 5 1 3 4 2 9 4 4

58、6 5 5 7 0 i j 1 7 0 5 1 3 4 2 4 6 9 4 5 5 7 0 i j 圖7 - 4 快 速 排 序 的 一 次 劃 分 3快速排序的效率分析快速排序的效率分析若快速排序出現最好的情形（左、右子區間的長度大致相若快速排序出現最好的情形（左、右子區間的長度大致相等），則結點數等），則結點數n與二叉樹深度與二叉樹深度h應滿足應滿足log2nhlog2n+1 ，所，所以總的比較次數不會超過以總的比較次數不會超過(n+1) log2n。因此，。因此，快速排序的最快速排序的最好時間復雜度應為好時間復雜度應為O（nlog2n）。）。已經證明，快速排序的平均時間復雜度也為O（nl

59、og2n）。若快速排序出現最壞的情形（每次能劃分成兩個子區間，但若快速排序出現最壞的情形（每次能劃分成兩個子區間，但其中一個是空），則這時得到的二叉樹是一棵單分枝樹，總其中一個是空），則這時得到的二叉樹是一棵單分枝樹，總的比較次數為的比較次數為n(n-1)/2 。因此，。因此，快速排序的最壞時間復雜度為O(n2)。快速排序所占用的輔助空間為棧的深度，故最好的空間復雜度為O（log2n），最壞的空間復雜度為O(n)。快速排序是一種不穩定的排序方法。 64 選擇排序選擇排序 6 . 4.1 直接選擇排序基本思想基本思想直接選擇排序是一種簡單的排序方法。基本思想是：第一次直接選擇排序是一種簡單的排序

60、方法。基本思想是：第一次從從array0arrayn-1中選取最小值，與中選取最小值，與array0交換，第二交換，第二次從次從array1arrayn-1中選取最小值，與中選取最小值，與array1交換，第交換，第三次從三次從array2arrayn-1中選取最小值，與中選取最小值，與array2交交換，換，第，第i次從次從arrayi-1arrayn-1中選取最小值，與中選取最小值，與arrayi-1交換，交換，, 第第n-1次從次從arrayn-2arrayn-1中選取最中選取最小值，與小值，與arrayn-2交換，總共通過交換，總共通過n-1次，得到一個按排序次，得到一個按排序碼從小到