復(fù)習(xí) 數(shù) 據(jù) 結(jié) 構(gòu)

1、數(shù)據(jù)結(jié)構(gòu)第1章 緒論重點(diǎn)歸納1、（1）數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中的計(jì)算機(jī)操作對象以及它們之間的關(guān)系和操作的學(xué)科。（2）數(shù)據(jù)結(jié)構(gòu)是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。（3）數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Data_Structure （D，R），其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。2、數(shù)據(jù)是對信息的一種符號表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的總稱。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定

2、義在該模型上的一組操作。它實(shí)際上就是對該數(shù)據(jù)結(jié)構(gòu)的定義，定義了一個(gè)數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組算法。抽象數(shù)據(jù)類型用三元組（D，S，P）描述.3、邏輯結(jié)構(gòu)是指數(shù)據(jù)之間的相互關(guān)系。通常分為四類結(jié)構(gòu)：（1）集合（2）線性結(jié)構(gòu)（3）樹型結(jié)構(gòu)（4）圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 4、存儲結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，又稱為數(shù)據(jù)的物理結(jié)構(gòu)。通常由四種基本的存儲方法實(shí)現(xiàn)：（1）順序存儲方式（2）鏈?zhǔn)酱鎯Ψ绞剑?）索引存儲方式（4）散列存儲方式5、算法是對特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個(gè)或多個(gè)操作。具有下列特性：有窮性確定性可行性輸入輸出。評價(jià)算法：正確可讀健壯高效。6、時(shí)間

3、復(fù)雜度：以基本運(yùn)算的原操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。一般情況下，算法中原操作重復(fù)執(zhí)行的次數(shù)是規(guī)模n的某個(gè)函數(shù)T(n)。常見的漸進(jìn)時(shí)間復(fù)雜度有：(1)(log2n)(n)(nlog2n)(n2)(n3)(2n) O(n!) O(nn)注意：有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。7、算法的存儲空間度量：若輸入數(shù)據(jù)所占空間只取決與問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。原地工作：若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。8、（1）for (int i=1; i<=n; i+) for (int j

4、=1; j<=i; j+)語句頻度是n (n+1)/2（2）for( i=1; i<=n; i+) for (j=1; j<=i; j+) for (k=1; k<=j; k+)語句頻度是n (n+1)(n+2)/6（3）循環(huán)條件是 (y+1)2n, 即 y-1,而 y 的初始值是0，則語句頻度應(yīng)為。習(xí)題：1. 以下屬于邏輯結(jié)構(gòu)的是（ ）。A順序表 B. 散列表 C. 有序表 D. 單鏈表第2章 線性表重點(diǎn)歸納1、線性表是具有相同數(shù)據(jù)類型的n(n0)個(gè)數(shù)據(jù)元素的有限序列，是最簡單、最基本、也是最常用的一種線性結(jié)構(gòu)，2、順序表上基本運(yùn)算的實(shí)現(xiàn)（1）順序表具有按數(shù)據(jù)元素的序

5、號隨機(jī)存取的特點(diǎn)，時(shí)間復(fù)雜度為O(1)。（2）按值x查找：主要運(yùn)算是比較，比較的次數(shù)與值x在表中的位置有關(guān)，也與表長有關(guān)，平均比較次數(shù)為（n+1）/2，時(shí)間復(fù)雜度為O(n)。（3）插入運(yùn)算：在第i個(gè)位置上插入x，從an到ai都要向下移動一個(gè)位置，共移動ni1個(gè)元素。等概率情況下，平均移動數(shù)據(jù)元素的次數(shù)： 說明：在順序表上做插入操作需移動表中一半的數(shù)據(jù)元素，時(shí)間復(fù)雜度為O(n)。（4）刪除運(yùn)算：刪除第i個(gè)元素，從ai+1到an都要向上移動一個(gè)位置，共移動 n-i 個(gè)元素。等概率情況下，平均移動數(shù)據(jù)元素的次數(shù)： 說明：順序表上作刪除運(yùn)算時(shí)大約需要移動表中一半的元素，時(shí)間復(fù)雜度為O(n)。3、單鏈表

