C語言入門教程全第9章ppt課件

1、第第9章章 數(shù)據(jù)結(jié)構(gòu)與算法基礎數(shù)據(jù)結(jié)構(gòu)與算法基礎 9.1 數(shù)據(jù)結(jié)構(gòu)與算法概述數(shù)據(jù)結(jié)構(gòu)與算法概述 9.2 線性表線性表9.3 棧和隊列棧和隊列 9.4 樹和二叉樹樹和二叉樹 9.5 圖圖9.6 排排 序序9.7 本章小結(jié)本章小結(jié)9.1 數(shù)據(jù)結(jié)構(gòu)與算法概述 9.1.1 數(shù)據(jù)結(jié)構(gòu)的相關概念數(shù)據(jù)結(jié)構(gòu)的相關概念實踐證明，要想更有效地使用計算機，僅僅掌握計算機語言而缺乏數(shù)據(jù)結(jié)構(gòu)和算法的有關知識，是難以處理諸多復雜應用問題的。早期的計算機主要解決純數(shù)值計算的問題，以此為加工對象的程序設計稱為數(shù)值型程序設計。其涉及的操作對象比較簡單，其一般為整型、實型數(shù)據(jù)等。后來，隨著計算機應用領域的不斷拓寬，解決非數(shù)值計算

2、的問題越來越引起人們的關注。例如，金融管理、文獻檢索、計算機輔助設計等。這些問題主要集中于對數(shù)據(jù)集合中的各元素以各種方式進行運算，如插入、更新、刪除、查找等。在此涉及的數(shù)據(jù)類型比較復雜，而且數(shù)據(jù)元素之間具有各種特定的聯(lián)系，所以，如果了解了數(shù)據(jù)集合中元素之間的關系以及如何組織和表示這些數(shù)據(jù)，就能大大提高計算機處理問題的效率。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值運算的程序設計問題的學科，它包含以下3個方面的內(nèi)容：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)。（2）對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲（物理）結(jié)構(gòu)。（3）對數(shù)據(jù)的抽象運算。1數(shù)據(jù)（data）數(shù)據(jù)是反映客觀事物信息符號的集合，也是計算機程序要加

3、工的對象。這個集合中包括客觀事物的數(shù)值、字符以及能夠輸入到計算機中并被計算機程序處理的符號。計算機發(fā)展初期，由于計算機主要用于數(shù)值計算，數(shù)據(jù)指的就是數(shù)值。隨后由于計算機應用的普及，數(shù)據(jù)的含義也比原來變得更加廣泛。如文字、表格、聲音、圖形、圖像等都屬于數(shù)據(jù)的范疇。2數(shù)據(jù)元素（data element）數(shù)據(jù)元素是數(shù)據(jù)集合中的客體（個體），是數(shù)據(jù)的基本單位，有時也稱為節(jié)點或記錄。例如數(shù)據(jù)集合N=1，2，3，4，5中整數(shù)15都是數(shù)據(jù)元素。每個數(shù)據(jù)元素的表現(xiàn)形式是由一個或多個數(shù)據(jù)項組成的。數(shù)據(jù)項是具有獨立含義的最小標識單位，例如，在老師檔案信息管理中的每一位老師就是一個數(shù)據(jù)元素，組成它的數(shù)據(jù)項可以是姓名

4、、性別、年齡等。3數(shù)據(jù)對象（data object）數(shù)據(jù)對象是具有相同特性的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如，一周中的7天就是一個數(shù)據(jù)對象，可表示為集合W=Mon，Tue，Wed， Thu，F(xiàn)ri，Sat，Sun；再如，字母數(shù)據(jù)對象可表 示為集合C=A， B ，Z。4數(shù)據(jù)類型（data type）數(shù)據(jù)類型是一個值的集合和定義在該值集上的一組操作的總稱。程序中出現(xiàn)的每一個變量必須與一個而且只能與一個數(shù)據(jù)類型相聯(lián)系，它不僅規(guī)定了該變量可以設定的值的集合，還規(guī)定了該集合上的運算。各種語言規(guī)定了它所允許的數(shù)據(jù)類型。在C語言中，基本數(shù)據(jù)類型包括整型、實型等，這些變量的值是不可再分的；而構(gòu)造類型包括

5、數(shù)組、結(jié)構(gòu)體等，這些變量的值是可以再分的，也可以說它們是帶結(jié)構(gòu)的數(shù)據(jù)，它們的成分可以是基本數(shù)據(jù)類型，也可以是構(gòu)造數(shù)據(jù)類型等。5數(shù)據(jù)結(jié)構(gòu)（data structure）數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關系，即數(shù)據(jù)的組織形式?？梢杂眉险摰姆椒ǘx數(shù)據(jù)結(jié)構(gòu)如下： S=(D,R)D=ai|aiElemSet,i=0,1,2,3,n,n0R=|ai-1,aiD,2in數(shù)據(jù)結(jié)構(gòu)S是一個二元組，其中D是一個數(shù)據(jù)元素的有限集合，R是定義在關系D上的有限集合，即R是由有限個關系所構(gòu)成的集合。若n=0時，則D是一個空集。數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與物理結(jié)構(gòu)兩種。 （1）數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)就是數(shù)據(jù)元素間的邏輯關

6、系，它研究的是數(shù)據(jù)元素及其關系的數(shù)學特性，與數(shù)據(jù)的存儲無關，是獨立于計算機的。數(shù)據(jù)的邏輯結(jié)構(gòu)可概括地分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩種，如圖9.1.1所示。圖9.1.1 數(shù)據(jù)的邏輯結(jié)構(gòu)線性結(jié)構(gòu)的邏輯特性是有且僅有一個開始元素和一個終結(jié)元素，除第一個元素以外，其他元素有且僅有一個直接前驅(qū)；除最后一個元素外，其他元素都有且僅有一個直接后繼。非線性結(jié)構(gòu)的邏輯特性是一個元素可能有多個直接前驅(qū)和直接后繼。線性結(jié)構(gòu)主要有線性表、棧和隊列等，而非線性結(jié)構(gòu)分為樹型結(jié)構(gòu)和圖型結(jié)構(gòu)等。 （2）數(shù)據(jù)的物理結(jié)構(gòu)。數(shù)據(jù)的物理結(jié)構(gòu)又稱存儲結(jié)構(gòu)，是數(shù)據(jù)及其關系在計算機中的存放形式，是邏輯結(jié)構(gòu)在計算機存儲器中的映像，也就是它的具體

7、實現(xiàn)，通常用高級語言中各種數(shù)據(jù)類型來描述。在進行實際的數(shù)據(jù)處理時，被處理的數(shù)據(jù)都是存放在計算機的存儲空間中，而且，各數(shù)據(jù)在計算機存儲空間的位置關系與它們的邏輯關系通常是不同的。因此，為了能表示出存放在計算機存儲空間的各個節(jié)點之間的邏輯關系，在數(shù)據(jù)的存儲結(jié)構(gòu)中，不但要存放各個節(jié)點的信息，還要存放各個節(jié)點之間邏輯關系的信息。下面介紹4種常見的存儲結(jié)構(gòu)：1）順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)主要用于線性的數(shù)據(jù)結(jié)構(gòu)。它是把邏輯上相鄰的數(shù)據(jù)元素節(jié)點存儲在物理上相鄰的存儲單元中，各節(jié)點之間的邏輯關系由存儲單元的鄰接關系來體現(xiàn)。如圖9.1.2所示為順序存儲結(jié)構(gòu)，假設每個節(jié)點占據(jù)長度為l（字母，以下同）的存儲空間，這

