1、 目錄TOC o ”13 h u HYPERLINK l _Toc16289 緒論 PAGEREF _Toc16289 3 HYPERLINK l _Toc29067 0.1 基本概念 PAGEREF _Toc29067 3 HYPERLINK l _Toc19513 第一章 線性表 PAGEREF _Toc19513 4 HYPERLINK l _Toc2204 1.1 線性表的定義 PAGEREF _Toc2204 4 HYPERLINK l _Toc21787 1.2 線性表的實現(xiàn) PAGEREF _Toc21787 4 HYPERLINK l _Toc30163 1。2。2 線性表的鏈

2、式存儲結(jié)構(gòu) PAGEREF _Toc30163 6 HYPERLINK l _Toc8061 第二章 棧、隊列和數(shù)組 PAGEREF _Toc8061 11 HYPERLINK l _Toc25533 2。1 棧 PAGEREF _Toc25533 11 HYPERLINK l _Toc25914 2。2 隊列 PAGEREF _Toc25914 15 HYPERLINK l _Toc60 2.3 特殊矩陣的壓縮存儲 PAGEREF _Toc60 17 HYPERLINK l _Toc29239 2。3.1 數(shù)組 PAGEREF _Toc29239 17 HYPERLINK l _Toc120

3、13 2.3.2 特殊矩陣 PAGEREF _Toc12013 17 HYPERLINK l _Toc28106 第三章 樹與二叉樹 PAGEREF _Toc28106 20 HYPERLINK l _Toc2924 3.1 樹的概念 PAGEREF _Toc2924 20 HYPERLINK l _Toc14405 1。樹的定義 PAGEREF _Toc14405 20 HYPERLINK l _Toc9000 2相關(guān)術(shù)語 PAGEREF _Toc9000 20 HYPERLINK l _Toc17959 3.2 二叉樹 PAGEREF _Toc17959 21 HYPERLINK l _T

4、oc19043 3.2.1 定義與性質(zhì) PAGEREF _Toc19043 21 HYPERLINK l _Toc28025 3。2.2 二叉樹的存儲 PAGEREF _Toc28025 22 HYPERLINK l _Toc20103 3.2。3 二叉樹的遍歷 PAGEREF _Toc20103 23 HYPERLINK l _Toc32605 3.2.4 線索二叉樹 PAGEREF _Toc32605 25 HYPERLINK l _Toc6155 3.3 樹和森林 PAGEREF _Toc6155 29 HYPERLINK l _Toc5857 3.3.1 樹的存儲結(jié)構(gòu) PAGEREF

5、_Toc5857 29 HYPERLINK l _Toc8301 3。3.2 森林和二叉樹的轉(zhuǎn)換 PAGEREF _Toc8301 30 HYPERLINK l _Toc3982 3.3。3 樹和森林的遍歷 PAGEREF _Toc3982 30 HYPERLINK l _Toc1296 3。4 哈夫曼（ Huffman)樹和哈夫曼編碼 PAGEREF _Toc1296 31 HYPERLINK l _Toc26956 第四章 圖 PAGEREF _Toc26956 32 HYPERLINK l _Toc1537 4.1 圖的概念 PAGEREF _Toc1537 32 HYPERLINK l

6、 _Toc19604 4。2 圖的存儲及基本操作 PAGEREF _Toc19604 33 HYPERLINK l _Toc30705 4.2.1 鄰接矩陣 PAGEREF _Toc30705 33 HYPERLINK l _Toc14601 4。2。2 鄰接表 PAGEREF _Toc14601 33 HYPERLINK l _Toc10978 4。3 圖的遍歷 PAGEREF _Toc10978 35 HYPERLINK l _Toc31208 4.3.1 深度優(yōu)先搜索 PAGEREF _Toc31208 35 HYPERLINK l _Toc4952 4。3。2 廣度優(yōu)先搜索 PAGER

7、EF _Toc4952 35 HYPERLINK l _Toc5874 4.4 圖的基本應(yīng)用 PAGEREF _Toc5874 37 HYPERLINK l _Toc12822 4。4.1 最小生成樹 PAGEREF _Toc12822 37 HYPERLINK l _Toc28098 4.4。2 最短路徑 PAGEREF _Toc28098 37 HYPERLINK l _Toc22183 4.4.3 拓撲排序 PAGEREF _Toc22183 39 HYPERLINK l _Toc16042 4。4。4 關(guān)鍵路徑 PAGEREF _Toc16042 40 HYPERLINK l _Toc

8、31555 第五章 查找 PAGEREF _Toc31555 42 HYPERLINK l _Toc4482 5。1 查找的基本概念 PAGEREF _Toc4482 42 HYPERLINK l _Toc11475 5.2 順序查找法 PAGEREF _Toc11475 43 HYPERLINK l _Toc14882 5.3 折半查找法 PAGEREF _Toc14882 44 HYPERLINK l _Toc18465 5。4 動態(tài)查找樹表 PAGEREF _Toc18465 45 HYPERLINK l _Toc16719 5.4.1 二叉排序樹 PAGEREF _Toc16719 4

9、5 HYPERLINK l _Toc23925 5.4.2 平衡二叉樹 PAGEREF _Toc23925 47 HYPERLINK l _Toc24162 5.4。3B 樹及其基本操作、 B+樹的基本概念 PAGEREF _Toc24162 49 HYPERLINK l _Toc22063 5。5 散列表 PAGEREF _Toc22063 51 HYPERLINK l _Toc20222 5。5.2 常用的散列函數(shù) PAGEREF _Toc20222 51 HYPERLINK l _Toc5150 5。5.3 處理沖突的方法 PAGEREF _Toc5150 52 HYPERLINK l

10、_Toc1414 5.5。4 散列表的查找 PAGEREF _Toc1414 52 HYPERLINK l _Toc16549 5。5.5 散列表的查找分析 PAGEREF _Toc16549 53 HYPERLINK l _Toc11317 第六章 排序 PAGEREF _Toc11317 54 HYPERLINK l _Toc29163 6。1 插入排序 PAGEREF _Toc29163 54 HYPERLINK l _Toc10758 6。1。1 直接插入排序 PAGEREF _Toc10758 54 HYPERLINK l _Toc32720 6。1。2 折半插入排序 PAGEREF