6、上基本運(yùn)算的實(shí)現(xiàn)（1）建立帶頭結(jié)點(diǎn)的單鏈表頭插法：讀入的數(shù)據(jù)元素的順序與生成的鏈表中元素的順序是相反的。LinkList Creat_LinkList1( ) LinkList L=(LNode *)malloc(sizeof(LNode); L->next=NULL； /*空表*/LNode *s;int x; /*設(shè)數(shù)據(jù)元素的類型為int*/scanf(%d,&x);while (x!=flag) s=malloc(sizeof(LNode);s->data=x;s->next=L->next; L->next=s; scanf (%d,&x)

7、; return L;尾插法：讀入的數(shù)據(jù)元素的順序與生成的鏈表中元素的順序是一致的。LinkList Creat_LinkList2( ) LinkList L=(LNode *)malloc(sizeof(LNode); L->next=NULL； /*空表*/LNode *s,*r=L;int x; /*設(shè)數(shù)據(jù)元素的類型為int*/scanf(%d,&x);while (x!=flag) s=malloc(sizeof(LNode); s->data=x;r->next=s; r=s; /*r指向新的尾結(jié)點(diǎn)*/ scanf(%d,&x);r->nex

8、t=NULL; return L;（2）求表長設(shè)L是帶頭結(jié)點(diǎn)的單鏈表(線性表的長度不包括頭結(jié)點(diǎn))。int Length_LinkList1 (LinkList L) LNode * p=L; /*p指向頭結(jié)點(diǎn)*/int j=0;while (p->next) p=p->next; j+ /*p所指的是第 j 個(gè)結(jié)點(diǎn)*/return j;設(shè)L是不帶頭結(jié)點(diǎn)的單鏈表。int Length_LinkList2 (LinkList L) LNode * p=L;int j;if (p=NULL) return 0; /*空表的情況*/j=1; /*在非空表的情況下，p所指的是第一個(gè)結(jié)點(diǎn)*/w

9、hile (p->next ) p=p->next; j+ return j;兩個(gè)算法的時(shí)間復(fù)雜度均為O(n)。不帶頭結(jié)點(diǎn)的單鏈表空表情況要單獨(dú)處理，而帶上頭結(jié)點(diǎn)之后則不用了。在以后的算法中不加說明則認(rèn)為單鏈表是帶頭結(jié)點(diǎn)的。（3）查找按序號查找 Get_Linklist(L,i)Lnode * Get_LinkList(LinkList L, int i); /*在單鏈表L中查找第i個(gè)元素結(jié)點(diǎn)*/ LNode * p=L;int j=0;while (p->next !=NULL && j<i ) p=p->next; j+; if (j=i) r

10、eturn p;else return NULL; 按值查找即定位 Locate_LinkList(L,x)Lnode * Locate_LinkList( LinkList L, ElemType x) /*在單鏈表L中查找值為x的結(jié)點(diǎn)*/ LNode * p=L->next;while ( p!=NULL && p->data != x)p=p->next; return p;以上兩個(gè)算法的時(shí)間復(fù)雜度均為O(n)。（4）插入圖1-2-1 在*p之后插入*s p s×后插結(jié)點(diǎn)：設(shè)p指向單鏈表中某結(jié)點(diǎn)，s指向待插入的值為x的新結(jié)點(diǎn)，將*s插入到*p的

11、后面，插入過程如圖1-2-1。圖1-2-2 在*p之前插入*s s×pq操作如下： s->next=p->next;p->next=s;注意：兩個(gè)指針的操作順序不能交換。后插操作的時(shí)間復(fù)雜度為O(1)。前插結(jié)點(diǎn)：設(shè)指向鏈表中某結(jié)點(diǎn)，指向待插入的值為x的新結(jié)點(diǎn)，將*s插入到*p的前面，插入過程如下圖1-2-2，與后插不同的是：首先要找到*p的前驅(qū)*q，然后再完成在*q之后插入*s，設(shè)單鏈表頭指針為L。操作如下：q=L;while (q->next!=p) q=q->next; /*找*p的直接前驅(qū)*/s->next=q->next; q->

12、;next=s;前插操作因?yàn)橐?p的前驅(qū)，時(shí)間性能為O(n)。其實(shí)前插操作可以用后插操作來實(shí)現(xiàn)，即仍然可以將 *s 插入到 *p 的后面，然后將->data與s->data交換即可，這樣即滿足了邏輯關(guān)系，也能使得時(shí)間復(fù)雜度為O(1)。（5）刪除刪除p結(jié)點(diǎn)：設(shè)p指向單鏈表中某結(jié)點(diǎn)，刪除*p。操作過程如下圖1-2-3。要實(shí)現(xiàn)對結(jié)點(diǎn)*p的刪除，首先要找到*p的前驅(qū)結(jié)點(diǎn)*q，然后完成指針的操作即可。圖1-2-3 刪除*p pq×操作如下：q=L;while (q->next!=p) q=q->next; /*找*p的直接前驅(qū)*/q->next=p->ne

13、xt;free(p);顯然找*p前驅(qū)的時(shí)間復(fù)雜度為O(n)。刪除p結(jié)點(diǎn)的后繼結(jié)點(diǎn)：若要刪除*p的后繼結(jié)點(diǎn)(假設(shè)存在)，則可以直接完成：操作如下：s=p->next;p->next=s->next;free(s);該操作的時(shí)間復(fù)雜度為O(1)。4、循環(huán)鏈表：在循環(huán)鏈表上的操作基本上與非循環(huán)鏈表相同，只是將原來判斷指針是否為NULL變?yōu)槭欠袷穷^指針而已，沒有其它較大的變化。對于單鏈表只能從頭結(jié)點(diǎn)開始遍歷整個(gè)鏈表，而對于單循環(huán)鏈表則可以從表中任意結(jié)點(diǎn)開始遍歷整個(gè)鏈表。不僅如此，有時(shí)對鏈表常做的操作是在表尾、表頭進(jìn)行，此時(shí)可以改變一下鏈表的標(biāo)識方法，不用頭指針而用一個(gè)指向尾結(jié)點(diǎn)的指針

14、R來標(biāo)識，可以使得操作效率得以提高。5、雙向鏈表圖1-2-5 雙向鏈表中刪除結(jié)點(diǎn)p××（1）插入：設(shè)p指向雙向鏈表中某結(jié)點(diǎn)，s指向待插入的值為x的新結(jié)點(diǎn)，將*s插入到*p的前面，插入過程如下圖1-2-4。圖1-2-4 雙向鏈表中的結(jié)點(diǎn)插入p××操作如下：s->prior=p->prior; p->prior->next=s;s->next=p; p->prior=s;指針操作的順序不是唯一的，但也不是任意的，操作必須要放到操作的前面完成，否則*p的前驅(qū)結(jié)點(diǎn)的指針就丟掉了。只要把每條指針操作的涵義搞清楚，就不難理解了。（

15、2）刪除：設(shè)p指向雙向鏈表中某結(jié)點(diǎn)，刪除*p。操作過程如下圖1-2-5。操作如下：p->prior->next=p->next;p->next->prior=p->prior; free(p); 6、靜態(tài)鏈表靜態(tài)鏈表借助數(shù)組來描述線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，這里的指針是結(jié)點(diǎn)的相對地址(數(shù)組的下標(biāo))。有關(guān)基于靜態(tài)鏈表上的線性表的操作基本與動態(tài)鏈表相同，除了一些描述方法有些區(qū)別外，算法思路是相同的。習(xí)題：1. 表長為n的順序存儲的線性表，當(dāng)在任何位置上刪除一個(gè)元素的概率相等時(shí)，刪除一個(gè)元素所需移動元素的平均個(gè)數(shù)為（ ）。An B. n/2 C. (n-1)/2 D.

16、(n+1)/22. 在一個(gè)長度為n的順序存儲線性表中，刪除第i個(gè)元素(1in+1)時(shí)，需要從前向后依次前移（ ）個(gè)元素。A. n-i B. n-i+1 C. n-i-1 D. i3. 設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為TYPEDEF STRUCT NODE /鏈表結(jié)點(diǎn)定義ELEMTYPE DATA; /數(shù)據(jù)STRUCT NODE * NEXT; /結(jié)點(diǎn)后繼指針 LISTNODE;已知指針P所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*P之后插入結(jié)點(diǎn)*S，則應(yīng)執(zhí)行下列哪一個(gè)操作（ ）。A S->NEXT = P; P->NEXT = S; B S->NEXT = P->NEXT; P->NEXT

17、= S;C S->NEXT = P->NEXT; P = S; D P->NEXT = S; S->NEXT = P;4. 在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行（ ）。A. HL = p; p->next = HL; B. p->next = HL; HL = p;C. p->next = HL; p = HL; D. p->next = HL->next; HL->next = p;5. 非空的循環(huán)單鏈表FIRST的尾結(jié)點(diǎn)（由P所指向）滿足：（ ）AP->NEXT = NULL; BP = NULL

18、; CP->NEXT = FIRST; DP = FIRST;第3章 棧、隊(duì)列和數(shù)組重點(diǎn)歸納1、棧和隊(duì)列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線性表。棧又稱為后進(jìn)先出的線性表，隊(duì)列又稱為先進(jìn)先出的線性表。線性表?xiàng)ｊ?duì)列Insert(L, i, x)1in+1Insert(S, n+1, x)Insert(Q, n+1, x)Delete(L, i) 1inDelete(S, n)Delete(Q, 1)2、順序棧形式描述：靜態(tài)分配：#define STACKSIZE 100typedef struct SElemType elemSTACKSIZE; int top; SqStack;這

