算法與數(shù)據(jù)結(jié)構(gòu)C語言習(xí)題參考答案5章匯編

1、學(xué)習(xí) 好資料1. 緒 論1將下列復(fù)雜度由小到大重新排序：A 2nBn!Cn5【答】10 000< n*log 2(n)< n5< 2n < n!D 10 000E. n*log 2 (n)2將下列復(fù)雜度由小到大重新排序：23A n*log 2(n)B n + n + nC.240.5D. n【答】 24< n0.5< n*log 2 (n) < n + n2 + n33 用大“ 0”表示法描述下列復(fù)雜度：5/2 2/5A 5n + nB.6*log 2(n) + 9n4C 3n + n* log 2(n)D.5n2 + n3/2【答】A : 0 (n5

2、/2)B : 0 (n)C：0 (n4)2D： 0 (n2)4按照增長率從低到高的順序排列以下表達(dá)式：4n2 , log3n, 3n , 20n , 2000 , log2nn2/3。又n!應(yīng)排在第幾位？【答】按照增長率從低到高依次為：2000, log3n, log2n , n2/3 , 20n , 4n2 , 3n。n!的增長率比它們中的每一個(gè)都要大，應(yīng)排在最后一位。5. 計(jì)算下列程序片斷的時(shí)間代價(jià)：int i=1;while(i<=n)printf( “i=%dn ”,i);i=i+1;【答】循環(huán)控制變量i從1增加到n,循環(huán)體執(zhí)行n次，第一句i的初始化執(zhí)行次數(shù)為1，第二 句執(zhí)行n次

3、，循環(huán)體中第一句 printf執(zhí)行n次，第二句i從1循環(huán)到n，共執(zhí)行n次。所以該程 序段總的時(shí)間代價(jià)為：T(n) = 1 + n + 2n = 3n+ 1 = O(n)6. 計(jì)算下列程序片斷的時(shí)間代價(jià)：int i=1;while(i<=n)int j=1;while(j<=n)int k=1;while(k<=n)printf( “i=%d,j=%d,k=%dn ”,I,j,k);k=k+1;j=j+1;i=i+1;【答】循環(huán)控制變量i從1增加到n,最外層循環(huán)體執(zhí)行 n次，循環(huán)控制變量j從1增加到n, 中間層循環(huán)體執(zhí)行n次，循環(huán)控制變量k從1增加到n,最內(nèi)層循環(huán)體執(zhí)行n次，所

4、以該程序段 總的時(shí)間代價(jià)為：T(n) = 1 + n + n 1 + n + n1 + n + 2n +1 +1 +1 + 132= 3n + 3n +4n +2= O(n3)更多精品文檔學(xué)習(xí)-好資料2.線性表1.試寫一個(gè)插入算法intinsertPost_seq(palist, p, x )，在palist所指順序表中，下標(biāo)為p的元素之后，插入一個(gè)值為x的元素，返回插入成功與否的標(biāo)志?！敬稹繑?shù)據(jù)結(jié)構(gòu)采用2.1.2節(jié)中順序表定義。int insertPost_seq(PseqList palist, int p, DataType x )/*在palist所指順序表中下標(biāo)為p的元素之后插入元素

5、 x */int q；if ( palist->n >= palist-> MAXNUM ) /* 溢出 */printf( “n”)；return 0;if (p<0| p>palist->n-1 ) /* 不存在下標(biāo)為 p 的元素 */printf( “Nn”； return 0;for(q=palist->n - 1; q>=p+1; q-)/*插入位置及之后的元素均后移一個(gè)位置*/palist->elementq+1 = palist->elementq;palist->elementp+1 = x;/* 插入元素 x

6、*/palist->n = palist->n + 1;/* 元素個(gè)數(shù)加 1 */return 1;2試寫一個(gè)刪除算法deleteV_seq(palist, x )，在palist所指順序表中，刪除一個(gè)值為 x的元素，返回刪除成功與否的標(biāo)志。【答】數(shù)據(jù)結(jié)構(gòu)采用2.1.2節(jié)中順序表定義。int deleteV_seq(PseqList palist, p, DataType x ) /*在palist所指順序表中刪除值為x的元素*/int p,q;for(p=0;p<n;p+)/*查找值為x的元素的下標(biāo)*/if(x=palist->elementp)for(q=p; q&

7、lt;palist->n-1; q+) /*被刪除元素之后的元素均前移一個(gè)位置*/palist->elementq = palist->elementq+1;/*元素個(gè)數(shù)減1 */palist->n = palist->n - 1; return 1 ;return 0;3.設(shè)有一線性表e =(eo,ei, e2,，en j )，其逆線性表定義為e = (en_i ,，e2,ei,eo)。請?jiān)O(shè)計(jì)一個(gè)算法，將用順序表表示的線性表置逆，要求逆線性表仍占用原線性表的 空間?！敬稹繑?shù)據(jù)結(jié)構(gòu) 采用2.1.2節(jié)中順序表的定義。思路考慮對數(shù)組element進(jìn)行置逆，即把第一個(gè)元

