1、21世紀高等院校規劃教材數據結構（C語言描述）第一章 學習數據結構課程的意義學習重點掌握學習本課程的意義掌握本課程的主體框架和討論范圍掌握如何對算法進行描述和分析引入： 一般情況下，用計算機解決一個實際問題時，都是先對具體問題抽象，建立問題的求解模型，然后設計相應的算法，編寫程序并上機調試，最后解決問題。 1.1 實例：高校選修課程管理1.2 數據結構的主要內容1.3 算法和算法分析本章總結1.1 實例：高校選修課程管理1.1.1 問題描述1.1.2 問題的分析1.1.3 學習本課程的意義1.1.1 問題描述 表1-1是一所學校學生選修課程的選修情況登記表。要求用計算機來完成對學生選修課程的全

2、程管理。 通常必備的功能有登記，修改、查詢和打印等。在本例中重點完成查詢功能。 學號姓名系別選修課程名學分成績課程名課程代碼等級分數0351103王杰計算機攝影技術50130351212李麗計算機電腦音樂50210351220商立計算機攝影技術50130432233趙燕機械三維動畫30320432118張欣機械三維動畫30320322140王芳材料證券投資2053表1-1 某學校學生選修課程情況登記表 1.1.2 問題的分析 利用計算機解決實際問題的步驟：第一步：從具體問題抽象出一個適當的數據模型。 第二步：進行算法設計。 第三步：實現抽象數據類型定義，即從編程語言的角度確定抽象數據類型的存儲

3、形式和確定抽象數據類型中每一種操作的具體實現算法。 第四步：編制相應的程序代碼并進行調試。 第一步：抽象數據模型一般包括三部分：處理的數據對象、對象間的關系和需要實現的操作。常用以下格式描述：ADT 選修課程 數據對象：D=ai | ai記錄類型，i=1,2,n , n0 數據關系：R=Ri | Ri記錄間關系，i=1,2,m , m0 基本操作： DengjiList ( &L) 完成功能：對學生選修情況進行登記 EditList(&L) 完成功能：對選修情況登記表進行修改 LocateList(&L,查詢條件) 完成功能：根據給定的查詢條件，從登記表中查找滿足條件的記錄 PrintList

4、(L) 完成功能：打印學生選修情況登記表 ADT選修課程第二步：根據上面給定的抽象數據類型定義，寫出實現各種操作的算法描述。下面以查詢操作為例給出偽代碼表示：int LocateList( 選修課程 &L, 查詢條件) 對給定的查詢條件進行分析，確定是對表中哪個數據項進行查詢； 對表中元素按給定的查詢條件進行查詢； 若查詢成功，返回記錄的位置；否則返回0值，表示表中不存在滿足給定條件的記錄；第三步：確定表中的記錄的類型（結構體），表在內存中存儲方式（按輸入順序存放）。具體定義如下：struct kechengsrtuct /選修課程名類型定義char *kechengming ; / 課程名i

5、nt kechengdaima ; / 課程代碼 ;struct chengjistruct / 成績類型定義char *dengji ; / 成績等級int fenshu ; / 分數 ;struct student / 表中學生記錄類型定義long int num ; / 學號char *name ; / 姓名char *xibie ; / 系別kechengstruct kechent ;int xuefen ; / 學分chengjistruct chengji ; ;表在內存中的存儲類型定義：struct sqlist student *A ; / 將記錄順序存放在一個一維數組中in

6、t len ; / 表中記錄的個數 ; 結論： 數據結構的實質就是一門研究非數值計算問題的程序設計中計算機的操作對象以及它們之間的關系和運算操作的一門學科。 1.1.3 學習本課程的意義 數據結構作為一門獨立的課程在國外是從1968年開始設立的 。瑞士著名計算機科學家N.Wirth提出的著名公式“程序=算法+數據結構”。數據結構是一門介于數學、計算機硬件和軟件三者之間的核心課程。 用一句話概括：本課程就是從實際問題抽象出數據類型的手段。主要研究計算機所處理的數據對象、對象間存在的關系及進行的各種操作。 1.2 數據結構的主要內容 1.2.1 基本概念和術語 1.2.2 數據結構定義 1.2.3

7、 邏輯結構的表示方法 1.2.1 基本概念和術語 數據是對客觀事物的符號表示，是一種信息的載體，是所有能輸入到計算機中并被識別、存儲和加以處理的信息的總稱。 數據元素是數據的基本單位。一個數據元素也可以由若干個數據項組成 。數據對象是性質相同的數據元素的集合，是數據的一個子集。 數據類型是對計算機中表示的數據對象、對象特征及該數據對象上的一組操作的描述。抽象數據類型是指一個數學模型及定義在該數學模型上的一組操作。定義取決于它的邏輯特性，與其在計算機內部如何表示（存儲）和實現無關。 1.2.2 數據結構定義 數據結構是指相互間存在一種或多種特定關系的數據元素的集合。 數據具有相同屬性的數據元素的

8、集合； 結構數據元素間存在的一種或多種關系。對一個給定的數據結構進行分析時，一般從它的邏輯結構、存儲結構及對數據元素所進行的操作三個方面進行討論。（本課程的主要討論點） 邏輯結構是對給定數據結構的一種描述方式，是從實際問題抽象出來的數據模型。主要描述數據元素，及元素之間存在的邏輯關系。 通常按元素間存在的邏輯關系的不同特征，將數據結構分為四類： 集合結構 線性結構 樹型結構 圖型結構集合結構：數據元素之間除了同屬于一個集合之外，沒有其他關系的數據結構。例子：從大街上隨意的找五個人組成一個小組，編號分別為1、2、3、4、5，則這五個人之間除了屬于同一組以外，相互間不存在任何的關系。 組成集合的數

9、據元素之間不存在任何的關系線性結構：數據元素之間存在“一對一”線性關系的數據結構。學號姓名系別學分0351103王杰計算機30351212李麗計算機1例：學生基本情況登記表中每條學生記錄都按一定的順序排列，除了第一條和最后一條以外，每條記錄都只有唯一的前驅和后繼元素。元素之間是1：1關系，都只有唯一的前驅和唯一的后繼樹型結構：數據元素之間存在“一對多”邏輯關系的數據結構。例：一個大學的人事檔案管理。每個系有多個專業，但一個專業只能屬于一個系；一個專業有多名學生，但一個學生只能屬于一個專業元素之間的關系是1：n，每個元素都只有唯一的前驅元素，但可以有多個后繼元素圖型結構：數據元素之間存在“多對多