8、個邏輯結(jié)構(gòu)在物理存儲器中以一定的順序占用連續(xù)的存儲空間。對于這種結(jié)構(gòu)，只需要知道第一個元素的地址和每一個元素所占的存儲單元數(shù)就可以得到任何一個元素所在的位置。在順序存儲結(jié)構(gòu)中存取任意一個元素所需要的時間是相等的。圖9.1.2 順序存儲結(jié)構(gòu) 2）鏈式存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)比較適合于線性結(jié)構(gòu)，而非線性結(jié)構(gòu)一般很難用順序存儲結(jié)構(gòu)來實現(xiàn)，所以，通常不用順序存儲結(jié)構(gòu)，而是用鏈式存儲結(jié)構(gòu)來實現(xiàn)非線性結(jié)構(gòu)。鏈式存儲結(jié)構(gòu)是給節(jié)點附加指針字段。在這種存儲結(jié)構(gòu)中，節(jié)點所占的存儲單元分為兩部分：一部分是用來存放節(jié)點自身的信息，稱為數(shù)據(jù)域；另一部分是用來存放該節(jié)點后繼節(jié)點的存儲單元的地址，稱為指針域。指針域中可以有一

9、個或者多個指針，用來表示節(jié)點的一個或多個后繼，也可以用來表示其他節(jié)點的地址。在用鏈式存儲結(jié)構(gòu)存儲一個非線性結(jié)構(gòu)時，節(jié)點中的指針個數(shù)可以根據(jù)該節(jié)點的直接后繼個數(shù)來設置。如圖9.1.3所示的鏈式存儲結(jié)構(gòu)，在Addr1的存儲單元中，既包含了節(jié)點a1本身的信息，又包含了它的后繼節(jié)點a2的存儲單元的地址Addr1+3l，其他節(jié)點與此類似。圖9.1.3 鏈式存儲結(jié)構(gòu) 由此不難看出，鏈式存儲結(jié)構(gòu)可以存儲線性結(jié)構(gòu)，也可以存儲非線性結(jié)構(gòu)。在鏈式存儲結(jié)構(gòu)中，各個節(jié)點在存儲空間中的前后位置關系與其邏輯順序也可以不一致，其存儲空間也可以不連續(xù)。3）索引存儲結(jié)構(gòu)。在線性結(jié)構(gòu)中，所有節(jié)點可以排成一個序列，每個節(jié)點在該序列

10、中都有對應的位置值，這個位置值就是節(jié)點的索引號。索引存儲結(jié)構(gòu)是用節(jié)點的索引號來確定節(jié)點的存儲地址?？捎靡韵聝煞N方法實現(xiàn)索引存儲： 建立一個附加的索引表，索引表中第i項的值就是第i個節(jié)點的存儲地址。 如果每個節(jié)點所占單元數(shù)都相等，可用位置值的線性函數(shù)的值來指出節(jié)點對應的存儲地址，即第i個節(jié)點di的地址為LOC(di)=(i-1)l+d，其中l(wèi)為節(jié)點所占單元數(shù)，d為開始節(jié)點d1對應的存儲地址。4）散列存儲結(jié)構(gòu)。散列存儲結(jié)構(gòu)是指根據(jù)節(jié)點的關鍵字值來確定其存儲地址，也稱為哈希法。用這種方法進行存儲時，每個節(jié)點分散地存儲在存儲單元中，其查找的效率是很高的，關鍵問題是怎樣選擇哈希函數(shù)和研究解決沖突的辦法。

11、 上述4種存儲結(jié)構(gòu)也可以組合起來對數(shù)據(jù)進行存儲映像。同一個邏輯結(jié)構(gòu)可以有多種不同的存儲方法，應根據(jù)具體情況進行選擇。另外，存儲結(jié)構(gòu)只是數(shù)據(jù)結(jié)構(gòu)的一個重要方面，如果邏輯結(jié)構(gòu)相同但存儲結(jié)構(gòu)不同，也是不同的數(shù)據(jù)結(jié)構(gòu)。例如，如果用順序存儲結(jié)構(gòu)存儲線性表，則稱為順序表；如果用鏈式存儲結(jié)構(gòu)存儲線性表，則稱為鏈表。9.1.2 算法評價算法評價在第3章中讀者已初步了解了算法的概念、特性等，在前面其他章節(jié)的編程舉例中還學習了不少給定的算法。而解決同一個問題通常有許多不同的算法。算法評價的目的首先在于從解決同一個問題的不同算法中選擇出較為合適的一種，其次在于知道怎樣對現(xiàn)有算法進行改進，進而設計出更好的算法。對于算

12、法的評價可以從以下幾個方面進行。 1正確性正確性（correctness）是設計和評價算法的首要條件，一個正確的算法是指在有合理的數(shù)據(jù)輸入的情況下，能夠在有限的運行時間內(nèi)得出正確的結(jié)果。要從理論上證明一個算法的正確性，并不是一件容易的事，所以通常可采用各種典型的輸入數(shù)據(jù)上機調(diào)試算法，并使算法中的每段代碼都被測試過，若發(fā)現(xiàn)錯誤及時修正，最終可以驗證出算法的正確性。 2健壯性健壯性（robustness）是指一個算法對不合理（又稱不正確、非法、錯誤等）數(shù)據(jù)輸入的反應和處理能力。一個好的算法應該能夠識別出錯誤數(shù)據(jù)并進行相應的處理。對錯誤數(shù)據(jù)的處理一般包括打印出錯誤信息、調(diào)用錯誤處理程序、返回標識錯誤

13、的特定信息、中止程序運行等。 3可讀性可讀性（readability）是指一個算法供人們閱讀和理解的容易程度。一個可讀性好的算法，應該符合結(jié)構(gòu)化和模塊化程序設計的思想，應該對其中的每個功能模塊、重要數(shù)據(jù)類型或語句加以必要注釋；應該建立相應的文檔，對整個算法的功能、結(jié)構(gòu)、使用及有關事項進行說明。4簡單性簡單性（simplicity）是指一個算法所采用數(shù)據(jù)結(jié)構(gòu)和方法的簡單程度。如對數(shù)組進行查找時，采用順序查找的方法比采用二分查找的方法要簡單；對數(shù)組進行排序時，采用簡單選擇排序的方法比采用堆排序或快速排序的方法要簡單。但最簡單的算法往往不是最有效的，即有可能占用較長的運行時間和較多的內(nèi)存空間。算法的

