數(shù)據(jù)結(jié)構(gòu)習(xí)題答案全部算法嚴(yán)蔚敏版

《數(shù)據(jù)結(jié)構(gòu)習(xí)題答案全部算法嚴(yán)蔚敏版》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)習(xí)題答案全部算法嚴(yán)蔚敏版（120頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題答案(全部算法)---嚴(yán)蔚敏版 第一章緒論 1.16 void print_descending(int x,int y,int z)//按從大到小順序輸出三個(gè)數(shù) { scanf("%d,%d,%d",&x,&y,&z); if(x<->y; //<->為表示交換的雙目運(yùn)算符,以下同 if(y<->z; if(x<->y; //冒泡排序 printf("%d %d %d",x,y,z); }//print_descending 1.17 Status fib(int k,int m,int &f)//求k階斐波那契序列的第m項(xiàng)的值f { int

2、tempd; if(k<2||m<0) return ERROR; if(melse if (m==k-1 || m==k) f=1; else { for(i=0;i<=k-2;i++) temp[i]=0; temp[k-1]=1;temp[k]=1; //初始化 sum=1; j=0; for(i=k+1;i<=m;i++,j++) //求出序列第k至第m個(gè)元素的值 temp[i]=2*sum-temp[j]; f=temp[m]; } return OK; }//fib 分析: k階斐波那契序列的第m項(xiàng)的值f[m]=f[m-1]+f[m-2]+.....

3、.+f[m-k] =f[m-1]+f[m-2]+......+f[m-k]+f[m-k-1]-f[m-k-1] =2*f[m-1]-f[m-k-1] 所以上述算法的時(shí)間復(fù)雜度僅為O(m). 如果采用遞歸設(shè)計(jì),將達(dá)到O(k^m). 即使采用暫存中間結(jié)果的方法,也將達(dá)到O(m^2). 1.18 typedef struct{ char *sport; enum{male,female} gender; char schoolname; //校名為'A','B','C','D'或'E' char *result; int score; } resulttype; typ

4、edef struct{ int malescore; int femalescore; int totalscore; } scoretype; void summary(resulttype result[ ])//求各校的男女總分和團(tuán)體總分,假設(shè)結(jié)果已經(jīng)儲存在result[ ]數(shù)組中 { scoretype score[MAXSIZE]; i=0; while(result[i].sport!=NULL) { switch(result[i].schoolname) { case 'A': score[ 0 ].totalscore+=result[i].s

5、core; if(result[i].gender==0) score[ 0 ].malescore+=result[i].score; else score[ 0 ].femalescore+=result[i].score; break; case 'B': score[ 0 ].totalscore+=result[i].score; if(result[i].gender==0) score[ 0 ].malescore+=result[i].score; else score[ 0 ].femalescore+=result[i].score; break; ………

6、……… } i++； } for(i=0;i<5;i++) { printf("School %d:\n",i); printf("Total score of male:%d\n",score[i].malescore); printf("Total score of female:%d\n",score[i].femalescore); printf("Total score of all:%d\n\n",score[i].totalscore); } }//summary 1.19 Status algo119(int a[ARRSIZE])//求i!*2^

7、i序列的值且不超過maxint { last=1; for(i=1;i<=ARRSIZE;i++) { a[i-1]=last*2*i; if((a[i-1]/last)!=(2*i)) reurn OVERFLOW; last=a[i-1]; return OK; } }//algo119 分析:當(dāng)某一項(xiàng)的結(jié)果超過了maxint時(shí),它除以前面一項(xiàng)的商會發(fā)生異常. 1.20 void polyvalue() { float temp; float *p=a; printf("Input number of terms:"); scanf("%d",&n)

8、; printf("Input value of x:"); scanf("%f",&x); printf("Input the %d coefficients from a0 to a%d:\n",n+1,n); p=a;xp=1;sum=0; //xp用于存放x的i次方 for(i=0;i<=n;i++) { scanf("%f",&temp); sum+=xp*(temp); xp*=x; } printf("Value is:%f",sum); }//polyvalue 第二章 線性表 2.10 Status DeleteK(SqList &a,in