19、里注意，非空棧時(shí)top始終在棧頂元素的位置。動態(tài)分配：#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct SElemType *base;SElemType *top;int stacksize; SqStack;這里注意，非空棧時(shí)top始終在棧頂元素的下一個(gè)位置。順序棧上基本操作的實(shí)現(xiàn)（1）入棧：若棧不滿，則將 e 插入棧頂靜態(tài)分配：Status Push (SqStack &S, SElemType e)if(S.top=STACKSIZE-1) return ERROR;/*棧滿不能入棧*/else

20、 S.elem+S.top=e;/*top始終在棧頂元素的位置*/return OK;動態(tài)分配：Status Push (SqStack &S, SElemType e) if (S.top-S.base>=S.stacksize) /*棧滿，追加存儲空間*/ *S.top+ = e; /*top始終在棧頂元素的下一個(gè)位置*/ return OK;（2）出棧：若棧不空，則刪除S的棧頂元素，用 e 返回其值，并返回OK，否則返回ERROR。靜態(tài)分配：Status Pop(Sqstack &s, SElemType &e) if(S.top=-1) return ER

21、ROR; e= S.elemS.top- -; return OK; 動態(tài)分配：Status Pop (SqStack &S, SElemType &e) if (S.top=S.base) return ERROR; e = *-S.top; return OK;3、鏈棧：因?yàn)闂Ｖ械闹饕\(yùn)算是在棧頂插入、刪除，顯然在鏈表的頭部做棧頂是最方便的，而且沒有必要象單鏈表那樣為了運(yùn)算方便附加一個(gè)頭結(jié)點(diǎn)。鏈棧上基本操作的實(shí)現(xiàn)（1）入棧：Status Push（LinkStack &S, SElemType e） StackNode *q; q=（StackNode *）mall

