數(shù)據(jù)結(jié)構(gòu)(C語言版)習(xí)題解答

1、1.3 設(shè)n是正整數(shù)。試寫出下列程序段中用記號“”標(biāo)注的語句的頻度： (2)i=1; k=0;do k+=10*i;i+;while(i=2時，執(zhí)行n-1次；(3) i=1; k=0; do k+ = 10*i; i+;while(i=n);當(dāng)n=2時，執(zhí)行2次；當(dāng)n!=2時，執(zhí)行1次；(4)i=1; j=0;while(i+jn) if(i=(y+1)*(y+1)y+;執(zhí)行n(向下取整)(6)x=91; y=100;while ( y0 )if(x100) x-=10; y-; else x+ ; If語句執(zhí)行100次(7)for( i=0; in; i+)for( j=i; jn; j+)

2、for( k=j; kx&i=0;i-)La.elemi+1=La.elemi;La.elemi+1=x;La.length+;return OK;/Insert_SqList2.5試寫一個算法，實現(xiàn)順序表的就地逆置，即在原表的存儲空間將線性表（a1,a2, ., an-1,an）逆置為(an,an-1, ., a2,a1)/思路就是兩個指示變量i，j同時分別從順序表的開始和結(jié)尾處相向改變void reverse(SqList &A)/順序表的就地逆置ElemType p;for(i=1,j=A.length;ij;i+,j-) /A.elemiA.elemj; p=A.elemi; A.el

3、emi=A.elemj; A.elemj=p; /reverse2.7 已知線性表L采用順序存儲結(jié)構(gòu)存放，對兩種不同情況分別寫出算法，刪除L中多余的元素，使得L中沒有重復(fù)元素：（1）L中數(shù)據(jù)元素?zé)o序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。void Delete_SameElem(SqLink &L, int L.length)/內(nèi)層循環(huán)移動參數(shù)，中層循環(huán)尋找相同元，外層循環(huán)遍歷整個表int i=0; int j=i+1; int length=L.length;while(ilength)for(j=i+1;jlength; j+)if(L.Elemj=L.Elemi)/for(k=j; kL

4、.Elemi) break;/第二小問添加此句/end for/end while/end functoion2.8已知線性表L采用鏈?zhǔn)浇Y(jié)構(gòu)存放。對兩種不同情況分別寫出算法，刪除L中值相同的多余元素，使得L中沒有重復(fù)元素：(1)L中數(shù)據(jù)元素?zé)o序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。（1）L中數(shù)據(jù)元素?zé)o序排列；思路：由于是無序排列，需要線性表中每個元素都要相互進(jìn)行比較。Status ListDelete（Linklist &L）/L是帶頭結(jié)點的線性表 ElemType *p,*q; p=L-next;q=p-next; /設(shè)定p變化較慢，q變化較快while(p-next) while(q)

5、if(p-data!=q-data) q=q-next;else q=q-next; p-next=q; /else/whilep=p-next;q=p-next;/開始后一結(jié)點的尋找return OK；/ListDelete(2)L中數(shù)據(jù)元素非遞減有序排列。思路：由于是有序的，遍歷一次線性表就行了Status ListDelete (LinkList &L) ElemType *p,*q; p=L-next;q=p-next; while(p-next) if (p-data!=q-data) p=p-next; /和第一問不同地方 q=p-next; /if else while(p-da

6、ta=q-data) q=q-next;/多個連續(xù)的重復(fù)值 /else p-next=q;p=q;q=p-next;/刪除值重復(fù)的結(jié)點，并修改相應(yīng)的指針return OK；/ListDelete2.9 設(shè)有兩個非遞減有序的單鏈表A,B。請寫出算法，將A和B就地歸并成一個按元素值非遞增有序的單鏈表。/ 將合并逆置后的結(jié)果放在C表中，并刪除B表Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C)LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;/ 保存pa的前驅(qū)指針qb=pb;/ 保存pb的前驅(qū)指針pa=

7、pa-next;pb=pb-next;A-next=NULL;C=A;while(pa&pb)if(pa-datadata)qa=pa;pa=pa-next;qa-next=A-next;/將當(dāng)前最小結(jié)點插入A表表頭A-next=qa;elseqb=pb;pb=pb-next;qb-next=A-next;/將當(dāng)前最小結(jié)點插入A表表頭A-next=qb;while(pa)qa=pa;pa=pa-next;qa-next=A-next;A-next=qa;while(pb)qb=pb;pb=pb-next;qb-next=A-next;A-next=qb;pb=B;free(pb);return