10、”邏輯關系的數據結構。例：五個城市間的交通圖。從1可以直達5，也可以經過2、3到達5，或也可以經過2、4到5。元素之間的關系是m:n，每個元素都可以有多個前驅元素和多個后繼元素 存儲結構又稱物理結構，就是數據結構在計算機中的存儲方式。它包括數據元素在計算機中的存儲方式，還包括元素之間關系在內存中的表示。 根據存儲空間的不同分配方式將數據結構分為兩類： 順序存儲 鏈式存儲第一方面第二方面 順序存儲：所有元素存放在一片連續的存儲空間中，邏輯上相鄰的元素在內存中的物理位置也是相鄰的。 注意：元素存放在連續的存儲空間中，元素之間的邏輯關系由在內存中的物理位置來體現。 例：對一個由（1，2，3，4，5）

11、五個元素組成的數據結構采用順序存儲，則內存中的存儲示意圖如下所示：元素1元素2元素3元素4元素5起始地址 鏈式存儲：所有元素存放在可以不連續的存儲單元中，以結點的形式存在，每個結點除了保存數據元素信息外，還通過指針來保存元素之間的關系。 注意：既元素存儲在不連續的存儲單元中，元素間的關系通過結點中的指針信息來體現。 元素1元素4元素3元素2例：對一個由（1，2，3，4）四個元素組成的數據結構采用鏈式存儲，則內存中的存儲示意圖如下所示：1.2.3 邏輯結構的表示方法 二元組表示法表示形式為： D=（K，R）其中，K=a1 , a2 , , an ，為數據元素的集合 R=r1 , r2 , , r

12、 m ，為元素之間關系的集合 r1= | 其中，x,yK 序偶表示：元素x和元素y之間存在關系，并且稱元素x為元素y的前驅，元素y為元素x的后繼。如果元素x既是元素y的前驅，也是元素y的后繼，既且，則用（x,y）形式表示。圖形表示法 用圓圈來代表數據元素，用帶箭頭的連線來表示元素之間的關系，如圖所示。二元組表示法：D1=( K , R ) 其中，K=a,b,c,d,e R=r r = , , , 1.3 算法和算法分析 1.3.1 算法定義 1.3.2 算法分析 1.3.1 算法定義 算法是對特定問題求解步驟的一種描述，是一組指令的有限序列，其中每一條指令都代表解題過程中的一個或者多個操作。算

13、法特點： 有窮性、確定性、可行性、輸入、輸出算法描述可以有多種方式，如：用流程圖描述、用自然語言描述、還可用數學語言或特定的符號進行描述。本書中所有算法都是用C語言來進行描述 。1.3.2 算法分析 算法的設計要求如下： 正確性 可讀性 健壯性 效率與低存儲量的需求 其中，效率指的是算法執行的時間。存儲量需求指的是算法執行過程中所需要的最大存儲空間，通常主要考慮算法所需的輔助存儲空間。 這四個設計要求中最主要的是算法的執行時間和執行時所占的存儲空間大小。 算法的執行時間是指一個算法在計算機上運行時所花費的時間。 =簡單操作所需要的時間簡單操作的次數影響算法執行時間的兩個因素： （1）每個簡單操

14、作執行時所需時間與機器有關，而與算法無關。討論算法中包含的簡單操作的執行次數。 （2）另外一個與算法的執行時間相關的是問題的規模。 通常算法的執行時間用時間復雜度表示： T(n) = O( f ( n ) ) 其中，n為問題的規模 T（n）為時間復雜度 此式子表示，隨著問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同。所以只要求出簡單操作的次數關于n的增長率即可，然后用n的最高數量級來表示算法的時間復雜度。 例： for (j=1;j=n;j+) for (k=1;k=m;k+) +x; s+=x; 分析：各個簡單操作的執行次數如下所示：for (j=1;j=n;j+)/次數為1+

15、（n+1）+nfor (k=1;k=n;k+) /執行次數為（1+（n+1）+n）n +x; /執行次數為n*n s+=x; /執行次數為n*n 簡單操作的執行次數之和為：4n2+4n+2，用n的最高數量級表示，時間復雜度為：O（n2）。衡量一個算法性能的另一個標準就是算法執行時所占的存儲空間的大小。一般一個算法所占的存儲空間包括存儲算法所占用的存儲空間、算法的輸入/輸出數據所占用的存儲空間和程序運行過程中臨時占用的存儲空間這三個方面。其中，只有算法執行過程中所占的臨時空間與算法有著密切關系。 通常一個算法在執行過程中所占用的臨時存儲空間的大小由空間復雜度來衡量，記作： S（n）= O（f（n

16、） 其中，n為問題的規模；S（n）為空間復雜度。通常用n的最高數量級來表示。 本章總結：本章介紹了學習數據結構課程的意義、本課程的主題框架及相關內容和如何對算法進行評價。 數據結構主要研究計算機所處理的數據對象、對象之間存在的各種關系及進行的各種操作，是用計算機來解決實際問題與編寫相應程序兩者之間的紐帶。數據結構從定義上可以理解為數據+結構。其中，數據指的是所要處理的若干個數據元素的集合；結構指的是數據元素之間的關系。按邏輯結構可分為集合結構、線性結構、樹型結構和圖型結構四種。按存儲結構可分為順序存儲和鏈式存儲兩種。 算法是解決問題步驟的一種描述，它有有窮性、確定性、可行性、輸入和輸出等五個特

