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

1、L3設(shè)n是正整數(shù)。試寫出下列程序段中用記號(hào)標(biāo)注的語(yǔ)句的頻度:i=l；k=0;dok+=10*i;i+;while(iv=n-l)當(dāng)n=l時(shí)，執(zhí)行1；當(dāng)n>=2時(shí)，執(zhí)行n-l次；i=l;k=0;dok+=10*i;i-+;while(i=n);當(dāng)n=2時(shí),執(zhí)行2次;當(dāng)n!=2時(shí),執(zhí)行1次;i=l;j=0;while(i+j<n)if(i<j)i+;elsej+;)執(zhí)行n次；x=n;y=0;/n是不小于1的常數(shù)while(x>=(y+l)*(y+l)y+；)執(zhí)行(向下取整)(6) x=91;y=100;while(y>0)if(x>100)x-=10;y-;el

2、sex+;)If語(yǔ)句執(zhí)行100次(7)for(i=0;ivn;i+)for(j=i;jvn;j+)for(k=j;kvn;k+)x+=2;過(guò)程：去，M第一早1 .3已知順序表La中數(shù)據(jù)元素按非遞減有序排列。試寫一個(gè)算法，將元素到La的合適位置上，保持該表的有序性。思路：先判斷線性表的存儲(chǔ)空間是否滿，若滿返回Error；否則從后向前先移動(dòng)數(shù)據(jù)，找到合適的位置插入。StatusInsert_SqList(SqList&La,intx)/把x插入遞增有力;表La中(if(La.Iength=La.listsize)returnERROR;for(i=La.Iength-1;La.elemi&

3、gt;x&&i>=0;i)La.elemi+l=La.elemi;La.elemi+l=x;La.Iength+;returnOK;/lnsert_SqList2 .5試寫一個(gè)算法，實(shí)現(xiàn)順序表的就地逆置，即在原表的存儲(chǔ)空間將線性表(ai,a2,an-1,an)逆置為(an,an-1,.,a2,a1)思路就是兩個(gè)指示變量i,j同時(shí)分別從順序表的開(kāi)始和結(jié)尾處相向改變voidreverse(SqList&A)順序表的就地逆置(ElemTypep;for(i=l,j=A.Iength;ivj;i+,j-)/A.elemi<->A.elemj;p=A.elemi

4、;A.elemi=A.elemj;A.elemj=p;/reverse2.7已知線性表L采用順序存儲(chǔ)結(jié)構(gòu)存放，對(duì)兩種不同情況分別寫出算法，刪除L中多余的元素，使得L中沒(méi)有重復(fù)元素：(1)L中數(shù)據(jù)元素?zé)o序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。int L. Ie ngth)voidDelete-SameElemCSqLink&L,吶層循環(huán)移動(dòng)參數(shù)，中層循環(huán)尋找相同元，外層循環(huán)遍歷整個(gè)表inti=0;intj=i+l;intlength=L.Iength;while(i<length)for(j=i+l;j<length;j+)if(L.EIemj=L.EIemil)for(k

5、=j;k<length-l;k+)L.Elemk=L.Elemk+1;length-j;移動(dòng)元素后，由于少了一個(gè)元素，因此要減1/endifIf(L.EIemj>L.EIemi)break;/第二小問(wèn)添加此句/endfor/endwhile/endfunctoion1 .8已知線性表L采用鏈?zhǔn)浇Y(jié)構(gòu)存放。對(duì)兩種不同情況分別寫出算法，刪除L中值相同的多余元素，使得L中沒(méi)有重復(fù)元素：L中數(shù)據(jù)元素?zé)o序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。(1) L中數(shù)據(jù)元素?zé)o序排列；思路：由于是無(wú)序排列，需要線性表中每個(gè)元素都要相互進(jìn)行比較。StatusListDelete(Linklist&L

6、)/L是帶頭結(jié)點(diǎn)的線性表(ElemType*p,*q;p=L-next;q=p-next;設(shè)定p變化較慢，q變化較快while(p->next)while(q)if(p->data【一q->data)q=q->next;elseq=q->next;p->next=q;/else/whilep=p->next;q=p->next;開(kāi)始后一結(jié)點(diǎn)的尋找returnOK;/ListDeleteL中數(shù)據(jù)元素非遞減有序排列。思路：由于是有序的，遍歷一次線性表就行了StatusListDelete(LinkList&L)ElemType*p,*q;p=

7、L->next;q=p->next;while(p->next)(if(p->data!=q->data)p=p->next;/和第一J可不同地方q=p->next;/ifelse(while(p->data=q->data)q=q->next;多個(gè)連續(xù)的重復(fù)值/elsep->next=q;p=q;q=p->next;刪除值重復(fù)的結(jié)點(diǎn)，并修改相應(yīng)的指針returnOK;/ListDelete2 .9設(shè)有兩個(gè)非遞減有序的單鏈表A,B。請(qǐng)寫出算法，將3和B就地歸并成一個(gè)按元素值非遞增有序的單鏈表。將合并逆置后的結(jié)果放在c表中，

8、并刪除B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C)LinkListpa,pb,qa,qb;pa=A;Pb=B;qa=pa;/保存pa的前驅(qū)指針qb=pb;保存pb的前驅(qū)指針pa=pa->next;pb=pb->next;A->next=NULL;while(pa&&pb)if(pa->data<pb->data)qa=pa;pa=pa->next;qa->n ext=A->n ext; A->n將當(dāng)前最小結(jié)點(diǎn)插入A表表頭e

9、xt=qa;elseqb=pb;pb=pb->next;將當(dāng)前最小結(jié)點(diǎn)插入 A表表頭qb->next=A->next;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);returnOK;3 .13設(shè)以帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表L=(al,a2,a3,.,an)o試寫一時(shí)間復(fù)雜度為0(n)的算法,將L

10、改造為L(zhǎng)=(ai,a3,.,an,.,a4,a2)。voidReform(DuLinkedList&L)按1,3,5,心2的順序重排雙|可循環(huán)鏈表L中的所有結(jié)點(diǎn)(p=L.next;while(p->next!=L&&p->next->next!=L)(p->next=p->next->next;p=p->next;p指向最后一個(gè)奇數(shù)結(jié)點(diǎn)if(p-next=L)結(jié)點(diǎn)個(gè)數(shù)是奇數(shù)，使最后一個(gè)奇數(shù)結(jié)點(diǎn)next指向最后一個(gè)偶數(shù)結(jié)點(diǎn)p->next=L->pre->pre;else結(jié)點(diǎn)個(gè)數(shù)是偶數(shù)，使最后一個(gè)奇數(shù)結(jié)點(diǎn)next指

11、向最后一個(gè)偶數(shù)結(jié)點(diǎn)p->next=L->pre;p=p->next;此時(shí)p指向最后一個(gè)偶數(shù)結(jié)點(diǎn)while(p->pre->pre!=L)p->next=p->pre->pre;p=p->next;p-next=L;最后一個(gè)結(jié)點(diǎn)next指網(wǎng)頭結(jié)點(diǎn)調(diào)整了next鏈的結(jié)構(gòu)，此時(shí)pre鏈仍為原狀調(diào)整pre鏈的結(jié)構(gòu)for(p=L;p->next!=L;p=p->next)p->next->pre=p;L->pre=p；頭結(jié)點(diǎn)的pre指|句a2結(jié)點(diǎn)*/Reform第三章棧和隊(duì)列4 .6試寫一個(gè)算法，識(shí)別依次讀入的一個(gè)以砂結(jié)

12、束符的字符序列是否為形如“序列序列2”模式的字符序列。其中，序列1和序列2中都不包含字符'且序列2是序列1的逆序。例如，"a+b&b+a，是屬于該模式的字符序列，而“1+3&3一1”則不是。算法：intSeqReverse()判斷輸入的字符串中&前和&后部分是否為逆串，是則返回1,否則返回0(InitStack(s);while(e=getchar0)!=，&1)(if(e='0return0;/不允許在&'之刖出現(xiàn)'push(s,e);序列1輸入完畢while(e=getchar()!='

13、9;)(if(StackEmpty(s)return0;pop(s,c);if(e!=c)return0;if(!StackEmpty(s)return0;序列1元素還有剩余return1;/lsReverse3.7假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三種符號(hào):圓括號(hào)”("和")"、方括號(hào)和“”、花括號(hào)“和“”，且這三種括號(hào)可按任意次序嵌套使用。編寫判別給定表達(dá)式中所含的括號(hào)是否正確配對(duì)的算法(已知表達(dá)式已存入數(shù)據(jù)元素為字符的順序表中)。算法:StatusBracketTest(char*str)判別表達(dá)式中二種括號(hào)是否匹配InitStack(s);for(p=str;*

14、p;p+)if(*p=*(，*p=T*p=*，)push(s,*p);elseP='')if(StackEmpty(s)returnERROR;pop(s,c);returnERROR;if(* p=T&&c!= V)return ERROR;if(*returnERROR;/必須與當(dāng)前棧頂括號(hào)匹配/forif(!StackE mp ty(s)return ERROR; 進(jìn)棧的符號(hào)還有剩余,ErrorreturnOK;/BracketTest3. 8設(shè)表達(dá)式由單字母變量、雙目運(yùn)算符和圓括號(hào)組成(如："(a*(b+c)-d)/e試寫一個(gè)算法，將一個(gè)書寫正

15、確的表達(dá)式轉(zhuǎn)換為逆波蘭式。思路:1 .遇到數(shù)字直接發(fā)送2.遇到'C直接入棧3遇到，)，則將棧內(nèi)元素發(fā)送直至遇到則直接入棧5.棧非空時(shí)若優(yōu)先級(jí)大于棧內(nèi)則入棧，否則棧內(nèi)元素出棧int Ran kOfO perator (char c)switch(c)casecasereturn1;0：casecasereturn1;returncase/casereturn2;')intPrecede(charc,charch)returnRankOfOperator(c)>RankOfOperator(ch);voidExpressionTOPolandStyle(charsuffixQ

16、,char*exp)Stacks;InitStack(s,100);inti=0;charc;while(*exp)if(isdigital(*suffixi+=*exp)elseswitchcasecaseexp;(*exp)'(：push(s,'(')；:while(c=pops(s)!=，('suffixi+=c;break;default：if(IsEmpty(s)push(s,*exp);elsesuffixi+=pop(s);exp;與后面的exp+相抵消，使得棧內(nèi)優(yōu)先級(jí)大于等于棧外的都出棧)/endswitch/endelseexp+;/endwh

17、ilewhile(!IsEmpty(s)suffixi+=pop(s);suffixi=0;3.1。假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示隊(duì)列，只設(shè)一個(gè)尾指針指向隊(duì)尾元素，不設(shè)頭指針。試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)和出隊(duì)算法(在出隊(duì)算法中要傳回隊(duì)頭元素的值)要點(diǎn)：定義好數(shù)據(jù)類型，帶頭結(jié)點(diǎn)的單循環(huán)鏈表，只有尾指針，注意刪除元素時(shí)只有一個(gè)元素的特殊性typ edefint DataT ypestructNodeData!ypedata;Node*next;);structCycleListQueueNode*tail;voidInitCycleListQueue(CycleListQueue&L)L

18、.tail=newNode;Ltail->next=L.tail;voidEnterQueue(CycleListQueue&L,DataTypevalue)Node*p=newNode;p->data=value;p->next=L.tail->next;L.tail->next=p;L.tail=p;voidDeparQueue(CycleListQueue&L,DataType&d)(Ltail->next!=L.tail->next->next)ifNode*p=L.tail->next->next;L

19、.tail->next->next=p->next;d=p->data;if(p=L.tail)L.tail=p->next;deletep;returnd;3.11假設(shè)將循環(huán)隊(duì)列定義為：以rear和length分別指示隊(duì)尾元素和隊(duì)列長(zhǎng)度。試給出此循環(huán)隊(duì)列的隊(duì)滿條件，并寫出相應(yīng)的入隊(duì)和出隊(duì)算法(在出隊(duì)算法中要傳遞回隊(duì)頭元素的值)。此循環(huán)隊(duì)列的隊(duì)滿條件：Q.Iength-MAXQSIZE;入隊(duì)算法：StatusEnCyQueue(CyQueue&Q,intx)/帶length域的循環(huán)隊(duì)列入隊(duì)算法(if(Q.Iength=MAXSIZE)returnOVERF

20、LOW;Q.rear=(Q.rea葉1)%MAXSIZE;Q.baseQ.rear=x;/rear指向隊(duì)尾兀素Q.Iength+;returnOK;/EnCyQueue出隊(duì)算法：StatusDeCyQueue(CyQueue&Q,int&x)/帶length域的循環(huán)隊(duì)列出隊(duì)算法，用x返回隊(duì)頭元素的值(if(Q.length=O)returnError;/空隊(duì)歹錯(cuò)誤head=(Q.rear-Q.Iength+l)%MAXSIZE;/head指1司隊(duì)頭x=Q.basehead;Q.Iength;returnOK;/DeCyQueue3.12試寫一個(gè)算法：判別讀入的一個(gè)以為結(jié)束符的字

21、符序列是否是“回文”(所謂“回文”是指正讀和反讀都相同的字符序列，如“xxyzyxx”是回文，而“abcab”則不是回文)。StatusTest()判別輸入的字符串是否回文序列，是則返回1,否則返回0(InitStack(S);InitQueue(Q);while(c=getchar()!=,)(Push(S,c);EnQueue(Q,c);同時(shí)使用棧和隊(duì)列兩種結(jié)構(gòu))while(IStackEmpty(S)(Pop(S,a);DeQueue(Q,b);if(a!=b)returnERROR;returnOK;/Test第五章多維數(shù)組5.4設(shè)有一個(gè)準(zhǔn)對(duì)角矩陣a1222riia2133a3443a

22、442m*f 2m J3.2m, 2m.a 2m , 2ma2m, 2m按以下方式存于一維數(shù)組BL詞中:alla12a21a22a33B34a43 a 1J a2m-l, 2ma2m, 2m01234564nl24m-1寫出由一對(duì)下標(biāo)(i, j)求k的轉(zhuǎn)換公式。因?yàn)閕行前有2(i-l)個(gè)元素?，F(xiàn)考慮i行情況,當(dāng)j是奇數(shù)，i行有1個(gè)元素,k=2(i-l)+l+2(i-l)；否則i行有 2 個(gè)元素，k=2(i-l)+2-l=2i-lo 故:1)腐奇數(shù)k=bni /為翩或若 i 為奇數(shù)，k=2(i-l)+j-i=i+j-2;當(dāng) i 為偶數(shù)時(shí)，k=2i-(i-j)-l=i+j-l5. 5已知稀疏矩陣A

23、4X 5如下:I 10 32 00 40051006000700 用三元組表作為存儲(chǔ)結(jié)構(gòu)，繪出相應(yīng)的三元組表示意圖; 用十字鏈表作為存儲(chǔ)結(jié)構(gòu)，繪出相應(yīng)的十字鏈表示意圖。三元組表:1jV121155212223246424457十字鏈表第六章數(shù)和二叉樹(shù)6.5已知一棵度為k的樹(shù)中有nl個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，nk個(gè)度為k的結(jié)點(diǎn)，問(wèn)該樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)？設(shè)葉子結(jié)點(diǎn)有x個(gè)，則樹(shù)的結(jié)點(diǎn)總數(shù)為nl+n2+nk+x;同時(shí)除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都指向一個(gè)結(jié)點(diǎn)，所有從這個(gè)角度考慮樹(shù)的結(jié)點(diǎn)總數(shù)為：nl+2?n2+k?nk+l;knl+n2+nk+x=nl+2?n2+k?nk+l可得x=S(i-i)-

24、ni+1iz26.8已知一棵樹(shù)如圖6-1所示，畫出與該樹(shù)對(duì)應(yīng)的二叉樹(shù)，并寫出該樹(shù)的先根遍歷序列和后根遍歷序列。圖6-1先根遍歷：ABCEIJFGKHD后根遍歷：BIJEFKGHCDA對(duì)應(yīng)的二叉樹(shù)：6.9將如圖6-2所示的森林轉(zhuǎn)化為對(duì)應(yīng)的二叉樹(shù)。樹(shù)對(duì)應(yīng)的二叉樹(shù)森林對(duì)應(yīng)的二叉樹(shù):圖6-2圖6-26.n己知某二叉樹(shù)的中序序列為請(qǐng)DCBGEAHFIJK,后序序列為DCEGBFHKJIA。畫出該二叉樹(shù)。每個(gè)字母在電文中出現(xiàn)6.14假設(shè)某個(gè)電文由(a,b,c,d,e,f,g,h)8個(gè)字母組成,的次數(shù)分別為(7,19,2,6,32,3,21,10),試解答下列問(wèn)題：(1)ifflj出出huffman樹(shù)；10

25、0寫出每個(gè)字母的huffman編碼;a:1010b:00c:10000d:1001e:llf:10001g:01h:1011在對(duì)該電文進(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寫出按層次遍歷二叉樹(shù)的算法。思路：用隊(duì)列存儲(chǔ)結(jié)構(gòu)，并用遞歸方法StatusLevelOrderTraverse(BitTreeStatus(*Visit)(TEIemTypee)/層序遍歷二叉樹(shù)InitQueue(Q);初始化隊(duì)列if(!T)returnError;/空樹(shù)，直接返回EnQueue(Q,T)；根結(jié)點(diǎn)入隊(duì)BiTNode*p

26、;while(JQueueEmpty(Q)(DeQueue(Q,p);Visit(p->data);if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);/whilereturnOk;/LevelOrderTraverse6. 19寫出判斷兩棵給定二叉樹(shù)是否相似的算法。（注：兩棵二叉樹(shù)B1和B2相似是指：B1和B2皆空，或者皆不空且B1的左、右子樹(shù)和B2的左、右子樹(shù)分別相似。）思路：采用遞歸進(jìn)行比較判斷boolBiTreeSimilar(BiTreeTl,BiTreeT2)if(Tl

27、=Null&&T2=Null)return1;elseif(T1二二NullT2=Null)return0;elsereturn(BiTreeSilimar(Tl->lchild,T2->lchild)&&BiTreeSimilar(Tl->rchild,T2->rchild);6.21寫出統(tǒng)計(jì)樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)的算法，樹(shù)用孩子兄弟鏈表表示。思路：在孩子兄弟鏈表中，若結(jié)點(diǎn)的firstchild為Null,則為葉子結(jié)點(diǎn)；采用遞歸方法。intCountLeaves(TreeT,int&num)/num傳遞的初值為0(if(T->n

28、extsibling!=Null)num+=CountLeaves(T->nextsibling);if(T->firstchild!=Null)num+=CountLeaves(T->firstchild);elsenum+=l;/firstchild域?yàn)榭?，則為葉子結(jié)點(diǎn)returnnum;)第七章圖7. 1已知有向圖如圖7-1所示,請(qǐng)給出該圖的鄰接矩陣示意圖鄰接表示意圖逆鄰接表(4)所有強(qiáng)連通分量鄰接矩陣o00000100100010001001011I 0000°II 10010(2)鄰接表(3)逆鄰接表強(qiáng)連通分量V2V6V4V37.2已知圖G的鄰接矩陣如圖7

29、-2所示。寫出該圖從頂點(diǎn)1出發(fā)的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列，并畫出相應(yīng)的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。1234567891010圖7-2深度優(yōu)先序歹lj:1734562109810深度優(yōu)先生成樹(shù)：廣度優(yōu)先序列：17931054862103廣度優(yōu)先生成樹(shù):9.1若對(duì)大小均為n的有序順序表和無(wú)序順序表分別進(jìn)行順序查找，試在下列三種情況下分別討論兩者在等概率時(shí)平均查找長(zhǎng)度是否相同？（1）查找不成功，即表中沒(méi)有關(guān)鍵字等于給定的值的記錄;（2 ）查找成功，且表中只有一個(gè)關(guān)鍵字等于給定值（3 ）查找成功，且表中有若干個(gè)關(guān)鍵字等于給定值 解: 對(duì)有序順序表：的記錄；的記錄，要求找出所有這些記 錄。11.1 +2 + . + (n 九+2)個(gè)元素序列的成功查找問(wèn)題)21 n +1nLJ 2（將該項(xiàng)看作一項(xiàng)混入原有序列中，問(wèn)題轉(zhuǎn)變成n+13.L1+2 + 一此k項(xiàng)看作一項(xiàng)n- (k- 1) L+ n- (k 1) 1 =J 2TA將對(duì)無(wú)序順序表:-rl +2 +