9、t i,int k)//刪除線性表a中第i個(gè)元素起的k個(gè)元素 { if(i<1||k<0||i+k-1>a.length) return INFEASIBLE; for(count=1;i+count-1<=a.length-k;count++) //注意循環(huán)結(jié)束的條件 a.elem[i+count-1]=a.elem[i+count+k-1]; a.length-=k; return OK; }//DeleteK 2.11 Status Insert_SqList(SqList &va,int x)//把x插入遞增有序表va中 { if(va.length+1>va.

10、listsize) return ERROR; va.length++; for(i=va.length-1;va.elem[i]>x&&i>=0;i--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; return OK; }//Insert_SqList 2.12 int ListComp(SqList A,SqList B)//比較字符表A和B,并用返回值表示結(jié)果,值為1,表示A>B;值為-1,表示A { for(i=1;i<=A.length&&i<=B.length;i++) if(A.elem[i]!=B.elem[i]

11、) return A.elem[i]>B.elem[i]?1:-1; if(A.length==B.length) return 0; return A.length>B.length?1:-1; //當(dāng)兩個(gè)字符表可以互相比較的部分完全相同時(shí),哪個(gè)較長,哪個(gè)就較大 }//ListComp 2.13 LNode* Locate(LinkList L,int x)//鏈表上的元素查找,返回指針 { for(p=l->next;p&&p->data!=x;p=p->next); return p; }//Locate 2.14 int Length(LinkList

12、L)//求鏈表的長度 { for(k=0,p=L;p->next;p=p->next,k++); return k; }//Length 2.15 void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把鏈表hb接在ha后面形成鏈表hc { hc=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é)點(diǎn)鏈表L的