14、簡單性便于用戶編寫、分析和調(diào)試，所以對于處理少量數(shù)據(jù)的情況是適用的，但若要處理大量的數(shù)據(jù)，則算法的有效性比簡單性更重要。有效性主要表現(xiàn)為時間復雜度和空間復雜度。 5時間復雜度時間復雜度（time complexity）是指計算機執(zhí)行一個算法時在時間上的消耗度量。度量一個程序的執(zhí)行時間通常有兩種方法：事后統(tǒng)計和事前分析估算。通常人們采用第二種方法，所以這里只介紹事前分析估算方法。一般情況下，把算法中一條語句重復執(zhí)行的次數(shù)稱為此語句的頻度，它常表示為問題規(guī)模n的某個函數(shù)，記作F(n)。而算法的時間復雜度則記作T(n)=O(F(n)下面舉例說明如何求時間復雜度：for(i=0;in;i+) for(

15、j=0;jn;j+) bij=0; for(k=0;kn;k+) bij=bij+aik*akj; 以執(zhí)行次數(shù)最多的語句（bij=bij+aik*akj;）進行計算：語句頻度：F(n)=n3時間復雜度：T(n)=O(F(n)=O(n3)下列程序段的時間復雜度如下： （1）x=x+1; T(n)=O(1)（2）for(j=0;jn;j+) x=x+1; T(n)=O(n)（3）for(j=0;jn;j+) for(k=0;knext=p-next;p-next=s;在進行指針的修改時，必須要注意其修改的順序，假如把上述兩條語句順序顛倒，那么執(zhí)行結(jié)果就完全錯誤。在帶頭節(jié)點的單鏈表的第i個元素之后插

16、入元素x的算法描述如下：ListInsert_L(LinkList *L,int i,ElemType x) （2）刪除運算。單鏈表的刪除運算與插入運算一樣，在刪除時，不需要移動元素，只須修改有關的指針內(nèi)容。在單鏈表上進行刪除運算時指針的變化如圖9.2.7所示。上述指針修改可描述如下：p-next=p-next-next;圖9.2.7 單鏈表上刪除節(jié)點時指針的變化情況在帶頭節(jié)點的單鏈表中刪除第i個元素的算法描述如下： 3其他形式的鏈表根據(jù)實際需要，線性表的鏈式存儲結(jié)構(gòu)還有循環(huán)鏈表和雙向鏈表等其他形式。（1）循環(huán)鏈表。循環(huán)鏈表是線性表的另一種鏈式存儲結(jié)構(gòu)，它的特點是表中最后一個節(jié)點的指針域不為空

17、，而是指向表頭，整個鏈表形成一個環(huán)。如圖9.2.8（a）、（b）所示分別表示具有頭節(jié)點的非空循環(huán)鏈表和空循環(huán)鏈表。圖9.2.8 循環(huán)鏈表循環(huán)鏈表與一般鏈表的不同之處在于只要給定循環(huán)鏈表中任一節(jié)點的地址，就可以遍歷表中所有節(jié)點，而不必從頭指針開始。這樣有可能對某些運算帶來方便。（2）雙向鏈表。前面討論的鏈表都是單向鏈表，它們只能單方向地尋找表中的節(jié)點，若要尋找前驅(qū)節(jié)點，則需從表頭指針出發(fā)查找或向后循環(huán)一周查找，當表長為n時執(zhí)行時間為O(n)。為克服其單向性缺點，可采用雙向鏈表。在雙向鏈表的節(jié)點中有兩個指針域，一個指向直接后繼，一個指向直接前驅(qū)，如圖9.2.9所示。圖9.2.9 雙向鏈表雙向鏈表的

18、節(jié)點類型定義如下：typedef struct Dlnode /*定義雙向鏈表節(jié)點 類型*/ ElemType data; struct DLnode *left; struct DLnode *right;DLnode,*DLinkList;此類型包含有3個域：數(shù)值域data、左指針域left和右指針域right。left域用于指向其前驅(qū)節(jié)點，right域用于指向其后繼節(jié)點。由于雙向鏈表具有對稱性，因此從表中某一給定的節(jié)點可隨意向前或向后查找。但在執(zhí)行插入、刪除運算時，需同時修改兩個方向上的指針。9.2.4 線性表的應用線性表的應用一元多項式相加是線性表的一個典型應用實例。多項式的操作是表處

19、理中經(jīng)常出現(xiàn)的操作，我們以一元多項式相加為例，說明線性鏈表在實際中的應用。一個一元多項式Pn(x)可以表示為Pn(x)= P0+P1x+P2x2+pnxn該多項式按升冪排列，并由n+1個系數(shù)唯一確定，因此可以用一個線性表P表示為P=(p0，p1，p2，pn)其指數(shù)i隱含在系數(shù)pi的序號內(nèi)。一元多項式的存儲結(jié)構(gòu)可以采用順序存儲結(jié)構(gòu)，也可以用鏈式存儲結(jié)構(gòu)，這要取決于執(zhí)行何種操作。如果只求多項式的值，無須修改多項式的系數(shù)和指數(shù)，則采用順序存儲結(jié)構(gòu)為宜。但在進行多項式相加時，通常要改變多項式的系數(shù)和指數(shù)，而且在實際問題中，經(jīng)常會出現(xiàn)多項式的次數(shù)很高但又存在大量的零系數(shù)項的情況，例如： S(x)=8+2

20、x1050+3x2000這時如果采用順序存儲結(jié)構(gòu)會浪費大量的存儲空間，故一般采用鏈式存儲結(jié)構(gòu)。用鏈式存儲結(jié)構(gòu)表示多項式是把每一個非零系數(shù)項構(gòu)成鏈表中的一個節(jié)點，節(jié)點是由兩個數(shù)據(jù)域和一個指針域構(gòu)成，如圖9.2.10（a）所示。其中，exp(i)表示該項的指數(shù)，稱為指數(shù)域；coef(i)表示該項的系數(shù)，稱為系數(shù)域；next(i)是指向下一個非零系數(shù)的節(jié)點，稱為指針域。整個多項式Pn(x)如圖 9.2.10（b）所示。圖9.2.10 一元多項式的鏈式存儲結(jié)構(gòu)設有一元多項式A(x)和B(x)，現(xiàn)要求其相加結(jié)果C(x)=A(x)+B(x)。其運算規(guī)則為：將兩個多項式中指數(shù)相同的項對應系數(shù)相加，若和不為零

21、，則構(gòu)成C(x)中的一項；A(x)和B(x)中所有指數(shù)不相同的項均復制到C(x)中。其運算規(guī)則如下：假設指針qa和qb分別指向多項式A和多項式B中當前進行比較的某個節(jié)點，則比較兩個節(jié)點中的指數(shù)項，有下列3種情況：（1）指針qa所指節(jié)點的指數(shù)值指針qb所指向節(jié)點的指數(shù)值，則應摘取qb指針所指節(jié)點插入到C(x)鏈表中去。（3）指針qa所指節(jié)點的指數(shù)值=指針qb所指向節(jié)點的指數(shù)值，則把兩個節(jié)點中的系數(shù)相加，若和數(shù)不為0，則修改qa所指節(jié)點的系數(shù)值，同時釋放 qb所指向節(jié)點；反之，從多項式A的鏈表中刪除相應節(jié)點，并釋放指針qa和qb所指節(jié)點。如圖9.2.11（a）所示，為帶頭節(jié)點的單鏈表表示的多項式A

22、5(x)=8-2x+15x5，B8(x)=2x+7x4-9x5 +3x8；如圖9.2.11（b）所示表示相加后的“和多項式”C(x)。圖9.2.11 用鏈式存儲結(jié)構(gòu)進行多項式求和9.3 棧和隊列 9.3.1 棧的定義及其運算棧的定義及其運算1棧的定義棧（stack）又稱堆棧，它實際上是一種操作受限的特殊的線性表，是限定僅在表的一端進行插入和刪除的線性表。在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的一端稱為棧底。棧頂元素總是最后被插入的元素，自然也是最先被刪除的元素；棧底元素總是最先被插入的元素，自然也是最后才被被刪除的元素。也是說棧是按照“先進后出”（First In Last O

23、ut，F(xiàn)ILO）或者“后進先出”（Last In First Out，LIFO）的原則組織數(shù)據(jù)的，所以，棧也被稱為“先進后出”表或“后進先出”表。由此可以看出，棧具有記憶功能。通常用指針top指示棧頂?shù)奈恢?，用指針bottom指向棧底。向棧中插入一個元素（即插入為新的棧頂元素）稱為入棧運算，從棧中刪除一個元素（即刪除棧頂元素）稱為出棧運算。棧頂指針top動態(tài)反圖9.3.1 棧的示意圖映了棧中元素的變化情況。如圖9.3.1所示為棧的示意圖。棧這種結(jié)構(gòu)在日常生活中是很常見的。例如子彈夾就是一種棧的例子，最先壓入的子彈總是最后一個被彈出，而最后壓入的子彈最先被彈出，這就遵循了“后進先出”或“先進后出

24、”的原則。2棧的基本運算（1）建立一個空棧。（2）判斷空棧。（3）讀棧頂元素。 （4）求棧的長度，返回棧的數(shù)據(jù)元素個數(shù)。（5）入棧，將元素插入到棧頂。（6）出棧，刪除棧頂元素。9.3.2 棧的存儲結(jié)構(gòu)棧的存儲結(jié)構(gòu)1棧的順序存儲結(jié)構(gòu)順序棧實現(xiàn)棧的順序存儲結(jié)構(gòu)最簡單的方法是用一維數(shù)組來存儲。由于棧底不變，而棧頂是隨入棧、出棧操作動態(tài)變化的，因此必須記住棧頂?shù)奈恢?，并且由于棧是有容量限制的，因此用C語言定義順序棧的結(jié)構(gòu)如下： #define Stack_NUM 100#define Stack_MORENUM 10typedef struct ElemType *bottom; ElemType *

25、top; int stacksize;SqStack;其中，stacksize說明棧當前可用的最大容量。棧的初始化操作如下：按設定的初始分配量進行第一次存儲分配，bottom稱為棧底指針，在順序棧中，它始終指向棧底的位置，如果bottom的值為NULL，則表明棧結(jié)構(gòu)不存在。在程序設計語言中，用一維數(shù)組S（1:m）作為棧的順序存儲空間，其中m為棧的最大容量。如圖9.3.2（a）所示是容量為10的棧順序存儲空間，棧中已經(jīng)有6個元素；如圖9.3.2（b）和圖9.3.2（c）所示分別為入棧與出棧后的狀態(tài)。圖9.3.2 順序棧的插入與刪除運算 在棧的順序存儲空間S（1:m）中，S（bottom）通常為棧

26、底元素（是在棧非空的情況下），S（top）為棧頂元素。top=0表示?？眨瑃op=m表示棧滿。在棧上進行操作，都比較容易實現(xiàn)，下面介紹順序棧的建立、插入和刪除的算法。（1）建立空棧。Init_StackSq(SqStack *S) 2棧的鏈式存儲結(jié)構(gòu)鏈棧順序棧最大的缺點是：必須設置最大容量，但是當棧的容量不固定時，這樣可能會造成很多存儲空間的浪費，也可能產(chǎn)生上溢。棧的鏈式存儲結(jié)構(gòu)克服了這個缺點，它采用一個鏈表結(jié)構(gòu)來表示棧，棧頂指針就是鏈表的頭指針，其插入和刪除操作僅在表頭進行，如圖9.3.3所示。圖9.3.3 鏈棧示意圖鏈棧節(jié)點類型的定義如下：typedef struct Snode Elem

27、Type data;/*數(shù)據(jù)域*/ struct Snode *next;/*指針域*/Snode,*LinkStack;假設s是LinkStack型的變量，則s為鏈棧的頭 指針。下面介紹鏈棧的插入和刪除算法。 p=*S;/*使棧頂指針指向下一節(jié)點*/*S=pnext; free(p);/*釋放棧頂元素*/return temp;9.3.3 棧的應用棧的應用棧最初用于高級語言的編譯程序中，如表達式求值、程序的嵌套以及遞歸調(diào)用等，后來在各類回溯求解問題中也得到應用。下面以過程嵌套的實例來說明棧的應用。過程（函數(shù)）嵌套是程序設計中很重要的應用。當過程調(diào)用子過程（自定義函數(shù)）時，必須把斷點的信息及地

28、址保留起來，當子過程執(zhí)行完畢返回時，取用這些信息，找到返回地址，由此斷點繼續(xù)執(zhí)行。當程序中出現(xiàn)多重嵌套調(diào)用時，必須開辟一個棧，將各層斷點信息依次入棧，當各層子過程返回時，又以相反的次序從棧頂取出。如圖9.3.4所示給出了具有嵌套調(diào)用關系的5個程序，其中主程序要調(diào)用子程序SUB1，SUB1要調(diào)用子程序SUB2，SUB2要調(diào)用子程序SUB3，SUB3要調(diào)用子程序SUB4，SUB4不再調(diào)用其他子程序。圖9.3.4 主程序與子程序之間的調(diào)用關系下面來具體介紹計算機系統(tǒng)是如何處理它們之間的調(diào)用關系的。其中的關鍵是要正確處理好執(zhí)行過程中的調(diào)用層次和返回路徑，這就需要記憶每一次調(diào)用時的返回點。計算機系統(tǒng)用一

29、個棧來動態(tài)記憶調(diào)用過程中的路徑，其基本原則如下：（1）在開始執(zhí)行程序前，先建立一個棧，其初始狀態(tài)為空。（2）當發(fā)生調(diào)用時，將當前調(diào)用的返回點地址（在圖9.3.4中用語句標號表示）插入到棧。 （3）當遇到從某個子程序返回時，就從棧頂取出返回點地址。根據(jù)以上原則，圖9.3.4中5個程序在執(zhí)行過程中的調(diào)用順序以及棧中元素變化的情況如下：（1）主程序開始執(zhí)行前，建立一個空棧，即棧的狀態(tài)為（）。（2）開始執(zhí)行主程序MAIN，當執(zhí)行到CALL SUB1時，調(diào)用子程序SUB1，這時，將本次調(diào)用的返回點地址A入棧。此時，棧的狀態(tài)為（A）。 （3）開始調(diào)用執(zhí)行子程序SUB1，當執(zhí)行CALL SUB2時，調(diào)用子程

30、序SUB2，這時將本次調(diào)用的返回點地址B入棧。此時棧狀態(tài)為（A，B）。（4）開始調(diào)用執(zhí)行子程序SUB2，當執(zhí)行到CALL SUB3時，調(diào)用子程序SUB3，這時將本次調(diào)用的返回點地址C入棧。此時棧狀態(tài)為（A，B，C）。（5）開始調(diào)用執(zhí)行子程序SUB3，當執(zhí)行到CALL SUB4時，調(diào)用子程序SUB4，這時，將本次調(diào)用的返回點地址D入棧。此時棧的狀態(tài)為（A，B，C，D）。從上述逐步調(diào)用的過程可以看出，每次發(fā)生調(diào)用時，都需要將當前調(diào)用的返回點地址入棧，而這種插入操作不需要移動棧中原有元素，并且，各返回點地址在棧中的存放順序恰好是調(diào)用順序。（6）開始調(diào)用執(zhí)行子程序SUB4，而SUB4不再調(diào)用其他子程序

31、，因此執(zhí)行完子程序后要返回到子程序SUB3的地址D處。其中返回點地址D從棧頂取出，這時，棧的狀態(tài)為（A，B，C）。 （7）返回到子程序SUB3的D處繼續(xù)執(zhí)行，執(zhí)行完子程序SUB3后要返回到子程序SUB2的地址C處。其中返回點地址C從棧頂取出，這時，棧的狀態(tài)為（A，B）。（8）返回到子程序SUB2的C處繼續(xù)執(zhí)行，執(zhí)行完子程序SUB2后要返回到子程序SUB1的地址B處。其中返回點地址B從棧頂取出，這時，棧的狀態(tài)為（A）。 （9）返回到子程序SUB1的B處繼續(xù)執(zhí)行，執(zhí)行完子程序SUB1后要返回到主程序MAIN的地址A處。其中返回點地址A從棧頂取出。取出A后，棧變?yōu)榭?，即棧的狀態(tài)為（）。（10）返回到