8、素和最后一個(gè)元素?fù)Q位置，把第二個(gè) 元素和倒數(shù)第二個(gè)元素?fù)Q位置。注意這種調(diào)換的工作只需對數(shù)組的前一半元素進(jìn)行，所以設(shè)置整數(shù)變量 count用于存放數(shù)組長度的一半的值。大家可以考慮一下：為什么不能對整個(gè)數(shù)組進(jìn)行如上的對元素“換位置”的工 作？(提示：這樣會將本來已經(jīng)置逆的線性表又置逆回來，即又變成了原來的表。)順序表的置逆算法void rev_seq(PSeqList palist)DataType x;int count, i;if (palist->n = 0 | palist->n = 1) return;/* 空表或只有一個(gè)元素，直接返回*/count = palist->

9、;n / 2;for ( i = 0; i < count; i+)/*只需調(diào)換半個(gè)表的元素 */x = palist->elementi;palist->elementi = palist->elementpalist->n 一 1 - i;palist->elementpalist->n 1 - i = x;代價(jià)分析該算法中包含一個(gè)for循環(huán)，其循環(huán)次數(shù)為 n/2。因此，算法的時(shí)間代價(jià)為 0(n)。4. 已知長度為n的線性表A采用順序存儲結(jié)構(gòu)，請寫一算法，找出該線性表中值最小 的數(shù)據(jù)元素?！敬稹繑?shù)據(jù)結(jié)構(gòu)采用2.1.2節(jié)中順序表定義。思路設(shè)置變量mi

10、n，遍歷整個(gè)表，不斷更新當(dāng)前已經(jīng)經(jīng)歷過的元素的最小值即可。為方便起見，事先假設(shè)表不為空。 算法DataType min_seq(PSeqList palist)DataType min;int i;min = palist->elementO;for ( i = 1; i < palist->n; i+)if (min > palist->elementi) min = palist->elementi;return min;代價(jià)分析該算法訪問順序表中每個(gè)元素各一次, 討論讀者可以試圖對上面的算法進(jìn)行修改,/*求非空順序表中的最小數(shù)據(jù)元素*/*初始化min*

11、/*min中保存的總是當(dāng)前的最小數(shù)據(jù) */時(shí)間代價(jià)為 0( n)。使返回的值不是最小元素的值而是它的下標(biāo)。5. 已知線性表A的長度為n,并且采用順序存儲結(jié)構(gòu)。寫一算法，刪除線性表中所有值為x的元素?！敬稹繑?shù)據(jù)結(jié)構(gòu)采用2.1.2節(jié)中順序表的定義。思路為了減少移動次數(shù)，可以采用快速檢索的思想，用兩個(gè)變量i, j記錄順序表中被處理的兩端元素的下標(biāo)，開始時(shí) i = 0，j = n-1,邊檢索第i個(gè)元素邊增加i，直到找到一個(gè)元素 值等于x，再邊檢索第j個(gè)元素邊減少j，直到找到一個(gè)元素值不等于X，把下標(biāo)為j的元素移到下標(biāo)為i的位置后重復(fù)上述過程，直到i >j。另用一變量count記錄刪除了多少個(gè)元素