17、點。 一個好的算法應該滿足正確性、可讀性、健壯性和效率與低存儲量需求等四個要求，其中算法的執行效率和低存儲量需求是衡量一個算法的最主要的標準。通常用時間復雜度來衡量算法的執行時間，用空間復雜度來衡量算法執行過程中所占用的臨時存儲空間的大小。它們都是問題的規模n的一個函數，所以用n的最高數量級來表示。 第5章 數組數組的基本概念和存儲結構稀疏矩陣的定義、表示方法、存儲結構及基本操作的實現算法特殊矩陣的存儲廣義表的定義、鏈式存儲結構，以及相應操作的實現算法。 第5章 數組 5.1 數組 5.2 數學中的應用 5.3 廣義表 本章總結5.1 數組 5.1.1 一維數組 5.1.2 多維數組 5.1.

18、1 一維數組 一維數組在數組結構中可以看成是一個線性表或一個向量，通常分配一塊連續的存儲單元。在C語言中，一維數組a n 的存儲單元是從a 0 至an1的一塊連續的存儲空間，設a 0 的存儲地址LOC（a 0 ），數據元素所占的存儲單元為k個字節，則任一元素a i 的首字節地址LOC（a i ）： LOC（a i ）= LOC（a 0 ）+ i * k (0in) 5.1.2 多維數組 多維數組的定義：1 行向量形式Amn=A，則A = （a0，a1，ai，am1）一維數組其中，aj =（aj, 0，aj, 1，aj, n-1）（0jm）是一個行向量形式的線性表。就是以行序為主序的存儲方式。

19、2 列向量形式Amn=A，則A = （a0，a1，ai，an1），其中，ap =（a0, p，a1, p，am-1, p）(0pn)是一個列向量形式的線性表，如式子（5-3）所示。是以列序為主序的存儲結構。 數組的存儲結構 對于二維數組來說，設數組的第一個元素a0, 0的地址LOC（a0, 0），每個元素所占的存儲單元為k，則二維數組中任一元素ai，j的存儲地址：LOC（ai , j）= LOC（a0 , 0）+（i * nj）* k n為列數 n維數組ad1d2 dn的數據元素存儲位置的計算公式：5.2 數學中的應用 5.2.1 稀疏矩陣 5.2.2 特殊矩陣 5.2.1 稀疏矩陣 稀疏矩陣

20、的概念 稀疏矩陣的三元組線性表表示 稀疏矩陣的順序存儲方式 稀疏矩陣的鏈式存儲方式 稀疏矩陣各種操作的實現 稀疏矩陣的概念： 在一個階數較大的矩陣中非零元素個數s相對于矩陣元素的總個數t非常小，即 s sublist)+1 其它情況 實現算法： （略） 時間復雜度為O（n），其中n為廣義表中所有結點的個數。該算法的空間復雜度為O（m），m為廣義表的深度。建立廣義表 分析：建立廣義表過程可以通過遞歸實現。將廣義表分解成表頭和表尾，而表頭和表尾若仍是廣義表，則繼續分解為表頭和表尾。創建過程就是建立表頭和建立表尾。 區分表頭和表尾中的元素是單元素還是表元素的方法： （1）如果 i為“（）”，表示這是

21、一個空的表元素，字符串長度為2； （2）如果 i長度為1，表明它是一個單元素； （3）如果長度1，這是一個表元素。 前兩種情況就可作為遞歸過程的結束條件。 實現算法： （略） 時間復雜度和空間復雜度：0（n），n廣義表中字符個數輸出廣義表 分析：設GL為表頭指針，則輸出時，需要對子表進行遞歸調用。當GL結點為表結點時，應首先輸出作為一個表的起始符號“（”。然后再輸出以sublist為表頭指針的表；當GL結點為原子結點時，則應輸出該元素的值。當以sublist為表頭指針的表輸出結束后，應在其最后輸出一個作為表終止符的“）”。當GL結點輸出結束后，若存在后繼結點，則應首先輸出一個逗號作為分隔符，然

22、后再遞歸輸出由next指針所指向的后繼表。 實現算法： （略） 時間復雜度和空間復雜度：0（n），n廣義表中結點個數。本章總結： 一維數組在內存中開辟一塊連續的存儲單元存儲數據，適合于隨機查找。多維數組可以看成是一維數組的推廣，也是一個線性表，表中的每個數據元素本身也是一個線性表。 稀疏矩陣是指非零元素個數相對于矩陣元素的總個數十分小的矩陣。稀疏矩陣的存儲方法有三種：第一種是三元組表示法，第二種是行邏輯鏈式存儲，第三種是十字鏈式存儲。稀疏矩陣的基本操作有五種，都采用了順序存儲方式。 特殊矩陣是指非零元素或零元素的分布有一定規律的矩陣。為了節省存儲空間可以對特殊矩陣進行壓縮存儲。 廣義表的元素分

23、為原子和子表，是一種遞歸結構。表中所含元素的個數稱為長度。表中括號嵌套的最大次數稱為深度。常用的基本操作有求廣義表的長度、深度、創建和輸出廣義表等，操作的共同點是都通過遞歸實現。 第6章 樹 學習重點：樹和二叉樹的概念、性質和相互間的轉換方法樹和二叉樹的遍歷方法和實現算法哈夫曼樹、線索二叉樹和二叉排序樹的構造方法與應用 第6章 樹 6.1 實例1：文件目錄管理 6.2 樹的邏輯結構6.3 樹的遍歷 6.4 實例2：通信中電文編碼 6.5 二叉樹定義、存儲結構 6.6 二叉樹遍歷 6.7 樹與二叉樹的轉換 6.8 應用舉例 本章總結 6.1 實例1：文件目錄管理 6.1.1 問題描述 6.1.2

24、 問題的分析 6.1.3 實現算法6.1.1 問題描述 在操作系統中對文件進行訪問時提供按名存取機制，只需給出文件名，就可以訪問到相應的文件，而無需知道文件的存儲位置。 如何實現按名存取機制呢？ 6.1.2 問題的分析 文件系統將這些說明部分的全部信息集中起來構成文件控制塊（FCB），文件目錄由文件控制塊組成。再將所有的文件目錄組合在一起構成一個目錄文件，目錄文件以樹型目錄結構存儲。樹型目錄結構中文件目錄的第一級系統目錄為樹的根結點，定義為根目錄，文件目錄的第二級和以下各級目錄均為樹的分支結點（非終結點），均定義為子目錄，只有樹的葉子結點（終結點）才為文件。所以實現文件的按名存取，就是從目錄結