13、第i個(gè)元素之前插入元素b { p=L;q=(LinkList*)malloc(sizeof(LNode)); q.data=b; if(i==1) { q.next=p;L=q; //插入在鏈表頭部 } else { while(--i>1) p=p->next; q->next=p->next;p->next=q; //插入在第i個(gè)元素的位置 } }//Insert 2.18 Status Delete(LinkList &L,int i)//在無頭結(jié)點(diǎn)鏈表L中刪除第i個(gè)元素 { if(i==1) L=L->next; //刪除第一個(gè)元素 else

14、{ p=L; while(--i>1) p=p->next; p->next=p->next->next; //刪除第i個(gè)元素 } }//Delete 2.19 Status Delete_Between(Linklist &L,int mink,int maxk)//刪除元素遞增排列的鏈表L中值大于mink且小于maxk的所有元素 { p=L; while(p->next->data<=mink) p=p->next; //p是最后一個(gè)不大于mink的元素 if(p->next) //如果還有比mink更大的元素 { q=p->next; while(q->d

15、atanext; //q是第一個(gè)不小于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; //當(dāng)相鄰兩元素不相等時(shí),p,q都向后推一步 } else { while(q->data==p->data) { free(

16、q); q=q->next; } p->next=q;p=q;q=p->next; //當(dāng)相鄰元素相等時(shí)刪除多余元素 }//else }//while }//Delete_Equal 2.21 void reverse(SqList &A)//順序表的就地逆置 { for(i=1,j=A.length;iA.elem[j]; }//reverse 2.22 void LinkList_reverse(Linklist &L)//鏈表的就地逆置;為簡化算法,假設(shè)表長大于2 { p=L->next;q=p->

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

18、>next;C=A; while(p&&q) { s=p->next;p->next=q; //將B的元素插入 if(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的當(dāng)前元素 whi

19、le(pa||pb) { if(pa->datadata||!pb) { pc=pa;q=pa->next;pa->next=pre;pa=q; //將A的元素插入新表 } else { pc=pb;q=pb->next;pb->next=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

20、A,SqList B,SqList &C)//求元素遞增排列的線性表A和B的元素的交集并存入C中 { i=1;j=1;k=0; while(A.elem[i]&&B.elem[j]) { if(A.elem[i] if(A.elem[i]>B.elem[j]) j++; if(A.elem[i]==B.elem[j]) { C.elem[++k]=A.elem[i]; //當(dāng)發(fā)現(xiàn)了一個(gè)在A,B中都存在的元素, i++;j++; //就添加到C中 } }//while }//SqList_Intersect 2.26 void LinkList_Intersec

21、t(LinkList A,LinkList B,LinkList &C)//在鏈表結(jié)構(gòu)上重做上題 { p=A->next;q=B->next; pc=(LNode*)malloc(sizeof(LNode)); C=pc; while(p&&q) { if(p->datadata) p=p->next; else if(p->data>q->data) q=q->next; else { s=(LNode*)malloc(sizeof(LNode)); s->data=p->data; pc->next=s;pc=s; p=p->next;q=q->next;

22、} }//while }//LinkList_Intersect 2.27 void SqList_Intersect_True(SqList &A,SqList B)//求元素遞增排列的線性表A和B的元素的交集并存回A中 { i=1;j=1;k=0; while(A.elem[i]&&B.elem[j]) { if(A.elem[i] else if(A.elem[i]>B.elem[j]) j++; else if(A.elem[i]!=A.elem[k]) { A.elem[++k]=A.elem[i]; //當(dāng)發(fā)現(xiàn)了一個(gè)在A,B中都存在的元素 i++;j

23、++; //且C中沒有,就添加到C中 } else {i++;j++;} }//while while(A.elem[k]) A.elem[k++]=0; }//SqList_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->data>q->data) q=q->next; else i

24、f(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_Delete(SqList &A,SqList B,SqList C) { i=0;j=0;k=0;m=0; //i指示A中元素原來的位置,m為移動(dòng)后的位置 while(i

25、j]>C.elem[k]) k++; else { same=B.elem[j]; //找到了相同元素same while(B.elem[j]==same) j++; while(C.elem[k]==same) k++; //j,k后移到新的元素 while(i

26、的剩余元素重新存儲。 A.length=m; }// SqList_Intersect_Delete 分析:先從B和C中找出共有元素,記為same,再在A中從當(dāng)前位置開始, 凡小于same的 元素均保留(存到新的位置),等于same的就跳過,到大于same時(shí)就再找下一個(gè)same. 2.30 void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)//在鏈表結(jié)構(gòu)上重做上題 { p=B->next;q=C->next;r=A-next; while(p&&q&&r) { if(p->datadat

27、a) p=p->next; else if(p->data>q->data) q=q->next; else { u=p->data; //確定待刪除元素u while(r->next->datanext; //確定最后一個(gè)小于u的元素指針r if(r->next->data==u) { s=r->next; while(s->data==u) { t=s;s=s->next;free(t); //確定第一個(gè)大于u的元素指針s }//while r->next=s; //刪除r和s之間的元素 }//if while(p->data=u) p=p->next; w

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

29、L;!p->next->pre;p=p->next) p->next->pre=p; return OK; }//DuLNode_Pre 2.33 Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把單鏈表L的元素按類型分為三個(gè)循環(huán)鏈表.CiList為帶頭結(jié)點(diǎn)的單循環(huán)鏈表類型. { s=L->next; A=(CiList*)malloc(sizeof(CiLNode));p=A; B=(CiList*)malloc(sizeof(CiLNode));q=B; C=(CiList*)mal

30、loc(sizeof(CiLNode));r=C; //建立頭結(jié)點(diǎn) while(s) { if(isalphabet(s->data)) { p->next=s;p=s; } else if(isdigit(s->data)) { q->next=s;q=s; } else { r->next=s;r=s; } }//while p->next=A;q->next=B;r->next=C; //完成循環(huán)鏈表 }//LinkList_Divide 2.34 void Print_XorLinkedList(XorLinkedList L)//從左向右輸出