22、oc（sizeof（StackNode）; q->data=e; q->next=S; S=q;return OK; （2）出棧Status Pop (LinkStack &S, SElemType &e) StackNode *p;if （S= =NULL） return ERROR;else e = S->data;p = S; S = S->next;free (p);return OK; 4、鏈隊(duì)列上基本操作的實(shí)現(xiàn)（1）入隊(duì)：插入元素e為Q的新的隊(duì)尾元素Status EnQueue (LinkQueue &Q, QElemType e)

23、QNode *p;p = （QNode *）malloc（sizeof（QNode）;p->data = e; p->next = NULL;Q.rear->next = p; Q.rear = p; return OK;（2）出隊(duì)：若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回其值，并返回OK；否則返回ERROR。Status DeQueue (LinkQueue &Q, QElemType &e) if (Q.front = Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front-&

24、gt;next = p->next; if(Q.rear=p) Q.rear= Q.front; free (p);return OK;5、順序隊(duì)列：設(shè)隊(duì)頭指針指向隊(duì)頭元素前面一個(gè)位置，隊(duì)尾指針指向隊(duì)尾元素（這樣的設(shè)置是為了某些運(yùn)算的方便，并不是唯一的方法）。（1）入隊(duì)： sq->data+sq->rear=x; （2）出隊(duì)： x=sq->data+sq->front;6、循環(huán)隊(duì)列上基本操作的實(shí)現(xiàn)（1）入隊(duì)：Status EnQueue (SqQueue &Q, QElemType e) if(Q.rear+1)%MAXQSIZE = Q.front) r

25、eturn ERROR; Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK;（2）出隊(duì)：Status DeQueue (SqQueue &Q, QElemType &e) if (Q.front = = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;（3）循環(huán)隊(duì)列元素個(gè)數(shù)：(Q.rear-Q.front+MAXQSIZE) %MAXQSIZE7、數(shù)組：一般采用順序存儲，是一個(gè)隨機(jī)存取結(jié)構(gòu)

26、。二維數(shù)組按行優(yōu)先尋址計(jì)算方法，每個(gè)數(shù)組元素占據(jù)d個(gè)地址單元。設(shè)數(shù)組的基址為LOC(a11)：LOC(aij)=LOC(a11)+(i-1)*n+j-1)*d設(shè)數(shù)組的基址為LOC(a00)：LOC(aij)=LOC(a00)+( i*n+j )*d二維數(shù)組按列優(yōu)先尋址計(jì)算方法。設(shè)數(shù)組的基址為LOC(a11)：LOC(aij)=LOC(a11)+(j-1)*n+i-1)*d設(shè)數(shù)組的基址為LOC(a00)：LOC(aij)=LOC(a00)+( j*n+i )*d8、特殊矩陣的壓縮存儲（假設(shè)以行序?yàn)橹餍颍?）對稱矩陣：將對稱矩陣A壓縮存儲到SAn(n+1)/2中，aij的下標(biāo)i、j與在SA中的對

27、應(yīng)元素的下標(biāo)k的關(guān)系。（2）三角矩陣與對稱矩陣類似，不同之處在于存完下（上）三角中的元素之后，接著存儲對角線上（下）方的常量，因?yàn)槭峭粋€(gè)常數(shù)，所以存一個(gè)即可。將三角矩陣A壓縮存儲到SAn(n+1)/2+1中，aij的下標(biāo)i、j與在SA中的對應(yīng)元素的下標(biāo)k的關(guān)系。（3）三對角矩陣將三對角矩陣A壓縮存儲到SA3n-2中，aij的下標(biāo)i、j與在SA中的對應(yīng)元素的下標(biāo)k的關(guān)系。習(xí)題：選擇題：1. 若已知一個(gè)棧的入棧序列是1,2,3,.n，其輸出序列為p1,p2,p3,.pn，若p1=n，則pi為（ ）A. i B. n-i C. n-i+1 D.不確定2. 若一個(gè)棧的輸入序列為1，2，3 .n，輸出

