嚴蔚敏版C語言數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案

《嚴蔚敏版C語言數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案》由會員分享，可在線閱讀，更多相關(guān)《嚴蔚敏版C語言數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案（127頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、說明: 1. 本文是對嚴蔚敏數(shù)據(jù)結(jié)構(gòu)(c語言版)習(xí)題集一書中所有算法設(shè)計題目的解決方案,主要作者為計算機版版主一具.以下網(wǎng)友:siice,龍?zhí)ь^,iamkent,zames,birdthinking等為答案的修訂和完善工作提出了寶貴意見,在此表示感謝;2. 本解答中的所有算法均采用類c語言描述,設(shè)計原則為面向交流、面向閱讀,作者不保證程序能夠上機正常運行(這種保證實際上也沒有任何意義);3. 本解答原則上只給出源代碼以及必要的注釋,對于一些難度較高或思路特殊的題目將給出簡要的分析說明,對于作者無法解決的題目將給出必要的討論.目前尚未解決的題目有: 5.20, 10.40;4. 請讀者在自己已經(jīng)

2、解決了某個題目或進行了充分的思考之后,再參考本解答,以保證復(fù)習(xí)效果;5. 由于作者水平所限,本解答中一定存在不少這樣或者那樣的錯誤和不足,希望讀者們在閱讀中多動腦、勤思考,爭取發(fā)現(xiàn)和糾正這些錯誤,寫出更好的算法來.請將你發(fā)現(xiàn)的錯誤或其它值得改進之處向作者報告: yi-ju 第一章 緒論 1.16 void print_descending(int x,int y,int z)/按從大到小順序輸出三個數(shù) scanf(%d,%d,%d,&x,&y,&z); if(xy) xy; /為表示交換的雙目運算符,以下同 if(yz) yz; if(xy) xy; /冒泡排序 printf(%d %d %d

3、,x,y,z);/print_descending 1.17 Status fib(int k,int m,int &f)/求k階斐波那契序列的第m項的值fint tempd;if(k2|m0) return ERROR;if(mk-1) f=0;else if (m=k-1) f=1;elsefor(i=0;i=k-2;i+) tempi=0;tempk-1=1; /初始化for(i=k;i=m;i+) /求出序列第k至第m個元素的值sum=0;for(j=i-k;ji;j+) sum+=tempj;tempi=sum;f=tempm;return OK;/fib分析:通過保存已經(jīng)計算出來的

4、結(jié)果,此方法的時間復(fù)雜度僅為O(m2).如果采用遞歸編程(大多數(shù)人都會首先想到遞歸方法),則時間復(fù)雜度將高達O(km). 1.18 typedef struct char *sport; enummale,female gender; char schoolname; /校名為A,B,C,D或E char *result; int score; resulttype; typedef struct int malescore; int femalescore; int totalscore; scoretype; void summary(resulttype result )/求各校的男女總

