數(shù)據(jù)結(jié)構(gòu)考研講義

1、目錄緒論30.1 基本概念3第一章 線性表41.1 線性表的定義41.2 線性表的實現(xiàn)41.2.2 線性表的鏈式存儲結(jié)構(gòu)6第二章 棧、隊列和數(shù)組112.1 棧112.2 隊列152.3 特殊矩陣的壓縮存儲172.3.1 數(shù)組172.3.2 特殊矩陣17第三章 樹與二叉樹203.1 樹的概念201.樹的定義202相關(guān)術(shù)語203.2 二叉樹213.2.1 定義與性質(zhì)213.2.2 二叉樹的存儲223.2.3 二叉樹的遍歷233.2.4 線索二叉樹253.3 樹和森林293.3.1 樹的存儲結(jié)構(gòu)293.3.2 森林和二叉樹的轉(zhuǎn)換303.3.3 樹和森林的遍歷303.4 哈夫曼（ Huffman）樹和

2、哈夫曼編碼31第四章 圖324.1 圖的概念324.2 圖的存儲及基本操作334.2.1 鄰接矩陣334.2.2 鄰接表334.3 圖的遍歷354.3.1 深度優(yōu)先搜索354.3.2 廣度優(yōu)先搜索354.4 圖的基本應(yīng)用374.4.1 最小生成樹374.4.2 最短路徑374.4.3 拓撲排序394.4.4 關(guān)鍵路徑40第五章 查找425.1 查找的基本概念425.2 順序查找法435.3 折半查找法445.4 動態(tài)查找樹表455.4.1 二叉排序樹455.4.2 平衡二叉樹475.4.3 B 樹及其基本操作、 B+樹的基本概念495.5 散列表515.5.2 常用的散列函數(shù)515.5.3 處

3、理沖突的方法525.5.4 散列表的查找525.5.5 散列表的查找分析53第六章 排序546.1 插入排序546.1.1 直接插入排序546.1.2 折半插入排序546.2 冒泡排序556.3 簡單選擇排序566.4 希爾排序576.5 快速排序586.6 堆排序606.7 二路歸并排序626.8 基數(shù)排序636.9 各種內(nèi)部排序算法的比較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)

4、系。通常分為四類結(jié)構(gòu)：（ 1）集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(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ù)元素間

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

6、有下列特性：有窮性確定性可行性輸入輸出。算法和程序十分相似，但又有區(qū)別。程序不一定具有有窮性，程序中的指令必須是機器可執(zhí)行的，而算法中的指令則無此限制。算法代表了對問題的解，而程序則是算法在計算機上的特定的實現(xiàn)。一個算法若用程序設(shè)計語言來描述，則它就是一個程序。2、算法的時間復(fù)雜度：以基本運算的原操作重復(fù)執(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)

7、的增長率和 f(n)的增長率相同。注意：有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。常見的漸進時間復(fù)雜度有： (1)(log2n)(n)(nlog2n)(n2)(n3)(2n) O(n!) O(nn)。3、算法的空間復(fù)雜度：是對一個算法在運行過程中臨時占用的存儲空間大小的量度。只需要分析除輸入和程序之外的輔助變量所占額外空間。原地工作：若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作，空間復(fù)雜度為 O(1)。第一章 線性表1.1 線性表的定義線性表是一種線性結(jié)構(gòu)，在一個線性表中數(shù)據(jù)元素的類型是相同的，或者說線性表是由同一類型的數(shù)據(jù)元素構(gòu)成的線性結(jié)構(gòu)，定