25、構的根目錄開始直到所要找的文件為止 。6.1.3 實現算法 實現算法：（略）結論： 文件目錄結構是一種樹型結構，目錄樹中的根目錄是樹的根結點，根目錄下各級子目錄和文件是樹的其余結點。對處在同一層的各個子目錄和文件進行比較可以發現各個子目錄和文件都只有一個共同的上一級目錄，而同一層的各個子目錄可以有任意多個下級子目錄和文件。 文件目錄結構中的各個目錄和文件都滿足樹型結構的特征。 6.2 樹的邏輯結構6.2.1 樹的邏輯結構 6.2.2 樹的相關術語 6.2.1 樹的邏輯結構 樹或者是一棵空樹，或者是一棵非空樹。一棵非空樹由n（n0）個結點來組成。它滿足以下條件： l有且僅有一個根結點，它沒有前驅

26、結點 l其余結點構成m(m=0)棵互不相交的樹，稱為該樹的子樹。每棵子樹又是一棵樹（遞歸定義）。 邏輯結構：一棵樹由若干個結點組成，元素以結點的形式存在；關系：樹的各個結點間是一對多的關系，即除根結點外，所有結點有且僅有一個前驅結點，所有結點或者沒有后繼結點，或者有任意多個后繼結點。6.2.2 樹的相關術語 根結點：唯一沒有前驅的結點。所有非空樹，都有唯一的一個根結點。 結點的度：結點所擁有的子樹的個數，或者結點所擁有的后繼結點的個數。樹的度是指樹中所有結點的度的最大值。 終端結點（葉子結點）：度為0的結點，或者樹中沒有后繼的結點。 非終端結點（分支結點）：度不為0的結點，或者指有后繼的結點。

27、 父結點、孩子結點：對一個結點來講，它的前驅結點是它的父結點（雙親結點）；它的后繼結點是它的孩子結點（子結點）。兄弟結點是指父結點相同的結點，即前驅結點是相同的結點。結點的深度是指該結點在樹中所處的層數，根結點所在的層為第一層。樹的深度是指樹中結點的最大層次數。有序樹是指構成樹的各子樹，從左到右有一定順序，不能互相交換的樹。無序樹是指構成樹的各子樹是無順序的，可以互相交換的樹。森林是指若干棵互不相交的樹。 6.3 樹的遍歷 6.3.1 先根遍歷 6.3.2 后根遍歷 6.3.3 按層遍歷 樹的遍歷指的是按照某一種順序訪問樹中的所有結點，并且每個結點只訪問一次。 樹的遍歷順序：先根遍歷（先序遍歷

28、）、后根遍歷（后序遍歷）和按層遍歷。6.3.1 先根遍歷先根遍歷指如果樹非空，則按下列規則進行遍歷： l 先訪問樹的根結點。 l從左到右訪問根結點的所有子樹。 l對子樹也按先根遍歷順序來訪問所有的結點。 6.3.2 后根遍歷后根遍歷指如果樹非空，則按下列規則進行遍歷： l 先從左到右訪問根結點的所有子樹。 l 后訪問樹的根結點。 l 對子樹也按后根遍歷順序來訪問所有的結點。 6.3.3 按層遍歷按層遍歷指如果樹非空，則按下列規則進行遍歷： l 從第一層開始，從上到下順序遍歷各層，同一層從左到右訪問各個結點。 l 樹的根結點所在層定義為第一層，依次類推。 6.4 實例2：通信中電文編碼 6.4.

29、1 問題的描述 6.4.2 問題的分析 6.4.3 實現算法 6.4.1 問題的描述 在電信科技日新月異的今天，人們早已淡忘了，曾經風靡一時的電報。電報的原文發送時，都按一定的規則翻譯成編碼，以編碼的形式傳送。收到的電文中，每個文字的下面都會有一個數字編碼。下面介紹的也是一種電報的編碼方法：發送的電文翻譯成0和1的數字序列。 6.4.2 問題的分析 電報主要依靠將傳送的文字轉換成由二進制數組成的字符串進行傳送。第一種解決方法：將所有傳送的文字都轉換成等長的二進制字符串來傳送，接收者只需按等長進行譯碼。第二種解決方法：對電文中出現的字符設計長度不等的字符編碼，對電文中出現次數比較多的字符采用盡可

30、能短的字符編碼，則傳送的信息的長度就可以減少了。 前綴編碼（哈夫曼編碼）：每個字符的編碼都不是另一個字符的編碼的前綴。 構造字符哈夫曼編碼的方法： 將每個字符按在代碼中出現的次數為出現頻率，構成一個頻率集合，然后畫一棵滿足以下條件的樹： l從頻率集合中，每次選擇出現頻率最小的兩個字符構成一棵樹，所構成樹的父結點的值等于這兩個字符的頻率之和。 l將選中的兩個字符的頻率從頻率集中刪除，并將它們的父結點加到頻率集合中。 重復上述兩個過程，直到頻率集合中只剩一個元素為止。 編碼規則：從樹的根結點起，左邊的孩子結點的編號為0，右邊的孩子結點的編號為1，對所有的子樹也按這個規則編碼。所畫的樹稱之為哈夫曼樹

31、，頻率稱之為權值。 6.4.3 實現算法 實現算法：（略）結論：哈夫曼樹的每個結點最多有兩個孩子結點，結點度的最大值為2，這種樹稱為二叉樹，兩個孩子結點分別稱為左孩子結點和右孩子結點。6.5 二叉樹定義、存儲結構 6.5.1 二叉樹的定義6.5.2 二叉樹的性質 6.5.3 二叉樹的存儲結構 6.5.1 二叉樹的定義 二叉樹定義（遞歸定義）： 或者是一棵空二叉樹，或者是一棵非空二叉樹。一棵非空二叉樹由n（n0）個結點組成。它滿足以下條件： l有且僅有一個根結點，它沒有前驅結點 l其余結點構成兩棵互不相交的子樹，稱為該樹的左子樹和右子樹。每棵子樹又是一棵二叉樹。 特點：每個結點最多只能有兩個孩子

