數(shù)據(jù)結(jié)構(gòu)復習資料(親自整理)

1、一、 簡答題1、 鏈表：鏈表就是一串存儲數(shù)據(jù)的鏈式結(jié)構(gòu)。鏈式的優(yōu)點在于，每個數(shù)據(jù)之間都是相關(guān)聯(lián)的。2、 線性結(jié)構(gòu)：線性結(jié)構(gòu)是一個有序數(shù)據(jù)元素的集合。常用的線性結(jié)構(gòu)有：線性表，棧，隊列，雙隊列，數(shù)組，串。3、 樹與二叉樹二叉樹是每個結(jié)點最多有兩個子樹的有序樹；樹是由n（n>=1）個有限節(jié)點組成一個具有層次關(guān)系的集合。樹和二叉樹的2個主要差別：1. 樹中結(jié)點的最大度數(shù)沒有限制，而二叉樹結(jié)點的最大度數(shù)為2；2. 樹的結(jié)點無左、右之分，而二叉樹的結(jié)點有左、右之分。4、 堆堆通常是一個可以被看做一棵樹的數(shù)組對象。堆總是滿足下列性質(zhì)：堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值； 堆總是一棵完全二

2、叉樹。5、 二叉排序樹二叉排序數(shù)的（遞歸）定義：1、若左子樹非空，則左子樹所有節(jié)點的值均小于它的根節(jié)點；2、若右子樹非空，則右子樹所有節(jié)點的值均大于于它的根節(jié)點；3、左右子樹也分別為二叉排序樹。二、應用題1、 樹與二叉樹 前中后序遍歷序列一、已知前序、中序遍歷，求后序遍歷例：前序遍歷: GDAFEMHZ中序遍歷: ADEFGHMZ畫樹求法：第一步，根據(jù)前序遍歷的特點，我們知道根結(jié)點為G第二步，觀察中序遍歷ADEFGHMZ。其中root節(jié)點G左側(cè)的ADEF必然是root的左子樹，G右側(cè)的HMZ必然是root的右子樹。第三步，觀察左子樹ADEF，左子樹的中的根節(jié)點必然是大樹的root的leftch

3、ild。在前序遍歷中，大樹的root的leftchild位于root之后，所以左子樹的根節(jié)點為D。第四步，同樣的道理，root的右子樹節(jié)點HMZ中的根節(jié)點也可以通過前序遍歷求得。在前序遍歷中，一定是先把root和root的所有左子樹節(jié)點遍歷完之后才會遍歷右子樹，并且遍歷的左子樹的第一個節(jié)點就是左子樹的根節(jié)點。同理，遍歷的右子樹的第一個節(jié)點就是右子樹的根節(jié)點。 樹與二叉樹的轉(zhuǎn)換樹轉(zhuǎn)換為二叉樹：二叉樹轉(zhuǎn)換為樹： 二叉樹線索化注意：圖中的實線表示指針，虛線表示線索。結(jié)點C的左線索為空，表示C是中序序列的開始結(jié)點，無前趨；結(jié)點E的右線索為空，表示E是中序序列的終端結(jié)點，無后繼。線索二叉樹中，一個結(jié)點是

4、葉結(jié)點的充要條件為：左、右標志均是1。2、 圖 鄰接表一、鄰接表鄰接表是圖的一種鏈式存儲結(jié)構(gòu)。鄰接表中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中的結(jié)點表示依附于頂點Vi的邊（對有向圖是以頂點Vi為尾的?。｀徑颖碇械谋斫Y(jié)點和頭結(jié)點結(jié)構(gòu)：表 結(jié) 點adjvexnextarcinfo頭結(jié)點datafirstarc二、無向圖的鄰接表3、4、 圖7-5三、有向圖的鄰接表和逆鄰接表（一）在有向圖的鄰接表中，第i個單鏈表鏈接的邊都是頂點i發(fā)出的邊。（二）為了求第i個頂點的入度，需要遍歷整個鄰接表。因此可以建立逆鄰接表。（三）在有向圖的逆鄰接表中，第i個單鏈表鏈接的邊都是進入頂點i的邊。 &#