31、異或鏈表的元素值 { p=L.left;pre=NULL; while(p) { printf("%d",p->data); q=XorP(p->LRPtr,pre); pre=p;p=q; //任何一個(gè)結(jié)點(diǎn)的LRPtr域值與其左結(jié)點(diǎn)指針進(jìn)行異或運(yùn)算即得到其右結(jié)點(diǎn)指針 } }//Print_XorLinkedList 2.35 Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)//在異或鏈表L的第i個(gè)元素前插入元素x { p=L.left;pre=NULL; r=(XorNode*)malloc(s

32、izeof(XorNode)); r->data=x; if(i==1) //當(dāng)插入點(diǎn)在最左邊的情況 { p->LRPtr=XorP(p.LRPtr,r); r->LRPtr=p; L.left=r; return OK; } j=1;q=p->LRPtr; //當(dāng)插入點(diǎn)在中間的情況 while(++jLRPtr,pre); pre=p;p=q; }//while //在p,q兩結(jié)點(diǎn)之間插入 if(!q) return INFEASIBLE; //i不可以超過表長 p->LRPtr=XorP(XorP(p->LRPtr,q)

33、,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個(gè)元素 { p=L.left;pre=NULL; if(i==1) //刪除最左結(jié)點(diǎn)的情況 { q=p->LRPtr; q->LRPtr=XorP(q->LRPtr,p); L.left=q;free(p); return OK

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

35、RPtr,q),r); r->LRPtr=XorP(XorP(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é)點(diǎn) { p=L.next; while(p->next!=L&&p->next->next!=L) { p->next=p->next->next; p=p->next; } //此時(shí)p指向最后一個(gè)奇數(shù)結(jié)點(diǎn) if(p->next==L)

36、p->next=L->pre->pre; else 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; //按題目要求調(diào)整了next鏈的結(jié)構(gòu),此時(shí)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)整只能分開進(jìn)行.如同時(shí)進(jìn)行調(diào)整的話

37、,必須使用堆棧保存偶數(shù)結(jié)點(diǎn)的指針,否則將會破壞鏈表結(jié)構(gòu),造成結(jié)點(diǎn)丟失. 2.38 DuLNode * Locate_DuList(DuLinkedList &L,int x)//帶freq域的雙向循環(huán)鏈表上的查找 { p=L.next; while(p.data!=x&&p!=L) p=p->next; if(p==L) return NULL; //沒找到 p->freq++;q=p->pre; while(q->freq<=p->freq&&p!=L) q=q->pre; //查找插入位置 if(q!=p->pre) { p->pre->next=p->next;

38、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)//求升冪順序存儲的稀疏多項(xiàng)式的值 { PolyTerm *q; xp=1;q=P.data; sum=0;ex=0; while(q->coef) { while(exexp) xp*=x0; sum+=q->coef*xp; q++; } return

39、 sum; }//GetValue_SqPoly 2.40 void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)//求稀疏多項(xiàng)式P1減P2的差式P3 { PolyTerm *p,*q,*r; Create_SqPoly(P3); //建立空多項(xiàng)式P3 p=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++;r++; } else if(p->exp

40、exp) { r->coef=-q->coef; r->exp=q->exp; q++;r++; } else { if((p->coef-q->coef)!=0) //只有同次項(xiàng)相減不為零時(shí)才需要存入P3中 { r->coef=p->coef-q->coef; r->exp=p->exp;r++; }//if p++;q++; }//else }//while while(p->coef) //處理P1或P2的剩余項(xiàng) { r->coef=p->coef; r->exp=p->exp; p++;r++; } while(q->coef) { r-

41、>coef=-q->coef; r->exp=q->exp; q++;r++; } }//Subtract_SqPoly 2.41 void QiuDao_LinkedPoly(LinkedPoly &L)//對有頭結(jié)點(diǎn)循環(huán)鏈表結(jié)構(gòu)存儲的稀疏多項(xiàng)式L求導(dǎo) { p=L->next; if(!p->data.exp) { L->next=p->next;p=p->next; //跳過常數(shù)項(xiàng) } while(p!=L) { p->data.coef*=p->data.exp--;//對每一項(xiàng)求導(dǎo) p=p->next; } }//QiuDao_LinkedPol