28、序列的第一個(gè)元素是i，則第j個(gè)輸出元素是（ ）Ai-j-1 B. i-j C. j-i+1 D. 不確定3. 棧在（ ）中應(yīng)用。A. 遞歸調(diào)用 B. 子程序調(diào)用 C. 表達(dá)式求值 D. A，B，C4. 設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號是否配對出現(xiàn)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu) B. 隊(duì)列 C. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) D. 棧5. 在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個(gè)（ ）結(jié)構(gòu)。A. 棧 B. 隊(duì)列C. 數(shù)組 D. 線性表6. 向一個(gè)帶頭結(jié)點(diǎn)HS的鏈

29、棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，則執(zhí)行（ ）A.HS->next = s; B. s->next = HS->next; HS->next = s ;C.s->next = HS ; HS = s ; D.s->next = HS ; HS = HS->next;7. 一個(gè)循環(huán)隊(duì)列Q最多可存儲m個(gè)元素，已知其頭尾指針分別是front和rear，則判定該循環(huán)隊(duì)列為滿的條件是（ ）A.Q.rear - Q.front = m B.Q.rear != Q.frontC.Q.front =( Q.rear +1)%mD.Q.front = Q.rear %m +18

30、. 循環(huán)隊(duì)列用數(shù)組A0.m-1存放其元素值，已知其頭尾指針分別為front和rear，則當(dāng)前元素個(gè)數(shù)為（ ）。A(rear-front+m) mod m Brear-front+1 Crear-front-1 Drear-front9. 若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？( ) A. 1和5 B. 2和4 C. 4和2 D. 5和110. 二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，其行下標(biāo)i=0,1,8,列下標(biāo)j=1,2,10。若A按行先存儲，元素A8,5的起始地址與當(dāng)

31、A按列先存儲時(shí)的元素（ ）的起始地址相同。設(shè)每個(gè)字符占一個(gè)字節(jié)。A. A8,5 B. A3,10 C. A5,8 D. A0,911. 設(shè)n階方陣是一個(gè)上三角矩陣，則需存儲的元素個(gè)數(shù)為（ ）An Bn*n Cn*n/2 Dn(n+1)/2 12. 設(shè)有一個(gè)10階的對稱矩陣A，采用壓縮存儲方式，以行序?yàn)橹鞔鎯?，a11為第一元素，其存儲地址為1，每個(gè)元素占一個(gè)地址空間，則a85（即該元素下標(biāo)i=85）的地址為（ ）。A. 13 B. 33 C. 18 D. 4013. 若對n階對稱矩陣A1.n，1.n以行序?yàn)橹餍蚍绞较聦⑵湎氯堑脑兀òㄖ鲗蔷€上的所有元素）依次存放于一維數(shù)組B1.n(n+1)

32、/2中，則在B中確定aij (i<j)的位置k的關(guān)系為（ ）。Ai*(i-1)/2+j Bj*(j-1)/2+i Ci*(i+1)/2+j Dj*(j+1)/2+i第4章 樹和二叉樹重點(diǎn)歸納1、二叉樹：是有序的，即若將其左、右子樹顛倒，就成為另一棵不同的二叉樹。即使樹中結(jié)點(diǎn)只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的一棵二叉樹稱作滿二叉樹。完全二叉樹：一棵深度為k的有n個(gè)結(jié)點(diǎn)的二叉樹，對樹中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號，如果編號為i（1in）的結(jié)點(diǎn)與滿二叉樹中編號為i的結(jié)點(diǎn)在二

33、叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。完全二叉樹的特點(diǎn)是：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點(diǎn)集中在樹的左部。2、二叉樹的性質(zhì)：性質(zhì)1：一棵非空二叉樹的第i層上最多有2i-1個(gè)結(jié)點(diǎn)（i1）。性質(zhì)2：一棵深度為k的二叉樹中，最多具有2k1個(gè)結(jié)點(diǎn)。性質(zhì)3：對于一棵非空的二叉樹，如果葉子結(jié)點(diǎn)數(shù)為n0，度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則有：n0n21 性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k為+1。性質(zhì)5：對于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從1開始順序編號，則對于任意的序號為i的結(jié)點(diǎn)，有：（1）如果i1，則序號i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號為；

34、如果i1，則序號為i的結(jié)點(diǎn)是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。（2）如果2in，則序號為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號為2i；如果2in，則序號為i的結(jié)點(diǎn)無左孩子。（3）如果2i1n，則序號為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號為2i1；如果2i1n，則序號為i的結(jié)點(diǎn)無右孩子。此外，若對二叉樹的根結(jié)點(diǎn)從0開始編號，則相應(yīng)的i號結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為，左孩子的編號為2i1，右孩子的編號為2i2。3、二叉樹的存儲結(jié)構(gòu)二叉鏈表形式描述：typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /*左右孩子指針*/ BiTNode,*BiTree