32、主程序MAIN的A處繼續(xù)執(zhí)行，直到主程序MAIN執(zhí)行完畢。由上述逐步返回的過程可以看出，當子程序返回到上一個調(diào)用程序時，需要從棧頂取出返回點地址，即對棧作出棧操作。由于各返回點地址在線性表中的存放順序恰好是對應的調(diào)用順序，因此，每次從棧頂取出的返回點地址正好對應了各次調(diào)用的正確返回順序。9.3.4 隊列的定義及其運算隊列的定義及其運算1隊列的定義隊列（equeue）簡稱隊，也是一種操作受限的線性表，它只允許在表的一端進行插入，而在表的另一端進行刪除的線性表。允許插入的一端稱為隊尾（rear），允許刪除的一端稱為隊首（front）。顯然，在隊列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將最先被刪除，反之，最

33、后插入的元素將最后才被刪除。所以，隊列又稱為“先進先出”（First In First Out，F(xiàn)IFO）或者“后進后出”（Last In Last Out， LILO）的線性表，它體現(xiàn)了“先來先服務”的原則。在隊列中，隊尾指針rear與隊首指針front共同反映了隊列中元素動態(tài)變化的情況。如圖9.3.5所示是具有5個元素的隊列示意圖。圖9.3.5 具有5個元素的隊列示意圖向隊列的尾部插入一個元素稱為入隊運算，從隊列的頭部刪除一個元素稱為出隊運算。如圖9.3.6所示在隊列中進行插入與刪除的示意圖。由圖9.3.6可看出，入隊運算只涉及尾指針rear的變化，而出隊運算只涉及頭指針front的變化。