8、 OK;2.13 設(shè)以帶頭結(jié)點的雙向循環(huán)鏈表表示的線性表L=(a1,a2,a3,.,an)。試寫一時間復(fù)雜度為O(n)的算法，將L改造為L=(a1,a3,.,an,.,a4,a2)。void Reform(DuLinkedList &L)/按1,3,5,.4,2 的順序重排雙向循環(huán)鏈表L 中的所有結(jié)點p=L.next;while(p-next!=L&p-next-next!=L)p-next=p-next-next;p=p-next; /p指向最后一個奇數(shù)結(jié)點if(p-next=L) /結(jié)點個數(shù)是奇數(shù)，使最后一個奇數(shù)結(jié)點next指向最后一個偶數(shù)結(jié)點 p-next=L-pre-pre;else/

9、結(jié)點個數(shù)是偶數(shù)，使最后一個奇數(shù)結(jié)點next指向最后一個偶數(shù)結(jié)點 p-next=L-pre;p=p-next; /此時p 指向最后一個偶數(shù)結(jié)點while(p-pre-pre!=L) p-next=p-pre-pre; p=p-next;p-next=L;/最后一個結(jié)點next指向頭結(jié)點 /調(diào)整了next 鏈的結(jié)構(gòu),此時pre 鏈仍為原狀/調(diào)整pre 鏈的結(jié)構(gòu)for(p=L;p-next!=L;p=p-next) p-next-pre=p;L-pre=p; /頭結(jié)點的pre指向a2結(jié)點 /Reform第三章 棧和隊列3.6 試寫一個算法，識別依次讀入的一個以為結(jié)束符的字符序列是否為形如“序列1&序