12、。算法void delx_seq(PSeqList p, DataType x)/*刪除順序表中所有值為 x的元素，新順序表可能不保持原有順序*/int i = 0, j = p->n -1, count = 0;/* i定位于順序表開始處，j定位于順序表最后*/while ( i < j) if (p->elemen ti = x) /*找到了一個(gè)要刪除的元素*/while (p->elementj = x) && (i != j) /*從后往前找不會被刪除的元素，當(dāng)i, j相等時(shí)退岀循環(huán)，count記錄從后往前找的過程中遇到了多少個(gè)要刪的元素*/j-

13、count+;if ( i = = j) p->n = p->n count .1;return;elsep->elementi = p->elementj;count+;j - ri+;p->n = p->n - count;if (p->elementi = x) p ->n _ 一；代價(jià)分析該算法訪問順序表中每個(gè)元素各一次，時(shí)間代價(jià)為0(n)。二討論這個(gè)算法使用了一點(diǎn)技巧使得在中間刪除元素時(shí)，避免了最后一串元素的移動。但 是，它破壞了原來線性表中元素之間的順序關(guān)系。如果需要保持原來的順序應(yīng)該怎樣做？這里提供一種可行的思路：從前向后遍歷表，如

14、果元素不是X,則繼續(xù)向后；如果元素是X,則尋找其后第一個(gè)不是x的元素，將這兩個(gè)元素互換。具體算法請讀者自己實(shí)現(xiàn)。6寫一算法，在帶頭結(jié)點(diǎn)的單鏈表 llist中，p所指結(jié)點(diǎn)前面插入值為x的新結(jié)點(diǎn)，并返 回插入成功與否的標(biāo)志?！敬稹繑?shù)據(jù)結(jié)構(gòu)采用2.1.3節(jié)中單鏈表定義。思想：由于在單鏈表中，只有指向后繼結(jié)點(diǎn)的指針，所以只有首先找到p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后才能完成插入。而找p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，只能從單鏈表的第一個(gè)結(jié)點(diǎn)開始，使用與locatenk類似的方式進(jìn)行搜索。算法：int insertPre_link(LinkList llist,PNode p,DataType x)/*在llist帶頭結(jié)點(diǎn)

15、的單鏈表中，p所指結(jié)點(diǎn)前面插入值為x的新結(jié)點(diǎn)*/PNode p1;if(llist=NULL) return 0;p1=llist;while(p1!=NULL&&p1->link!=p)p仁p1->link; /*尋找 p 所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) */if(p1=NULL) return 0;PNode q=(PNode)malloc(sizeof(struct Node);/* 申請新結(jié)點(diǎn) */if(q=NULL) printf( Out of space!n ”return 0; q->info=x;更多精品文檔學(xué)習(xí)-好資料q->link=p1->

16、;link;p1->link=q; return 1;7. 寫一算法， 在帶頭結(jié)點(diǎn)的單鏈表 llist 中,刪除 p 所指的結(jié)點(diǎn)， 并返回刪除成功與否的標(biāo) 志?！敬稹繑?shù)據(jù)結(jié)構(gòu) 采用 2.1.3 節(jié)中單鏈表定義。思想：由于在單鏈表中， 只有指向后繼結(jié)點(diǎn)的指針， 所以只有首先找到 p 所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)， 然 后才能完成刪除。而找 p 所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，只能從單鏈表的第一個(gè)結(jié)點(diǎn)開始，使用與 locate_link 類似的方式進(jìn)行搜索。int deleteP_link(LinkList llist,PNode p)/* 在 llist 帶頭結(jié)點(diǎn)的單鏈表中，刪除 p 所指的結(jié)點(diǎn) */PNode

17、 p1;if(llist=NULL)return Null;p1=llist; while(p1!=NULL&&p1->link!=p)p1=p1->link; /* 尋找 p 所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) */ if(p1=NULL)return 0;p1->link=p->link;free(p); /* 刪除結(jié)點(diǎn) p */return 1;8. 已知 list 是指向無頭結(jié)點(diǎn)的單鏈表的指針變量，寫出刪除該鏈表下標(biāo)為 i 的(第 i+1 個(gè))結(jié)點(diǎn)的算法?！敬稹繑?shù)據(jù)結(jié)構(gòu)采用 2.1.3 節(jié)中單鏈表定義。思路依次遍歷表中的每一個(gè)結(jié)點(diǎn)并計(jì)數(shù)， 到第 i+1 個(gè)結(jié)點(diǎn)時(shí)