11、 _Toc32720 54 HYPERLINK l _Toc23898 6。2 冒泡排序 PAGEREF _Toc23898 55 HYPERLINK l _Toc18235 6.3 簡單選擇排序 PAGEREF _Toc18235 56 HYPERLINK l _Toc4552 6。4 希爾排序 PAGEREF _Toc4552 57 HYPERLINK l _Toc10883 6.5 快速排序 PAGEREF _Toc10883 58 HYPERLINK l _Toc1116 6。6 堆排序 PAGEREF _Toc1116 60 HYPERLINK l _Toc8991 6。7 二路歸并

12、排序 PAGEREF _Toc8991 62 HYPERLINK l _Toc14493 6。8 基數(shù)排序 PAGEREF _Toc14493 63 HYPERLINK l _Toc32449 6.9 各種內(nèi)部排序算法的比較 PAGEREF _Toc32449 64緒論0.1 基本概念1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是一個二元組 Data_Structure （ D， R)，其中， D 是數(shù)據(jù)元素的有限集, R 是D 上關(guān)系的有限集。2、邏輯結(jié)構(gòu)：是指數(shù)據(jù)之間的相互關(guān)系。通常分為四類結(jié)構(gòu)：（ 1）集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它

13、關(guān)系。（ 2)線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系.（ 3）樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。( 4）圖狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。3、存儲結(jié)構(gòu)：是指數(shù)據(jù)結(jié)構(gòu)在計算機中的表示,又稱為數(shù)據(jù)的物理結(jié)構(gòu)。通常由四種基本的存儲方法實現(xiàn)：（ 1）順序存儲方式。數(shù)據(jù)元素順序存放，每個存儲結(jié)點只含一個元素。存儲位置反映數(shù)據(jù)元素間的邏輯關(guān)系.存儲密度大。但有些操作（如插入、刪除)效率較差。（ 2）鏈式存儲方式.每個存儲結(jié)點除包含數(shù)據(jù)元素信息外還包含一組（至少一個）指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲空間連續(xù)，便于動態(tài)操作（如插入、刪除等），但存儲空間