32、結點，也就是說二叉樹中不存在度大于2的結點。 Root (BT) 求根結點。ParentBT(BT,elem) 求父結點。LchildBT(BT,elem)和RchildBT(BT,elem)求左、右孩子結點。CreateBT(BT,R,n)創建一棵二叉樹。DepthBT(BT)求層數。PreOrdetBT(BT)先根遍歷。InOrdetBT(BT)中根遍歷。PostOrdetBT(BT)后根遍歷。 LeverOrdetBT(BT)按層遍歷。二叉樹的基本操作：6.5.2 二叉樹的性質 性質1：如果計二叉樹的根結點所在層為第一層，則第k層的結點數最多為2 k-1個。 性質2：層數為k的二叉樹的最

33、大結點數為2 k-1個。 性質3：在一個二叉樹中，度為0的結點的個數為n0，度為2的結點的個數為n2，則n0=n2+1。性質4：具有n個結點的完全二叉樹的層數為： 或 。 滿二叉樹是指層數為k的有2 k-1個結點的二叉樹，既每層都保持它的最大結點數，每層結點都是滿的。 完全二叉樹是指如果一棵層數為k的n個結點的二叉樹的所有結點都與層數為k的滿二叉樹中編號為1 n的結點一一對應，則稱此二叉樹為完全二叉樹。 性質5：對一棵有n個結點的完全二叉樹來講，編號為i的結點滿足以下條件：（1）如果i=1，則結點i是根結點，無父結點；如果i1，則父結點的編號是 。（2）如果2in，則結點i沒有左孩子結點的葉子

34、結點；否則其左孩子結點的編號是2i。（3）如果2i+1n，則結點 i沒有右孩子結點；否則其右孩子結點的編號是2i+1 。 6.5.3 二叉樹的存儲結構 存在兩種存儲方式： 順序存儲方式 鏈式存儲方式 用一組連續的存儲空間來存放一棵二叉樹的所有結點。結點存放時對二叉樹中的所有結點都按滿二叉樹中結點編號來順序編號，將編號當成存儲結點的數組元素的下標來處理。順序存儲方式： 指存儲二叉樹中的全部結點信息及結點間的關系。結點間的關系通常有兩種：一種是左右孩子結點的關系，另一種是父結點的關系。 二叉鏈表存儲方式：每個結點除了存儲結點元素的信息外，還存儲該結點的左、右孩子結點的信息。（常用存儲方式） 三叉鏈

35、表存儲方式：在二叉鏈表的基礎上，在結點中再增加一個存放該結點的父結點信息的指針域。鏈式存儲方式：typedef struct Btnode Elemtype data ; / 存儲二叉樹結點元素的信息 Btnode *lchild ; / 存儲該結點的左孩子結點的信息 Btnode *rchild ; / 存儲該結點的右孩子結點的信息 BtTree ;二叉鏈表存儲的結點類型定義：6.6 二叉樹遍歷 6.6.1 先根遍歷 6.6.2 中根遍歷 6.6.3 后根遍歷 6.6.4 按層遍歷 6.6.5 二叉樹遍歷的應用 一棵二叉樹是由根結點、左子樹和右子樹組成，爭別用D、L和R表示，并要求左子樹在右

36、子樹前遍歷，則可得到DLR（先根遍歷）、LDR（中根遍歷）和LRD（后根遍歷）三種。除了這三種外，還可按結點所在層數進行遍歷，稱按層遍歷。 6.6.1 先根遍歷 先根遍歷（先序遍歷）定義： 若二叉樹為非空樹，則 l訪問二叉樹的根結點 l先根遍歷左子樹 l先根遍歷右子樹 分析：先根遍歷是一個遞歸過程，先遍歷根結點，后先根遍歷左、右子樹。對左、右子樹也是按先根遍歷。 先根遍歷的遞歸算法為：（二叉鏈表形式存儲） void PreOrdetBT( BtTree *BT ) if ( BT ) printf( “輸出格式串”，BT-data ) ; PreOrdetBT( BT-lchild ) ; P

37、reOrdetBT( BT-rchild ) ; 先根遍歷的遞歸算法 分析：二叉樹的先根遍歷從根結點開始，沿左子樹一直到左孩子為空為止。在整個過程中，訪問所遇到的結點，然后沿線往回返，每返回一個結點都去遍歷該結點的右子樹，直到遍歷完右子樹為止。在沿左子樹遍歷過程中，若左子樹為空，都要往上一個訪問結點返回（退棧）。所以需要存儲（進棧）遍歷過程中每個訪問到的結點（定義一個棧）。重復此過程，直到棧為空或指向結點的指針為空時停止。 先根遍歷的非遞歸算法為： （略）先根遍歷的非遞歸算法6.6.2 中根遍歷 中根遍歷（中序遍歷）的定義：若二叉樹為非空樹，則 l中根遍歷左子樹 l訪問二叉樹的根結點 l中根遍

38、歷右子樹中根遍歷的遞歸算法 分析：中根遍歷是一個遞歸過程，先中根遍歷左子樹，然后訪問根結點，最后中根遍歷右子樹。對左、右子樹也按中根遍。 中根遍歷的遞歸算法：（二叉鏈表形式存儲） void InOrdetBT( BtTree *BT ) if ( BT ) PreOrdetBT( BT-lchild ) ; printf( “輸出格式串”，BT-data )； PreOrdetBT( BT-rchild ) ; 中根遍歷的非遞歸算法 分析：中根遍歷是一個從二叉樹的根結點開始，沿左子樹一直到左孩子為空時，沿線往回返，每返回一個結點都先訪問該結點，然后去遍歷該結點的右子樹。在沿左子樹遍歷的過程中，