18、實(shí)行刪除。 由于鏈表是無頭結(jié) 點(diǎn)的，所以在刪除第一個(gè)結(jié)點(diǎn)時(shí)要特別注意。算法int deleteindex_link_nohead(LinkList * pllist, int i) /*刪除單鏈表中下標(biāo)為 i 的結(jié)點(diǎn)。刪除成功返回 TRUE ，否則返回 FALSE。*/ int j;PNode p, q;if (*pllist) = NULL | i < 0) return FALSE;if ( i = = 0) /* 如果需要刪除第一個(gè)結(jié)點(diǎn) */q = (*pllist);(*pllist) = (*pllist)->link;free(q); return TRUE;p = (

19、*pllist);j = 0;while (p->link != NULL && j < i 1) /*尋找下標(biāo)為 i _1 的結(jié)點(diǎn)的地址 */p = p->link;j+;if (p->link = NULL) return FALSE;/* 此元素不存在 */q = p->link;p->link = q->link;free(q); return TRUE;代價(jià)分析該算法訪問單鏈表中前面i個(gè)結(jié)點(diǎn)，時(shí)間代價(jià)為 0(i)，最大不超過 0(n)。二討論如果函數(shù)參數(shù)不是LinkList *類型而是LinkList類型，在刪除i=0的結(jié)點(diǎn)時(shí)

20、，程序不能正確實(shí)現(xiàn)，其原因請讀者思考(考慮 C語言的參數(shù)傳遞方式)。如果單鏈表帶表頭結(jié)點(diǎn)，重寫本題的算法。比較這兩個(gè)算法，是否能體會到表頭結(jié) 點(diǎn)的作用。9. 已知list是指向無頭結(jié)點(diǎn)的單鏈表的指針變量，寫出刪除該鏈表中從下標(biāo)為i的(第i+1個(gè))結(jié)點(diǎn)開始的連續(xù) k個(gè)結(jié)點(diǎn)的算法?！敬稹繑?shù)據(jù)結(jié)構(gòu)采用2.1.3節(jié)單鏈表定義。思路這道題與上題相似，只需要增加計(jì)數(shù)即可。要注意的是應(yīng)該判斷給出的i和k是否合理，是不是會超出鏈表長度。算法int del_link_nohead(LinkList * pllist, int i, int k) /*刪除單鏈表中從下標(biāo)i開始的k個(gè)結(jié)點(diǎn)。刪除成功返回 TRUE，否

21、則返回FALSE。*/int j;PNode p, q;if (*pllist) = NULL | i < 0 | k <= 0) return FALSE;if ( i = = 0) /*如果需要刪除從第一個(gè)結(jié)點(diǎn)開始的k個(gè)結(jié)點(diǎn)*/for ( j = 0; j < k && (*pllist) != NULL; j+) q = (*pllist);(*pllist) = (*pllist)->link;free(q);更多精品文檔學(xué)習(xí)-好資料更多精品文檔return TRUE;p = (*pllist);j = 0;while ( p->link

22、!= NULL && j < i -1) /*尋找下標(biāo)為i _1的結(jié)點(diǎn)的地址*/p = p_>link;j+；if (p->link = NULL) return FALSE;/*第i個(gè)結(jié)點(diǎn)不存在*/for ( j = 0; j < k && p->link != NULL; j+) q = p->link;p->link = q->link;free(q);return TRUE;代價(jià)分析該算法訪問單鏈表中前面i + k個(gè)結(jié)點(diǎn)，時(shí)間代價(jià)為 O(i+k)，最大不超過 0(n)。13請?jiān)O(shè)計(jì)一個(gè)算法，求出循環(huán)表中結(jié)點(diǎn)的