14、開銷大（用于指針),另外不能折半查找等。（ 3)索引存儲方式。除數(shù)據(jù)元素存儲在一組地址連續(xù)的內(nèi)存空間外，還需建立一個索引表，索引表中索引指示存儲結(jié)點的存儲位置（下標)或存儲區(qū)間端點(下標）。( 4）散列存儲方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲地址。其特點是存取速度快，只能按關(guān)鍵字隨機存取,不能順序存取，也不能折半存取。2 算法和算法的衡量1、算法是對特定問題求解步驟的一種描述，是指令的有限序列.其中每一條指令表示一個或多個操作。算法具有下列特性：有窮性確定性可行性輸入輸出。算法和程序十分相似，但又有區(qū)別.程序不一定

15、具有有窮性，程序中的指令必須是機器可執(zhí)行的，而算法中的指令則無此限制。算法代表了對問題的解，而程序則是算法在計算機上的特定的實現(xiàn).一個算法若用程序設(shè)計語言來描述,則它就是一個程序。2、算法的時間復雜度：以基本運算的原操作重復執(zhí)行的次數(shù)作為算法的時間度量.一般情況下，算法中基本運算次數(shù) T（n）是問題規(guī)模 n(輸入量的多少,稱之為問題規(guī)模）的某個函數(shù)f(n),記作：T（n） （f(n)；也可表示 T（n） m(f（n）)，其中 m 為常量.記號“O”讀作“大 O”，它表示隨問題規(guī)模 n 的增大，算法執(zhí)行時間 T(n）的增長率和 f(n）的增長率相同。注意：有的情況下，算法中基本操作重復執(zhí)行的次數(shù)

16、還隨問題的輸入數(shù)據(jù)集不同而不同。常見的漸進時間復雜度有：（1)(log2n）（n)（nlog2n）（n2）（n3）(2n） O（n！) O（nn）。3、算法的空間復雜度：是對一個算法在運行過程中臨時占用的存儲空間大小的量度.只需要分析除輸入和程序之外的輔助變量所占額外空間.原地工作:若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作，空間復雜度為 O（1)。第一章 線性表1。1 線性表的定義線性表是一種線性結(jié)構(gòu),在一個線性表中數(shù)據(jù)元素的類型是相同的，或者說線性表是由同一類型的數(shù)據(jù)元素構(gòu)成的線性結(jié)構(gòu)，定義如下：線性表是具有相同數(shù)據(jù)類型的n（n0)個數(shù)據(jù)元素的有限序列，通常記為：(a1

17、， a2， ai1， ai， ai+1， an）其中n為表長， n0 時稱為空表。需要說明的是： ai為序號為 i 的數(shù)據(jù)元素（ i=1,2，n）,通常將它的數(shù)據(jù)類型抽象為ElemType， ElemType根據(jù)具體問題而定。1。2 線性表的實現(xiàn)1。2.1 線性表的順序存儲結(jié)構(gòu)1。順序表線性表的順序存儲是指在內(nèi)存中用地址連續(xù)的一塊存儲空間順序存放線性表的各元素,用這種存儲形式存儲的線性表稱其為順序表.因為內(nèi)存中的地址空間是線性的，因此,用物理上的相鄰實現(xiàn)數(shù)據(jù)元素之間的邏輯相鄰關(guān)系是既簡單又自然的。設(shè)a的存儲地址為Loc(a)，每個數(shù)據(jù)元素占d個存儲地址,則第i個數(shù)據(jù)元素的地址為：Loc（ai）

18、=Loc(a）+（i-1）d 1in這就是說只要知道順序表首地址和每個數(shù)據(jù)元素所占地址單元的個數(shù)就可求出第i個數(shù)據(jù)元素的地址來，這也是順序表具有按數(shù)據(jù)元素的序號隨機存取的特點。線性表的動態(tài)分配順序存儲結(jié)構(gòu)：define LIST_INIT_SIZE 100 /存儲空間的初始分配量define LISTINCREMENT 10 /存儲空間的分配增量typedef structElemType *elem; /線性表的存儲空間基址int length; /當前長度int listsize; /當前已分配的存儲空間SqList;2。順序表上基本運算的實現(xiàn)（ 1）順序表的初始化順序表的初始化即構(gòu)造一個

19、空表, 這對表是一個加工型的運算， 因此， 將L設(shè)為引用參數(shù)，首先動態(tài)分配存儲空間，然后,將length置為0,表示表中沒有數(shù)據(jù)元素。int Init_SqList (SqList L）L.elem = （ElemType )malloc（LIST_INIT_SIZE * sizeof(ElemType）)；if (！L。elem） exit (OVERFLOW); /存儲分配失敗L.length=0;L。 listsize = LIST_INIT_SIZE； /初始存儲容量return OK;( 2）插入運算線性表的插入是指在表的第i（i的取值范圍: 1in+1）個位置上插入一個值為 x 的

20、新元素，插入后使原表長為 n的表:(a1, a2， .。. ， ai-1， ai， ai+1， 。. ， an)成為表長為 n+1 表:(a1, a2, .。， ai1， x, ai， ai+1， .。., an ） .順序表上完成這一運算則通過以下步驟進行： 將aian 順序向下移動，為新元素讓出位置；（注意數(shù)據(jù)的移動方向：從后往前依次后移一個元素） 將 x 置入空出的第i個位置； 修改表長.int Insert_SqList (SqList L, int i， ElemType x）if （i 1 | i L。length+1) return ERROR； / 插入位置不合法if （L.l

21、ength = L.listsize) return OVERFLOW； / 當前存儲空間已滿,不能插入/需注意的是，若是采用動態(tài)分配的順序表，當存儲空間已滿時也可增加分配q = (L。elemi-1)； / q 指示插入位置for （p = &（L.elemL.length1）； p = q; -p)*(p+1） = p； / 插入位置及之后的元素右移*q = e; / 插入e+L.length; / 表長增1return OK;順序表上的插入運算， 時間主要消耗在了數(shù)據(jù)的移動上， 在第i個位置上插入 x , 從 ai 到an 都要向下移動一個位置，共需要移動 ni1個元素.（ 3）刪除運算

22、線性表的刪除運算是指將表中第 i （ i 的取值范圍為 : 1 in）個元素從線性表中去掉,刪除后使原表長為 n 的線性表：（a1， a2， .。 ， ai1, ai， ai+1， 。.， an)成為表長為 n1 的線性表：（a1， a2, .。. ， ai1， ai+1， .。 ， an）.順序表上完成這一運算的步驟如下: 將ai+1an 順序向上移動；(注意數(shù)據(jù)的移動方向:從前往后依次前移一個元素） 修改表長。int Delete_SqList (SqList &L;int i） if (（i L。length）) return ERROR； / 刪除位置不合法p = &（L.elemi1

23、）; / p 為被刪除元素的位置e = p； / 被刪除元素的值賦給 eq = L.elem+L。length1； / 表尾元素的位置for （+p； p next=NULL; /空表LNode s,r=L；int x; /設(shè)數(shù)據(jù)元素的類型為intscanf（%d，&x）；while (x!=flag) s=（LNode *)malloc（sizeof(LNode)）;sdata=x；rnext=s；r=s； /r 指向新的尾結(jié)點scanf（%d,&x)；rnext=NULL；return L；因此，頭結(jié)點的加入會帶來以下兩個優(yōu)點：第一個優(yōu)點：由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中，所以在

24、鏈表的第一個位置上的操作就和在表的其它位置上的操作一致，無需進行特殊處理；第二個優(yōu)點：無論鏈表是否為空，其頭指針是指向頭結(jié)點在的非空指針（空表中頭結(jié)點的指針域為空），因此空表和非空表的處理也就統(tǒng)一了。在以后的算法中不加說明則認為單鏈表是帶頭結(jié)點的。(2）查找操作按序號查找 Get_LinkList(L,i）從鏈表的第一個元素結(jié)點起，判斷當前結(jié)點是否是第i個，若是，則返回該結(jié)點的指針，否則繼續(xù)后一個，表結(jié)束為止，沒有第個結(jié)點時返回空。LNode Get_LinkList(LinkList L, int i); LNode * p=L；int j=0；while （p-next ！=NULL ji

25、 ）p=pnext; j+；if （j=i) return p；else return NULL；（3）插入運算后插結(jié)點：設(shè)p指向單鏈表中某結(jié)點， s指向待插入的值為x的新結(jié)點，將*s插入到*p的后面，插入示意圖如圖所示.操作如下:snext=p-next；pnext=s;注意：兩個指針的操作順序不能交換。（4）刪除運算刪除結(jié)點設(shè)p指向單鏈表中某結(jié)點，刪除*p。操作過程如圖。要實現(xiàn)對結(jié)點*p的刪除，首先要找到*p的前驅(qū)結(jié)點q，然后完成指針的操作即可。操作如下：q=L;while (qnext!=p）q=qnext； /找p的直接前驅(qū)qnext=pnext；free(p)；因為找p前驅(qū)的時間復雜

26、度為O（n），所以該操作的時間復雜度為O（n）通過上面的基本操作我們得知：（1) 單鏈表上插入、刪除一個結(jié)點,必須知道其前驅(qū)結(jié)點。（2） 單鏈表不具有按序號隨機訪問的特點，只能從頭指針開始一個個順序進行。1.2。2.2 循環(huán)鏈表對于單鏈表而言，最后一個結(jié)點的指針域是空指針，如果將該鏈表頭指針置入該指針域,則使得鏈表頭尾結(jié)點相連，就構(gòu)成了單循環(huán)鏈表.在單循環(huán)鏈表上的操作基本上與非循環(huán)鏈表相同,只是將原來判斷指針是否為 NULL 變?yōu)槭欠袷穷^指針而已,沒有其它較大的變化。對于單鏈表只能從頭結(jié)點開始遍歷整個鏈表，而對于單循環(huán)鏈表則可以從表中任意結(jié)點開始遍歷整個鏈表,不僅如此,有時對鏈表常做的操作是在

27、表尾、表頭進行，此時可以改變一下鏈表的標識方法，不用頭指針而用一個指向尾結(jié)點的指針 R 來標識,可以使得操作效率得以提高。1。2.2.3 雙向鏈表單鏈表的結(jié)點中只有一個指向其后繼結(jié)點的指針域 next,因此若已知某結(jié)點的指針為 p，其后繼結(jié)點的指針則為 p-next ，而找其前驅(qū)則只能從該鏈表的頭指針開始,順著各結(jié)點的next 域進行,也就是說找后繼的時間性能是 O（1），找前驅(qū)的時間性能是 O（n），如果也希望找前驅(qū)的時間性能達到 O(1），則只能付出空間的代價:每個結(jié)點再加一個指向前驅(qū)的指針域，結(jié)點的結(jié)構(gòu)為如圖所示,用這種結(jié)點組成的鏈表稱為雙向鏈表。線性表的雙向鏈表存儲結(jié)構(gòu)C語言描述下：t

28、ypedef struct DuLNodeElemType data；struct DuLNode prior,next；DuLNode,DuLinkList;和單鏈表類似，雙向鏈表通常也是用頭指針標識,也可以帶頭結(jié)點。( 1）雙向鏈表中結(jié)點的插入:設(shè) p 指向雙向鏈表中某結(jié)點， s 指向待插入的值為 x 的新結(jié)點，將s 插入到*p 的前面，插入示意圖如所示.操作如下： s-prior=pprior; ppriornext=s; snext=p; pprior=s；指針操作的順序不是唯一的，但也不是任意的，操作必須要放到操作的前面完成，否則*p 的前驅(qū)結(jié)點的指針就丟掉了。( 2)雙向鏈表中結(jié)點

29、的刪除：設(shè) p 指向雙向鏈表中某結(jié)點,刪除p.操作示意圖如圖所示。操作如下：操作如下：p-prior-next=p-next;p-next-prior=p-prior;free(p);1。2.2.4 順序表和鏈表的比較總之,兩種存儲結(jié)構(gòu)各有長短，選擇那一種由實際問題中的主要因素決定。通常“較穩(wěn)定”的線性表選擇順序存儲，而頻繁做插入刪除的即動態(tài)性較強的線性表宜選擇鏈式存儲.第二章 棧、隊列和數(shù)組2.1 棧2。1.1 棧的定義棧是限制在表的一端進行插入和刪除的線性表。允許插入、刪除的這一端稱為棧頂，另一個固定端稱為棧底。當表中沒有元素時稱為空棧。2.1。2 棧的存儲實現(xiàn)和運算實現(xiàn)棧是運算受限的線性

30、表，線性表的存儲結(jié)構(gòu)對棧也是適用的，只是操作不同而已。利用順序存儲方式實現(xiàn)的棧稱為順序棧。與線性表類似，棧的動態(tài)分配順序存儲結(jié)構(gòu)如下:define STACK_INIT_SIZE 100 /存儲空間的初始分配量#define STACKINCREMENT 10 /存儲空間的分配增量typedef structSElemType base; /在棧構(gòu)造之前和銷毀之后， base 的值為 NULLSElemType *top； /棧頂指針int stacksize； /當前已分配的存儲空間SqStack；需要注意，在棧的動態(tài)分配順序存儲結(jié)構(gòu)中, base 始終指向棧底元素，非空棧中的 top始終在

31、棧頂元素的下一個位置。下面是順序棧上常用的基本操作的實現(xiàn)。（ 1）入棧：若棧不滿,則將 e 插入棧頂.int Push (SqStack &S, SElemType e) if （S。top-S。base=S。stacksize) /棧滿,追加存儲空間S.top+ = e；/top 始終在棧頂元素的下一個位置return OK；( 2）出棧：若棧不空，則刪除 S 的棧頂元素，用 e 返回其值，并返回 OK,否則返回ERROR.int Pop (SqStack S, SElemType e) if (S。top=S。base) return ERROR；e = -S。top;return OK;

32、出棧和讀棧頂元素操作，先判棧是否為空，為空時不能操作，否則產(chǎn)生錯誤。通常棧空常作為一種控制轉(zhuǎn)移的條件。2。1.3 棧的應(yīng)用舉例由于棧的“先進先出”特點，在很多實際問題中都利用棧做一個輔助的數(shù)據(jù)結(jié)構(gòu)來進行求解,下面通過幾個例子進行說明。1數(shù)制轉(zhuǎn)換十進制數(shù) N 和其他 d 進制數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題，其解決方法很多，其中一個簡單算法基于下列原理：假設(shè)現(xiàn)要編制一個滿足下列要求的程序:對于輸入的任意一個非負十進制整數(shù)，打印輸出與其等值的八進制數(shù)。由于上述計算過程是從低位到高位順序產(chǎn)生八進制數(shù)的各個數(shù)位,而打印輸出,一般來說應(yīng)從高位到低位進行，恰好和計算過程相反。因此，若將計算過程中得到的八

33、進制數(shù)的各位順序進棧，則按出棧序列打印輸出的即為與輸入對應(yīng)的八進制數(shù)。算法思想：當 N0 時重復( 1）,（ 2）（ 1)若 N0，則將 N % r 壓入棧 s 中 ,執(zhí)行（ 2） ；若 N=0，將棧 s 的內(nèi)容依次出棧，算法結(jié)束。（ 2)用 N / r 代替 N.void conversion (） InitStack(S)； / 構(gòu)造空棧scanf （%d，N）;while (N） Push(S， N 8)；N = N/8;while （!StackEmpty(S)） Pop（S,e);printf （ ”d, e ）；2。.表達式求值表達式求值是程序設(shè)計語言編譯中一個最基本的問題，它的實

34、現(xiàn)也是需要棧的加入.下面的算法是由運算符優(yōu)先法對表達式求值。在此僅限于討論只含二目運算符的算術(shù)表達式。（ 1)中綴表達式求值：中綴表達式：每個二目運算符在兩個運算量的中間,假設(shè)所討論的算術(shù)運算符包括： + 、- 、 、 /、 、 （乘方）和括號(）。設(shè)運算規(guī)則為：運算符的優(yōu)先級為：（) - -、 /、 %- +、 ;有括號出現(xiàn)時先算括號內(nèi)的,后算括號外的,多層括號，由內(nèi)向外進行;乘方連續(xù)出現(xiàn)時先算最右面的。表達式作為一個滿足表達式語法規(guī)則的串存儲,如表達式“3*2( 4+22*3） 5”，它的的求值過程為：自左向右掃描表達式，當掃描到 32 時不能馬上計算,因為后面可能還有更高的運算，正確的處

35、理過程是：需要兩個棧:對象棧 s1 和運算符棧 s2。當自左至右掃描表達式的每一個字符時，若當前字符是運算對象,入對象棧，是運算符時，若這個運算符比棧頂運算符高則入棧,繼續(xù)向后處理，若這個運算符比棧頂運算符低則從對象棧出棧兩個運算量，從運算符棧出棧一個運算符進行運算，并將其運算結(jié)果入對象棧，繼續(xù)處理當前字符，直到遇到結(jié)束符。中綴表達式表達式 “32（ 4+223） 5”求值過程中兩個棧的狀態(tài)情況見圖所示。圖 中綴表達式 32（ 4+2*2-1*3） -5 的求值過程為了處理方便，編譯程序常把中綴表達式首先轉(zhuǎn)換成等價的后綴表達式，后綴表達式的運算符在運算對象之后。在后綴表達式中，不在引入括號，所

36、有的計算按運算符出現(xiàn)的順序，嚴格從左向右進行,而不用再考慮運算規(guī)則和級別。中綴表達式“32（ 4+2*2-13) 5 ”的后綴表達式為： “32422+13*5。（ 2）后綴表達式求值計算一個后綴表達式，算法上比計算一個中綴表達式簡單的多。這是因為表達式中即無括號又無優(yōu)先級的約束。具體做法:只使用一個對象棧，當從左向右掃描表達式時,每遇到一個操作數(shù)就送入棧中保存,每遇到一個運算符就從棧中取出兩個操作數(shù)進行當前的計算,然后把結(jié)果再入棧，直到整個表達式結(jié)束,這時送入棧頂?shù)闹稻褪墙Y(jié)果。( 3) 中綴表達式轉(zhuǎn)換成后綴表達式：將中綴表達式轉(zhuǎn)化為后綴表達示和前述對中綴表達式求值的方法完全類似，但只需要運算

37、符棧，遇到運算對象時直接放后綴表達式的存儲區(qū)，假設(shè)中綴表達式本身合法且在字符數(shù)組 A 中，轉(zhuǎn)換后的后綴表達式存儲在字符數(shù)組 B 中。具體做法：遇到運算對象順序向存儲后綴表達式的 B 數(shù)組中存放，遇到運算符時類似于中綴表達式求值時對運算符的處理過程，但運算符出棧后不是進行相應(yīng)的運算，而是將其送入 B 中存放。具體算法在此不再贅述。3棧與遞歸在高級語言編制的程序中，調(diào)用函數(shù)與被調(diào)用函數(shù)之間的鏈接和信息交換必須通過棧進行。當在一個函數(shù)的運行期間調(diào)用另一個函數(shù)時，在運行該被調(diào)用函數(shù)之前,需先完成三件事：（ 1)將所有的實在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存；（ 2）為被調(diào)用函數(shù)的局部變量分配存儲

38、區(qū);（ 3)將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口.從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成:（ 1）保存被調(diào)函數(shù)的計算結(jié)果；（ 2）釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū);( 3)依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù).多個函數(shù)嵌套調(diào)用的規(guī)則是：后調(diào)用先返回，此時的內(nèi)存管理實行“棧式管理”。遞歸函數(shù)的調(diào)用類似于多層函數(shù)的嵌套調(diào)用，只是調(diào)用單位和被調(diào)用單位是同一個函數(shù)而已。在每次調(diào)用時系統(tǒng)將屬于各個遞歸層次的信息組成一個活動記錄( ActivaTion Record），這個記錄中包含著本層調(diào)用的實參、返回地址、局部變量等信息，并將這個活動記錄保存在系統(tǒng)的“遞歸工作棧”中，每當遞歸調(diào)用一次，就要在棧頂為過程建立一個新

39、的活動記錄，一旦本次調(diào)用結(jié)束,則將棧頂活動記錄出棧，根據(jù)獲得的返回地址信息返回到本次的調(diào)用處。將遞歸程序轉(zhuǎn)化為非遞歸程序時常使用棧來實現(xiàn).2.2 隊列2。2.1 隊列的定義及基本運算棧是一種后進先出的數(shù)據(jù)結(jié)構(gòu),在實際問題中還經(jīng)常使用一種“先進先出的數(shù)據(jù)結(jié)構(gòu)：即插入在表一端進行,而刪除在表的另一端進行，將這種數(shù)據(jù)結(jié)構(gòu)稱為隊或隊列,把允許插入的一端叫隊尾(rear) ；把允許刪除的一端叫隊頭(front）。2。2。2 隊列的存儲實現(xiàn)及運算實現(xiàn)與線性表、棧類似，隊列也有順序存儲和鏈式存儲兩種存儲方法。1順序隊列循環(huán)隊列的類型定義如下:define MAXQSIZE 100 /最大隊列長度typede

40、f struct QElemType base; /動態(tài)分配存儲空間int front; /頭指針，若隊列不空，指向隊列頭元素int rear; /尾指針，若隊列不空，指向隊列尾元素的下一個位置 SqQueue；下面是循環(huán)隊列上基本操作的實現(xiàn)。（ 3）求循環(huán)隊列元素個數(shù)：int QueueLength（ SqQueue Q） return (Q.rear-Q.front+MAXQSIZE) MAXQSIZE；2鏈隊列鏈式存儲的隊稱為鏈隊列.和鏈棧類似，用單鏈表來實現(xiàn)鏈隊列,根據(jù)隊的先進先出原則，為了操作上的方便,分別需要一個頭指針和尾指針。定義一個指向鏈隊列的指針: LinkQueue Q；下

41、面是鏈隊列的基本運算的實現(xiàn)。( 1）入隊int EnQueue (LinkQueue &Q, QElemType e） QNode p;p = （ QNode ) malloc（ sizeof（ QNode) ;p-data = e;p-next = NULL;Q.rear-next = p;Q.rear = p；return OK;( 2）出隊int DeQueue （LinkQueue Q， QElemType e) if （Q.front = Q。rear) return ERROR； /隊空，出隊失敗p = Q。front-next;e = pdata； /隊頭元素放 e 中Q。fro

42、ntnext = p-next;if（Q.rear=p) Q.rear= Q.front; /只有一個元素時，此時還要修改隊尾指針free （p）；return OK；3除了棧和隊列之外,還有一種限定性數(shù)據(jù)結(jié)構(gòu)是雙端隊列。( 1）雙端隊列：可以在雙端進行插入和刪除操作的線性表.（ 2）輸入受限的雙端隊列：線性表的兩端都可以輸出數(shù)據(jù)元素,但是只能在一端輸入數(shù)據(jù)元素.( 3）輸出受限的雙端隊列：線性表的兩端都可以輸入數(shù)據(jù)元素,但是只能在一端輸出數(shù)據(jù)元素。2.3 特殊矩陣的壓縮存儲2。3。1 數(shù)組數(shù)組可以看作線性表的推廣.數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)其特點是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同

43、一數(shù)據(jù)類型，數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)有序集，每一個數(shù)據(jù)元素有唯一的一組下標來標識，因此，在數(shù)組上不能做插入、刪除數(shù)據(jù)元素的操作。通常在各種高級語言中數(shù)組一旦被定義,每一維的大小及上下界都不能改變。現(xiàn)在來討論數(shù)組在計算機中的存儲表示.通常，數(shù)組在內(nèi)存被映象為向量，即用向量作為數(shù)組的一種存儲結(jié)構(gòu)，這是因為內(nèi)存的地址空間是一維的，數(shù)組的行列固定后,通過一個映象函數(shù)，則可根據(jù)數(shù)組元素的下標得到它的存儲地址.對于一維數(shù)組按下標順序分配即可。對多維數(shù)組分配時,要把它的元素映象存儲在一維存儲器中，一般有兩種存儲方式：一是以行為主序（或先行后列）的順序存放，即一行分配完了接著分配下一行。另一種是以列

44、為主序（先列后行）的順序存放，即一列一列地分配.以行為主序的分配規(guī)律是:最右邊的下標先變化，即最右下標從小到大,循環(huán)一遍后，右邊第二個下標再變, ，從右向左，最后是左下標。以列為主序分配的規(guī)律恰好相反:最左邊的下標先變化，即最左下標從小到大，循環(huán)一遍后,左邊第二個下標再變， ,從左向右，最后是右下標。設(shè)有 mn 二維數(shù)組 Amn，下面我們看按元素的下標求其地址的計算:以“以行為主序”的分配為例:設(shè)數(shù)組的基址為 LOC(a11），每個數(shù)組元素占據(jù) d 個地址單元，那么 aij 的物理地址可用一線性尋址函數(shù)計算：LOC（aij) = LOC(a11) + （ （i1）*n + j-1 ） * d這

45、是因為數(shù)組元素 aij 的前面有 i1 行，每一行的元素個數(shù)為 n，在第 i 行中它的前面還有j1 個數(shù)組元素。在 C 語言中，數(shù)組中每一維的下界定義為 0，則：LOC（aij) = LOC(a00） + （ i*n + j ） d推廣到一般的二維數(shù)組： Ac1。.d1 c2。d2，則 aij 的物理地址計算函數(shù)為：LOC（aij）=LOC(a c1 c2）+( (i- c1) *( d2 c2 + 1）+ （j- c2) )d2。3。2 特殊矩陣對于一個矩陣結(jié)構(gòu)顯然用一個二維數(shù)組來表示是非常恰當?shù)模?矩陣在這種存儲表示之下，可以對其元素進行隨機存取，各種矩陣運算也非常簡單，并且存儲的密度為

46、1。但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，比如常見的一些特殊矩陣，如三角矩陣、對稱矩陣、對角矩陣、稀疏矩陣等,從節(jié)約存儲空間的角度考慮,這種存儲是不太合適的，看起來存儲密度仍為 1，但實際上占用了許多單元去存儲重復的非零元素或零元素,這對高階矩陣會造成極大的浪費，為了節(jié)省存儲空間，我們可以對這類矩陣進行壓縮存儲:即為多個相同的非零元素只分配一個存儲空間；對零元素不分配空間。1.對稱矩陣對稱矩陣的特點是:在一個 n 階方陣中，有 aij=aji ，其中 1i , jn，對稱矩陣關(guān)于主對角線對稱，因此只需存儲上三角或下三角部分即可，比如，我們只存儲下三角中的元素 a

47、ij,其特點是中 ji 且 1in，對于上三角中的元素 aij ，它和對應(yīng)的 aji 相等，因此當訪問的元素在上三角時,直接去訪問和它對應(yīng)的下三角元素即可,這樣，原來需要 nn 個存儲單元,現(xiàn)在只需要 n（n+1)/2 個存儲單元了，節(jié)約了 n(n-1)/2 個存儲單元。對下三角部分以行為主序順序存儲到一個向量中去,在下三角中共有 n*（n+1）/2 個元素,因此，不失一般性,設(shè)存儲到向量 SAn(n+1）/2中,存儲順序可用圖示意，這樣，原矩陣下三角中的某一個元素 aij 則具體對應(yīng)一個 sak,下面的問題是要找到 k 與 i、 j 之間的關(guān)系。對于下三角中的元素 aij，其特點是： ij

48、且 1in，存儲到 SA 中后,根據(jù)存儲原則，它前面有 i-1 行，共有 1+2+i1=i（i-1)/2 個元素，而 aij 又是它所在的行中的第 j 個，所以在上面的排列順序中， aij 是第 i(i-1)/2+j 個元素，因此它在 SA 中的下標 k 與 i、 j 的關(guān)系為：k=i*(i1)/2+j-1 (kn(n+1)/2 )若 ij，則 aij 是上三角中的元素,因為 aij=aji ，這樣，訪問上三角中的元素 aij 時則去訪問和它對應(yīng)的下三角中的 aji 即可,因此將上式中的行列下標交換就是上三角中的元素在 SA中的對應(yīng)關(guān)系：k=j(j1)/2+i-1 （kn*(n+1)/2 ）綜