8、義如下：線性表是具有相同數(shù)據(jù)類型的n(n0)個數(shù)據(jù)元素的有限序列，通常記為：(a1， a2， ai-1， 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的存儲地址

9、為Loc(a)，每個數(shù)據(jù)元素占d個存儲地址，則第i個數(shù)據(jù)元素的地址為：Loc(ai)=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; /當(dāng)前長度int listsize; /當(dāng)前已分配的存儲

10、空間SqList;2.順序表上基本運算的實現(xiàn)（ 1）順序表的初始化順序表的初始化即構(gòu)造一個空表， 這對表是一個加工型的運算， 因此， 將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

11、;（ 2）插入運算線性表的插入是指在表的第i(i的取值范圍： 1in+1)個位置上插入一個值為 x 的新元素，插入后使原表長為 n的表:(a1， a2， . ， ai-1， ai， ai+1， . ， an)成為表長為 n+1 表:(a1， a2， .， ai-1， x， ai， ai+1， .， an ) 。順序表上完成這一運算則通過以下步驟進行： 將aian 順序向下移動，為新元素讓出位置；（注意數(shù)據(jù)的移動方向：從后往前依次后移一個元素） 將 x 置入空出的第i個位置； 修改表長。int Insert_SqList (SqList &L， int i， ElemType x)if

12、(i < 1 | i > L.length+1) return ERROR; / 插入位置不合法if (L.length >= L.listsize) return OVERFLOW; / 當(dāng)前存儲空間已滿,不能插入/需注意的是，若是采用動態(tài)分配的順序表，當(dāng)存儲空間已滿時也可增加分配q = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.length-1); p >= q; -p)*(p+1) = *p; / 插入位置及之后的元素右移*q = e; / 插入e+L.length; / 表長增1return OK;順序

13、表上的插入運算， 時間主要消耗在了數(shù)據(jù)的移動上， 在第i個位置上插入 x ， 從 ai 到an 都要向下移動一個位置，共需要移動 ni1個元素。（ 3）刪除運算線性表的刪除運算是指將表中第 i （ i 的取值范圍為 ： 1 in）個元素從線性表中去掉，刪除后使原表長為 n 的線性表：(a1， a2， . ， ai-1， ai， ai+1， .， an)成為表長為 n1 的線性表：(a1， a2， . ， ai-1， ai+1， . ， an)。順序表上完成這一運算的步驟如下： 將ai+1an 順序向上移動；（注意數(shù)據(jù)的移動方向：從前往后依次前移一個元素） 修改表長。int Delete_SqL

14、ist (SqList &L;int i) if (i < 1) | (i > L.length) return ERROR; / 刪除位置不合法p = &(L.elemi-1); / p 為被刪除元素的位置e = *p; / 被刪除元素的值賦給 eq = L.elem+L.length-1; / 表尾元素的位置for (+p; p <= q; +p)*(p-1) = *p; / 被刪除元素之后的元素左移-L.length; / 表長減1return OK;順序表的刪除運算與插入運算相同，其時間主要消耗在了移動表中元素上，刪除第i個元素時，其后面的元素 ai+

15、1an 都要向上移動一個位置，共移動了 n-i 個元素，順序表的插入、刪除需移動大量元素 O(n)；但在尾端插入、刪除效率高 O(1)。1.2.2 線性表的鏈式存儲結(jié)構(gòu)1.2.2.1 單鏈表1.鏈表表示鏈表是通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素的。為建立起數(shù)據(jù)元素之間的線性關(guān)系，對每個數(shù)據(jù)元素ai，除了存放數(shù)據(jù)元素的自身的信息 ai 之外，還需要和ai一起存放其后繼 ai+1 所在的存儲單元的地址，這兩部分信息組成一個“結(jié)點”，結(jié)點的結(jié)構(gòu)如圖所示。其中，存放數(shù)據(jù)元素信息的稱為數(shù)據(jù)域，存放其后繼地址的稱為指針域。因此n個元素的線性表通過每個結(jié)點的指針域拉成了一個“鏈”，稱之為鏈表。因為

16、每個結(jié)點中只有一個指向后繼的指針，所以稱其為單鏈表。線性表的單鏈表存儲結(jié)構(gòu)C語言描述下：typedef struct LNodeElemType data; / 數(shù)據(jù)域struct LNode *next; / 指針域LNode， *LinkList;LinkList L； / L 為單鏈表的頭指針通常用“頭指針”來標(biāo)識一個單鏈表，如單鏈表L、單鏈表H等，是指某鏈表的第一個結(jié)點的地址放在了指針變量 L、 H 中， 頭指針為“NULL”則表示一個空表。2.單鏈表上基本運算的實現(xiàn)(1)建立單鏈表單鏈表結(jié)點結(jié)構(gòu)data next頭插法在鏈表的頭部插入結(jié)點建立單鏈表鏈表與順序表不同，它是一種動態(tài)管理的