34、圖9.3.6 隊列的插入與刪除運算 2隊列的基本運算（1）建立空隊列。（2）判定隊列是否為空。（3）入隊，在隊尾插入元素。（4）出隊，刪除隊首元素。（5）返回隊首元素。9.3.5 隊列的存儲結(jié)構(gòu)隊列的存儲結(jié)構(gòu)線性表的存儲結(jié)構(gòu)同樣適用于隊列，也可根據(jù)不同的應用場合分別采用順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。 1隊列的順序存儲結(jié)構(gòu)順序隊列在程序設計語言中，一般要用一維數(shù)組作為隊列的順序存儲空間，同時尚需附設兩個指針front和 rear分別指示隊列頭元素及隊列尾元素的位置。為了在C語言中描述方便，我們約定：用隊尾指針rear指向隊列中的隊尾元素，用隊首指針front指向頭元素的前一個位置。每當插入新的隊列

35、尾元素時，“尾指針增1”；每當刪除隊列頭元素時，“頭指針增1”。 若對存儲隊列的數(shù)組空間采用動態(tài)分配，則順序隊列的結(jié)構(gòu)類型可定義如下： typedef struct ElemType *base;/*初始化的動態(tài)分配存儲空間*/ int front;/*頭指針，若隊列不空，則指向隊列頭元素*/ int rear;/*尾指針，若隊列不空，則指向隊列尾元素的下一位置*/SqQueue;假設為某隊列分配的最大空間為n，則當隊尾指針指向數(shù)組空間的最后一個位置時，不能再繼續(xù)插入新的隊尾元素，否則會因數(shù)組越界而導致程序代碼被破壞。然而此時又不適合進行存儲再分配擴大數(shù)組空間，因為隊列的實際可用空間可能并未占

36、滿。一個巧妙的方法是采用循環(huán)隊列。所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用，如圖9.3.7所示。在循環(huán)隊列結(jié)構(gòu)中，當存儲空間的最后一個位置已被使用而再要進行入隊運算時，只要存儲空間的第一個位置空閑，便可將元素加入到第一個位置，即將存儲空間的第一個位置作為隊尾。循環(huán)隊列的初始狀態(tài)為空，即rear=front=0，如圖9.3.7所示。圖9.3.7 循環(huán)隊列存儲空間示意圖在循環(huán)隊列中，每進行一次入隊的運算，隊尾指針就加1，當隊尾指針rear=m+1時，置rear=0；每進行一次出隊運算，隊首指針就加1，當隊首指針front=m+1時，置fro

37、nt=0。下面介紹順序隊列的建立、插入和刪除算法。（1）建立空隊列。Init_Queue(SqQueue *Q) 2隊列的鏈式存儲結(jié)構(gòu)鏈隊列如果應用程序中使用順序隊列，則必須為它設定一個最大的隊列長度，但這樣往往會造成存儲空間的浪費；當無法預先估計所用隊列的最大長度時，則宜采用鏈式存儲結(jié)構(gòu)，即鏈隊列，如圖9.3.8所示。鏈隊列的操作即為單鏈表的插入和刪除操作的特殊情況，只是同時需要修改尾指針或頭指針，如圖9.3.9所示為進行這兩種操作時指針變化的情況。圖9.3.8 鏈隊列示意圖圖9.3.9 鏈隊列操作指針變化情況 假定鏈隊列的節(jié)點類型類似于前面定義的單鏈表節(jié)點類型，定義如下：9.3.6 隊列的

38、應用隊列的應用這里從兩個方面簡述隊列在計算機科學領域中的應用：一是解決主機與外部設備之間速度不匹配的問題，二是解決由多用戶引起的資源競爭問題。對于第一個方面，這里以主機和打印機之間速度不匹配的問題為例進行簡要說明。主機輸出數(shù)據(jù)給打印機，輸出數(shù)據(jù)的速度比打印數(shù)據(jù)的速度要快得多，若直接把輸出的數(shù)據(jù)送給打印機打印，則由于速度不匹配，顯然是不行的。所以解決的方法是設置一個打印數(shù)據(jù)緩沖區(qū)，主機把需要打印的數(shù)據(jù)依次寫入到這個緩沖區(qū)中，寫滿后就暫停寫入，轉(zhuǎn)去做其他的事情；打印機就從緩沖區(qū)中按照先進先出的隊列操作原則依次取出數(shù)據(jù)并打印，打印完后再向主機發(fā)出請求，主機接到請求后再向緩沖區(qū)寫入打印數(shù)據(jù)，這樣做既保