49、上所述,對于對稱矩陣中的任意元素 aij，若令 I=max（i，j), J=min（i,j）,則將上面兩個式子綜合起來得到：k=I*（I1）/2+J-1。2.三角矩陣（ 1)下三角矩陣與對稱矩陣類似,不同之處在于存完下三角中的元素之后，緊接著存儲對角線上方的常量,因為是同一個常數(shù)，所以存一個即可，這樣一共存儲了 n(n+1)+1 個元素,設(shè)存入向量:（ 2）上三角矩陣對于上三角矩陣，存儲思想與下三角類似，以行為主序順序存儲上三角部分， 最后存儲對角線下方的常量.3。對角矩陣對角矩陣也稱為帶狀矩陣。，在這種三對角矩陣中，所有非零元素都集中在以主對角線為中心的對角區(qū)域中，即除了主對角線和它的上下方

50、若干條對角線的元素外,所有其他元素都為零(或同一個常數(shù) c)。三對角矩陣 A 也可以采用壓縮存儲，將三對角矩陣壓縮到向量 SA 中去，按以行為主序，順序的存儲其非零元素，如圖所示，按其壓縮規(guī)律，找到相應(yīng)的映象函數(shù).第三章 樹與二叉樹3.1 樹的概念1。樹的定義樹（ Tree）是 n( n0)個有限數(shù)據(jù)元素的集合.當 n0 時，稱這棵樹為空樹。在一棵非樹 T 中：1)有一個特殊的數(shù)據(jù)元素稱為樹的根結(jié)點，根結(jié)點沒有前驅(qū)結(jié)點；2）若 n1， 除根結(jié)點之外的其余數(shù)據(jù)元素被分成 m （ m0）個互不相交的集合 T1， T2，Tm，其中每一個集合 Ti（ 1im)本身又是一棵樹。樹 T1， T2， ， T