39、若左子樹為空，都要往上一個訪問結點返回，所以需要存儲遍歷過程中遇到的每個結點（設定一個棧）。沿左子樹遍歷時每遇到一個結點，就將該結點進棧，當左子樹為空時，從棧頂退棧一個結點，先訪問該結點，然后去訪問該結點的右孩子結點。重復此過程，直到棧為空或指向結點的指針為空時停止。 中根遍歷的非遞歸算法：（略） 6.6.3 后根遍歷 后根遍歷（后序遍歷 ）的定義：若二叉樹為非空樹，則 l 后根遍歷左子樹 l后根遍歷右子樹 l訪問二叉樹的根結點后根遍歷的遞歸算法 分析：后根遍歷過程是一個遞歸過程，先后根遍歷左、右子樹，后遍歷根結點。對左、右子樹也是先后根遍歷其左、右分支，后遍歷根結點。 后根遍歷的遞歸算法：（

40、二叉鏈表形式存儲） void PostOrdetBT( BtTree *BT ) if ( BT ) PreOrdetBT( BT-lchild ) ; PreOrdetBT( BT-rchild ) ; printf( “輸出格式串”，BT-data ) ; 后根遍歷的非遞歸算法 分析：后根遍歷過程從二叉樹的根結點開始，沿左子樹一直到左孩子為空停止，左孩子為空時，沿線往回返，每返回一個結點都先去遍歷該結點的右子樹，最后才訪問該結點。所以每個結點第一次出棧時，剛遍歷完該結點的左子樹，還需要將結點再次壓入棧中，等再次彈出時，已遍歷完該結點的右子樹，這時才可以訪問該結點。為了區分同一結點的兩次進棧

41、，可以引入一個標志棧，當從存放結點的棧中出棧一個結點時，從標志棧也要出棧一個元素，根據此元素的值來確定該結點是再次進棧，還是訪問該結點。 后根遍歷的非遞歸算法：（略） 6.6.4 按層遍歷 按層遍歷的定義：若二叉樹為非空樹，則 l先訪問根結點 l按從左到右的順序遍歷根結點的左、右孩子結點l 依次類推，由層數的從低到高，同層從左到右的順序遍歷所有結點 注意：二叉樹中定義根結點的層數為第一層 按層遍歷的非遞歸算法 分析：實現按層遍歷時就可以定義一個隊列來存放結點。整個按層遍歷的過程就從根結點開始，訪問完一個結點就讓該結點進隊，然后從隊列中出隊一個結點，去訪問該結點的左、右孩子結點，每訪問一個結點就

42、讓該結點進隊。直到隊列為空時停止。二叉樹以二叉鏈表形式存儲 。 按層遍歷的非遞歸算法：（略） 6.6.5 二叉樹遍歷的應用 例1：寫出圖6-9中給出的二叉樹的先根、中根、后根和按層遍歷的結點序列。解： 先根遍歷：ABDEKCFG中根遍歷：DBEKAFCG后根遍歷：DKEBFGCA按層遍歷：ABCDEFGK 已知：給定的先根遍歷結點序列為：ABDGHCEIJF，中根遍歷結點序列為：GDHBAEIJCF。 分析：對一棵二叉樹先根遍歷時，第一個訪問到的結點肯定是二叉樹的根結點，所以從先根遍歷的結點序列中可得知，二叉樹的根結點為A。中根遍歷先遍歷左子樹，然后遍歷根結點，最后遍歷右子樹，所以在結點序列中

43、確定根結點后，根結點前面的結點序列肯定是左子樹中結點的中根遍歷后的結果，而后面的是右子樹的中根遍歷后的所得結果。即可將二叉樹分成左子樹、根和右子樹三部分，依次類推。 解題過程：（略） 例2：根據給定的遍歷序列，畫出相應的二叉樹。6.7 樹與二叉樹的轉換 6.7.1 樹的存儲結構 6.7.2 樹與二叉樹的轉換 6.7.3 森林與二叉樹的轉換 6.7.1 樹的存儲結構 雙親表示法 孩子表示法 孩子雙親表示法 孩子兄弟表示法 雙親表示法： 實現：開辟一段連續的存儲單元來存放結點信息及該結點的雙親結點信息。通常定義一個一維數組存放結點的元素信息及雙親結點的信息。（順序存儲）雙親表示法的存儲類型定義為：

44、const int maxsize = 常數 ;struct node Elemtype data ; /存放樹中結點元素信息int parent ; /存放雙親結點在數組t中的下標 ; node t maxsize ; /存儲結點及雙親信息 孩子表示法： 實現：將每個結點的所有孩子結點鏈接成一個單鏈表，并將所有的單鏈表的表頭結點存放在一個一維數組。孩子表示法的存儲類型定義為：const maxsize = 常數 ; / 存儲空間的大小struct Link int child ; / 存放孩子結點在數組中的下標 Link *next ; / 指向該結點的下一個孩子結點的指針 ; / 單鏈表的

45、結點類型定義 struct node Elemtype data ; / 存儲樹中結點元素的信息 Link*next ; /指向該結點所有子結點組成的單鏈表的第一個結點 ; / 數組元素的類型定義node t maxsize ; / 用數組來存儲樹中結點的相關信息 孩子雙親表示法 ：實現：將孩子表示法和雙親表示法結合在一起就是孩子雙親表示法。孩子雙親表示法存儲類型定義：（略）孩子兄弟表示法： 實現：在孩子兄弟表示法中每個結點由三個域組成，除了存放結點信息的值域外，另外兩個指針域分別指向該結點的第一個孩子結點和與該結點相鄰的兄弟結點，是一種鏈式存儲方式。孩子兄弟表示法存儲類型定義：（略）6.7.

46、2 樹與二叉樹的轉換 將樹轉換為二叉樹的方法： l連線：將每個結點跟與它相鄰的右邊的兄弟結點用線連起來。 l 抹線：對所有結點，除了該結點的最左邊的孩子結點外，將該結點與其它孩子結點之間的連線全部刪除。 l 旋轉：將樹以根結點為重心，順時針方向旋轉大概45。角，把樹中的水平連線變成右分支，原有連線變成左分支。 將二叉樹還原為樹的方法： l 加線：對二叉樹中所有具有雙親結點的左孩子的右孩子，及右孩子的右孩子都與雙親結點連起來。 l 抹線：抹掉二叉樹中所有雙親結點與右孩子間的連線。 l 調整：以二叉樹的根結點作為樹的根結點，將其余結點的位置進行調整。 結論： 1 樹轉換成的二叉樹是一棵右子樹為空的