23、個(gè)數(shù)。【答】數(shù)據(jù)結(jié)構(gòu)采用不帶頭結(jié)點(diǎn)的循環(huán)鏈表。struct Node;typedef struct Node * PNode;struct NodeDataType info;PNode link;typedef struct Node * LinkList;思路遍歷整個(gè)循環(huán)鏈表，同時(shí)計(jì)數(shù)即可。二錯(cuò)誤算法int count(LinkList clist)int count;PNode p, q; p = clist;q = p->link;if (clist = NULL) return 0;/*如果是空表*/count = 1;while ( q != p)q = q->link

24、;count+;return count;錯(cuò)誤：如果clist是一個(gè)空表，那么第 5行的語句"q = p->link; ”是非法的。分析：應(yīng)把第 6行語句(用下劃線表示)提前 1行或 2行。一定要放在語句“ q = p->link; ”之、八前。缺點(diǎn)：增加局部變量p。分析：這樣做沒有必要，因?yàn)閜的初值置為clist，在程序中并沒有對p做其他修改，所以程序中不需要引入 p 而直接使用 clist 即可。算法int count(LinkList clist)int count;PNode q;if (clist = NULL) return 0;/* 如果是空表 */q =

25、clist->link;count = 1;while ( q != clist)q = q->link;count+;return count;代價(jià)分析該算法訪問循環(huán)鏈表中每個(gè)結(jié)點(diǎn)各一次，時(shí)間代價(jià)為O(n)。4. 棧與隊(duì)列1. 寫一個(gè)遞歸算法來把整數(shù)字符串轉(zhuǎn)換為整數(shù)。(例：“4356743567。)【答】思路先遞歸調(diào)用本算法轉(zhuǎn)換除去末位外剩余的字符串，結(jié)果乘以10。再轉(zhuǎn)換末位。將兩結(jié)果相加即為所求。算法int stringTolnt1(char * s, int start, int end) /*把整數(shù)字符串s中從start到end的部分轉(zhuǎn)換為整數(shù)*/if (start >

26、; end) return V;/* 轉(zhuǎn)換失敗 */if (start = end) return send 一'O'/* 只有一個(gè)字符，直接轉(zhuǎn)換*/return stringToInt1(s, start, end -1) * 10 + send - 'O'/* 先轉(zhuǎn)換其他位，再轉(zhuǎn)換末位*/int stringToInt(char * s) /*把整數(shù)字符串 s轉(zhuǎn)換為整數(shù)*/int i = 0;while (si != '0') i+;/* 計(jì)算字符串的長度 */return stringTolnt1(s, 0, i 1);代價(jià)分析設(shè)n為字符串

27、的長度。該算法訪問每個(gè)字符各一次，時(shí)間代價(jià)為0(n)，計(jì)算字符串的長度的時(shí)間代價(jià)也為0(n)。故總的時(shí)間代價(jià)為0(n)。遞歸算法需要棧的支持，棧的大小與遞歸調(diào)用的深度成正比。所以實(shí)際空間開銷為0(n)。2. 編寫一個(gè)算法，對于輸入的十進(jìn)制非負(fù)整數(shù)，將它的二進(jìn)制表示打印出來?！敬稹繑?shù)據(jù)結(jié)構(gòu)采用4.1.2節(jié)中棧的順序表示。思路將輸入的十進(jìn)制數(shù)字反復(fù)除以2,直到它變?yōu)?。將每次的數(shù)字模2的余數(shù)入棧。棧中存放的就是所要求的二進(jìn)制表示。再將棧中的元素依次彈出打印即可。算法void print_bin(int dec_number) /* 將十進(jìn)制非負(fù)整數(shù)轉(zhuǎn)化為二進(jìn)制數(shù)打印出來*/PSeqStack pa