51、m 稱為這個根結(jié)點的子樹。2相關(guān)術(shù)語（ 1）結(jié)點的度：結(jié)點所擁有的子樹的個數(shù)稱為該結(jié)點的度。（ 2）葉結(jié)點:度為 0 的結(jié)點稱為葉結(jié)點,或者稱為終端結(jié)點。( 3)分支結(jié)點：度不為 0 的結(jié)點稱為分支結(jié)點，或者稱為非終端結(jié)點。一棵樹的結(jié)點除葉結(jié)點外，其余的都是分支結(jié)點。( 4）孩子、雙親、兄弟：樹中一個結(jié)點的子樹的根結(jié)點稱為這個結(jié)點的孩子.這個結(jié)點稱為它孩子結(jié)點的雙親。具有同一個雙親的孩子結(jié)點互稱為兄弟。（ 5)路徑、路徑長度:如果一棵樹的一串結(jié)點 n1,n2，,nk 有如下關(guān)系：結(jié)點 ni 是 ni+1 的父結(jié)點（ 1in，則序號為 i 的結(jié)點無左孩子。（ 3）如果 2i1n，則序號為 i 的

52、結(jié)點的右孩子結(jié)點的序號為 2i1；如果 2i1n,則序號為 i 的結(jié)點無右孩子。此外，若對二叉樹的根結(jié)點從 0 開始編號,則相應(yīng)的 i 號結(jié)點的雙親結(jié)點的編號為 ,左孩子的編號為 2i1,右孩子的編號為 2i2.3。2。2 二叉樹的存儲1順序存儲結(jié)構(gòu)所謂二叉樹的順序存儲,就是用一組連續(xù)的存儲單元存放二叉樹中的結(jié)點。一般是按照二叉樹結(jié)點從上至下、從左到右的順序存儲.這樣結(jié)點在存儲位置上的前驅(qū)后繼關(guān)系并不一定就是它們在邏輯上的鄰接關(guān)系，然而只有通過一些方法確定某結(jié)點在邏輯上的前驅(qū)結(jié)點和后繼結(jié)點，這種存儲才有意義。依據(jù)二叉樹的性質(zhì)，完全二叉樹和滿二叉樹采用順序存儲比較合適,樹中結(jié)點的序號可以唯一地反