5、分和團體總分,假設(shè)結(jié)果已經(jīng)儲存在result 數(shù)組中scoretype score;i=0;while(resulti.sport!=NULL)switch(resulti.schoolname)case A:score 0 .totalscore+=resulti.score;if(resulti.gender=0) score 0 .malescore+=resulti.score;else score 0 .femalescore+=resulti.score;break;case B:score.totalscore+=resulti.score;if(resulti.gender=0

6、) score.malescore+=resulti.score;else score.femalescore+=resulti.score;break;i+；for(i=0;i5;i+)printf(School %d:n,i);printf(Total score of male:%dn,scorei.malescore);printf(Total score of female:%dn,scorei.femalescore);printf(Total score of all:%dnn,scorei.totalscore);/summary 1.19 Status algo119(int

7、 aARRSIZE)/求i!*2i序列的值且不超過maxintlast=1;for(i=1;i=ARRSIZE;i+) ai-1=last*2*i; if(ai-1/last)!=(2*i) reurn OVERFLOW; last=ai-1; return OK;/algo119分析:當某一項的結(jié)果超過了maxint時,它除以前面一項的商會發(fā)生異常. 1.20 void polyvalue()float ad;float *p=a;printf(Input number of terms:);scanf(%d,&n);printf(Input the %d coefficients from

8、 a0 to a%d:n,n,n);for(i=0;i=n;i+) scanf(%f,p+);printf(Input value of x:);scanf(%f,&x);p=a;xp=1;sum=0; /xp用于存放x的i次方for(i=0;i=n;i+)sum+=xp*(*p+);xp*=x;printf(Value is:%f,sum);/polyvalue第二章 線性表 2.10 Status DeleteK(SqList &a,int i,int k)/刪除線性表a中第i個元素起的k個元素if(i1|ka.length) return INFEASIBLE;for(count=1;i

9、+count-1va.listsize) return ERROR;va.length+;for(i=va.length-1;va.elemix&i=0;i-)va.elemi+1=va.elemi;va.elemi+1=x;return OK;/Insert_SqList 2.12 int ListComp(SqList A,SqList B)/比較字符表A和B,并用返回值表示結(jié)果,值為正,表示AB;值為負,表示Anext;p&p-data!=x;p=p-next);return p;/Locate 2.14 int Length(LinkList L)/求鏈表的長度for(k=0,p=L;

10、p-next;p=p-next,k+);return k;/Length 2.15 void ListConcat(LinkList ha,LinkList hb,LinkList &hc)/把鏈表hb接在ha后面形成鏈表hchc=ha;p=ha;while(p-next) p=p-next;p-next=hb;/ListConcat 2.16 見書后答案. 2.17 Status Insert(LinkList &L,int i,int b)/在無頭結(jié)點鏈表L的第i個元素之前插入元素bp=L;q=(LinkList*)malloc(sizeof(LNode);q.data=b;if(i=1)

11、q.next=p;L=q; /插入在鏈表頭部elsewhile(-i1) p=p-next;q-next=p-next;p-next=q; /插入在第i個元素的位置/Insert 2.18 Status Delete(LinkList &L,int i)/在無頭結(jié)點鏈表L中刪除第i個元素if(i=1) L=L-next; /刪除第一個元素elsep=L;while(-i1) p=p-next;p-next=p-next-next; /刪除第i個元素/Delete 2.19 Status Delete_Between(Linklist &L,int mink,int maxk)/刪除元素遞增排列

12、的鏈表L中值大于mink且小于maxk的所有元素p=L;while(p-next-datanext; /p是最后一個不大于mink的元素if(p-next)/如果還有比mink更大的元素q=p-next;while(q-datanext; /q是第一個不小于maxk的元素p-next=q;/Delete_Between 2.20 Status Delete_Equal(Linklist &L)/刪除元素遞增排列的鏈表L中所有值相同的元素p=L-next;q=p-next; /p,q指向相鄰兩元素while(p-next)if(p-data!=q-data)p=p-next;q=p-next;

13、/當相鄰兩元素不相等時,p,q都向后推一步elsewhile(q-data=p-data) free(q); q=q-next; p-next=q;p=q;q=p-next; /當相鄰元素相等時刪除多余元素/else/while/Delete_Equal 2.21 void reverse(SqList &A)/順序表的就地逆置for(i=1,j=A.length;ij;i+,j-)A.elemiA.elemj;/reverse 2.22 void LinkList_reverse(Linklist &L)/鏈表的就地逆置;為簡化算法,假設(shè)表長大于2p=L-next;q=p-next;s=q-

14、next;p-next=NULL;while(s-next)q-next=p;p=q;q=s;s=s-next; /把L的元素逐個插入新表表頭q-next=p;s-next=q;L-next=s;/LinkList_reverse分析:本算法的思想是,逐個地把L的當前元素q插入新的鏈表頭部,p為新表表頭. 2.23 void merge1(LinkList &A,LinkList &B,LinkList &C)/把鏈表A和B合并為C,A和B的元素間隔排列,且使用原存儲空間p=A-next;q=B-next;C=A;while(p&q)s=p-next;p-next=q; /將B的元素插入if(

15、s)t=q-next;q-next=s; /如A非空,將A的元素插入p=s;q=t;/while/merge1 2.24 void reverse_merge(LinkList &A,LinkList &B,LinkList &C)/把元素遞增排列的鏈表A和B合并為C,且C中元素遞減排列,使用原空間pa=A-next;pb=B-next;pre=NULL; /pa和pb分別指向A,B的當前元素while(pa|pb)if(pa-datadata|!pb)pc=pa;q=pa-next;pa-next=pre;pa=q; /將A的元素插入新表elsepc=pb;q=pb-next;pb-next

16、=pre;pb=q; /將B的元素插入新表pre=pc;C=A;A-next=pc; /構(gòu)造新表頭/reverse_merge分析:本算法的思想是,按從小到大的順序依次把A和B的元素插入新表的頭部pc處,最后處理A或B的剩余元素. 2.25 void SqList_Intersect(SqList A,SqList B,SqList &C)/求元素遞增排列的線性表A和B的元素的交集并存入C中i=1;j=1;k=0;while(A.elemi&B.elemj)if(A.elemiB.elemj) j+;if(A.elemi=B.elemj)C.elem+k=A.elemi; /當發(fā)現(xiàn)了一個在A,

17、B中都存在的元素,i+;j+; /就添加到C中/while/SqList_Intersect 2.26 void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)/在鏈表結(jié)構(gòu)上重做上題p=A-next;q=B-next;pc=(LNode*)malloc(sizeof(LNode);while(p&q)if(p-datadata) p=p-next;else if(p-dataq-data) q=q-next;elses=(LNode*)malloc(sizeof(LNode);s-data=p-data;pc-next=s;pc=s;

18、p=p-next;q=q-next;/whileC=pc;/LinkList_Intersect 2.27 void SqList_Intersect_True(SqList &A,SqList B)/求元素遞增排列的線性表A和B的元素的交集并存回A中i=1;j=1;k=0;while(A.elemi&B.elemj)if(A.elemiB.elemj) j+;else if(A.elemi!=A.elemk)A.elem+k=A.elemi; /當發(fā)現(xiàn)了一個在A,B中都存在的元素i+;j+; /且C中沒有,就添加到C中/whilewhile(A.elemk) A.elemk+=0;/SqLi

19、st_Intersect_True 2.28 void LinkList_Intersect_True(LinkList &A,LinkList B)/在鏈表結(jié)構(gòu)上重做上題p=A-next;q=B-next;pc=A;while(p&q)if(p-datadata) p=p-next;else if(p-dataq-data) q=q-next;else if(p-data!=pc-data)pc=pc-next;pc-data=p-data;p=p-next;q=q-next;/while/LinkList_Intersect_True 2.29 void SqList_Intersect_

20、Delete(SqList &A,SqList B,SqList C) i=0;j=0;k=0;m=0;/i指示A中元素原來的位置,m為移動后的位置 while(iA.length&jB.length& kC.length) if(B.elemjC.elemk) k+; else same=B.elemj;/找到了相同元素same while(B.elemj=same) j+; while(C.elemk=same) k+;/j,k后移到新的元素 while(iA.length&A.elemisame) A.elemm+=A.elemi+;/需保留的元素移動到新位置 while(iA.leng

21、th&A.elemi=same) i+;/跳過相同的元素 /while while(inext;q=C-next;r=A-next;while(p&q&r)if(p-datadata) p=p-next;else if(p-dataq-data) q=q-next;elseu=p-data; /確定待刪除元素uwhile(r-next-datanext; /確定最后一個小于u的元素指針rif(r-next-data=u)s=r-next;while(s-data=u)t=s;s=s-next;free(t); /確定第一個大于u的元素指針s/whiler-next=s; /刪除r和s之間的元素

22、/ifwhile(p-data=u) p=p-next;while(q-data=u) q=q-next;/else/while/LinkList_Intersect_Delete 2.31 Status Delete_Pre(CiLNode *s)/刪除單循環(huán)鏈表中結(jié)點s的直接前驅(qū)p=s;while(p-next-next!=s) p=p-next; /找到s的前驅(qū)的前驅(qū)pp-next=s;return OK;/Delete_Pre 2.32 Status DuLNode_Pre(DuLinkList &L)/完成雙向循環(huán)鏈表結(jié)點的pre域for(p=L;!p-next-pre;p=p-ne

23、xt) p-next-pre=p;return OK;/DuLNode_Pre 2.33 Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)/把單鏈表L的元素按類型分為三個循環(huán)鏈表.CiList為帶頭結(jié)點的單循環(huán)鏈表類型.s=L-next;A=(CiList*)malloc(sizeof(CiLNode);p=A;B=(CiList*)malloc(sizeof(CiLNode);q=B;C=(CiList*)malloc(sizeof(CiLNode);r=C; /建立頭結(jié)點while(s)if(isalphab

24、et(s-data)p-next=s;p=s;else if(isdigit(s-data)q-next=s;q=s;elser-next=s;r=s;/whilep-next=A;q-next=B;r-next=C; /完成循環(huán)鏈表/LinkList_Divide 2.34 void Print_XorLinkedList(XorLinkedList L)/從左向右輸出異或鏈表的元素值p=L.left;pre=NULL;while(p)printf(%d,p-data);q=XorP(p-LRPtr,pre);pre=p;p=q; /任何一個結(jié)點的LRPtr域值與其左結(jié)點指針進行異或運算即得

25、到其右結(jié)點指針/Print_XorLinkedList 2.35 Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)/在異或鏈表L的第i個元素前插入元素xp=L.left;pre=NULL;r=(XorNode*)malloc(sizeof(XorNode);r-data=x;if(i=1) /當插入點在最左邊的情況p-LRPtr=XorP(p.LRPtr,r);r-LRPtr=p;L.left=r;return OK;j=1;q=p-LRPtr; /當插入點在中間的情況while(+jLRPtr,pre);pre=p;p=q;/

26、while /在p,q兩結(jié)點之間插入if(!q) return INFEASIBLE; /i不可以超過表長p-LRPtr=XorP(XorP(p-LRPtr,q),r);q-LRPtr=XorP(XorP(q-LRPtr,p),r);r-LRPtr=XorP(p,q); /修改指針return OK;/Insert_XorLinkedList 2.36 Status Delete_XorLinkedList(XorlinkedList &L,int i)/刪除異或鏈表L的第i個元素p=L.left;pre=NULL;if(i=1) /刪除最左結(jié)點的情況q=p-LRPtr;q-LRPtr=Xor

27、P(q-LRPtr,p);L.left=q;free(p);return OK;j=1;q=p-LRPtr;while(+jLRPtr,pre);pre=p;p=q;/while /找到待刪結(jié)點qif(!q) return INFEASIBLE; /i不可以超過表長if(L.right=q) /q為最右結(jié)點的情況p-LRPtr=XorP(p-LRPtr,q);L.right=p;free(q);return OK;r=XorP(q-LRPtr,p); /q為中間結(jié)點的情況,此時p,r分別為其左右結(jié)點p-LRPtr=XorP(XorP(p-LRPtr,q),r);r-LRPtr=XorP(Xor

28、P(r-LRPtr,q),p); /修改指針free(q);return OK;/Delete_XorLinkedList 2.37 void OEReform(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) p-next=L-pre-pre;else p-next=l-pre;p=p-next; /此時p指向最后一個偶數(shù)結(jié)點while(p-pre-pre!=L

29、)p-next=p-pre-pre;p=p-next;p-next=L; /按題目要求調(diào)整了next鏈的結(jié)構(gòu),此時pre鏈仍為原狀for(p=L;p-next!=L;p=p-next) p-next-pre=p;L-pre=p; /調(diào)整pre鏈的結(jié)構(gòu),同2.32方法/OEReform分析:next鏈和pre鏈的調(diào)整只能分開進行.如同時進行調(diào)整的話,必須使用堆棧保存偶數(shù)結(jié)點的指針,否則將會破壞鏈表結(jié)構(gòu),造成結(jié)點丟失. 2.38 DuLNode * Locate_DuList(DuLinkedList &L,int x)/帶freq域的雙向循環(huán)鏈表上的查找p=L.next;while(p.data

30、!=x&p!=L) p=p-next;if(p=L) return NULL; /沒找到p-freq+;q=p-pre;while(q-freqfreq) q=q-pre; /查找插入位置if(q!=p-pre)p-pre-next=p-next;p-next-pre=p-pre;q-next-pre=p;p-next=q-next;q-next=p;p-pre=q; /調(diào)整位置return p;/Locate_DuList 2.39 float GetValue_SqPoly(SqPoly P,int x0)/求升冪順序存儲的稀疏多項式的值PolyTerm *q;xp=1;q=P.data;

31、sum=0;ex=0;while(q-coef)while(exexp) xp*=x0;sum+=q-coef*xp;q+;return sum;/GetValue_SqPoly 2.40 void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)/求稀疏多項式P1減P2的差式P3PolyTerm *p,*q,*r;Create_SqPoly(P3); /建立空多項式P3p=P1.data;q=P2.data;r=P3.data;while(p-coef&q-coef)if(p-expexp)r-coef=p-coef;r-exp=p-exp;p+

32、;r+;else if(p-expexp)r-coef=-q-coef;r-exp=q-exp;q+;r+;elseif(p-coef-q-coef)!=0) /只有同次項相減不為零時才需要存入P3中r-coef=p-coef-q-coef;r-exp=p-exp;r+;/ifp+;q+;/else/whilewhile(p-coef) /處理P1或P2的剩余項r-coef=p-coef;r-exp=p-exp;p+;r+;while(q-coef)r-coef=-q-coef;r-exp=q-exp;q+;r+;/Subtract_SqPoly 2.41 void QiuDao_Linked

33、Poly(LinkedPoly &L)/對有頭結(jié)點循環(huán)鏈表結(jié)構(gòu)存儲的稀疏多項式L求導(dǎo)p=L-next;if(!p-data.exp)L-next=p-next;p=p-next; /跳過常數(shù)項while(p!=L)p-data.coef*=p-data.exp-;/對每一項求導(dǎo)p=p-next;/QiuDao_LinkedPoly 2.42 void Divide_LinkedPoly(LinkedPoly &L,&A,&B)/把循環(huán)鏈表存儲的稀疏多項式L拆成只含奇次項的A和只含偶次項的Bp=L-next;A=(PolyNode*)malloc(sizeof(PolyNode);B=(Poly

34、Node*)malloc(sizeof(PolyNode);pa=A;pb=B;while(p!=L)if(p-data.exp!=2*(p-data.exp/2)pa-next=p;pa=p;elsepb-next=p;pb=p;p=p-next;/whilepa-next=A;pb-next=B; /Divide_LinkedPoly第三章 棧與隊列 3.15 typedef struct Elemtype *base2; Elemtype *top2; BDStacktype; /雙向棧類型 Status Init_Stack(BDStacktype &tws,int m)/初始化一個大

35、小為m的雙向棧twstws.base0=(Elemtype*)malloc(sizeof(Elemtype);tws.base1=tws.base0+m;tws.top0=tws.base0;tws.top1=tws.base1;return OK;/Init_Stack Status push(BDStacktype &tws,int i,Elemtype x)/x入棧,i=0表示低端棧,i=1表示高端棧if(tws.top0tws.top1) return OVERFLOW; /注意此時的棧滿條件if(i=0) *tws.top0+=x;else if(i=1) *tws.top1-=x;

36、else return ERROR;return OK;/push Status pop(BDStacktype &tws,int i,Elemtype &x)/x出棧,i=0表示低端棧,i=1表示高端棧if(i=0)if(tws.top0=tws.base0) return OVERFLOW;x=*-tws.top0;else if(i=1)if(tws.top1=tws.base1) return OVERFLOW;x=*+tws.top1;else return ERROR;return OK;/pop 3.16 void Train_arrange(char *train)/這里用字符

37、串train表示火車,H表示硬席,S表示軟席p=train;q=train;InitStack(s);while(*p)if(*p=H) push(s,*p); /把H存入棧中else *(q+)=*p; /把S調(diào)到前部p+;while(!StackEmpty(s)pop(s,c);*(q+)=c; /把H接在后部/Train_arrange 3.17 int IsReverse()/判斷輸入的字符串中&前和&后部分是否為逆串,是則返回1,否則返回0InitStack(s);while(e=getchar()!=&)push(s,e);while(e=getchar()!=)if(StackE

38、mpty(s) return 0;pop(s,c);if(e!=c) return 0;if(!StackEmpty(s) return 0;return 1;/IsReverse 3.18 Status Bracket_Test(char *str)/判別表達式中小括號是否匹配count=0;for(p=str;*p;p+)if(*p=() count+;else if(*p=) count-;if (count1)if(gx-1y=old)gx-1y=color;EnQueue(Q,x-1,y); /修改左鄰點的顏色if(y1)if(gxy-1=old)gxy-1=color;EnQueu

39、e(Q,x,y-1); /修改上鄰點的顏色if(xm)if(gx+1y=old)gx+1y=color;EnQueue(Q,x+1,y); /修改右鄰點的顏色if(y=0) s=0;else if(m0&n=0) s=n+g(m-1,2*n);else return ERROR;return OK;/g 3.25 Status F_recursive(int n,int &s)/遞歸算法if(n0) return ERROR;if(n=0) s=n+1;elseF_recurve(n/2,r);s=n*r;return OK;/F_recursive Status F_nonrecursive(int n,int s)/非遞歸算法if(n0) return ERROR;if(n=0) s=n+1;elseInitStack(s); /s的元素類型為struct int a;int b;while(n!=0)a=n;b=n/2;push(s,a,b);n=b;/whiles=1;while(!StackEmpty(s)pop(s,t);s*=t.a;/whilereturn OK;/F_nonrecursive 3.26 float Sqrt