42、y 2.42 void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循環(huán)鏈表存儲的稀疏多項(xiàng)式L拆成只含奇次項(xiàng)的A和只含偶次項(xiàng)的B { p=L->next; A=(PolyNode*)malloc(sizeof(PolyNode)); B=(PolyNode*)malloc(sizeof(PolyNode)); pa=A;pb=B; while(p!=L) { if(p->data.exp!=2*(p->data.exp/2)) { pa->next=p;pa=p; } else { pb->next=p;pb=p; }

43、 p=p->next; }//while pa->next=A;pb->next=B; }//Divide_LinkedPoly 第三章 棧與隊(duì)列 3.15 typedef struct{ Elemtype *base[2]; Elemtype *top[2]; }BDStacktype; //雙向棧類型 Status Init_Stack(BDStacktype &tws,int m)//初始化一個(gè)大小為m的雙向棧tws { tws.base[0]=(Elemtype*)malloc(sizeof(Elemtype)); tws.base[1]=tws.b

44、ase[0]+m; tws.top[0]=tws.base[0]; tws.top[1]=tws.base[1]; return OK; }//Init_Stack Status push(BDStacktype &tws,int i,Elemtype x)//x入棧,i=0表示低端棧,i=1表示高端棧 { if(tws.top[0]>tws.top[1]) return OVERFLOW; //注意此時(shí)的棧滿條件 if(i==0) *tws.top[0]++=x; else if(i==1) *tws.top[1]--=x; else return ERROR; re

45、turn OK; }//push Status pop(BDStacktype &tws,int i,Elemtype &x)//x出棧,i=0表示低端棧,i=1表示高端棧 { if(i==0) { if(tws.top[0]==tws.base[0]) return OVERFLOW; x=*--tws.top[0]; } else if(i==1) { if(tws.top[1]==tws.base[1]) return OVERFLOW; x=*++tws.top[1]; } else return ERROR; return OK; }//pop

46、3.16 void Train_arrange(char *train)//這里用字符串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()/