53、映出結(jié)點之間的邏輯關(guān)系，這樣既能夠最大可能地節(jié)省存儲空間，又可以利用數(shù)組元素的下標值確定結(jié)點在二叉樹中的位置，以及結(jié)點之間的關(guān)系。對于一般的二叉樹，如果仍按從上至下和從左到右的順序?qū)渲械慕Y(jié)點順序存儲在一維數(shù)組中，則數(shù)組元素下標之間的關(guān)系不能夠反映二叉樹中結(jié)點之間的邏輯關(guān)系，只有增添一些并不存在的空結(jié)點，使之成為一棵完全二叉樹的形式,然后再用一維數(shù)組順序存儲。顯然，這種存儲對于需增加許空結(jié)點才能將一棵二叉樹改造成為一棵完全二叉樹的存儲時,會造成空間的大量浪費，不宜用順序存儲結(jié)構(gòu)。最壞的情況是右單支樹，一棵深度為 k 的右單支樹,只有 k 個結(jié)點,卻需分配 2k1 個存儲單元.二叉樹的順序存儲表

54、示可描述為：#define MAX_TREE_SIZE 100 /二叉樹的最大結(jié)點數(shù)typedef TElemType SqBiTreeMAX_TREE_SIZE /0 號單元存放根結(jié)點SqBiTree b; /將 b 定義為含有 MAX_TREE_SIZE 個 TElemType 類型元素的一維數(shù)組2鏈式存儲結(jié)構(gòu)所謂二叉樹的鏈式存儲結(jié)構(gòu)是指,用鏈表來表示一棵二叉樹,即用鏈來指示著元素的邏輯關(guān)系。通常有下面兩種形式。（ 1）二叉鏈表鏈表中每個結(jié)點由三個域組成,除了數(shù)據(jù)域外，還有兩個指針域，分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址。結(jié)點的存儲的結(jié)構(gòu)為：其中, data 域存放某結(jié)點