47、二叉樹。 2 二叉樹中每個結點的左孩子結點在原樹中是它的最左孩子結點，而右孩子結點是它的兄弟結點。 3 樹的孩子兄弟表示法其實就是將樹轉換成二叉樹的方法。 6.7.3 森林與二叉樹的轉換 森林轉換成二叉樹的方法： l 轉換：將組成森林的所有樹轉換成一棵棵二叉樹。 l 連線：將轉換成的所有二叉樹的根結點連起來。 l 旋轉：以第一棵樹的根結點為中心，按順時針方向旋轉所添加的所有的水平線和原有連線。 二叉樹轉換成森林的方法： l 抹線：抹掉二叉樹中根結點右鏈上的所有結點的連線，將二叉樹分成若干棵以右鏈上的結點為根結點的二叉樹。 l轉換：將分成的二叉樹轉換成樹。 l 調整：以樹的根結點為準，排列成一排

48、。 6.8 應用舉例 6.8.1 線索二叉樹 6.8.2 二叉排序樹 6.8.3 哈夫曼樹 6.8.4 二叉樹的綜合實例 6.8.1 線索二叉樹 線索二叉樹定義: 如果對一棵二叉樹用指針指出按某種方式遍歷時的結點的前驅和后繼信息，則稱指針為線索，而給出線索的二叉樹就稱為線索二叉樹，畫出線索的過程稱為線索化。 線索化二叉樹(二叉鏈表的形式存儲)： 結點結構如下所示：lchildltagdatartagrchild6.8.2 二叉排序樹 二叉排序樹的定義（遞歸定義 ） 或者是一棵空二叉樹，或者是一棵滿足以下條件的二叉樹： l左子樹中所有結點的值都小于根結點的值 l右子樹中所有結點的值都大于等于根結

49、點的值 l左、右子樹本身也是一棵二叉排序樹 結論：中根遍歷后的結點序列是一個有序序列。如果用待排序數據構造一棵二叉排序樹，并對它進行中根遍歷，則達到排序目的。 二叉排序樹是一種排序方法。 構造二叉排序樹 構造過程：從空樹逐步插入各個結點的過程。每插入一個結點時，插入位置的確定都從根結點開始，根據二叉排序樹的定義，小于根結點的插入位置應在左子樹中，否則，插入位置應在右子樹中。一直進行比較，直到找到一個合適的插入位置，將結點插入成為一個葉子結點為止。二叉排序樹的插入算法 ：（略）6.8.3 哈夫曼樹 哈夫曼樹的相關概念 路徑：連接兩個結點的分支 路徑長度：兩個結點間路徑上的分支個數。 樹的路徑長度

50、：從根結點到其余各結點間路徑之和。 結點的權：樹中結點所賦的數值。 結點的帶權路徑長度：從根結點到該結點的路徑長度和該結點的權植的乘積。 樹的帶權路徑長度是指樹中所有葉子結點的帶權路徑長度之和。通常記作： 其中，wi代表第i個結點的權值；li代表第i個結點的路徑長度；n為樹中葉子結點的個數 哈夫曼樹（最優二叉樹）是指帶權路徑長度最小的二叉樹。哈夫曼樹的構造方法： l根據給定的n個權值（w1,w2,wn），構成n棵二叉樹的集合。其中，每棵二叉樹都只有一個權值為wi的根結點，沒有左、右子樹。 l從二叉樹的集合中，選擇權值最小的兩棵樹作為左右子樹，構成一棵新的二叉樹，新二叉樹的根結點的值為左右孩子結

51、點的權值之和。 l從二叉樹集合中，刪除剛選取的兩棵樹，同時將新得到的二叉樹添加到二叉樹集合中。 重復上述過程，直到二叉樹集合中只有一棵二叉樹為止，該樹既為哈夫曼樹。 6.8.4 二叉樹的綜合實例 問題的描述： 創建一棵二叉樹，給出此二叉樹按四種遍歷方式遍歷后的結點序列、計算此二叉樹的層數。問題的分析： 設二叉鏈表形式存儲，結點值用單個字符表示。 創建：按先序遍歷的順序建立二叉鏈表。先建立根結點，然后依次建立根的左、右子樹。在建立過程中，將二叉樹當成完全二叉樹，二叉樹中與完全二叉樹對應的結點輸入結點元素的值；沒有對應的結點時，輸入#來代替，直到二叉樹的全部結點輸入完畢為止。二叉樹的遍歷過程是一個

52、遞歸過程，所以建立算法也可以寫成一個遞歸算法。遍歷：可以直接調用6.6二叉樹遍歷中給定的算法。求深度：二叉樹的深度為樹中結點層次的最大值，所以從上一層的根結點開始往下遞推可得到樹的層數。在整個過程中也需要確定一個遍歷方式，本例中使用后序遍歷來實現。實現算法 ： （略）本章總結 本章介紹了樹和二叉樹的邏輯結構、存儲結構、各種基本操作的實現及應用。 樹是若干個結點的有限集合。主要特征是只有一個沒有前驅的結點為根結點，其余結點都只有一個前驅，所有結點可以有任意多個后繼，是一對多的關系。 樹有四種存儲方式：雙親表示法、孩子表示法、孩子雙親表示法和孩子兄弟表示法。樹的主要操作是樹的遍歷。遍歷是指訪問樹中

53、所有結點，并且每個結點只能訪問一次。樹有三種遍歷方法：先根遍歷、后根遍歷和按層遍歷。 森林是若干棵樹的集合，有先根遍歷和后根遍歷兩種遍歷方式。 二叉樹主要特征是只有一個沒有前驅的根結點，其余結點都只有一個前驅，所有結點最多有兩個后繼結點，分別為該結點的左孩子結點和右孩子結點。 二叉樹的存儲方式：順序存儲，鏈式存儲（二叉鏈表）。順序存儲適合存儲完全二叉樹，普通二叉樹適合用鏈式存儲方式。 二叉樹有四種遍歷方式：先根遍歷、中根遍歷、后根遍歷和按層遍歷。 樹、森林和二叉樹之間可以進行轉換，轉換的主要依據就是樹的孩子兄弟表示法，組成森林的所有樹的根結點之間是兄弟關系。 樹、森林與二叉樹進行轉換結論：樹的