17、存儲結(jié)構(gòu)，鏈表中的每個結(jié)點占用的存儲空間不是預(yù)先分配，而是運行時系統(tǒng)根據(jù)需求而生成的，因此建立單鏈表從空表開始，每讀入一個數(shù)據(jù)元素則申請一個結(jié)點，然后插在鏈表的頭部。LinkList CreateListF ( )LinkList L=NULL； /空表LNode *s;int x; /設(shè)數(shù)據(jù)元素的類型為intscanf(%d,&x);while (x!=flag) s=(LNode *)malloc(sizeof(LNode);s->data=x;s->next=L; L=s;scanf (%d,&x);return L;尾插法在單鏈表的尾部插入結(jié)點建立單鏈表頭插

18、入建立單鏈表簡單， 但讀入的數(shù)據(jù)元素的順序與生成的鏈表中元素的順序是相反的，若希望次序一致，則用尾插入的方法。因為每次是將新結(jié)點插入到鏈表的尾部，所以需加入一個指針 r 用來始終指向鏈表中的尾結(jié)點，以便能夠?qū)⑿陆Y(jié)點插入到鏈表的尾部。初始狀態(tài)， 頭指針L=NULL， 尾指針 r=NULL; 按線性表中元素的順序依次讀入數(shù)據(jù)元素，不是結(jié)束標(biāo)志時，申請結(jié)點，將新結(jié)點插入到 r 所指結(jié)點的后面，然后 r 指向新結(jié)點（注意第一個結(jié)點有所不同）。LinkList CreateListR1 ( )LinkList L=NULL;LNode *s,*r=NULL;int x; /設(shè)數(shù)據(jù)元素的類型為intsca