28、stack;int temp = dec_number; if (temp < 0) printf("Error!n"); return;pastack = createEmptyStack_seq();/* 建立一個(gè)空棧 */if (pastack = NULL) return;while (temp > 0) push_seq(pastack, temp % 2);temp /= 2; while(!isEmptyStack_seq(pastack) printf("%d", top_seq(pastack); pop_seq(pasta

29、ck); free(pastack);代價(jià)分析設(shè)輸入的十進(jìn)制數(shù)字為n,則算法的時(shí)間代價(jià)為 O(log2 n)?？臻g代價(jià)主要是棧的大小，為O( log 2 n)。3寫一個(gè)算法： PSeqStack createEmptyStack_seq( int m ) 創(chuàng)建一個(gè)空棧。 數(shù)據(jù)結(jié)構(gòu)采用 4.1.2 節(jié)中棧的順序表示。PSegStack createEmptyStack_seq(int m)/* 創(chuàng)建一個(gè)空棧 */PSeqStack pastack = (PSeqStack)malloc(sizeof(struct SeqStack); if (pastack!=NULL) pastack -&g

30、t;s = (DataType*)malloc(sizeof(DataType)*m);if (pastack ->s)pastack ->MAXNUM=m;pastack ->t= -1;/* 棧頂變量賦值為 -1 */return (pastack );else free pastack;printf( “n”);/* 存儲分配失敗 */return NULL;4,寫一個(gè)算法：int isEmptyStack_seq( PSeqStack pastack )判斷 pastack所指的棧是否 為空棧。數(shù)據(jù)結(jié)構(gòu)采用4.1.2節(jié)中棧的順序表示。int isEmptyStack_

31、seq(PSeqStack pastack)/*判斷pastack所指的棧是否為空棧 */if(pastack->t = -1) return 1;else return 0;8假設(shè)以循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)隊(duì)頭指 針)，試編寫相應(yīng)的創(chuàng)建空隊(duì)列、入隊(duì)列和出隊(duì)列的算法?！敬稹繑?shù)據(jù)結(jié)構(gòu) 采用不帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列。struct Node;typedef struct Node * PNode; struct Node DataType info;PNode link;/*循環(huán)鏈表表示的隊(duì)列類型*/*尾指針*/struct ClinkQueue PNo

32、de r;typedef struct ClinkQueue * PClinkQueue;/*指向循環(huán)鏈表表示的隊(duì)列的指針類型*/認(rèn)列的需壞鏈我投示思路與隊(duì)列的單鏈表表示相似，但節(jié)省了指向隊(duì)頭的指針變量，所以在需要找表頭結(jié)點(diǎn)時(shí)必須通過表尾指針進(jìn)行。算法PClinkQueue createEmptyQueue_clink() /*創(chuàng)建空隊(duì)列 */PClinkQueue pcqu = (PCIinkQueue)malloc(sizeof(struct ClinkQueue); pcqu->r = NULL;學(xué)習(xí)-好資料return pcqu;void enQueue_clink(PCIink

33、Queue pcqu, DataType x) /* 進(jìn)隊(duì)列 */PNode p;p = (PNode)malloc(sizeof(struct Node);p->info = x;if (pcqu->r = NULL) pcqu->r = p;p->link = p;return;p->link = pcqu->r->link;pcqu->r->link = p;pcqu->r = p;void deQueue_clink(PClinkQueue pcqu) PNode p;if (pcqu->r = NULL) printf

34、("Underflow!n"); return;if (pcqu->r->link = pcqu->r) free(pcqu->r); pcqu->r = NULL;return;p = pcqu->r->link;pcqu->r->link = p->link; free(p);代價(jià)分析上述幾個(gè)算法都不包含循環(huán)，只有常數(shù)條語句,二討論本題可以看成隊(duì)列的循環(huán)表實(shí)現(xiàn)。/*進(jìn)空隊(duì)列，即往空隊(duì)列中加入第一個(gè)結(jié)點(diǎn)*/*出隊(duì)列*/*是空隊(duì)列*/*只有一個(gè)元素的隊(duì)列*/*指向隊(duì)頭*/因此每個(gè)算法的時(shí)間代價(jià)均為0(1)。5. 二

35、叉樹與樹1.寫一個(gè)算法來計(jì)算給定二叉樹的葉結(jié)點(diǎn)數(shù)?！敬稹繑?shù)據(jù)結(jié)構(gòu)采用5.1.3節(jié)中二叉樹的鏈接表示。算法int num_of_leaves(BinTree t) /* 計(jì)算二叉樹的葉結(jié)點(diǎn)個(gè)數(shù) */if (t = = NULL) return 0;/*空樹，返回 0*/if (t->llink = = NULL && t->rlink = = NULL) return 1;/* 根結(jié)點(diǎn)是樹葉，返回 1*/return num_of_leaves(t->llink) + num_of_leaves(t->rlink);/*返回“左子樹的葉結(jié)點(diǎn)數(shù)+右子樹的葉結(jié)

36、點(diǎn)數(shù)"*/代價(jià)分析該算法訪問每個(gè)結(jié)點(diǎn)各一次，時(shí)間代價(jià)為0(n)?？臻g代價(jià)為 0(h)。2假設(shè)二叉樹采用鏈接方法存儲，編寫一個(gè)計(jì)算一棵二叉樹t的高度的函數(shù)?！敬稹繑?shù)據(jù)結(jié)構(gòu)采用5.1.3節(jié)中二叉樹的鏈接表示。思路對一棵二叉樹t，考察它左右子樹的高度，取其中大的一個(gè)，再加1即為t的高度。算法int depth(BinTree t)PBinTreeNode pbtree;int dl, dr;pbtree = t;if (pbtree = = NULL)return -1;dl = depth(pbtree->llink);dr = depth(pbtree->rlink);re