10、列2”模式的字符序列。其中，序列1和序列2中都不包含字符&,且序列2是序列1的逆序。例如，“a+b&b+a”是屬于該模式的字符序列，而“13&31”則不是。算法：int SeqReverse()/判斷輸入的字符串中&前和&后部分是否為逆串,是則返回1,否則返回0InitStack(s);while(e=getchar()!=&)if(e=) return 0;/不允許在&之前出現(xiàn)push(s,e);/序列1輸入完畢while( (e=getchar()!=)if(StackEmpty(s) return 0;pop(s,c);if(e!=c) return 0;if(!StackEmpty(s

11、) return 0;/序列1元素還有剩余return 1;/IsReverse3.7 假設(shè)一個算術(shù)表達(dá)式中可以包含三種符號：圓括號“(”和“)”、方括號“”和“”、花括號“”和“”，且這三種括號可按任意次序嵌套使用。編寫判別給定表達(dá)式中所含的括號是否正確配對的算法（已知表達(dá)式已存入數(shù)據(jù)元素為字符的順序表中）。算法：Status BracketTest(char *str)/判別表達(dá)式中三種括號是否匹配InitStack(s);for(p=str;*p;p+)if(*p=( | *p= | *p= ) push(s,*p);else if(*p= ) | *p= | *p= ) if(Stac

12、kEmpty(s) return ERROR;pop(s,c);if(*p=)&c!=() return ERROR;if(*p=&c!=) return ERROR;if(*p=&c!=) return ERROR; /必須與當(dāng)前棧頂括號匹配/if/forif(!StackEmpty(s) return ERROR;/進(jìn)棧的符號還有剩余，Errorreturn OK;/BracketTest3.8 設(shè)表達(dá)式由單字母變量、雙目運算符和圓括號組成（如:“(a*(b+c)-d)/e）”。試寫一個算法，將一個書寫正確的表達(dá)式轉(zhuǎn)換為逆波蘭式。思路：1.遇到數(shù)字直接發(fā)送 2.遇到(直接入棧 3.遇到)則

13、將棧內(nèi)元素發(fā)送直至遇到( 4.棧空則直接入棧 5.棧非空時若優(yōu)先級大于棧內(nèi)則入棧，否則棧內(nèi)元素出棧int RankOfOperator(char c)switch(c)case #: return -1;case (: return 0;case +:case -: return 1;case *:case /:case ):return 2;int Precede(char c, char ch)return RankOfOperator(c)RankOfOperator(ch);void ExpressionTOPolandStyle(char suffix,char *exp)Stack

14、 s; InitStack(s,100); int i=0; char c;while(*exp)if(isdigital(*exp)suffixi+=*exp;elseswitch(*exp)case (: push(s,();case ): while(c=pops(s)!=() suffixi+=c;break;default: if(IsEmpty(s) push(s,*exp); else suffixi+=pop(s); exp-; /與后面的exp+相抵消，使得棧內(nèi)優(yōu)先級大于等于棧外的都出棧 /end switch/end elseexp+;/end whilewhile(!Is

15、Empty(s) suffixi+=pop(s); suffixi=0;3.10 假設(shè)以帶頭結(jié)點的單循環(huán)鏈表表示隊列，只設(shè)一個尾指針指向隊尾元素，不設(shè)頭指針。試編寫相應(yīng)的隊列初始化、入隊和出隊算法（在出隊算法中要傳回隊頭元素的值）要點：定義好數(shù)據(jù)類型，帶頭結(jié)點的單循環(huán)鏈表，只有尾指針，注意刪除元素時只有一個元素的特殊性typedef int DataTypestruct NodeDataType data;Node * next;struct CycleListQueueNode * tail;void InitCycleListQueue(CycleListQueue&L) L.tail =

16、 new Node; L.tail-next = L.tail;void EnterQueue(CycleListQueue&L,DataType value)Node* p = new Node;p-data = value;p-next = L.tail-next;L.tail-next = p;L.tail = p;void DeparQueue(CycleListQueue&L,DataType &d)if(L.tail-next != L.tail-next-next)Node *p = L.tail-next-next;L.tail-next-next = p-next;d = p

17、-data;if(p=L.tail) L.tail=p-next;delete p;return d;3.11 假設(shè)將循環(huán)隊列定義為：以rear和length分別指示隊尾元素和隊列長度。試給出此循環(huán)隊列的隊滿條件，并寫出相應(yīng)的入隊和出隊算法（在出隊算法中要傳遞回隊頭元素的值）。此循環(huán)隊列的隊滿條件：Q.length=MAXQSIZE;入隊算法：Status EnCyQueue(CyQueue &Q,int x)/帶length 域的循環(huán)隊列入隊算法if(Q.length=MAXSIZE) return OVERFLOW;Q.rear=(Q.rear+1)%MAXSIZE; Q.baseQ.re

18、ar=x; /rear指向隊尾元素Q.length+;return OK;/EnCyQueue出隊算法：Status DeCyQueue(CyQueue &Q,int &x)/帶length 域的循環(huán)隊列出隊算法，用x返回隊頭元素的值if(Q.length=0) return Error;/空隊列，錯誤head=(Q.rear-Q.length+1)%MAXSIZE; /head指向隊頭x=Q.basehead;Q.length-;return OK；/DeCyQueue3.12 試寫一個算法：判別讀入的一個以為結(jié)束符的字符序列是否是“回文”（所謂“回文”是指正讀和反讀都相同的字符序列，如“x

19、xyzyxx”是回文，而“abcab”則不是回文）。Status Test()/判別輸入的字符串是否回文序列,是則返回1,否則返回0 InitStack(S); InitQueue(Q); while(c=getchar()!=) Push(S,c); EnQueue(Q,c); /同時使用棧和隊列兩種結(jié)構(gòu) while(!StackEmpty(S) Pop(S,a); DeQueue(Q,b); if(a!=b) return ERROR; return OK;/ Test第五章 多維數(shù)組5.4 設(shè)有一個準(zhǔn)對角矩陣按以下方式存于一維數(shù)組B4m中：0123456k4m-24m-1a11a12a2

20、1a22a33a34a43.aij.a2m-1,2ma2m,2m寫出由一對下標(biāo)(i,j)求k的轉(zhuǎn)換公式。因為i行前有2(i-1)個元素?，F(xiàn)考慮i行情況，當(dāng)j是奇數(shù)，i行有1個元素,k=2(i-1)+1-1=2(i-1)；否則i行有2個元素，k=2(i-1)+2-1=2i-1。故：k=2i-1 j為奇數(shù)2i-1 j為偶數(shù)或若i為奇數(shù)，k=2(i-1)+j-i=i+j-2;當(dāng)i為偶數(shù)時，k=2i-(i-j)-1=i+j-1k=i+j-2 i為奇數(shù)i+j-1 i為偶數(shù)5.5 已知稀疏矩陣A45如下：(1)用三元組表作為存儲結(jié)構(gòu)，繪出相應(yīng)的三元組表示意圖；(2)用十字鏈表作為存儲結(jié)構(gòu)，繪出相應(yīng)的十字鏈

21、表示意圖。(1)三元組表：ijv121155212223246424457(2)十字鏈表第六章 數(shù)和二叉樹6.5 已知一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，.，nk個度為k的結(jié)點，問該樹中有多少個葉子結(jié)點？設(shè)葉子結(jié)點有x個，則樹的結(jié)點總數(shù)為n1+n2+nk+x;同時除了根結(jié)點外，每個結(jié)點都指向一個結(jié)點，所有從這個角度考慮樹的結(jié)點總數(shù)為：n1+2n2+knk+1;n1+n2+nk+x= n1+2n2+knk+1,可得x=6.8已知一棵樹如圖6-1所示，畫出與該樹對應(yīng)的二叉樹，并寫出該樹的先根遍歷序列和后根遍歷序列。ABCDEFGHKIJ圖6-1先根遍歷：ABCEIJFGKHD

22、后根遍歷：BIJEFKGHCDA對應(yīng)的二叉樹：ABCDEFGHKIJ6.9 將如圖6-2所示的森林轉(zhuǎn)化為對應(yīng)的二叉樹。K圖6-2ACDEBFGHJILMNO樹對應(yīng)的二叉樹K圖6-2ACDEBFGHJILMNO 森林對應(yīng)的二叉樹：KACDEBFGHJILMNO6.11已知某二叉樹的中序序列為DCBGEAHFIJK，后序序列為DCEGBFHKJIA。請畫出該二叉樹。KACDEBFGHJI6.14 假設(shè)某個電文由(a,b,c,d,e,f,g,h)8個字母組成，每個字母在電文中出現(xiàn)的次數(shù)分別為(7,19,2,6,32,3,21,10)，試解答下列問題： (1) 畫出出huffman樹；10002c3f

23、511G287a1732e606d19b21g4010h (2) 寫出每個字母的huffman編碼； a:1010 b:00 c:10000 d:1001 e:11 f:10001 g:01 h:1011 (3) 在對該電文進(jìn)行最優(yōu)二進(jìn)制編碼處理后，電文的二進(jìn)制位數(shù)。 4*7+2*19+5*2+4*6+2*32+5*3+2*21+4*10=2616.17 寫出按層次遍歷二叉樹的算法。思路：用隊列存儲結(jié)構(gòu)，并用遞歸方法Status LevelOrderTraverse(BitTree T,Status (*Visit)(TElemType e)/層序遍歷二叉樹InitQueue(Q); /初始化

24、隊列if(!T) return Error;/空樹，直接返回EnQueue(Q,T);/根結(jié)點入隊BiTNode *p;while(!QueueEmpty(Q)DeQueue(Q,p);Visit(p-data);if(p-lchild) EnQueue(Q,p-lchild);if(p-rchild) EnQueue(Q,p-rchild);/whilereturn Ok;/LevelOrderTraverse6.19 寫出判斷兩棵給定二叉樹是否相似的算法。(注：兩棵二叉樹B1和B2相似是指：B1和B2皆空，或者皆不空且B1的左、右子樹和B2的左、右子樹分別相似。)思路：采用遞歸進(jìn)行比較判斷

25、bool BiTreeSimilar (BiTree T1,BiTree T2) if(T1=Null&T2=Null) return 1;else if(T1=Null | T2=Null) return 0; else return (BiTreeSilimar(T1-lchild,T2-lchild)&BiTreeSimilar(T1-rchild,T2-rchild);6.21 寫出統(tǒng)計樹中葉子結(jié)點個數(shù)的算法，樹用孩子兄弟鏈表表示。思路：在孩子兄弟鏈表中，若結(jié)點的firstchild為Null，則為葉子結(jié)點；采用遞歸方法。 int CountLeaves(Tree T，int &num

26、)/num傳遞的初值為0 if(T-nextsibling!=Null) num+=CountLeaves (T-nextsibling); if(T-firstchild!=Null) num+=CountLeaves(T- firstchild); else num+=1;/firstchild域為空，則為葉子結(jié)點return num;圖7-1V5V4V2V3V1V6第七章 圖7.1 已知有向圖如圖7-1所示，請給出該圖的 (1)鄰接矩陣示意圖 (2)鄰接表示意圖 (3)逆鄰接表 (4)所有強連通分量(1) 鄰接矩陣 （2）鄰接表 （3）逆鄰接表V5V4V2V3V1V6 （4）強連通分量7

27、.2 已知圖G的鄰接矩陣如圖7-2所示。寫出該圖從頂點1出發(fā)的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列，并畫出相應(yīng)的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。12345678910100000010102001000100030001000100400001000105000001000161100000000700100000018100100001090000101001101000010000圖7-2深度優(yōu)先序列：1 7 3 4 5 6 2 10 9 8深度優(yōu)先生成樹：廣度優(yōu)先序列：1 7 9 3 10 5 4 8 6 2廣度優(yōu)先生成樹：9.1若對大小均為n的有序順序表和無序順序表分別進(jìn)行順序查找，試在下列三種情況下分別討論兩者在等概率時平均查找長度是否相同？（1）查找不成功，即表中沒有關(guān)鍵字等于給定的值K