數據結構習題答案(全部算法)-嚴蔚敏版 第一章緒論1.16 void print_descending(int x,int y,int z)/按從大到小順序輸出三個數scanf("%d,%d,%d",&x,&y,&z);if(x<->y; /<->為表示交換的雙目運算符,以下同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項的值fint tempd;if(k<2|m<0) return ERROR; if(melse if (m=k-1 | m=k) f=1;elsefor(i=0;i<=k-2;i+) tempi=0;tempk-1=1;tempk=1; /初始化sum=1;j=0;for(i=k+1;i<=m;i+,j+) /求出序列第k至第m個元素的值tempi=2*sum-tempj;f=tempm;return OK;/fib分析: k階斐波那契序列的第m項的值fm=fm-1+fm-2+.+fm-k=fm-1+fm-2+.+fm-k+fm-k-1-fm-k-1=2*fm-1-fm-k-1所以上述算法的時間復雜度僅為O(m). 如果采用遞歸設計,將達到O(km). 即使采用暫存中間結果的方法,也將達到O(m2). 1.18 typedef structchar *sport;enummale,female gender;char schoolname; /校名為'A','B','C','D'或'E'char *result;int score; resulttype; typedef structint malescore;int femalescore;int totalscore; scoretype; void summary(resulttype result )/求各校的男女總分和團體總分,假設結果已經儲存在result 數組中scoretype scoreMAXSIZE;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 0 .totalscore+=resulti.score;if(resulti.gender=0) score 0 .malescore+=resulti.score;else score 0 .femalescore+=resulti.score;break;i+；for(i=0;i<5;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 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分析:當某一項的結果超過了maxint時,它除以前面一項的商會發(fā)生異常. 1.20 void polyvalue()float temp;float *p=a;printf("Input number of terms:");scanf("%d",&n);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,int i,int k)/刪除線性表a中第i個元素起的k個元素if(i<1|k<0|i+k-1>a.length) return INFEASIBLE;for(count=1;i+count-1<=a.length-k;count+) /注意循環(huán)結束的條件a.elemi+count-1=a.elemi+count+k-1;a.length-=k;return OK;/DeleteK 2.11Status Insert_SqList(SqList &va,int x)/把x插入遞增有序表va中if(va.length+1>va.listsize) return ERROR;va.length+;for(i=va.length-1;va.elemi>x&&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,并用返回值表示結果,值為1,表示A>B;值為-1,表示Afor(i=1;i<=A.length&&i<=B.length;i+)if(A.elemi!=B.elemi)return A.elemi>B.elemi?1:-1;if(A.length=B.length) return 0;return A.length>B.length?1:-1; /當兩個字符表可以互相比較的部分完全相同時,哪個較長,哪個就較大/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 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后面形成鏈表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)/在無頭結點鏈表L的第i個元素之前插入元素bp=L;q=(LinkList*)malloc(sizeof(LNode);q.data=b;if(i=1)q.next=p;L=q; /插入在鏈表頭部elsewhile(-i>1) p=p->next;q->next=p->next;p->next=q; /插入在第i個元素的位置/Insert 2.18 Status Delete(LinkList &L,int i)/在無頭結點鏈表L中刪除第i個元素if(i=1) L=L->next; /刪除第一個元素elsep=L;while(-i>1) p=p->next;p->next=p->next->next; /刪除第i個元素/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是最后一個不大于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; /當相鄰兩元素不相等時,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;i<J;I+,J-)A.elemi<->A.elemj;/reverse 2.22 void LinkList_reverse(Linklist &L)/鏈表的就地逆置;為簡化算法,假設表長大于2p=L->next;q=p->next;s=q->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(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=pre;pb=q; /將B的元素插入新表pre=pc;C=A;A->next=pc; /構造新表頭/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.elemiif(A.elemi>B.elemj) j+;if(A.elemi=B.elemj)C.elem+k=A.elemi; /當發(fā)現(xiàn)了一個在A,B中都存在的元素,i+;j+; /就添加到C中/while/SqList_Intersect 2.26 void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)/在鏈表結構上重做上題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;elses=(LNode*)malloc(sizeof(LNode);s->data=p->data;pc->next=s;pc=s;p=p->next;q=q->next;/while/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.elemielse if(A.elemi>B.elemj) j+;else if(A.elemi!=A.elemk)A.elem+k=A.elemi; /當發(fā)現(xiàn)了一個在A,B中都存在的元素i+;j+; /且C中沒有,就添加到C中else i+;j+;/whilewhile(A.elemk) A.elemk+=0;/SqList_Intersect_True 2.28 void LinkList_Intersect_True(LinkList &A,LinkList B)/在鏈表結構上重做上題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 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_Delete(SqList &A,SqList B,SqList C) i=0;j=0;k=0;m=0; /i指示A中元素原來的位置,m為移動后的位置while(i<A.LENGTH&&J<B.LENGTH&& kif(B.elemjelse if(B.elemj>C.elemk) k+;elsesame=B.elemj; /找到了相同元素samewhile(B.elemj=same) j+;while(C.elemk=same) k+; /j,k后移到新的元素while(i<A.LENGTH&&A.ELEMIA.elemm+=A.elemi+; /需保留的元素移動到新位置while(i<A.LENGTH&&A.ELEMI=SAME) i+; 跳過相同的元素/whilewhile(iA.elemm+=A.elemi+; /A的剩余元素重新存儲。A.length=m; / SqList_Intersect_Delete分析:先從B和C中找出共有元素,記為same,再在A中從當前位置開始, 凡小于same的元素均保留(存到新的位置),等于same的就跳過,到大于same時就再找下一個same. 2.30 void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)/在鏈表結構上重做上題p=B->next;q=C->next;r=A-next;while(p&&q&&r)if(p->datadata) p=p->next;else if(p->data>q->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之間的元素/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)鏈表中結點s的直接前驅p=s;while(p->next->next!=s) p=p->next; /找到s的前驅的前驅pp->next=s;return OK;/Delete_Pre 2.32 Status DuLNode_Pre(DuLinkList &L)/完成雙向循環(huán)鏈表結點的pre域for(p=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的元素按類型分為三個循環(huán)鏈表.CiList為帶頭結點的單循環(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; /建立頭結點while(s)if(isalphabet(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; /任何一個結點的LRPtr域值與其左結點指針進行異或運算即得到其右結點指針/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(+j<I&&Q)q=XorP(p->LRPtr,pre);pre=p;p=q;/while /在p,q兩結點之間插入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) /刪除最左結點的情況q=p->LRPtr;q->LRPtr=XorP(q->LRPtr,p);L.left=q;free(p);return OK;j=1;q=p->LRPtr;while(+j<I&&Q)q=XorP(p->LRPtr,pre);pre=p;p=q;/while /找到待刪結點qif(!q) return INFEASIBLE; /i不可以超過表長if(L.right=q) /q為最右結點的情況p->LRPtr=XorP(p->LRPtr,q);L.right=p;free(q);return OK;r=XorP(q->LRPtr,p); /q為中間結點的情況,此時p,r分別為其左右結點p->LRPtr=XorP(XorP(p->LRPtr,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中的所有結點p=L.next;while(p->next!=L&&p->next->next!=L)p->next=p->next->next;p=p->next; /此時p指向最后一個奇數結點if(p->next=L) p->next=L->pre->pre;else p->next=l->pre;p=p->next; /此時p指向最后一個偶數結點while(p->pre->pre!=L)p->next=p->pre->pre;p=p->next;p->next=L; /按題目要求調整了next鏈的結構,此時pre鏈仍為原狀for(p=L;p->next!=L;p=p->next) p->next->pre=p;L->pre=p; /調整pre鏈的結構,同2.32方法/OEReform分析:next鏈和pre鏈的調整只能分開進行.如同時進行調整的話,必須使用堆棧保存偶數結點的指針,否則將會破壞鏈表結構,造成結點丟失. 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;p->next->pre=p->pre;q->next->pre=p;p->next=q->next;q->next=p;p->pre=q; /調整位置return p;/Locate_DuList 2.39 float GetValue_SqPoly(SqPoly P,int x0)/求升冪順序存儲的稀疏多項式的值PolyTerm *q;xp=1;q=P.data;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+;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_LinkedPoly(LinkedPoly &L)/對有頭結點循環(huán)鏈表結構存儲的稀疏多項式L求導p=L->next;if(!p->data.exp)L->next=p->next;p=p->next; /跳過常數項while(p!=L)p->data.coef*=p->data.exp-;/對每一項求導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=(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;elsepb->next=p;pb=p;p=p->next;/whilepa->next=A;pb->next=B; /Divide_LinkedPoly第三章 棧與隊列 3.15 typedef structElemtype *base2;Elemtype *top2;BDStacktype; /雙向棧類型 Status Init_Stack(BDStacktype &tws,int m)/初始化一個大小為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.top0>tws.top1) return OVERFLOW; /注意此時的棧滿條件if(i=0) *tws.top0+=x;else if(i=1) *tws.top1-=x;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)/這里用字符串train表示火車,'H'表示硬席,'S'表示軟席p=train;q=train;InitStack(s);while(*p)if(*p='H') push(s,*p); /把'H'存入棧中else *(q+)=*p; /把'S'調到前部p+;while(!StackEmpty(s)pop(s,c);*(q+)=c; /把'H'接在后部/Train_arrange 3.17 int IsReverse()/判斷輸入的字符串中'&'前和'&'后部分是否為逆串,是則返回1,否則返回0InitStack(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 Status Bracket_Test(char *str)/判別表達式中小括號是否匹配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)/判別表達式中三種括號是否匹配InitStack(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; /必須與當前棧頂括號匹配/forif(!StackEmpty(s) return ERROR;return OK;/AllBrackets_Test 3.20 typedef struct . int x; int y; coordinate;void Repaint_Color(int gmn,int i,int j,int color)/把點(i,j)相鄰區(qū)域的顏色置換為colorold=gij;InitQueue(Q);EnQueue(Q,I,j);while(!QueueEmpty(Q)DeQueue(Q,a);x=a.x;y=a.y;if(x>1)if(gx-1y=old)gx-1y=color;EnQueue(Q,x-1,y); /修改左鄰點的顏色if(y>1)if(gxy-1=old)gxy-1=color;EnQueue(Q,x,y-1); /修改上鄰點的顏色if(x<M)if(gx+1y=old)gx+1y=color;EnQueue(Q,x+1,y); /修改右鄰點的顏色if(y<N)if(gxy+1=old)gxy+1=color;EnQueue(Q,x,y+1); /修改下鄰點的顏色/while/Repaint_Color分析:本算法采用了類似于圖的廣度優(yōu)先遍歷的思想,用兩個隊列保存相鄰同色點的橫坐標和縱坐標.遞歸形式的算法該怎么寫呢? 3.21 void NiBoLan(char *str,char *new)/把中綴表達式str轉換成逆波蘭式newp=str;q=new; /為方便起見,設str的兩端都加上了優(yōu)先級最低的特殊符號InitStack(s); /s為運算符棧while(*p)if(*p是字母) *q+=*p; /直接輸出elsec=gettop(s);if(*p優(yōu)先級比c高) push(s,*p);elsewhile(gettop(s)優(yōu)先級不比*p低)pop(s,c);*(q+)=c;/whilepush(s,*p); /運算符在棧內遵循越往棧頂優(yōu)先級越高的原則/else/elsep+;/while/NiBoLan /參見編譯原理教材 3.22 int GetValue_NiBoLan(char *str)/對逆波蘭式求值p=str;InitStack(s); /s為操作數棧while(*p)if(*p是數) push(s,*p);elsepop(s,a);pop(s,b);r=compute(b,*p,a); /假設compute為執(zhí)行雙目運算的過程push(s,r);/elsep+;/whilepop(s,r);return r;/GetValue_NiBoLan 3.23 Status NiBoLan_to_BoLan(char *str,stringtype &new)/把逆波蘭表達式str轉換為波蘭式newp=str;Initstack(s); /s的元素為stringtype類型while(*p)if(*p為字母) push(s,*p);elseif(StackEmpty(s) return ERROR;pop(s,a);if(StackEmpty(s) return ERROR;pop(s,b);c=link(link(*p,b),a);push(s,c);/elsep+;/whilepop(s,new);if(!StackEmpty(s) return ERROR;return OK;/NiBoLan_to_BoLan分析:基本思想見書后注釋.本題中暫不考慮串的具體操作的實現(xiàn),而將其看作一種抽象數據類型stringtype,對其可以進行連接操作:c=link(a,b). 3.24 Status g(int m,int n,int &s)/求遞歸函數g的值sif(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;elseF_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;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_recursive(float A,float p,float e)/求平方根的遞歸算法if(abs(p2-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(p2-A)>=e)p=(p+A/p)/2;return p;/Sqrt_nonrecursive 3.27 這一題的所有算法以及棧的變化過程請參見數據結構(pascal版),作者不再詳細寫出. 3.28 void InitCiQueue(CiQueue &Q)/初始化循環(huán)鏈表表示的隊列QQ=(CiLNode*)malloc(sizeof(CiLNode);Q->next=Q;/InitCiQueue void EnCiQueue(CiQueue &Q,int x)/把元素x插入循環(huán)鏈表表示的隊列Q,Q指向隊尾元素,Q->next指向頭結點,Q->next->next指向隊頭元素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)鏈表表示的隊列Q頭部刪除元素xif(Q=Q->next) return INFEASIBLE; /隊列已空p=Q->next->next;x=p->data;Q->next->next=p->next;free(p);return OK;/DeCiQueue 3.29 Status EnCyQueue(CyQueue &Q,int x)/帶tag域的循環(huán)隊列入隊算法if(Q.front=Q.rear&&Q.tag=1) /tag域的值為0表示"空",1表示"滿"return OVERFLOW;Q.baseQ.rear=x;Q.rear=(Q.rear+1)%MAXSIZE;if(Q.front=Q.rear) Q.tag=1; /隊列滿/EnCyQueue Status DeCyQueue(CyQueue &Q,int &x)/帶tag域的循環(huán)隊列出隊算法if(Q.front=Q.rear&&Q.tag=0) return INFEASIBLE;Q.front=(Q.front+1)%MAXSIZE;x=Q.baseQ.front;if(Q.front=Q.rear) Q.tag=1; /隊列空return OK;/DeCyQueue分析:當循環(huán)隊列容量較小而隊列中每個元素占的空間較多時,此種表示方法可以節(jié)約較多的存儲空間,較有價值. 3.30 Status EnCyQueue(CyQueue &Q,int x)/帶length域的循環(huán)隊列入隊算法if(Q.length=MAXSIZE) return OVERFLOW;Q.rear=(Q.rear+1)%MAXSIZE;Q.baseQ.rear=x;Q.length+;return OK;/EnCyQueue Status DeCyQueue(CyQueue &Q,int &x)/帶length域的循環(huán)隊列出隊算法if(Q.length=0) return INFEASIBLE;head=(Q.rear-Q.length+1)%MAXSIZE; /詳見書后注釋x=Q.basehead;Q.length-;/DeCyQueue 3.31 int Palindrome_Test()/判別輸入的字符串是否回文序列,是則返回1,否則返回0InitStack(S);InitQueue(Q);while(c=getchar()!='')Push(S,c);EnQueue(Q,c); /同時使用棧和隊列兩種結構while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b) return ERROR;return OK;/Palindrome_Test 3.32 void GetFib_CyQueue(int k,int n)/求k階斐波那契序列的前n+1項InitCyQueue(Q); /其MAXSIZE設置為kfor(i=0;iQ.basek-1=1; /給前k項賦初值for(i=0;ifor(i=k;i<=n;i+)m=i%k;sum=0;for(j=0;jQ.basem=sum; /求第i項的值存入隊列中并取代已無用的第一項printf("%d",sum);/GetFib_CyQueue 3.33 Status EnDQueue(DQueue &Q,int x)/輸出受限的雙端隊列的入隊操作if(Q.rear+1)%MAXSIZE=Q.front) return OVERFLOW; /隊列滿avr=(Q.baseQ.rear-1+Q.baseQ.front)/2;if(x>=avr) /根據x的值決定插入在隊頭還是隊尾Q.baseQ.rear=x;Q.rear=(Q.rear+1)%MAXSIZE; /插入在隊尾elseQ.front=(Q.front-1)%MAXSIZE;Q.baseQ.front=x; /插入在隊頭return OK;/EnDQueue Status DeDQueue(DQueue &Q,int &x)/輸出受限的雙端隊列的出隊操作if(Q.front=Q.rear) return INFEASIBLE; /隊列空x=Q.baseQ.front;Q.front=(Q.front+1)%MAXSIZE;return OK;/DeDQueue 3.34 void Train_Rearran