47、/判斷輸入的字符串中'&'前和'&'后部分是否為逆串,是則返回1,否則返回0 { InitStack(s); while((e=getchar())!='&') { if(e==’@’) return 0;//不允許在’&’之前出現(xiàn)’@’ push(s,e); } while( (e=getchar())!='@') { if(StackEmpty(s)) return 0; pop(s,c); if(e!=c) return 0; } if(!StackEmpty(s)) return 0; return 1; }//IsReverse 3.18 S

48、tatus Bracket_Test(char *str)//判別表達(dá)式中小括號是否匹配 { count=0; for(p=str;*p;p++) { if(*p=='(') count++; else if(*p==')') count--; if (count<0) return ERROR; } if(count) return ERROR; //注意括號不匹配的兩種情況 return OK; }//Bracket_Test 3.19 Status AllBrackets_Test(char *str)//判別表達(dá)式中三種括號是否匹配 { InitSta

49、ck(s); for(p=str;*p;p++) { if(*p=='('||*p=='['||*p=='{') push(s,*p); else if(*p==')'||*p==']'||*p=='}') { if(StackEmpty(s)) return ERROR; pop(s,c); if(*p==')'&&c!='(') return ERROR; if(*p==']'&&c!='[') return ERROR; if(*p=='}'&&c!='{') return ERROR; //必須與當(dāng)前棧頂括號匹配 } }//for if(!StackEmpty

50、(s)) return ERROR; return OK; }//AllBrackets_Test 3.20 typedef struct { . int x; int y; } coordinate; void Repaint_Color(int g[m][n],int i,int j,int color)//把點(diǎn)(i,j)相鄰區(qū)域的顏色置換為color { old=g[i][j]; InitQueue(Q); EnQueue(Q,{I,j}); while(!QueueEmpty(Q)) { DeQueue(Q,a); x=a.x;y=a.y;

51、 if(x>1) if(g[x-1][y]==old) { g[x-1][y]=color; EnQueue(Q,{x-1,y}); //修改左鄰點(diǎn)的顏色 } if(y>1) if(g[x][y-1]==old) { g[x][y-1]=color; EnQueue(Q,{x,y-1}); //修改上鄰點(diǎn)的顏色 } if(x

52、lor; EnQueue(Q,{x,y+1}); //修改下鄰點(diǎn)的顏色 } }//while }//Repaint_Color 分析:本算法采用了類似于圖的廣度優(yōu)先遍歷的思想,用兩個(gè)隊(duì)列保存相鄰?fù)c(diǎn)的橫坐標(biāo)和縱坐標(biāo).遞歸形式的算法該怎么寫呢? 3.21 void NiBoLan(char *str,char *new)//把中綴表達(dá)式str轉(zhuǎn)換成逆波蘭式new { p=str;q=new; //為方便起見,設(shè)str的兩端都加上了優(yōu)先級最低的特殊符號 InitStack(s); //s為運(yùn)算符棧 while(*p) { if(*p是字母)) *q++=*p; //

53、直接輸出 else { c=gettop(s); if(*p優(yōu)先級比c高) push(s,*p); else { while(gettop(s)優(yōu)先級不比*p低) { pop(s,c);*(q++)=c; }//while push(s,*p); //運(yùn)算符在棧內(nèi)遵循越往棧頂優(yōu)先級越高的原則 }//else }//else p++; }//while }//NiBoLan //參見編譯原理教材 3.22 int GetValue_NiBoLan(char *str)//對逆波蘭式求值 { p=str;InitStack(s); //s為操作數(shù)棧 w

54、hile(*p) { if(*p是數(shù)) push(s,*p); else { pop(s,a);pop(s,b); r=compute(b,*p,a); //假設(shè)compute為執(zhí)行雙目運(yùn)算的過程 push(s,r); }//else p++; }//while pop(s,r);return r; }//GetValue_NiBoLan 3.23 Status NiBoLan_to_BoLan(char *str,stringtype &new)//把逆波蘭表達(dá)式str轉(zhuǎn)換為波蘭式new { p=str;Initstack(s); //s的元素為strin

55、gtype類型 while(*p) { if(*p為字母) push(s,*p); else { if(StackEmpty(s)) return ERROR; pop(s,a); if(StackEmpty(s)) return ERROR; pop(s,b); c=link(link(*p,b),a); push(s,c); }//else p++; }//while pop(s,new); if(!StackEmpty(s)) return ERROR; return OK; }//NiBoLan_to_BoLan 分析:基本思想見書后注釋.本題中暫

56、不考慮串的具體操作的實(shí)現(xiàn),而將其看作一種抽象數(shù)據(jù)類型stringtype,對其可以進(jìn)行連接操作:c=link(a,b). 3.24 Status g(int m,int n,int &s)//求遞歸函數(shù)g的值s { if(m==0&&n>=0) s=0; else if(m>0&&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(n<0) return ERROR; if(n==0) s=n+1;

57、else { F_recurve(n/2,r); s=n*r; } return OK; }//F_recursive Status F_nonrecursive(int n,int s)//非遞歸算法 { if(n<0) return ERROR; if(n==0) s=n+1; else { InitStack(s); //s的元素類型為struct {int a;int b;} while(n!=0) { a=n;b=n/2; push(s,{a,b}); n=b; }//while s=1; while(!StackEmpty(s)) {

58、 pop(s,t); s*=t.a; }//while } return OK; }//F_nonrecursive 3.26 float Sqrt_recursive(float A,float p,float e)//求平方根的遞歸算法 { if(abs(p^2-A)<=e) return p; else return sqrt_recurve(A,(p+A/p)/2,e); }//Sqrt_recurve float Sqrt_nonrecursive(float A,float p,float e)//求平方根的非遞歸算法 { while(abs(p^

59、2-A)>=e) p=(p+A/p)/2; return p; }//Sqrt_nonrecursive 3.27 這一題的所有算法以及棧的變化過程請參見《數(shù)據(jù)結(jié)構(gòu)(pascal版)》,作者不再詳細(xì)寫出. 3.28 void InitCiQueue(CiQueue &Q)//初始化循環(huán)鏈表表示的隊(duì)列Q { Q=(CiLNode*)malloc(sizeof(CiLNode)); Q->next=Q; }//InitCiQueue void EnCiQueue(CiQueue &Q,int x)//把元素x插入循環(huán)鏈表表示的隊(duì)列Q,Q指向隊(duì)尾元素,Q->next

60、指向頭結(jié)點(diǎn),Q->next->next指向隊(duì)頭元素 { p=(CiLNode*)malloc(sizeof(CiLNode)); p->data=x; p->next=Q->next; //直接把p加在Q的后面 Q->next=p; Q=p; //修改尾指針 } Status DeCiQueue(CiQueue &Q,int x)//從循環(huán)鏈表表示的隊(duì)列Q頭部刪除元素x { if(Q==Q->next) return INFEASIBLE; //隊(duì)列已空 p=Q->next->next; x=p->data; Q->next->next=p->next; free

61、(p); return OK; }//DeCiQueue 3.29 Status EnCyQueue(CyQueue &Q,int x)//帶tag域的循環(huán)隊(duì)列入隊(duì)算法 { if(Q.front==Q.rear&&Q.tag==1) //tag域的值為0表示"空",1表示"滿" return OVERFLOW; Q.base[Q.rear]=x; Q.rear=(Q.rear+1)%MAXSIZE; if(Q.front==Q.rear) Q.tag=1; //隊(duì)列滿 }//EnCyQueue Status DeCyQueue(CyQueue &Q,int &x)

62、//帶tag域的循環(huán)隊(duì)列出隊(duì)算法 { if(Q.front==Q.rear&&Q.tag==0) return INFEASIBLE; Q.front=(Q.front+1)%MAXSIZE; x=Q.base[Q.front]; if(Q.front==Q.rear) Q.tag=1; //隊(duì)列空 return OK; }//DeCyQueue 分析:當(dāng)循環(huán)隊(duì)列容量較小而隊(duì)列中每個(gè)元素占的空間較多時(shí),此種表示方法可以節(jié)約較多的存儲空間,較有價(jià)值. 3.30 Status EnCyQueue(CyQueue &Q,int x)//帶length域的循環(huán)隊(duì)列入隊(duì)算法 {

63、 if(Q.length==MAXSIZE) return OVERFLOW; Q.rear=(Q.rear+1)%MAXSIZE; Q.base[Q.rear]=x; Q.length++; return OK; }//EnCyQueue Status DeCyQueue(CyQueue &Q,int &x)//帶length域的循環(huán)隊(duì)列出隊(duì)算法 { if(Q.length==0) return INFEASIBLE; head=(Q.rear-Q.length+1)%MAXSIZE; //詳見書后注釋 x=Q.base[head]; Q.length--; }/

64、/DeCyQueue 3.31 int Palindrome_Test()//判別輸入的字符串是否回文序列,是則返回1,否則返回0 { InitStack(S);InitQueue(Q); while((c=getchar())!='@') { Push(S,c);EnQueue(Q,c); //同時(shí)使用棧和隊(duì)列兩種結(jié)構(gòu) } while(!StackEmpty(S)) { Pop(S,a);DeQueue(Q,b)); if(a!=b) return ERROR; } return OK; }//Palindrome_Test 3.32 void Ge

65、tFib_CyQueue(int k,int n)//求k階斐波那契序列的前n+1項(xiàng) { InitCyQueue(Q); //其MAXSIZE設(shè)置為k for(i=0;iQ.base[k-1]=1; //給前k項(xiàng)賦初值 for(i=0;i for(i=k;i<=n;i++) { m=i%k;sum=0; for(j=0;jQ.base[m]=sum; //求第i項(xiàng)的值存入隊(duì)列中并取代已無用的第一項(xiàng) printf("%d",sum); } }//GetFib_CyQueue 3.33 Status EnDQueue(DQueue &Q,int x)//輸出受限的雙端

66、隊(duì)列的入隊(duì)操作 { if((Q.rear+1)%MAXSIZE==Q.front) return OVERFLOW; //隊(duì)列滿 avr=(Q.base[Q.rear-1]+Q.base[Q.front])/2; if(x>=avr) //根據(jù)x的值決定插入在隊(duì)頭還是隊(duì)尾 { Q.base[Q.rear]=x; Q.rear=(Q.rear+1)%MAXSIZE; } //插入在隊(duì)尾 else { Q.front=(Q.front-1)%MAXSIZE; Q.base[Q.front]=x; } //插入在隊(duì)頭 return OK; }//EnDQueue Status DeDQueue(DQueue &Q,int &x)//輸出受限的雙端隊(duì)列的出隊(duì)操作 { if(Q.front==Q.rear) return INFEASIBLE; //隊(duì)列空 x=Q.base[Q.front]; Q.front=(Q.front+1)%MAXSIZE; return OK; }//DeDQueue 3.34 void Train_Rearran