37、turn (dl > dr ? dl : dr) + 1;代價(jià)分析設(shè)樹中的結(jié)點(diǎn)個(gè)數(shù)為n,遞歸訪問次數(shù)只可能是n。所以，時(shí)間代價(jià)為 0(n)?？臻g代價(jià)為0(h)。h為二叉樹的高度。6. 設(shè)計(jì)一個(gè)程序，根據(jù)二叉樹的先根序列和對稱序序列創(chuàng)建一棵用左右指針表示的二 叉樹?！敬稹繑?shù)據(jù)結(jié)構(gòu)采用5.1.3節(jié)中二叉樹的鏈接表示。思路二叉樹的先根序列和對稱序序列，用兩個(gè)數(shù)組preorder和in order存放。先根序列的第一個(gè)元素的值preorder0應(yīng)為二叉樹的根上的元素值，在另一個(gè)數(shù)組中查到此值，設(shè)為inorderk。此時(shí)，數(shù)組 preorder中從preorder1到preorder k的序列(長

38、度為 k)和數(shù)組in order中從inorder0到inorderk_1(長度為k)的序列，恰好分別是根結(jié)點(diǎn)左子樹( k個(gè)結(jié)點(diǎn))的先根序列和對稱序序列。數(shù)組preorder中從preorderk+1到preordern-1的序列(長度為n-k-1) 和數(shù)組in order中從in orderk+1到inordern-1(長度為n-k-1)的序列，恰好分別是根結(jié)點(diǎn)左子樹(n*-1個(gè)結(jié)點(diǎn))的先根序列和對稱序序列。根據(jù)上述分析，算法先創(chuàng)建根結(jié)點(diǎn)，再遞歸調(diào)用自己兩次來分別創(chuàng)建左右子樹。算法int create_BTree(PBinTree pbtree, DataType * preorder, D

39、ataType * inorder, int n)/*根據(jù)先根序列 preorder和對稱序序列inorder (長度為n)創(chuàng)建二叉樹 pbtree。對于正確的先根 序列和對稱序序列，算法返回TRUE，否則返回FALSE。*/int i, k;int tag1, tag2;if (n = = 0) *pbtree = NULL;return TRUE;for (i = 0; i < n; i+)if (inorderi = = preorder0)break;if (i = = n) *pbtree = NULL;return FALSE;/*輸入的先根序列或?qū)ΨQ序序列有誤，創(chuàng)建失敗*/