5、160;四、鄰接表小結(jié) 設圖中有n個頂點，e條邊，則用鄰接表表示無向圖時，需要n個頂點結(jié)點，2e個表結(jié)點；用鄰接表表示有向圖時，若不考慮逆鄰接表，只需n個頂點結(jié)點，e個邊結(jié)點。 在無向圖的鄰接表中，頂點vi的度恰為第i個鏈表中的結(jié)點數(shù)。 在有向圖中，第i個鏈表中的結(jié)點個數(shù)只是頂點vi的出度。在逆鄰接表中的第i個鏈表中的結(jié)點個數(shù)為vi的入度。 鄰接矩陣（有向、無向）1圖的鄰接矩陣表示法 在圖的鄰接矩陣表示法中： 用鄰接矩陣表示頂點間的相鄰關(guān)系 用一個順序表來存儲頂點信息2圖的鄰接矩陣(Adacency Matrix) 設G=(V，E)是具有n個頂點的圖，則G的鄰接矩

6、陣是具有如下性質(zhì)的n階方陣：【例】下圖中無向圖G 5 和有向圖G 6 的鄰接矩陣分別為A l 和A 2 。 廣度優(yōu)先遍歷廣度優(yōu)先遍歷是連通圖的一種遍歷策略。其基本思想如下：1、從圖中某個頂點V0出發(fā)，并訪問此頂點；2、從V0出發(fā)，訪問V0的各個未曾訪問的鄰接點W1，W2，,Wk;然后,依次從W1,W2,Wk出發(fā)訪問各自未被訪問的鄰接點；3、重復步驟2，直到全部頂點都被訪問為止。例如下圖中：1.從0開始，首先找到0的關(guān)聯(lián)頂點3,42.由3出發(fā)，找到1，2；由4出發(fā)，找到1，但是1已經(jīng)遍歷過，所以忽略。3.由1出發(fā)，沒有關(guān)聯(lián)頂點；由2出發(fā)，沒有關(guān)聯(lián)頂點。所以最后順序是0,3,4,1,2 深度優(yōu)先遍

7、歷深度優(yōu)先遍歷是連通圖的一種遍歷策略。其基本思想如下：設x是當前被訪問頂點，在對x做過訪問標記后，選擇一條從x出發(fā)的未檢測過的邊(x，y)。若發(fā)現(xiàn)頂點y已訪問過，則重新選擇另一條從x出發(fā)的未檢測過的邊，否則沿邊(x，y)到達未曾訪問過的y，對y訪問并將其標記為已訪問過；然后從y開始搜索，直到搜索完從y出發(fā)的所有路徑，即訪問完所有從y出發(fā)可達的頂點之后，才回溯到頂點x，并且再選擇一條從x出發(fā)的未檢測過的邊。上述過程直至從x出發(fā)的所有邊都已檢測過為止。例如下圖中：1.從0開始，首先找到0的關(guān)聯(lián)頂點32.由3出發(fā)，找到1；由1出發(fā)，沒有關(guān)聯(lián)的頂點。3.回到3，從3出發(fā)，找到2；由2出發(fā)，沒有關(guān)聯(lián)的頂

8、點。4.回到4，出4出發(fā)，找到1，因為1已經(jīng)被訪問過了，所以不訪問。所以最后順序是0,3,1,2,4Prim算法 基本思想：假設G(V，E)是連通的，TE是G上最小生成樹中邊的集合。算法從Uu0（u0V）、TE開始。重復執(zhí)行下列操作： 在所有uU，vVU的邊(u，v)E中找一條權(quán)值最小的邊(u0,v0)并入集合TE中，同時v0并入U，直到VU為止。 此時，TE中必有n-1條邊，T=(V，TE)為G的最小生成樹。 Prim算法的核心:始終保持TE中的邊集構(gòu)成一棵生成樹。注意：prim算法適合稠密圖，其時間復雜度為O(n2)，其時間復雜度與邊得數(shù)目無關(guān)，而kruskal算法的時間復雜度為O(elo

9、ge)跟邊的數(shù)目有關(guān)，適合稀疏圖。Krusal算法圖中先將每個頂點看作獨立的子圖，然后查找最小權(quán)值邊，這條邊是有限制條件的，邊得兩個頂點必須不在同一個圖中，如上圖，第一個圖中找到最小權(quán)值邊為（v1，v3），且滿足限制條件，繼續(xù)查找到邊（v4，v6），（v2，v5），（v3，v6），當查找到最后一條邊時，僅僅只有（v2，v3）滿足限制條件，其他的如（v3，v4），（v1，v4）都在一個子圖里面，不滿足條件，至此已經(jīng)找到最小生成樹的所有邊。拓撲排序由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。對上圖進行拓撲排序的結(jié)果：2->8->0->3->7-&g