54、先根遍歷和后根遍歷的結點序列就是該樹轉換成二叉樹后的先根和中根遍歷的結點序列；森林的先根遍歷和后根遍歷的結點序列就是該森林轉換成二叉樹后的先根和中根遍歷的結點序列。 二叉樹的主要應用：線索二叉樹、二叉排序樹和哈夫曼樹等。第7章 圖 學習重點：掌握圖的基本概念、邏輯特征和圖的存儲結構。掌握圖的深度優先搜索遍歷和廣度優先搜索遍歷的思想、遍歷過程及鄰接矩陣和鄰接表上的實現算法。 掌握圖的最小生成樹的概念和求圖的最小生成樹的克魯斯卡爾算法和普里姆算法的思想、求解過程和畫出對應的最小生成樹并求出最小生成樹的權。掌握求有向圖最短路徑和拓撲序列的思想和求解過程。 第7章 圖 7.1 實例：求城市間最短路徑

55、7.2 圖的邏輯結構、特征 7.3 圖的存儲結構 7.4 圖的遍歷 7.5 最小生成樹 7.6 應用舉例 本章總結7.1 實例：求城市間最短路徑 7.1.1 問題描述 假設乘飛機旅行，想選擇一條所要參觀的兩個城市間距離最短的路線。 7.1.2 問題的分析 如果以點代表城市，以線代表兩個城市之間的距離，并在線上標出具體的距離值，可畫出相應的圖。通常將解決這種問題中的出發點稱之為源點，則求最短路徑就變成一個求從源點到終點的最短路徑的問題。解決此問題時需要求出源點到其余各頂點間的最短路徑才能得到最終的答案。 第一步：先求從源點出發的各個路徑中的最短路徑。有兩種情況：第一種直接有線相連，比較路徑值的大

56、小；另一種沒有直接連線，表示這兩個城市間不直接通。第二步：在上一結果的基礎上求從源點出發的各個路徑中的最短路徑。到達各個城市的路徑存在二種可能性：第一種是途徑剛選擇的城市仍沒有通路；第二種是途徑剛選擇的城市后，到達該城市的路徑又多出一種選擇，此時選擇短的路徑。第三步：重復第二步，每選中一個城市，都要修改一下到其余各城市間的最短路徑，直到求出源點到其余各城市間的最短路徑為止。 求解過程大體如下： 從畫出的圖可知，此圖是一種圖型結構，圖中每個圓圈就是圖型結構中的一個頂點，連線稱之為邊，所以圖是由若干個頂點的集合和邊的集合組成的。 上面的例子就是圖的日常生活中的一種應用：求從源點到其余各頂點間的最短

57、距離。 結論：7.2 圖的邏輯結構、特征 7.2.1 圖的邏輯結構 7.2.2 圖的特征 圖是一種復雜的非線性數據結構。在圖形結構中，結點之間的關系是任意的，即圖中的每個結點都可以有任意多個前驅結點和任意多個后繼結點，是多對多的關系。 7.2.1 圖的邏輯結構 圖的定義： 圖（Graph）由兩個集合V和E組成，它的二元組定義可以表示成： Graph=（V，E） 其中， V是頂點的有窮非空集合，即V=vi | n1，viVertexType，VertexType為頂點值的類型，它可以代表任何類型，n為頂點數； E是V上頂點間二元關系的有窮集合，稱這種關系為邊。 用V（G）表示圖的頂點集合；E（G

58、）來表示圖G的邊集合，E（G）可以為空集。當E（G）為空集時，圖G稱為空圖。 無向圖：在圖G中，如果代表邊的頂點序偶關系都是對稱的，即和同時成立，則以無序對（vi，vj）替代這兩個有序對。 有向圖：圖G中邊的頂點是有序的。在有向圖中邊表示從頂點vi到頂點vj的一條有向邊（弧），頂點vi稱為有向邊的尾（或始點），頂點vj稱為有向邊的頭（或終點），用由起點指向終點的箭頭表示有向邊。 7.2.2 圖的特征 端點和鄰接點 在一個無向圖中，若存在一條邊（vi，vj），則稱vi，vj為此邊的兩個端點，并稱它們互為鄰接點。在一個有向圖中，若存在一條邊，則稱此邊為頂點vi的一條出邊，頂點vj的一條入邊（ine

59、dge）；稱vj是vi的出邊鄰接點，vi是vj的入邊鄰接點。頂點的度、入度、出度 在無向圖中，頂點v所具有的邊的數目稱為該頂點的度。有向圖中頂點v的度又分為入度（以頂點v為終點的入邊的數目）和出度（以頂點v為始點的出邊的數目）。一個頂點的入度與出度的和為該頂點的度。完全圖、稠密圖、稀疏圖 若無向圖中的每兩個頂點之間都存在著一條邊，有向圖中的每兩個頂點之間都存在著方向相反的兩條邊，則稱此圖為完全圖。當一個圖接近完全圖時，則稱它為稠密圖。相反，當一個圖含有較少的邊數時，則稱為稀疏圖。子圖 設有兩個圖G=（V，E）和G=(V，E)，若V是V的子集，即VV，且E是E的子集，即EE，則稱G是G的子圖。

60、路徑和路徑長度路徑（path）是一個頂點序列。路徑長度是指該路徑上經過的邊的數目。若一條路徑上除了開始點和結束點可以相同外，其余頂點均不相同，則稱此路徑為簡單路徑。回路或環若一條路徑上的開始點與結束點為同一個頂點，則此路徑被稱為回路或環（cycle）。開始點與結束點相同的簡單路徑被稱為簡單回路或簡單環。連通、連通圖和連通分量 在無向圖G中，若從頂點vi 到頂點vj有路徑，則稱vi和vj是連通的。若圖G中任意兩個頂點都連通，則稱G為連通圖，否則稱為非連通圖。無向圖G中極大連通子圖稱為G的連通分量。強連通圖和強連通分量 在有向圖G中，若從頂點vi 到頂點vj有路徑，則稱vi和vj是連通的。若任意兩