35、;盡管在二叉鏈表中無法由結(jié)點(diǎn)直接找到其雙親，但由于二叉鏈表結(jié)構(gòu)靈活，操作方便，對于一般情況的二叉樹，甚至比順序存儲結(jié)構(gòu)還節(jié)省空間。后面所涉及到的二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)不加特別說明的都是指二叉鏈表結(jié)構(gòu)。4、遍歷二叉樹（必背的七個(gè)算法） 遍歷二叉樹是以一定規(guī)則將二叉樹中結(jié)點(diǎn)排列成一個(gè)線性序列，實(shí)質(zhì)是對一個(gè)非線性結(jié)構(gòu)進(jìn)行線性化操作。（1）前序遍歷的遞歸實(shí)現(xiàn)void PreOrder（BiTree bt）/*前序遍歷二叉樹bt*/ if (bt=NULL) return; /*遞歸調(diào)用的結(jié)束條件*/Visit（bt->data）; /*訪問結(jié)點(diǎn)的數(shù)據(jù)域*/ PreOrder（bt->lchi

36、ld）; /*前序遞歸遍歷bt的左子樹*/PreOrder（bt->rchild）; /*前序遞歸遍歷bt的右子樹*/ （2）中序遍歷的遞歸實(shí)現(xiàn)void InOrder（BiTree bt） /*中序遍歷二叉樹bt*/ if (bt=NULL) return; /*遞歸調(diào)用的結(jié)束條件*/InOrder（bt->lchild）; /*中序遞歸遍歷bt的左子樹*/Visit（bt->data）; /*訪問結(jié)點(diǎn)的數(shù)據(jù)域*/InOrder（bt->rchild）; /*中序遞歸遍歷bt的右子樹*/ （3）后序遍歷的遞歸實(shí)現(xiàn)void PostOrder（BiTree bt）/*后

37、序遍歷二叉樹bt*/ if (bt=NULL) return; /*遞歸調(diào)用的結(jié)束條件*/PostOrder（bt->lchild）; /*后序遞歸遍歷bt的左子樹*/PostOrder（bt->rchild）; /*后序遞歸遍歷bt的右子樹*/ Visit（bt->data）; /*訪問結(jié)點(diǎn)的數(shù)據(jù)域*/（4）層序遍歷的實(shí)現(xiàn)一維數(shù)組QueueMAX_TREE_SIZE用以實(shí)現(xiàn)隊(duì)列，變量front和rear分別表示當(dāng)前對隊(duì)首元素和隊(duì)尾元素在數(shù)組中的位置。void LevelOrder（BiTree bt） /*層序遍歷二叉樹bt*/BiTree QueueMAX_TREE_SI

38、ZE; int front,rear; if (bt=NULL) return; front=-1; rear=0; queuerear=bt;while(front!=rear) Visit(queue+front->data); /*訪問隊(duì)首結(jié)點(diǎn)數(shù)據(jù)域*/ if (queuefront->lchild!=NULL) /*將隊(duì)首結(jié)點(diǎn)的左孩子結(jié)點(diǎn)入隊(duì)列*/ queue+rear=queuefront->lchild; if (queuefront->rchild!=NULL) /*將隊(duì)首結(jié)點(diǎn)的右孩子結(jié)點(diǎn)入隊(duì)列*/queue+rear=queuefront->rch

39、ild; （5）前序遍歷的非遞歸實(shí)現(xiàn)二叉樹以二叉鏈表存放，一維數(shù)組stackMAX_TREE_SIZE用以實(shí)現(xiàn)棧，變量top用來表示當(dāng)前棧頂?shù)奈恢谩oid NRPreOrder（BiTree bt）/*非遞歸先序遍歷二叉樹*/ BiTree stackMAX_TREE_SIZE,p; int top; if (bt=NULL) return;top=0;p=bt;while(!(p=NULL&&top=0) while(p!=NULL) Visit(p->data); /*訪問結(jié)點(diǎn)的數(shù)據(jù)域*/ if(top MAX_TREE_SIZE-1)/*將當(dāng)前指針p壓棧*/ st

40、acktop+=p; else printf(“棧溢出”)； return； p=p->lchild； /*指針指向p的左孩子結(jié)點(diǎn)*/ if (top<=0) return; /*?？諘r(shí)結(jié)束*/ else p=stack- -top;/*從棧中彈出棧頂元素*/p=p->rchild; /*指針指向p的右孩子結(jié)點(diǎn)*/（6）中序遍歷的非遞歸實(shí)現(xiàn)只需將先序遍歷的非遞歸算法中的Visit(p->data)移到p=stack- -top和p=p->rchild之間即可。（7）后序遍歷的非遞歸實(shí)現(xiàn)后序遍歷與先序遍歷和中序遍歷不同，在后序遍歷過程中，結(jié)點(diǎn)在第一次出棧后，還需再次

41、入棧，也就是說，結(jié)點(diǎn)要入兩次棧，出兩次棧，而訪問結(jié)點(diǎn)是在第二次出棧時(shí)訪問。因此，為了區(qū)別同一個(gè)結(jié)點(diǎn)指針的兩次出棧，設(shè)置一標(biāo)志flag，令：1 第一次出棧，結(jié)點(diǎn)不能訪問2 第二次出棧，結(jié)點(diǎn)可以訪問 flag當(dāng)結(jié)點(diǎn)指針進(jìn)、出棧時(shí)，其標(biāo)志flag也同時(shí)進(jìn)、出棧。因此，可將棧中元素的數(shù)據(jù)類型定義為指針和標(biāo)志flag合并的結(jié)構(gòu)體類型。定義如下：typedef struct BiTree link; int flag;stacktype;后序遍歷二叉樹的非遞歸算法如下。在算法中，一維數(shù)組stackMAX_TREE_SIZE用于實(shí)現(xiàn)棧的結(jié)構(gòu)，指針變量p指向當(dāng)前要處理的結(jié)點(diǎn)，整型變量top用來表示當(dāng)前棧頂?shù)奈?/p>