19、nf(%d,&x);while (x!=flag) s=(LNode *)malloc(sizeof(LNode);s->data=x;if (L=NULL) L=s; /第一個結(jié)點的處理else r->next=s; /其它結(jié)點的處理r=s; /r 指向新的尾結(jié)點scanf(%d,&x);if ( r!=NULL) r->next=NULL; /對于非空表，最后結(jié)點的指針域放空指針return L;在算法CreateListR1中，第一個結(jié)點的處理和其它結(jié)點是不同的，原因是第一個結(jié)點加入時鏈表為空，它沒有直接前驅(qū)結(jié)點，它的地址就是整個鏈表的指針，需要放在鏈表

20、的頭指針變量中；而其它結(jié)點有直接前驅(qū)結(jié)點，其地址放入直接前驅(qū)結(jié)點的指針域。 “第一個結(jié)點”的問題在很多操作中都會遇到，如在鏈表中插入結(jié)點時，將結(jié)點插在第一個位置和其它位置是不同的，在鏈表中刪除結(jié)點時，刪除第一個結(jié)點和其它結(jié)點的處理也是不同的，等等。為了方便操作，有時在鏈表的頭部加入一個“頭結(jié)點”，頭結(jié)點的類型與數(shù)據(jù)結(jié)點一致，標(biāo)識鏈表的頭指針變量L中存放該結(jié)點的地址，這樣即使是空表，頭指針變量L也不為空了。頭結(jié)點的加入使得“第一個結(jié)點”的問題不再存在，也使得“空表”和“非空表”的處理成為一致。頭結(jié)點的加入完全是為了運算的方便，它的數(shù)據(jù)域無定義，指針域中存放的是第一個數(shù)據(jù)結(jié)點的地址，空表時為空。尾

21、插法建立帶頭結(jié)點的單鏈表，將算法CreateListR1改寫成算法CreateListR2形式。LinkList CreateListR2( )LinkList L=(LNode *)malloc(sizeof(LNode);L->next=NULL； /空表LNode *s,*r=L;int x; /設(shè)數(shù)據(jù)元素的類型為intscanf(%d,&x);while (x!=flag) s=(LNode *)malloc(sizeof(LNode);s->data=x;r->next=s;r=s; /r 指向新的尾結(jié)點scanf(%d,&x);r->next

22、=NULL;return L;因此，頭結(jié)點的加入會帶來以下兩個優(yōu)點：第一個優(yōu)點：由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中，所以在鏈表的第一個位置上的操作就和在表的其它位置上的操作一致，無需進行特殊處理；第二個優(yōu)點：無論鏈表是否為空，其頭指針是指向頭結(jié)點在的非空指針（空表中頭結(jié)點的指針域為空），因此空表和非空表的處理也就統(tǒng)一了。在以后的算法中不加說明則認為單鏈表是帶頭結(jié)點的。(2)查找操作按序號查找 Get_LinkList(L,i)從鏈表的第一個元素結(jié)點起，判斷當(dāng)前結(jié)點是否是第i個，若是，則返回該結(jié)點的指針，否則繼續(xù)后一個，表結(jié)束為止，沒有第個結(jié)點時返回空。LNode * Get_LinkL

23、ist(LinkList L, int i); LNode * p=L;int j=0;while (p->next !=NULL && j<i )p=p->next; j+;if (j=i) return p;else return NULL;(3)插入運算后插結(jié)點：設(shè)p指向單鏈表中某結(jié)點， s指向待插入的值為x的新結(jié)點，將*s插入到*p的后面，插入示意圖如圖所示。操作如下：s->next=p->next;p->next=s;注意：兩個指針的操作順序不能交換。(4)刪除運算刪除結(jié)點設(shè)p指向單鏈表中某結(jié)點，刪除*p。操作過程如圖。要實現(xiàn)對結(jié)點

24、*p的刪除，首先要找到*p的前驅(qū)結(jié)點*q，然后完成指針的操作即可。操作如下：q=L;while (q->next!=p)q=q->next; /找*p的直接前驅(qū)q->next=p->next;free(p);因為找*p前驅(qū)的時間復(fù)雜度為O(n)，所以該操作的時間復(fù)雜度為O(n)通過上面的基本操作我們得知：(1) 單鏈表上插入、刪除一個結(jié)點，必須知道其前驅(qū)結(jié)點。(2) 單鏈表不具有按序號隨機訪問的特點，只能從頭指針開始一個個順序進行。1.2.2.2 循環(huán)鏈表對于單鏈表而言，最后一個結(jié)點的指針域是空指針，如果將該鏈表頭指針置入該指針域，則使得鏈表頭尾結(jié)點相連，就構(gòu)成了單循環(huán)

25、鏈表。在單循環(huán)鏈表上的操作基本上與非循環(huán)鏈表相同，只是將原來判斷指針是否為 NULL 變?yōu)槭欠袷穷^指針而已，沒有其它較大的變化。對于單鏈表只能從頭結(jié)點開始遍歷整個鏈表，而對于單循環(huán)鏈表則可以從表中任意結(jié)點開始遍歷整個鏈表，不僅如此，有時對鏈表常做的操作是在表尾、表頭進行，此時可以改變一下鏈表的標(biāo)識方法，不用頭指針而用一個指向尾結(jié)點的指針 R 來標(biāo)識，可以使得操作效率得以提高。1.2.2.3 雙向鏈表單鏈表的結(jié)點中只有一個指向其后繼結(jié)點的指針域 next，因此若已知某結(jié)點的指針為 p，其后繼結(jié)點的指針則為 p->next ，而找其前驅(qū)則只能從該鏈表的頭指針開始，順著各結(jié)點的next 域進行

26、，也就是說找后繼的時間性能是 O(1)，找前驅(qū)的時間性能是 O(n)，如果也希望找前驅(qū)的時間性能達到 O(1)，則只能付出空間的代價：每個結(jié)點再加一個指向前驅(qū)的指針域，結(jié)點的結(jié)構(gòu)為如圖所示，用這種結(jié)點組成的鏈表稱為雙向鏈表。線性表的雙向鏈表存儲結(jié)構(gòu)C語言描述下：typedef struct DuLNodeElemType data;struct DuLNode *prior,*next;DuLNode,*DuLinkList;和單鏈表類似，雙向鏈表通常也是用頭指針標(biāo)識，也可以帶頭結(jié)點。（ 1）雙向鏈表中結(jié)點的插入：設(shè) p 指向雙向鏈表中某結(jié)點， s 指向待插入的值為 x 的新結(jié)點，將*s 插入

27、到*p 的前面，插入示意圖如所示。操作如下： s->prior=p->prior; p->prior->next=s; s->next=p; p->prior=s;指針操作的順序不是唯一的，但也不是任意的，操作必須要放到操作的前面完成，否則*p 的前驅(qū)結(jié)點的指針就丟掉了。（ 2）雙向鏈表中結(jié)點的刪除：設(shè) p 指向雙向鏈表中某結(jié)點，刪除*p。操作示意圖如圖所示。操作如下：p->prior->next=p->next;p->next->prior=p->prior;free(p);1.2.2.4 順序表和鏈表的比較總之，兩種存

28、儲結(jié)構(gòu)各有長短，選擇那一種由實際問題中的主要因素決定。通?！拜^穩(wěn)定”的線性表選擇順序存儲，而頻繁做插入刪除的即動態(tài)性較強的線性表宜選擇鏈式存儲。第二章 棧、隊列和數(shù)組2.1 棧2.1.1 棧的定義棧是限制在表的一端進行插入和刪除的線性表。允許插入、刪除的這一端稱為棧頂，另一個固定端稱為棧底。當(dāng)表中沒有元素時稱為空棧。2.1.2 棧的存儲實現(xiàn)和運算實現(xiàn)棧是運算受限的線性表，線性表的存儲結(jié)構(gòu)對棧也是適用的，只是操作不同而已。利用順序存儲方式實現(xiàn)的棧稱為順序棧。與線性表類似，棧的動態(tài)分配順序存儲結(jié)構(gòu)如下：#define STACK_INIT_SIZE 100 /存儲空間的初始分配量#define S

29、TACKINCREMENT 10 /存儲空間的分配增量typedef structSElemType *base; /在棧構(gòu)造之前和銷毀之后， base 的值為 NULLSElemType *top; /棧頂指針int stacksize; /當(dāng)前已分配的存儲空間SqStack;需要注意，在棧的動態(tài)分配順序存儲結(jié)構(gòu)中， base 始終指向棧底元素，非空棧中的 top始終在棧頂元素的下一個位置。下面是順序棧上常用的基本操作的實現(xiàn)。（ 1）入棧：若棧不滿，則將 e 插入棧頂。int Push (SqStack &S, SElemType e) if (S.top-S.base>=S.

30、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;出棧和讀棧頂元素操作，先判棧是否為空，為空時不能操作，否則產(chǎn)生錯誤。通常?？粘Ｗ鳛橐环N控制轉(zhuǎn)移的條件。2.1.3 棧的應(yīng)用舉例由于棧的“先進先出”特點，在很多實際問題中都利用棧做一個輔

31、助的數(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)從高位到低位進行，恰好和計算過程相反。因此，若將計算過程中得到的八進制數(shù)的各位順序進棧，則按出棧序列打印輸出的即為與輸入對應(yīng)的八進制數(shù)。算法思想：當(dāng) N>0 時重復(fù)（ 1），（ 2）（ 1）若 N0，則將 N % r 壓入棧 s 中 ，執(zhí)行（

32、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è)計語言編譯中一個最基本的問題，它的實現(xiàn)也是需要棧的加入。下面的算法是由運算符優(yōu)先法對表達式求值。在此僅限于討論只含二目運算符的算術(shù)表達式。（ 1）中綴表達式求值：中

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

34、前字符是運算對象，入對象棧，是運算符時，若這個運算符比棧頂運算符高則入棧，繼續(xù)向后處理，若這個運算符比棧頂運算符低則從對象棧出棧兩個運算量，從運算符棧出棧一個運算符進行運算，并將其運算結(jié)果入對象棧，繼續(xù)處理當(dāng)前字符，直到遇到結(jié)束符。中綴表達式表達式 “3*2（ 4+2*2-*3） -5”求值過程中兩個棧的狀態(tài)情況見圖所示。 圖 中綴表達式 3*2（ 4+2*2-1*3） -5 的求值過程為了處理方便，編譯程序常把中綴表達式首先轉(zhuǎn)換成等價的后綴表達式，后綴表達式的運算符在運算對象之后。在后綴表達式中，不在引入括號，所有的計算按運算符出現(xiàn)的順序，嚴格從左向右進行，而不用再考慮運算規(guī)則和級別。中綴表

35、達式“3*2（ 4+2*2-1*3） -5 ”的后綴表達式為： “32422*+13*-*5-”。（ 2）后綴表達式求值計算一個后綴表達式，算法上比計算一個中綴表達式簡單的多。這是因為表達式中即無括號又無優(yōu)先級的約束。具體做法：只使用一個對象棧，當(dāng)從左向右掃描表達式時，每遇到一個操作數(shù)就送入棧中保存，每遇到一個運算符就從棧中取出兩個操作數(shù)進行當(dāng)前的計算，然后把結(jié)果再入棧，直到整個表達式結(jié)束，這時送入棧頂?shù)闹稻褪墙Y(jié)果。（ 3） 中綴表達式轉(zhuǎn)換成后綴表達式：將中綴表達式轉(zhuǎn)化為后綴表達示和前述對中綴表達式求值的方法完全類似，但只需要運算符棧，遇到運算對象時直接放后綴表達式的存儲區(qū)，假設(shè)中綴表達式本身

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

37、數(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)的“遞歸工作?！敝?，每當(dāng)遞歸調(diào)用一次，就要在棧頂為過程建立一個新的活動記錄，一旦本次調(diào)用結(jié)束，則將棧頂活動記錄出棧，根據(jù)獲得的返

38、回地址信息返回到本次的調(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 /最大隊列長度typedef struct QElemType *base; /動態(tài)分

39、配存儲空間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;下面是鏈隊列的基本運算的實現(xiàn)。（ 1）入隊int EnQu

40、eue (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 = p->data; /隊頭元素放

41、 e 中Q.front->next = 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)中的元素本

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

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

44、 + ( (i-1)*n + j-1 ) * d這是因為數(shù)組元素 aij 的前面有 i-1 行，每一行的元素個數(shù)為 n，在第 i 行中它的前面還有j-1 個數(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ù)組來表示是非常恰當(dāng)?shù)模?矩陣在這種存儲表示之下，可以對其

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

46、儲上三角或下三角部分即可，比如，我們只存儲下三角中的元素 aij，其特點是中 ji 且 1in，對于上三角中的元素 aij ，它和對應(yīng)的 aji 相等，因此當(dāng)訪問的元素在上三角時，直接去訪問和它對應(yīng)的下三角元素即可，這樣，原來需要 n*n 個存儲單元，現(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、

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

48、角中的元素在 SA中的對應(yīng)關(guān)系：k=j*(j-1)/2+i-1 (k<n*(n+1)/2 )綜上所述，對于對稱矩陣中的任意元素 aij，若令 I=max(i,j)， J=min(i,j)，則將上面兩個式子綜合起來得到：k=I*(I-1)/2+J-1。2.三角矩陣（ 1）下三角矩陣與對稱矩陣類似，不同之處在于存完下三角中的元素之后，緊接著存儲對角線上方的常量，因為是同一個常數(shù)，所以存一個即可，這樣一共存儲了 n*(n+1)+1 個元素，設(shè)存入向量：（ 2）上三角矩陣對于上三角矩陣，存儲思想與下三角類似，以行為主序順序存儲上三角部分， 最后存儲對角線下方的常量。3.對角矩陣對角矩陣也稱為帶狀

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

50、>0）個互不相交的集合 T1， T2，Tm，其中每一個集合 Ti（ 1im）本身又是一棵樹。樹 T1， T2， ， Tm 稱為這個根結(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 有如下

51、關(guān)系：結(jié)點 ni 是 ni+1 的父結(jié)點（ 1i<k） ,就把 n1,n2,nk 稱為一條由 n1 至 nk 的路徑。這條路徑的長度是 k-1。（ 6）祖先、子孫：在樹中，如果有一條路徑從結(jié)點 M 到結(jié)點 N，那么 M 就稱為 N 的祖先，而 N 稱為 M 的子孫。（ 7）結(jié)點的層數(shù)：樹的根結(jié)點的層數(shù)為 1，其余結(jié)點的層數(shù)等于它的雙親結(jié)點的層數(shù)加1。（ 8）樹的深度：樹中所有結(jié)點的最大層數(shù)稱為樹的深度。（ 9）樹的度：樹中各結(jié)點度的最大值稱為該樹的度。（ 10）有序樹和無序樹：如果一棵樹中結(jié)點的各子樹從左到右是有次序的，即若交換了某結(jié)點各子樹的相對位置，則構(gòu)成不同的樹，稱這棵樹為有序樹；

52、反之，則稱為無序樹。（ 11）森林：零棵或有限棵不相交的樹的集合稱為森林。自然界中樹和森林是不同的概念，但在數(shù)據(jù)結(jié)構(gòu)中，樹和森林只有很小的差別。任何一棵樹，刪去根結(jié)點就變成了森林。3.2 二叉樹3.2.1 定義與性質(zhì)1.二叉樹二叉樹（ Binary Tree）是 n 個有限元素的集合，該集合或者為空、或者由一個稱為根(root)的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成。當(dāng)集合為空時，稱該二叉樹為空二叉樹。在二叉樹中，一個元素也稱作一個結(jié)點。二叉樹是有序的，即若將其左、右子樹顛倒，就成為另一棵不同的二叉樹。即使樹中結(jié)點只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。2.滿二叉樹與完

53、全二叉樹（ 1）滿二叉樹在一棵二叉樹中，如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子結(jié)點都在同一層上，這樣的一棵二叉樹稱作滿二叉樹。（ 2）完全二叉樹一棵深度為 k 的有 n 個結(jié)點的二叉樹，對樹中的結(jié)點按從上至下、從左到右的順序進行編號，如果編號為 i（ 1in）的結(jié)點與滿二叉樹中編號為 i 的結(jié)點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。完全二叉樹的特點是：葉子結(jié)點只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點集中在樹的左部。顯然，一棵滿二叉樹必定是一棵完全二叉樹，而完全二叉樹未必是滿二叉樹。3.二叉樹的性質(zhì)性質(zhì) 1 一棵非空二叉樹的第 i 層上最多有 2i-1 個結(jié)點（ i1

54、）。（證明略）性質(zhì) 2 一棵深度為 k 的二叉樹中，最多具有 2k1 個結(jié)點。證明：設(shè)第 i 層的結(jié)點數(shù)為 xi（ 1ik），深度為 k 的二叉樹的結(jié)點數(shù)為 M， xi 最多為 2i-1，則有：M xi 2i-1 2k-1性質(zhì) 3 對于一棵非空的二叉樹，如果葉子結(jié)點數(shù)為 n0，度數(shù)為 2 的結(jié)點數(shù)為 n2，則有:n0n21。證明：設(shè) n 為二叉樹的結(jié)點總數(shù)， n1 為二叉樹中度為 1 的結(jié)點數(shù)，則有：nn0n1n2 （式 1-3-1）在二叉樹中，除根結(jié)點外，其余結(jié)點都有唯一的一個進入分支。設(shè) B 為二叉樹中的分支數(shù)，那么有：Bn1 （式 1-3-2）這些分支是由度為 1 和度為 2 的結(jié)點發(fā)出的，一個度為 1 的結(jié)點發(fā)出一個分支，一個度為 2 的結(jié)點發(fā)出兩個分支，所以有：Bn12n2 （式 1-3-3）綜合（式 1-3-1）、（式 1-3-2）、（式 1-3-3）式可以得到：n0n21性質(zhì) 4 具有 n 個結(jié)點的完全二叉樹的深度 k 為性質(zhì) 5 對于具有 n 個結(jié)點的完全二叉樹，如果按照從上至下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點從 1 開始順序編號，則對于任意的