39、證了打印數(shù)據(jù)的正確性，又提高了主機的效率。由此可見，在打印數(shù)據(jù)緩沖區(qū)中所存儲的數(shù)據(jù)就是一個隊列。對于第二個方面，CPU資源的競爭也是一個典型的例子。在一個帶有多終端的計算機系統(tǒng)上，有多個用戶需要CPU運行自己的程序，它們分別通過各自終端向操作系統(tǒng)提出占用CPU的請求，操作系統(tǒng)通常按照每個請求在時間上的先后順序，把它們排成一個隊列，每次把CPU分配給隊首請求的用戶使用，當相應的程序運行結(jié)束或用完規(guī)定的時間間隔后，則令其出隊，再把CPU分配給新的隊首請求的用戶使用，這樣既滿足了每個用戶的請求，又使CPU能夠正常運行。9.4 樹和二叉樹 樹型結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)，它與線性結(jié)構(gòu)的最大區(qū)別在于：在

40、這種結(jié)構(gòu)中，除去根節(jié)點外每個節(jié)點最多只能和上層的一個節(jié)點相關，除葉子節(jié)點外每個節(jié)點都可以和下層的多個節(jié)點相關，節(jié)點間存在著明顯的分支和層次關系。樹型結(jié)構(gòu)在客觀世界中廣泛存在，例如家族關系中的家譜、各種社會組織機構(gòu)等，都可以形象地用樹型結(jié)構(gòu)表示；在計算機軟件技術(shù)中，樹型結(jié)構(gòu)也得到廣泛的應用，例如操作系統(tǒng)中的目錄（樹型）結(jié)構(gòu)、高級語言中源程序的語法結(jié)構(gòu)等。本節(jié)主要討論樹和二叉樹的定義及其存儲結(jié)構(gòu)。9.4.1 樹的定義及其存儲結(jié)構(gòu)樹的定義及其存儲結(jié)構(gòu)1樹的定義和術(shù)語樹（tree）是由n個（n0）節(jié)點組成的有限集合T，其中有且僅有一個節(jié)點稱為根節(jié)點（root），其余節(jié)點可分為m（m0）個互不相交的有限

41、集合T1，T2，Tm，其中每個集合Ti本身又是一棵樹，稱為根節(jié)點root的子樹。當n =0時稱為空樹。 這是一個遞歸的描述，即在描述樹時又用到樹本身這個術(shù)語。如圖9.4.1所示為一棵樹，A為根節(jié)點，其余節(jié)點分為3個不相交的子集T1=B,E,F,K,L，T2=C,G，T3=D,H,I,J,M，它們均為根節(jié)點 A下的3棵子樹，而這3棵子樹本身也是樹。圖9.4.1 樹樹型結(jié)構(gòu)中常用的術(shù)語有：（1）節(jié)點（node）：表示樹中的元素。（2）節(jié)點的度（degree）：節(jié)點擁有的子樹數(shù)，如圖9.4.1中節(jié)點D的度為3，C的度為1。一棵 樹中最大的節(jié)點度數(shù)為這棵樹的度，如圖9.4.1所示的樹的度為3。（3）葉

42、子（leaf）：度為零節(jié)點，又稱端節(jié)點。（4）孩子（child）：除根節(jié)點外，每個節(jié)點都是其前驅(qū)節(jié)點的孩子。（5）雙親（parents）：對應上述孩子節(jié)點的上層節(jié)點稱為這些節(jié)點的雙親。（6）兄弟（sibling）：同一雙親的孩子。（7）節(jié)點的層次（level）：從根節(jié)點開始算起，根為第一層，根的直接后繼節(jié)點為第二層，其余各層以此類推。例如圖9.4.1中的節(jié)點K，L和M都在第4層。（8）深度（depth）：樹中節(jié)點的最大層次數(shù)。如圖9.4.1中樹的深度為4。 （9）森林（forest）：是m（m0）棵互不相交的樹的集合。（10）有序樹、無序樹：樹中節(jié)點在同層中按從左至右有序排列、不能互換的稱為有

43、序樹，并把各子樹分別稱為第一子樹，第二子樹反之稱為無序樹。2樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)根據(jù)應用可以有多種形式，如常見的順序存儲和鏈式存儲結(jié)構(gòu)等，但由于樹是非線性結(jié)構(gòu)，因此常采用鏈式存儲結(jié)構(gòu)來表示樹，在這里我們只介紹鏈式存儲結(jié)構(gòu)。因為樹是多分支非線性表，所以需要采用多重鏈表結(jié)構(gòu)，即每個節(jié)點設有多個指針域，其中每一個指針指向一棵子樹的根節(jié)點。對于每一個節(jié)點的結(jié)構(gòu)類型可以有兩種形式：一種是節(jié)點異構(gòu)型，它根據(jù)每個節(jié)點的子樹數(shù)設置相應的指針域，由于樹中每個節(jié)點的度數(shù)不盡相同，因此一棵樹中各節(jié)點的結(jié)構(gòu)形式也不同。這種結(jié)構(gòu)形式雖能節(jié)省存儲空間，但不方便運算；另一種是采用同構(gòu)型，即每個節(jié)點的指針域個數(shù)均為樹的度

44、數(shù)，這種形式運算方便，但會使鏈表中出現(xiàn)很多空鏈域，浪費空間，如圖9.4.2所示。假設有一棵具有n個節(jié)點的k叉樹，則有nk個指針域，其中有用的指針域為n1個，這時的空鏈域個數(shù)為nk(n1)=n(k1)+1個。 圖9.4.2 樹的鏈式存儲結(jié)構(gòu)由此可見，k越大則空鏈域所占比例也越高，其中k=2時空鏈域的比例最低，這就是我們下面要著重討論的二叉樹結(jié)構(gòu)。9.4.2 二叉樹二叉樹1二叉樹的定義二叉樹（binary tree）是n（n0）個節(jié)點的有限集合，它或為空樹（n=0），或由一個根節(jié)點和兩棵互不相交的分別稱為這個根的左子樹和右子樹的二叉樹構(gòu)成?？梢钥闯?，和樹的定義一樣，二叉樹也是遞歸定義的。應該引起注

45、意的是，二叉樹的節(jié)點的子樹有明確的左、右之分。2幾種特殊形式的二叉樹（1）滿二叉樹。深度為h且含有2h1個節(jié)點的二叉樹稱為滿二叉樹。如圖9.4.3所示為一棵深度為4的滿二叉樹，其節(jié)點的編號為自上至下，自左至右，共有241=15個節(jié)點。圖9.4.3 滿二叉樹 （2）完全二叉樹。如果一棵有n個節(jié)點的二叉樹，按與滿二叉樹相同的編號方式對節(jié)點進行編號，若樹中n個節(jié)點和滿二叉樹1n編號完全一致，則稱該樹為完全二叉樹，如圖9.4.4（a）所示。如圖9.4.4（b）所示的就不是完全二叉樹。圖9.4.4 完全二叉樹與非完全二叉樹 完全二叉樹具有以下特點： 1）葉子節(jié)點只在層次最大的兩層出現(xiàn)。 2）其中任一節(jié)點