42、置，整型變量sign為結(jié)點(diǎn)p的標(biāo)志量。void NRPostOrder(BiTree bt) /*非遞歸后序遍歷二叉樹bt*/ stacktype stackMAX_TREE_SIZE;BiTree p;int top,sign;if (bt=NULL) return;top=-1; /*棧頂位置初始化*/p=bt;while (!(p=NULL && top=-1) if (p!=NULL) /*結(jié)點(diǎn)第一次進(jìn)棧*/ stack+top.link=p; stacktop.flag=1; p=p->lchild; /*找該結(jié)點(diǎn)的左孩子*/ else p=stacktop.l

43、ink; sign=stacktop- -.flag; if (sign=1) /*結(jié)點(diǎn)第二次進(jìn)棧*/ stack+top.link=p; stacktop.flag=2; /*標(biāo)記第二次出棧*/ p=p->rchild; else Visit(p->data); /*訪問該結(jié)點(diǎn)數(shù)據(jù)域值*/ p=NULL; 5、建立二叉鏈表方式存儲的二叉樹void CreateBinTree(BinTree *bt) /*以加入結(jié)點(diǎn)的前序序列輸入，構(gòu)造二叉鏈表*/char ch; scanf("%c",&ch); if (ch='0') *bt=NULL

44、; /*讀入0時(shí)，將相應(yīng)結(jié)點(diǎn)置空*/ else *bt=(BinTNode *)malloc(sizeof(BinTNode); /*生成結(jié)點(diǎn)空間*/ (*bt)->data=ch; CreateBinTree(&(*bt)->lchild); /*構(gòu)造左子樹*/ CreateBinTree(&(*bt)->rchild); /*構(gòu)造右子樹*/6、線索二叉樹（1）按照某種遍歷方式對二叉樹進(jìn)行遍歷，可把二叉樹中所有結(jié)點(diǎn)排列為一個(gè)線性序列，二叉樹中每個(gè)結(jié)點(diǎn)在這個(gè)序列中的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)是什么，二叉樹的存儲結(jié)構(gòu)中并沒有反映出來，只能在對二叉樹遍歷的動態(tài)過程

45、中得到這些信息。為了保留結(jié)點(diǎn)在某種遍歷序列中直接前驅(qū)和直接后繼的位置信息，可以利用具有n個(gè)結(jié)點(diǎn)的二叉樹中的葉子結(jié)點(diǎn)和一度結(jié)點(diǎn)的n1個(gè)空指針域來指示，這些指向直接前驅(qū)結(jié)點(diǎn)和指向直接后繼結(jié)點(diǎn)的指針被稱為線索，加了線索的二叉樹稱為線索二叉樹。線索二叉樹將為二叉樹的遍歷提供許多遍歷，遍歷時(shí)可不需要棧，也不需要遞歸了。（2）線索二叉樹的存儲表示的描述：typedef enum PointerTag Link,Thread;typedef struct BiThrNode TElemType data; struct BiThrNode *lchild,*rchild;PointerTag Ltag,Rt

46、ag;BiThrNode, *BiThrTree;（3）建立一棵中序線索二叉樹：實(shí)質(zhì)上就是遍歷一棵二叉樹。在遍歷過程中，Visit操作是檢查當(dāng)前結(jié)點(diǎn)的左、右指針域是否為空，如果為空，將它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線索。為實(shí)現(xiàn)這一過程，設(shè)指針pre始終指向剛剛訪問過的結(jié)點(diǎn)，即若指針p指向當(dāng)前結(jié)點(diǎn)，則pre指向它的前驅(qū)，以便增設(shè)線索。int InOrderThr(BiThrTree &head,BiThrTree T) /*中序遍歷二叉樹T，將其中序線索化，head指向頭結(jié)點(diǎn)。*/if (!(head=(BiThrNode *)malloc(sizeof(BiThrNode) retu

47、rn 0;head->Ltag=0; head->Rtag=1; /*建立頭結(jié)點(diǎn)*/head->rchild=head; /*右指針回指*/ if (!T) head->lchild =head; /*若二叉樹為空，則左指針回指*/else head->lchild=T; pre= head; InThreading(T); /*中序遍歷進(jìn)行中序線索化*/ pre->rchild=head; pre->rtag=1; /*最后一個(gè)結(jié)點(diǎn)線索化*/ head->rchild=pre; return 1;void InTreading(BiThrTre

48、e p) if (p) InThreading(p->lchild); /*左子樹線索化*/if (!p->lchild) /*前驅(qū)線索*/ p->ltag=1; p->lchild=pre;if (!pre->rchild) /*后繼線索*/ pre->rtag=1; pre->rchild=p; pre=p;InThreading(p->rchild); /*右子樹線索化*/ 7、樹形結(jié)構(gòu)： 在樹形結(jié)構(gòu)中，結(jié)點(diǎn)間具有分支層次關(guān)系，每一層上的結(jié)點(diǎn)只能和上一層中的至多一個(gè)結(jié)點(diǎn)相關(guān)，但可能和下一層的多個(gè)結(jié)點(diǎn)相關(guān)。一棵樹采用孩子兄弟表示法所建立的存儲

49、結(jié)構(gòu)與它所對應(yīng)的二叉樹的二叉鏈表存儲結(jié)構(gòu)是完全相同的。8、樹、森林與二叉樹的轉(zhuǎn)換設(shè)森林F = (T1，T2，Tn);T1 = ( root，t11, t12, , t1m);二叉樹B =( LBT, Node(root), RBT );（1）森林轉(zhuǎn)換為二叉樹的方法：若 F = ，則 B = ;否則，由 ROOT(T1) 對應(yīng)得到Node(root);由 (t11, t12, , t1m )對應(yīng)得到 LBT;由 (T2，T3，Tn )對應(yīng)得到 RBT。（2）二叉樹轉(zhuǎn)換為樹和森林：樹和森林都可以轉(zhuǎn)換為二叉樹，二者不同的是樹轉(zhuǎn)換成的二叉樹，其根結(jié)點(diǎn)無右分支，而森林轉(zhuǎn)換后的二叉樹，其根結(jié)點(diǎn)有右分支。這

50、一轉(zhuǎn)換過程是可逆的，即可以依據(jù)二叉樹的根結(jié)點(diǎn)有無右分支，將一棵二叉樹還原為樹或森林。若 B = , 則 F = ;否則，由 Node(root) 對應(yīng)得到ROOT(T1);由 LBT對應(yīng)得到(t11, t12, , t1m );由 RBT對應(yīng)得到(T2，T3，Tn )。由此，樹和森林的各種操作均可與二叉樹的各種操作相對應(yīng)。應(yīng)當(dāng)注意的是，和樹對應(yīng)的二叉樹，其左、右子樹的概念已改變?yōu)椋?左是孩子，右是兄弟。9、樹和森林的遍歷：可采用對應(yīng)二叉樹的遍歷算法來實(shí)現(xiàn)的樹森林二叉樹先根遍歷前序遍歷前序遍歷后根遍歷中序遍歷中序遍歷10、哈夫曼樹：最小帶權(quán)路徑長度的二叉樹（1）構(gòu)造哈夫曼樹的基本思想是：常見錯誤

51、：在合并中不是選取根結(jié)點(diǎn)權(quán)值最小的兩棵二叉樹（包括已合并的和未合并的），而是選取未合并的根結(jié)點(diǎn)權(quán)值最小的一棵二叉樹與已經(jīng)合并的二叉樹合并。哈夫曼樹的特點(diǎn)：具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有2n1個(gè)結(jié)點(diǎn)。（2）哈夫曼編碼：求哈夫曼編碼，實(shí)質(zhì)上就是在已建立的哈夫曼樹中，從葉結(jié)點(diǎn)開始，沿結(jié)點(diǎn)的雙親鏈域回退到根結(jié)點(diǎn)，每回退一步，就走過了哈夫曼樹的一個(gè)分支，從而得到一位哈夫曼碼值，由于一個(gè)字符的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng)葉結(jié)點(diǎn)所經(jīng)過的路徑上各分支所組成的0，1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的高位碼。利用哈夫曼樹可以構(gòu)造一種不等長的二進(jìn)制編碼，并且構(gòu)造所得的哈夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。難點(diǎn)釋疑遍歷二叉樹的應(yīng)用（1）二叉樹遞歸算法的設(shè)計(jì)技巧對于二叉樹，一般遞歸模型如下：f(b)=c 當(dāng)b=NULL時(shí)f(b)=g(f(b->lchild),f(b->lchild),c) 其他情況其中，f()為遞歸函數(shù)，g為非遞歸函數(shù)，c為常量。（2）統(tǒng)計(jì)一棵給定二叉樹中的所有葉子結(jié)點(diǎn)數(shù)解析：遞歸模型如下：f(b)=0 若b=NULLf(b)=1 若b