55、的數(shù)據(jù)信息; lchild 與 rchild 分別存放指向左孩子和右孩子的指針,當左孩子或右孩子不存在時，相應(yīng)指針域值為空。二叉樹的二叉鏈表存儲表示可描述為：typedef struct BiTNodeTElemType data;struct BiTNode *lchild;*rchild; /左右孩子指針BiTNode，*BiTree；BiTree b； /即將 b 定義為指向二叉鏈表結(jié)點結(jié)構(gòu)的指針類型。（ 2)三叉鏈表每個結(jié)點由四個域組成,結(jié)點的存儲的結(jié)構(gòu)為:其中， data、 lchild 以及 rchild 三個域的意義與二叉鏈表結(jié)構(gòu)相同; parent 域為指向該結(jié)點雙親結(jié)點的指針

56、。這種存儲結(jié)構(gòu)既便于查找孩子結(jié)點，又便于查找雙親結(jié)點；但是，相對于二叉鏈表存儲結(jié)構(gòu)而言，它增加了空間開銷。盡管在二叉鏈表中無法由結(jié)點直接找到其雙親，但由于二叉鏈表結(jié)構(gòu)靈活，操作方便，因此，二叉鏈表是最常用的二叉樹存儲方式，本書后面所涉及到的二叉樹的鏈式存儲結(jié)構(gòu)不加特別說明的都是指二叉鏈表結(jié)構(gòu).3。2。3 二叉樹的遍歷二叉樹的遍歷是指按照某種順序訪問二叉樹中的每個結(jié)點，使每個結(jié)點被訪問一次且僅被訪問一次.遍歷是二叉樹中經(jīng)常要用到的一種操作。因為在實際應(yīng)用問題中，常常需要按一定順序?qū)Χ鏄渲械拿總€結(jié)點逐個進行訪問，查找具有某一特點的結(jié)點，然后對這些滿足條件的結(jié)點進行處理。通過一次完整的遍歷，可使二