10、t;1->5->6->9->4->11->10->125、 檢索 二叉排序建立typedef struct node int data; struct node * lchild; struct node * rchild;node;void Init(node *t) t = NULL;void InOrder(node * t) /中序遍歷輸出 if(t != NULL) InOrder(t->lchild); printf("%d ", t->data); InOrder(t->rchild); 二叉排序刪除

11、btree * DelNode(btree *p) if (p->lchild) btree *r = p->lchild; /r指向其左子樹; btree *prer = p->lchild; /prer指向其左子樹; while(r->rchild != NULL)/搜索左子樹的最右邊的葉子結(jié)點r prer = r; r = r->rchild; p->data = r->data; if(prer != r)/若r不是p的左孩子，把r的左孩子作為r的父親的右孩子 prer->rchild = r->lchild; else p->

12、;lchild = r->lchild; /否則結(jié)點p的左子樹指向r的左子樹 free(r); return p; else btree *q = p->rchild; /q指向其右子樹; free(p); return q; Huffman樹、編碼與解碼例. 給定有18個字符組成的文本：A A D A T A R A E F R T A A F T E R 求各字符的哈夫曼碼。（1） 統(tǒng)計：（2） 構(gòu)造Huffman樹： （3） 在左分枝標0,右分枝標1: （4） 確定Huffman編碼： （5）譯碼：例. 給定代碼序列： 0 0 1 0 0 0 1 1 1 0 1 0 1 0

13、1 0 1 1 1 10文本為：A A F A R A D E T 散列存儲6、 內(nèi)排序 希爾排序void ShellPass(SeqList R，int d) /希爾排序中的一趟排序，d為當前增量 for(i=d+1;i<=n；i+) /將Rd+1n分別插入各組當前的有序區(qū) if(Ri.key<Ri-d.key) R0=Ri;j=i-d； /R0只是暫存單元，不是哨兵 do /查找Ri的插入位置 Rj+d；=Rj； /后移記錄 j=j-d； /查找前一記錄 while(j>0&&R0.key<Rj.key)； Rj+d=R0； /插入Ri到正確的位置上

14、 /endif /ShellPass void ShellSort(SeqList R) int increment=n； /增量初值，不妨設n>0 do increment=increment/3+1； /求下一增量 ShellPass(R，increment)； /一趟增量為increment的Shell插入排序 while(increment>1) /ShellSort 直接插入排序void lnsertSort(SeqList R) /對順序表R中的記錄R1.n按遞增序進行插入排序 int i，j； for(i=2;i<=n；i+) /依次插入R2，Rn if(Ri.

15、key<Ri-1.key)/若Ri.key大于等于有序區(qū)中所有的keys，則Ri /應在原有位置上 R0=Ri;j=i-1; /R0是哨兵，且是Ri的副本 do /從右向左在有序區(qū)R1i-1中查找Ri的插入位置 Rj+1=Rj； /將關(guān)鍵字大于Ri.key的記錄后移 j- ； while(R0.key<Rj.key)； /當Ri.keyRj.key時終止 Rj+1=R0； /Ri插入到正確的位置上 /endif /InsertSort 選擇排序void SelectSort(SeqList R) int i，j，k； for(i=1;i<n;i+)/做第i趟排序(1in-1)

16、 k=i； for(j=i+1;j<=n;j+) /在當前無序區(qū)Ri.n中選key最小的記錄Rk if(Rj.key<Rk.key) k=j; /k記下目前找到的最小關(guān)鍵字所在的位置 if(k!=i) /交換Ri和Rk R0=Ri；Ri=Rk；Rk=R0； /R0作暫存單元 /endif /endfor /SeleetSort 交換排序void BubbleSort(SeqList R) /R（l.n)是待排序的文件，采用自下向上掃描，對R做冒泡排序 int i，j； Boolean exchange； /交換標志 for(i=1;i<n;i+) /最多做n-1趟排序 exc

