數(shù)據(jù)結構(C語言版)習題解答

1、L3設n是正整數(shù)。試寫出下列程序段中用記號標注的語句的頻度:i=l；k=0;dok+=10*i;i+;while(iv=n-l)當n=l時，執(zhí)行1；當n>=2時，執(zhí)行n-l次；i=l;k=0;dok+=10*i;i-+;while(i=n);當n=2時,執(zhí)行2次;當n!=2時,執(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語句執(zhí)行100次(7)for(i=0;ivn;i+)for(j=i;jvn;j+)for(k=j;kvn;k+)x+=2;過程：去，M第一早1 .3已知順序表La中數(shù)據(jù)元素按非遞減有序排列。試寫一個算法，將元素到La的合適位置上，保持該表的有序性。思路：先判斷線性表的存儲空間是否滿，若滿返回Error；否則從后向前先移動數(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試寫一個算法，實現(xiàn)順序表的就地逆置，即在原表的存儲空間將線性表(ai,a2,an-1,an)逆置為(an,an-1,.,a2,a1)思路就是兩個指示變量i,j同時分別從順序表的開始和結尾處相向改變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采用順序存儲結構存放，對兩種不同情況分別寫出算法，刪除L中多余的元素，使得L中沒有重復元素：(1)L中數(shù)據(jù)元素無序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。int L. Ie ngth)voidDelete-SameElemCSqLink&L,吶層循環(huán)移動參數(shù)，中層循環(huán)尋找相同元，外層循環(huán)遍歷整個表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;移動元素后，由于少了一個元素，因此要減1/endifIf(L.EIemj>L.EIemi)break;/第二小問添加此句/endfor/endwhile/endfunctoion1 .8已知線性表L采用鏈式結構存放。對兩種不同情況分別寫出算法，刪除L中值相同的多余元素，使得L中沒有重復元素：L中數(shù)據(jù)元素無序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。(1) L中數(shù)據(jù)元素無序排列；思路：由于是無序排列，需要線性表中每個元素都要相互進行比較。StatusListDelete(Linklist&L

6、)/L是帶頭結點的線性表(ElemType*p,*q;p=L-next;q=p-next;設定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;開始后一結點的尋找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;多個連續(xù)的重復值/elsep->next=q;p=q;q=p->next;刪除值重復的結點，并修改相應的指針returnOK;/ListDelete2 .9設有兩個非遞減有序的單鏈表A,B。請寫出算法，將3和B就地歸并成一個按元素值非遞增有序的單鏈表。將合并逆置后的結果放在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將當前最小結點插入A表表頭e

9、xt=qa;elseqb=pb;pb=pb->next;將當前最小結點插入 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設以帶頭結點的雙向循環(huán)鏈表表示的線性表L=(al,a2,a3,.,an)o試寫一時間復雜度為0(n)的算法,將L

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

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

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ù)據(jù)元素為字符的順序表中)。算法:StatusBracketTest(char*str)判別表達式中二種括號是否匹配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;/必須與當前棧頂括號匹配/forif(!StackE mp ty(s)return ERROR; 進棧的符號還有剩余,ErrorreturnOK;/BracketTest3. 8設表達式由單字母變量、雙目運算符和圓括號組成(如："(a*(b+c)-d)/e試寫一個算法，將一個書寫正

15、確的表達式轉(zhuǎn)換為逆波蘭式。思路:1 .遇到數(shù)字直接發(fā)送2.遇到'C直接入棧3遇到，)，則將棧內(nèi)元素發(fā)送直至遇到則直接入棧5.棧非空時若優(yōu)先級大于棧內(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)先級大于等于棧外的都出棧)/endswitch/endelseexp+;/endwh

17、ilewhile(!IsEmpty(s)suffixi+=pop(s);suffixi=0;3.1。假設以帶頭結點的單循環(huán)鏈表表示隊列，只設一個尾指針指向隊尾元素，不設頭指針。試編寫相應的隊列初始化、入隊和出隊算法(在出隊算法中要傳回隊頭元素的值)要點：定義好數(shù)據(jù)類型，帶頭結點的單循環(huán)鏈表，只有尾指針，注意刪除元素時只有一個元素的特殊性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假設將循環(huán)隊列定義為：以rear和length分別指示隊尾元素和隊列長度。試給出此循環(huán)隊列的隊滿條件，并寫出相應的入隊和出隊算法(在出隊算法中要傳遞回隊頭元素的值)。此循環(huán)隊列的隊滿條件：Q.Iength-MAXQSIZE;入隊算法：StatusEnCyQueue(CyQueue&Q,intx)/帶length域的循環(huán)隊列入隊算法(if(Q.Iength=MAXSIZE)returnOVERF

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

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

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

23、4X 5如下:I 10 32 00 40051006000700 用三元組表作為存儲結構，繪出相應的三元組表示意圖; 用十字鏈表作為存儲結構，繪出相應的十字鏈表示意圖。三元組表:1jV121155212223246424457十字鏈表第六章數(shù)和二叉樹6.5已知一棵度為k的樹中有nl個度為1的結點，n2個度為2的結點，nk個度為k的結點，問該樹中有多少個葉子結點？設葉子結點有x個，則樹的結點總數(shù)為nl+n2+nk+x;同時除了根結點外，每個結點都指向一個結點，所有從這個角度考慮樹的結點總數(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已知一棵樹如圖6-1所示，畫出與該樹對應的二叉樹，并寫出該樹的先根遍歷序列和后根遍歷序列。圖6-1先根遍歷：ABCEIJFGKHD后根遍歷：BIJEFKGHCDA對應的二叉樹：6.9將如圖6-2所示的森林轉(zhuǎn)化為對應的二叉樹。樹對應的二叉樹森林對應的二叉樹:圖6-2圖6-26.n己知某二叉樹的中序序列為請DCBGEAHFIJK,后序序列為DCEGBFHKJIA。畫出該二叉樹。每個字母在電文中出現(xiàn)6.14假設某個電文由(a,b,c,d,e,f,g,h)8個字母組成,的次數(shù)分別為(7,19,2,6,32,3,21,10),試解答下列問題：(1)ifflj出出huffman樹；10

25、0寫出每個字母的huffman編碼;a:1010b:00c:10000d:1001e:llf:10001g:01h:1011在對該電文進行最優(yōu)二進制編碼處理后，電文的二進制位數(shù)。4*7+2*19+5*2+4*6+2*32+5*3+2*21+4*10=2616.17寫出按層次遍歷二叉樹的算法。思路：用隊列存儲結構，并用遞歸方法StatusLevelOrderTraverse(BitTreeStatus(*Visit)(TEIemTypee)/層序遍歷二叉樹InitQueue(Q);初始化隊列if(!T)returnError;/空樹，直接返回EnQueue(Q,T)；根結點入隊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寫出判斷兩棵給定二叉樹是否相似的算法。（注：兩棵二叉樹B1和B2相似是指：B1和B2皆空，或者皆不空且B1的左、右子樹和B2的左、右子樹分別相似。）思路：采用遞歸進行比較判斷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)計樹中葉子結點個數(shù)的算法，樹用孩子兄弟鏈表表示。思路：在孩子兄弟鏈表中，若結點的firstchild為Null,則為葉子結點；采用遞歸方法。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域為空，則為葉子結點returnnum;)第七章圖7. 1已知有向圖如圖7-1所示,請給出該圖的鄰接矩陣示意圖鄰接表示意圖逆鄰接表(4)所有強連通分量鄰接矩陣o00000100100010001001011I 0000°II 10010(2)鄰接表(3)逆鄰接表強連通分量V2V6V4V37.2已知圖G的鄰接矩陣如圖7

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