46、，如果其左子樹深度為k，則其右子樹的深度為k或k1。（3）平衡二叉樹。平衡二叉樹又稱AVL樹，它或者是一顆空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，而且左子樹和右子樹的深度之差的絕對值不超過1。節(jié)點的左子樹深度減去它的右子樹深度定義為節(jié)點的平衡因子，所以，平衡二叉樹上所有節(jié)點的平衡因子只可能是1，0和1。只要二叉樹上有一個節(jié)點的平衡因子絕對值大于1，則該二叉樹就是不平衡的。如圖9.4.5（a）所示為平衡二叉樹，如圖9.4.5（b）所示為不平衡二叉樹。圖9.4.5 平衡二叉樹與不平衡二叉樹 3二叉樹的基本性質(zhì)性質(zhì)1：二叉樹的第i層上至多有2i-1（i1）個節(jié)點?？捎脭?shù)學

47、歸納法予以證明。性質(zhì)2：深度為h的二叉樹中至多含有2h1個節(jié)點。利用性質(zhì)1的結(jié)論可推導得出。性質(zhì)3：在任意二叉樹中，若有n0個葉子節(jié)點，n2個度為2的節(jié)點，則必有n0=n2+1。性質(zhì)4：具有n個節(jié)點的完全二叉樹的深度為log2n+1或log2( n+1)。性質(zhì)5：如果對一棵有n個節(jié)點的完全二叉樹（深度為log2n+1）的節(jié)點編號，從根節(jié)點開始，自上而下，自左而右，則對任一節(jié)點i(1in)有（1）如果i=l，則節(jié)點i是二叉樹的根，無雙親；如果i1，則其雙親是節(jié)點i/2 。（2）如果2in，則節(jié)點i無左孩子（節(jié)點i為葉子節(jié)點）；否則其左孩子是節(jié)點2i。（3）如果2i+1n，則節(jié)點i無右孩子；否則其

48、右孩子是節(jié)點2i+1。 【注意】符號x表示不大于x的最大整數(shù)，反之，x表示不小于x的最小整數(shù)。4二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)有順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)兩種。（1）順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)是將二叉樹的所有節(jié)點，按照一定的順序方式，存儲到一段連續(xù)的存儲單元中。節(jié)點的順序反映出節(jié)點之間的邏輯關系。對于滿二叉樹或完全二叉樹，可用順序存儲結(jié)構(gòu)將n個節(jié)點按自上而下、自左至右的順序依次存放在一段地址連續(xù)的存儲單元中，即按層存放。如用C語言定義一個完全二叉樹為anytype bn;為處理方便，我們定義數(shù)組長度為n+1，不用 b0，只用b1bn。一般的二叉樹雖然也可以按完全二叉樹的形式來存儲，但會造成存

49、儲空間的浪費。（2）鏈式存儲結(jié)構(gòu)。二叉樹通常都采用鏈式存儲。在這種存儲方式下，二叉樹的每個節(jié)點由數(shù)據(jù)域（data）、左指針域（Lchild）和右指針域（Rchild）組成，即鏈式存儲不要求各個節(jié)點的存儲空間連續(xù)，二叉樹的這種存儲結(jié)構(gòu)也稱為二叉鏈表，如圖9.4.6（a）所示二叉樹的二叉鏈表如圖9.4.6（b）所示。圖9.4.6 二叉樹二叉鏈表節(jié)點描述如下：typedef int datatype;typedef struct node datatype data; struct node *lchild,*rchild;BTnode;BTnode *root;其中，root是指向根節(jié)點的頭指針，

50、當二叉樹為空時，rootNULL。當節(jié)點某個孩子不存在時，相應的指針為空。5一般樹轉(zhuǎn)換為二叉樹為了使一般樹也能像二叉樹一樣用二叉鏈表表示，必須找出樹與二叉樹間的對應關系。這樣當給定一棵樹時，可找到唯一的一棵二叉樹與之對應，而且這種關系的逆變換也是存在的。在這里只介紹變換的方法，對于變換過程的唯一性不作證明。將一般樹轉(zhuǎn)換為二叉樹的步驟如下：（1）在兄弟節(jié)點之間加一連線。（2）對每個節(jié)點，除了保留與其左孩子的連線外，去除與其他孩子間的連線。（3）以樹根為軸心，將整棵樹順時針旋轉(zhuǎn)45。如圖9.4.7（a），（b），（c）所示為一般樹轉(zhuǎn)換為二叉樹的過程。圖9.4.7 一般樹轉(zhuǎn)換為二叉樹由轉(zhuǎn)換結(jié)果可以看

51、出，任何一棵樹轉(zhuǎn)換成二叉樹，其右子樹必為空。9.4.3 二叉樹的遍歷二叉樹的遍歷遍歷（traversing）是指按照某條搜索路線，依次訪問某數(shù)據(jù)結(jié)構(gòu)中的全部節(jié)點，而且每個節(jié)點只被訪問一次。對于線性結(jié)構(gòu)來說，遍歷很容易實現(xiàn)，只需順序訪問每個節(jié)點即可；但是對于非線性結(jié)構(gòu)來說，則要人為設定搜索的路徑，路徑即連接兩個節(jié)點的邊的集合。 遍歷是二叉樹中最重要的運算。按照搜索路徑的不同，二叉樹的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方式。 1深度優(yōu)先遍歷 一棵非空二叉樹是由根節(jié)點、左子樹和右子樹 3個基本部分組成的，深度優(yōu)先遍歷二叉樹就是依次遍歷這3部分。若我們以D，L，R分別表示訪問根節(jié)點、遍歷左子樹和遍

52、歷右子樹，則按順序排列可以有DLR，LDR，LRD，DRL，RDL和RLD 6種遍歷形式。 若規(guī)定先左后右，那么上述6種形式可以歸并成下述3種形式： DLR：先序遍歷； LDR：中序遍歷； LRD：后序遍歷。由于二叉樹是遞歸定義，因此用遞歸方式描述二叉樹的深度優(yōu)先遍歷較清楚。如先序遍歷可定義為：若二叉樹為空，則為空操作，否則先訪問根節(jié)點，然后先序遍歷左子樹，再先序遍歷右子樹。這里在遍歷左、右子樹時遞歸應用先序遍歷的定義。對于中序、后序遍歷的定義與此類似，不再贅述。由上述遍歷的定義可知，用不同的遍歷方式對同一棵二叉樹進行遍歷，可以得到不同的節(jié)點序列。以如圖9.4.8所示的二叉樹為例，分別用3種遍

53、歷方式遍歷的結(jié)果如下：圖9.4.8 遍歷二叉樹先序：ABCDEFG；中序：CBDAEFG；后序：CDBGFEA。由遍歷的定義可以看出，遍歷左、右子樹的問題仍然是遍歷二叉樹的問題，當二叉樹為空時遞歸結(jié)束，所以很容易給出這3種遍歷的遞歸算法。算法中參量p是指向當前遍歷二叉樹的根節(jié)點指針,函數(shù)Visit表示訪問當前遍歷的節(jié)點。 Post_Order(plchild); /*后序遍歷左子樹*/ Post_Order(prchild); /*后序遍歷右子樹*/ Visit(pdata); /*訪問根節(jié)點*/在這3種遍歷算法中，訪問根節(jié)點的操作Visit可視具體應用情況而定。 2廣度優(yōu)先遍歷二叉樹的廣度優(yōu)