17、hange=FALSE； /本趟排序開始前，交換標志應為假 for(j=n-1;j>=i；j-) /對當前無序區(qū)Ri.n自下向上掃描 if(Rj+1.key<Rj.key)/交換記錄 R0=Rj+1； /R0不是哨兵，僅做暫存單元 Rj+1=Rj； Rj=R0； exchange=TRUE； /發(fā)生了交換，故將交換標志置為真 if(!exchange) /本趟排序未發(fā)生交換，提前終止算法 return； /endfor(外循環(huán)) /BubbleSortvoid QuickSort(SeqList R，int low，int high) /對Rlow.high快速排序 int piv

18、otpos； /劃分后的基準記錄的位置 if(low<high)/僅當區(qū)間長度大于1時才須排序 pivotpos=Partition(R，low，high)； /對Rlow.high做劃分 QuickSort(R，low，pivotpos-1)； /對左區(qū)間遞歸排序 QuickSort(R，pivotpos+1，high)； /對右區(qū)間遞歸排序 /QuickSort 歸并排序void Merge(SeqList R，int low，int m，int high) /將兩個有序的子文件Rlow.m)和Rm+1.high歸并成一個有序的 /子文件Rlow.high int i=low，j=m

19、+1，p=0； /置初始值 RecType *R1； /R1是局部向量，若p定義為此類型指針速度更快 R1=(ReeType *)malloc(high-low+1)*sizeof(RecType)； if(! R1) /申請空間失敗 Error("Insufficient memory available!")； while(i<=m&&j<=high) /兩子文件非空時取其小者輸出到R1p上 R1p+=(Ri.key<=Rj.key)?Ri+：Rj+； while(i<=m) /若第1個子文件非空，則復制剩余記錄到R1中 R1p+

20、=Ri+； while(j<=high) /若第2個子文件非空，則復制剩余記錄到R1中 R1p+=Rj+； for(p=0，i=low；i<=high；p+，i+) Ri=R1p；/歸并完成后將結(jié)果復制回Rlow.high /Merge三、選擇題1、二叉樹的第i層至多有2(i 1)個結(jié)點；深度為k的二叉樹至多有2k 1個結(jié)點（根結(jié)點的深度為1）2、二維數(shù)組A10.20，5.10采用行序為主存方式存儲，每個元素占4個存儲單元，且A10，5的存儲地址為1000，則A18，9的存儲地址？a.不管按行還是按列，都是順序存儲。按行存儲，每行10-5+1共6個元素。A10, 9距離A10, 5

21、之間相差4個元素；A18, 9與A10, 9相差8行，共8×6=48個元素；所以A18, 9與A10, 5相差4+48=52個元素，共52×4=208個存儲單元；A18, 9的地址應該是1208。 b.更一般的算法：基地址+（行標之差×每行元素個數(shù)+列標之差）×元素所占存儲單元3、n個頂點的連通圖最多多少邊、最少多少條邊？答：最多n（n-1）/2,最少n-14、設一個無向圖有5頂點,度數(shù)分別是4,3,3,2,2,求該圖邊數(shù)？答：每條邊與兩個頂點相連接,所以所有頂點上的度數(shù)之和就是圖中邊的兩倍,本題中共有4+3+3+2+2=14個邊的端點,因而共有14/2

22、=7條邊。6、 建立最小堆建堆過程6、huffman編碼7、 直接排序法過程用直接排序法將無序列49，38，65，97，76，13，27按照從大到小的順序排為有序列時，每一趟將把當前最大的放到第一位，然后例舉出前五趟就是每一趟將把當前最大的放到第一位即第一趟97，49，38，65，76，13，27第二趟97，76，49，38，65，13，27，第三趟97，76，65，49，38，13，27，第四趟97，76，65，49，38，13，27，第五趟97，76，65，49，38，13，27 8、四、編程題1、 二叉樹：二叉樹的建立：#include <stdio.h>#define El