57、叉樹中結(jié)點信息由非線性排列變?yōu)槟撤N意義上的線性序列.也就是說，遍歷操作實質(zhì)是對一個非線性結(jié)構(gòu)進行線性化操作。1先序遍歷先序遍歷的遞歸過程為：若二叉樹為空，遍歷結(jié)束.否則,（ 1)訪問根結(jié)點；（ 2）先序遍歷根結(jié)點的左子樹；（ 3）先序遍歷根結(jié)點的右子樹。void PreOrder( BiTree b） if (b!=NULL)Visit（ bdata) ； /訪問結(jié)點的數(shù)據(jù)域PreOrder（ b-lchild） ； /先序遞歸遍歷 b 的左子樹lchild data rchildlchild data rchild parentPreOrder（ b-rchild） ; /先序遞歸遍歷 b

58、的右子樹2中序遍歷中序遍歷的遞歸過程為：若二叉樹為空,遍歷結(jié)束.否則，（ 1）中序遍歷根結(jié)點的左子樹;( 2）訪問根結(jié)點；（ 3）中序遍歷根結(jié)點的右子樹。3后序遍歷后序遍歷的遞歸過程為:若二叉樹為空，遍歷結(jié)束。否則,（ 1）后序遍歷根結(jié)點的左子樹；（ 2）后序遍歷根結(jié)點的右子樹。（ 3)訪問根結(jié)點；4層次遍歷所謂二叉樹的層次遍歷,是指從二叉樹的第一層（根結(jié)點)開始,從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問.由層次遍歷的定義可以推知，在進行層次遍歷時,對一層結(jié)點訪問完后,再按照它們的訪問次序?qū)Ω鱾€結(jié)點的左孩子和右孩子順序訪問，這樣一層一層進行,先遇到的結(jié)點先訪問，這與隊列的

59、操作原則比較吻合.因此,在進行層次遍歷時,可設(shè)置一個隊列結(jié)構(gòu),遍歷從二叉樹的根結(jié)點開始，首先將根結(jié)點指針入隊列，然后從對頭取出一個元素，每取一個元素，執(zhí)行下面兩個操作：( 1）訪問該元素所指結(jié)點；（ 2）若該元素所指結(jié)點的左、右孩子結(jié)點非空,則將該元素所指結(jié)點的左孩子指針和右孩子指針順序入隊。此過程不斷進行,當隊列為空時，二叉樹的層次遍歷結(jié)束。在下面的層次遍歷算法中，二叉樹以二叉鏈表存放，一維數(shù)組 QueueMAX_TREE_SIZE用以實現(xiàn)隊列,變量 front 和 rear 分別表示當前對隊首元素和隊尾元素在數(shù)組中的位置.void LevelOrder( BiTree b） BiTree

60、QueueMAX_TREE_SIZE;int front，rear;if (b=NULL) return；front=1;rear=0；Queuerear=b；while（front！=rear) Visit（Queue+frontdata）; /訪問隊首結(jié)點數(shù)據(jù)域if (Queuefrontlchild!=NULL) /將隊首結(jié)點的左孩子結(jié)點入隊列Queue+rear= Queuefrontlchild；if （Queuefrontrchild！=NULL） /將隊首結(jié)點的右孩子結(jié)點入隊列Queue+rear= Queuefrontrchild；5二叉樹遍歷的非遞歸實現(xiàn)前面給出的二叉樹先序、