54、先遍歷又稱為按層次遍歷，這種遍歷方式是先遍歷二叉樹的第一層節(jié)點，然后遍歷第二層節(jié)點，最后遍歷最下層的節(jié)點，而對每一層的遍歷是按從左至右的方式進行的。對如圖9.4.8所示的二叉樹進行廣度優(yōu)先遍歷，可得到遍歷序列ABECDFG。廣度優(yōu)先遍歷算法一般需使用一個隊列，開始時把整個樹的根節(jié)點入隊，然后每從隊列中刪除一個節(jié)點并輸出該節(jié)點的值時，都把它的非空左、右孩子節(jié)點入隊，當隊列為空時算法結(jié)束。9.4.4 二叉樹的應用二叉樹的應用二叉樹是一種非常有用的樹型結(jié)構(gòu)，其應用十分廣泛。例如在通信中，對于概率不等的數(shù)據(jù)的發(fā)送，為使傳送的代碼長度最短，使用了哈夫曼編碼，其結(jié)構(gòu)就稱哈夫曼樹。除此之外二叉樹的應用還有二

55、叉排序樹與表達式樹等，在這里以二叉排序樹作為應用的一個例子。二叉排序樹是一種特殊結(jié)構(gòu)的二叉樹，它或是空樹或是具有下述性質(zhì)的二叉樹：（1）其左子樹上所有節(jié)點的數(shù)據(jù)值均小于根節(jié)點的數(shù)值。（2）其右子樹上所有節(jié)點的數(shù)據(jù)值均大于或等于根節(jié)點的數(shù)據(jù)值。（3）左子樹和右子樹又各是一棵二叉排序樹。如圖9.4.9所示就是一棵二叉排序樹。圖9.4.9 二叉樹的排序在二叉排序樹中，若按中序遍歷就可以得到由 小到大的有序序列，如圖9.4.9所示的二叉排序樹，中序遍歷可得有序序列2，5，6，7，9，11，14， 16，19，21。二叉排序樹是一種動態(tài)表結(jié)構(gòu)，也就是說二叉 排序樹的生成過程是不斷地向二叉排序樹中插入新

56、的節(jié)點。對任意的一組數(shù)據(jù)元素序列R1，R2，Rn，生成一棵二叉排序樹的過程為（1）令R1為二叉排序樹的根節(jié)點。（2）若R2R1，則令R2為R1的左子樹的根節(jié)點；否則R2為R1的右子樹的根節(jié)點。（3）R3，Rn節(jié)點的插入方法同上。如圖9.4.10所示為將序列11，18，3，9，12，2，7，5構(gòu)成一棵二叉排序樹的過程。從以上插入過程可以看出，每次插入的新節(jié)點都是二叉排序樹上新的葉子節(jié)點，因此在進行插入操作時不必移動其他節(jié)點。這一特性適用于需要經(jīng)常插入有序表的場合。圖9.4.10 二叉排序樹插入過程9.5 圖 圖（graph）是一種比樹和二叉樹更為復雜的非線性數(shù)據(jù)結(jié)構(gòu)。在圖這種數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)節(jié)點

57、之間的關系是任意的，因此，圖這種數(shù)據(jù)結(jié)構(gòu)可以更廣泛地表示數(shù)據(jù)元素之間的關系?？梢哉f，樹和二叉樹是圖的特例，也可以說，樹和二叉樹是最簡單的圖。本節(jié)簡要介紹圖的基本概念、存儲結(jié)構(gòu)以及遍歷。9.5.1 圖的定義及其基本操作圖的定義及其基本操作1圖的定義和術(shù)語如果數(shù)據(jù)元素集合D中的各數(shù)據(jù)元素之間存在任意的直接前驅(qū)或直接后繼關系，則此數(shù)據(jù)結(jié)構(gòu)稱為圖，通常用G表示。G是一個有序?qū)Γ╒，E），記作G=（V，E），V是一個非空有限集合，它的元素稱為頂點（vertex）；E是由V中兩個元素vi.，vj組成的序偶或無序?qū)Φ募?，E的元素稱為邊（edge）。圖分為有向圖和無向圖。在有向圖中，每個邊都是有方向的，又稱

58、為弧，兩頂點間弧的流向只能朝一個指定方向。在無向圖中，邊是沒有方向的，兩頂點間的流向可以朝任意一個方向。在無向圖中，用不帶箭頭的邊來連接兩個有關聯(lián)的節(jié)點（表示這兩個節(jié)點互為直接前驅(qū)和直接后繼關系），如圖9.5.1所示為兩個無向圖。若任意兩個節(jié)點之間存在路徑，則稱該無向圖為連通圖。圖9.5.1 無向圖在有向圖中，通常用帶有箭頭的邊（路徑）來連接兩個有關聯(lián)的頂點（由直接前驅(qū)節(jié)點指向直接后繼節(jié)點）。如圖9.5.2所示為兩個有向圖。若任意一對頂點之間都存在路徑，則稱該有向圖為強連通圖，如圖9.5.2（b）所示。圖9.5.2 有向圖在具有n個頂點的無向圖中，邊的最大數(shù)目為n(n1)/2。邊數(shù)達最大值的無

59、向圖稱為無向完全圖。若一個有向圖中每一對頂點之間都存在兩條不同方向的邊，則稱該有向圖為有向完全圖，此時在n個頂點的有向圖中，其邊數(shù)為n(n1)。在圖中，一個頂點的直接后繼個數(shù)稱為該頂點的出度，其直接前驅(qū)個數(shù)稱為該頂點的入度。一個頂點的入度與出度之和稱為該頂點的度。對于無向圖來說，其中每一個頂點的入度等于該頂點的出度。圖中頂點的最大度稱為圖的度。 實際應用中，圖中的每條邊可以標上具有某種含義的數(shù)值，此數(shù)值稱為該邊的權(quán)（weight）；邊上帶有權(quán)的圖稱做帶權(quán)圖，也稱做網(wǎng)（network）。帶權(quán)圖有著極為廣泛的應用，例如，在用圖表示有公共交通聯(lián)系的一組城市時，帶權(quán)圖可以表示每兩個城市（即圖中兩個頂點

60、）之間的距離、車費、班次數(shù)目等。2圖的基本運算由于圖中的任何一個頂點都可看成第一個頂點，因此任一頂點的鄰接點之間不存在次序問題。為了操作方便，人為地將圖中的頂點按一定順序排列起來，這就出現(xiàn)了對頂點和其鄰接點的相應操作，下面列出圖的幾種基本運算：（1）定位頂點。（2）取頂點。（3）求第一個鄰接點。（4）求下一個鄰接點。（5）插入頂點。 （6）插入弧。（7）刪除頂點。（8）刪除弧。9.5.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)由于圖的結(jié)構(gòu)比較復雜，圖中任意兩個頂點之間都有可能存在聯(lián)系，因此無法用數(shù)據(jù)元素在存儲空間中的物理位置來表示各數(shù)據(jù)元素之間的直接前驅(qū)和直接后繼關系。圖的存儲方法很多，常用的有鄰接矩陣法、