40、k = i;*pbtree = (PBinTreeNode)malloc(sizeof(struct BinTreeNode);(*pbtree)->i nfo = preorder0;tagl = create_BTree(&(*pbtree)->llink, preorder + 1, inorder, k);/*遞歸調(diào)用本算法創(chuàng)建左子樹*/tag2 = create_BTree (&(*pbtree)->rlink, preorder + k + 1, inorder + k + 1, nk 1);/*遞歸調(diào)用本算法創(chuàng)建右子樹*/if (tag1 = =

41、 TRUE && tag2 = = TRUE) return TRUE;return FALSE;/*二叉樹創(chuàng)建成功當(dāng)且僅當(dāng)其左右子樹都創(chuàng)建成功*/代價(jià)分析最壞的情況是，每個(gè)非葉結(jié)點(diǎn)只有左子樹。這時(shí)兩個(gè)數(shù)組之間需要比較n+(n-1)+ +1=0( n2)次。所以，該算法的時(shí)間代價(jià)為O(n2)?？臻g代價(jià)主要包括：存放二叉樹的空間O( n)和用于遞歸調(diào)用的?？臻g(不超過O(n )。并給出在這種表示基礎(chǔ)上主要運(yùn)算的實(shí)現(xiàn)算法。7試設(shè)計(jì)樹的子表表示法的存儲結(jié)構(gòu),【答】數(shù)據(jù)結(jié)構(gòu)/*邊表中結(jié)點(diǎn)的定義*/*子結(jié)點(diǎn)位置*/*下一個(gè)邊的指針*/*結(jié)點(diǎn)的定義*/*結(jié)點(diǎn)本身信息*/*到子結(jié)點(diǎn)的邊表*/

42、*樹的定義*/*結(jié)點(diǎn)表*/*根的位置*/*結(jié)點(diǎn)的個(gè)數(shù)*/struct EdgeNodeint nodeposition;struct EdgeNode * link;struct ChiTreeNodeDataType info;struct EdgeNode * children;struct ChiTree struct ChiTreeNode nodelistMAXNUM;int root;int n;typedef struct ChiTree * PChiTree;算法創(chuàng)建空樹PChiTree CreateNullTree_chitree(void)PChiTree p;p = (P

43、ChiTree)malloc(sizeof(struct ChiTree);if (p = = NULL)printf("Out of space!n");elsep_>n=O;p->root = -1; return p;判斷樹是否為空int isNull_chitree (PChiTree t)return t->n = = 0;返回非空樹的根結(jié)點(diǎn)的下標(biāo)DataType root_chitree (PChiTree t)return t->root;返回下標(biāo)為p的結(jié)點(diǎn)的父結(jié)點(diǎn)的下標(biāo)int parent_chitree (PChiTree t, i

44、nt p)int i;struct EdgeNode * v;if (p < 0 | p >= t->n) return -1; for (i = 0; i < t->n; i+)v = t->nodelisti.children; while (v != NULL)if (v->nodeposition = = p) return i;elsev = v->link;return J;返回下標(biāo)為p的結(jié)點(diǎn)的最左子結(jié)點(diǎn)的下標(biāo)int leftChild_chitree(PParTree t, int p)struct EdgeNode * v;if

45、(p < 0 | p >= t->n) return -1;v = t->nodelisti.children; if (v = = NULL) return_1;return v->nodeposition;返回下標(biāo)為p的結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)的下標(biāo)int rightSibling_chitree(PParTree t, int p) int i;struct EdgeNode * v;if (p < 0 | p >= t->n) return -1;for (i = 0; i < t->n; i+)v = t->nodelisti

46、.children; while (v != NULL)if (v->nodeposition = = p) if(v->link = = NULL) return -1;elsereturn v->link->nodeposition;/*沒有下標(biāo)為p的結(jié)點(diǎn)*/*for循環(huán)每次檢查結(jié)點(diǎn)下標(biāo)中一個(gè)元素*/*每次循環(huán)檢查結(jié)點(diǎn)i的邊表中的一個(gè)元素*/*沒有右兄弟結(jié)點(diǎn)*/*返回右兄弟結(jié)點(diǎn)在結(jié)點(diǎn)表中的位置*/elsev=v->link;return 4;/*沒有右兄弟結(jié)點(diǎn)*/代價(jià)分析這是一個(gè)兩重循環(huán)程序，外層循環(huán)最多執(zhí)行n次，內(nèi)層循環(huán)對每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)進(jìn)行檢查,子結(jié)點(diǎn)的個(gè)數(shù)最大可能與 n接近，所以表面看來這是一個(gè)n2階的時(shí)間代價(jià)；但是，仔細(xì)分析內(nèi)層的循環(huán)體，可以看出內(nèi)層循環(huán)最多對樹中的每條邊執(zhí)行一次，由于樹中邊的個(gè)數(shù)與