23、emType char/節(jié)點聲明，數(shù)據(jù)域、左孩子指針、右孩子指針typedef struct BiTNode char data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/先序建立二叉樹BiTree CreateBiTree() char ch; BiTree T; scanf("%c",&ch); if(ch='#')T=NULL; else T = (BiTree)malloc(sizeof(BiTNode); T->data = ch; T->lchild = CreateBi

24、Tree(); T->rchild = CreateBiTree(); return T;/返回根節(jié)點/先序遍歷二叉樹void PreOrderTraverse(BiTree T) if(T) printf("%c",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); /中序遍歷void InOrderTraverse(BiTree T) if(T) PreOrderTraverse(T->lchild); printf("%c",T->

25、;data); PreOrderTraverse(T->rchild); /后序遍歷void PostOrderTraverse(BiTree T) if(T) PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); printf("%c",T->data); void main() BiTree T; T = CreateBiTree();/建立 PreOrderTraverse(T);/輸出 getch(); 在二叉樹中插入結(jié)點x，找中序首點（順著左支一直走）、尾點（順右）/首先執(zhí)行查找

26、算法，找出被插結(jié)點的父親結(jié)點。判斷被插結(jié)點是其父親結(jié)點的左、右兒子。將被插結(jié)點作為葉子結(jié)點插入。若二叉樹為空。則首先單獨生成根結(jié)點。注意：新插入的結(jié)點總是葉子結(jié)點。/一typedef struct node int data; struct node * lchild; struct node * rchild;node;node * Insert(node *t , int key) if(t = NULL) node * p; p = (node *)malloc(sizeof(node); p->data = key; p->lchild = NULL; p->rchi

27、ld = NULL; t = p; else if(key < t->data) t->lchild = Insert(t->lchild, key); else t->rchild = Insert(t->rchild, key); return t; /important!二typedef struct Node int data; struct Node *lc,*rc;node,*Link;void insert( Link *L,int n ) if( *L = NULL ) ( *L ) = new node;/若找到插入位置，則新申請節(jié)點 (

28、*L ) -> lc = ( *L ) -> rc = NULL; ( *L ) -> data = n; else if( n = ( *L ) -> data )/若n與當前節(jié)點的值相等，則不需插入了 return ; else if( n < ( *L ) -> data )/若n比當前節(jié)點的值小，則往當前節(jié)點的左子樹插 insert( &( *L ) -> lc,n ); else/若n比當前節(jié)點的值大，則往當前節(jié)點的右子樹插 insert( &( *L ) -> rc,n ); 中序遍歷：typedef struct B

29、iTNode/*結(jié)點結(jié)構(gòu) */ int data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;void Inorder(BiTree T) /* 中序遍歷二叉樹 */ if (T) Inorder(T->lchild); /* 遍歷左子樹 */ printf("%d ",T->data); /*訪問結(jié)點 */ Inorder(T->rchild);/* 遍歷右子樹 */ 當調(diào)用該子函數(shù)時：加入傳的就是根節(jié)點，他將不斷的遞歸一直到最左的一個葉子節(jié)點，就是不斷重復T位最左葉子節(jié)點是那么第一句再遞歸式就失敗了

30、，所有退回上一層輸出，緊接著就執(zhí)行開始遞歸以此類推在遞歸第三句時候也是嚴格按著1,2,3這個順序執(zhí)行。 求一度結(jié)點，葉子結(jié)點int count=0;void preOrder(TTree:tree) if (tree!=NULL) count+; / 先根訪問，且計數(shù) / 這里顯示tree的數(shù)據(jù) if (tree->Left!=NULL) preOrder(tree->Left); if(tree->Right!=NULL) preOrder(tree->Right); main() count=0; preOrder(tree); / 顯示count 2、 檢索： 二

31、分法搜索（遞歸與非遞歸）必背！遞歸：void Search(int p,int low,int height,int key) int middle=(low+height)/2; if(low>height) printf("沒有該數(shù)！"); return; if(pmiddle=key) printf("%dn",middle); return; else if(pmiddle>key) Search(p,low,middle-1,key); else if(pmiddle<key) Search(p,middle+1,height,key); int main() int p5=1,2,3,4,5; Search(p,0,4,4); return 0; 非遞歸int BinarySearch(int* s, int x, int low, int high) int mid; while(l