《數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)習(xí)題集》

說(shuō)明:.本文是對(duì)嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）習(xí)題集》ー書(shū)中所有算法設(shè)計(jì)題目的解決方案,主要作者為一具.以下網(wǎng)友:biwier,szm99,siice,龍?zhí)：,iamkent,zames,birdthinking,lovebuaa等為答案的修訂和完善工作提出了寶貴意見(jiàn),在此表示感謝;.本解答中的所有算法均采用類(lèi)c語(yǔ)言描述,設(shè)計(jì)原則為面向交流、面向閱讀,作者不保證程序能夠上機(jī)正常運(yùn)行（這種保證實(shí)際上也沒(méi)有任何意義）；.本解答原則上只給出源代碼以及必要的注釋,對(duì)于一些難度較高或思路特殊的題目將給出簡(jiǎn)要的分析說(shuō)明,對(duì)于作者無(wú)法解決的題目將給出必要的討論.目前尚未解決的題目有:5.20,10.40;.請(qǐng)讀者在自己已經(jīng)解決了某個(gè)題目或進(jìn)行了充分的思考之后,再參考本解答,以保證復(fù)習(xí)效果;.由于作者水平所限,本解答中一定存在不少這樣或者那樣的錯(cuò)誤和不足,希望讀者們?cè)陂喿x中多動(dòng)腦、勤思考,爭(zhēng)取發(fā)現(xiàn)和糾正這些錯(cuò)誤,寫(xiě)出更好的算法來(lái).請(qǐng)將你發(fā)現(xiàn)的錯(cuò)誤或其它值得改進(jìn)之處向作者報(bào)告:yi-ju@263.net第一章緒論1.16voidprint_descending(intx,inty,intz)〃按從大到小順序輸出三個(gè)數(shù)(scanf("%d,%d,%d",&x,&y,&z);if(x<y)x<->y;〃く>為表示交換的雙目運(yùn)算符,以下同if(y<z)y<->z;if(x<y)x<->y;〃冒泡排序printf("%d%d%d',,x,y,z);)//print_descending1.17Statusfib(intk,intm,int&f)〃求k階斐波那契序列的第m項(xiàng)的值f{inttempd;if(k<2llm<0)returnERROR;if(m<k-l)f=0;elseif(m==k-lIIm==k)fel;else(for(i=0;i<=k-2;i++)temp[i]=0;temp[k-l]=1;temp[k]=l;〃初始化sum=l;j=0；for(i=k+l;iv=m;i++,j++)〃求出序列第k至第m個(gè)元素的值tempfi]=2*sum-temp[j];f=temp[m];)returnOK;}//fib分析:k階斐波那契序列的第m項(xiàng)的值f[mJ=f[m-lJ+f[m-2]+……+f[m-k]=f[m-l]+f[m-2]+ +f[m-k]+f[m-k-l]-f[m-k-l]=2*f[m-l]-f[m-k-l]所以上述算法的時(shí)間復(fù)雜度僅為O(m).如果采用遞歸設(shè)計(jì),將達(dá)到O(kハm).即使采用暫存中間結(jié)果的方法,也將達(dá)到O(mハ2).1.18typedefstruct{char*sport;enum{male,female}gender;charschoolname;〃校名為‘A','B?C?D’或Echar*result;intscore;}resulttype;typedefstruct{intmalescore;intfemalescore;inttotalscore;}scoretype;voidsummary(resulttyperesultロ)〃求各校的男女總分和團(tuán)體總分,假設(shè)結(jié)果已經(jīng)儲(chǔ)存在result]]數(shù)組中(scoretypescorefMAXSIZE];i=0;whi!e(result[i].sport!=NULL)(switch(result[ij.schoolname)(case'A':score[0].totalscore+=result[i].score;if(result]i].gender==0)score]01.malescore+=resultfi].score;elsescore[0].femalescore+=result]i].score;break;case'B':score[0J.totalscore+=result[i].score;if(result[i].gender==O)score[0].malescore+=resuIt[i].score;elsescore[0].femalescore+=result[i].score;break;i++;)for(i=0;i<5;i++)(printf(nSchool%d:\nM,i);printf(nTotalscoreofmale:%d\nn,score[i].malescore);printf("Totalscoreoffemale:%d\n",score[i].femalescore);printf("Totalscoreofall:%d\n\n",score[i].totalscore);)}//summary1.19Statusalgoll9(inta[ARRSIZE])〃求i!*2Ai序列的值且不超過(guò)maxint(last=l;for(i=l;i<=ARRSIZE;i++){a[i-l]=last*2*i;if((a[i-lJ/last)!=(2*i))reurnOVERFLOW;last=a[i-l];returnOK;}}//algoll9分析:當(dāng)某ー項(xiàng)的結(jié)果超過(guò)了maxint時(shí),它除以前面一項(xiàng)的商會(huì)發(fā)生異常.1.20voidpolyvalue(){floattemp;float*p=a;printf("Inputnumberofterms:");scanf("%d",&n);printf("Inputvalueofx:");scanf("%f,,&x);printf("Inputthe%dcoefficientsfromaOtoa%d:\n",n+l,n);p=a;xp=l;sum=0;//xp用于存放x的i次方fbr(i=0;i<=n;i++)scanf("%F',&temp);sum+=xp*(temp);xp*=x;)printf("Valueis:%f',sum);}//polyvalue第二章線(xiàn)性表2.10StatusDeleteK(SqList&a,inti,intk)〃刪除線(xiàn)性表a中第i個(gè)元素起的k個(gè)元素(if(i<lllk<Olli+k-l>a.length)returnINFEASIBLE;for(count=l;i+count-l<=a.length-k;count++)//ft意循環(huán)結(jié)束的條件a.elem[i4-count-l]=a.elem[i+count4-k-l];a.length-=k;returnOK;}//DeleteK2.11StatusInsert_SqList(SqList&va,intx)〃把x插入遞增有序表va中{if(va.length+1>va.listsize)returnERROR;va.length++;for(i=va.length-1;va.elem[iJ>x&&i>=0;i—)va.elemli+l]=va.elem[i];va.elem[i+l]=x;returnOK;}//Insert_SqList2.12intListComp(SqListA,SqListB)〃比較字符表A和B,并用返回值表示結(jié)果,值為1,表示A>B;超為ー1,表示A<B;值為〇,表示A=B{for(i=1;i<=A.length&&i<=B.length;i++)if(A.elem[i]!=B.elem[i])returnA.elem[iJ>B.elem[i]?l:-l;if(A.length==B.length)return0;returnA.length>B.length?1:-l;〃當(dāng)兩個(gè)字符表可以互相比較的部分完全相同時(shí),哪個(gè)較長(zhǎng),哪個(gè)就較大}//ListComp2.13LNode*Locate(LinkListL,intx)〃鏈表上的元素查找,返回指針(for(p=l->next;p&&p->data!=x;p=p->next);returnp;}//Locate2.14intLength(LinkListL)〃求鏈表的長(zhǎng)度(for(k=O,p=L;p->next;p=p->next,k++);returnk;}//Length2.15voidListConcat(LinkListha,LinkListhb,LinkList&hc)〃把鏈表hb接在ha后面形成鏈表he(hc=ha;p=ha;while(p->next)p=p->next;p->next=hb;}//ListConcat2.16見(jiàn)書(shū)后答案.2.17StatusInsert(LinkList&L,inti,intb)〃在無(wú)頭結(jié)點(diǎn)鏈表L的第i個(gè)元素之前插入元素b(p=L;q=(LinkList*)malloc(sizeof(LNode));q.data=b;if(i==l){q.next=p;L=q;//插入在鏈表頭部)elsewhile(—i>l)p=p->next;q->next=p->next;p->next=q;〃插入在第i個(gè)元素的位置)}//Insert2.18StatusDelete(LinkList&L,inti)〃在無(wú)頭結(jié)點(diǎn)鏈表L中刪除第i個(gè)元素{if(i==l)L=レ〉next;〃刪除第一個(gè)元素else(P=L;while(—i>l)p=p->next;p->next=p->next->next;〃冊(cè)リ除第i個(gè)元素)}//Delete2.19StatusDelete_Between(Linklist&L,intminkjntmaxk)〃刪除元素遞增排列的鏈表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->data<maxk)q=q->next;//q是第一個(gè)不小于maxk的兀素p->next=q;}}//Delete_Between2.20StatusDelete_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(q);q=q->next;}p->next=q;p=q;q=p?>next;〃當(dāng)相鄰元素相等時(shí)刪除多余元素}//else}//while}//Delete_Equal2.21voidreverse(SqList&A)〃順序表的就地逆置(for(i=1,j=A.length;i<j;i++,j-)A.elem[i]<->A.elem[jJ;}//reverse2.22voidLinkList_reverse(Linklist&L)〃鏈表的就地逆置;為簡(jiǎn)化算法,假設(shè)表長(zhǎng)大于2(p=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的元素逐個(gè)插入新表表頭)q->next=p;s->next=q;L->next=s;}//LinkList_reverse分析:本算我的思想是,逐個(gè)地把L的當(dāng)前元素q插入新的鏈表頭部,p為新表表頭.2.23voidmergel(LinkList&A,LinkList&B,LinkList&C)〃把鏈表A和B合并為C,A和B的元素間隔排列,且使用原存儲(chǔ)空間(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}//merge12.24voidreverse_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)前元素while(pallpb)(if(pa->data<pb->dataII!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.25voidSqList_Intersect(SqListA,SqListB,SqList&C)〃求元素遞增排列的線(xiàn)性表A和B的元翥的交集并存入C中(i=l；j=l；k=O;while(A.elem[i]&&B.elem[j]){if(A.elem[i]<B.elem[j])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_Intersect2.26voidLinkList_Intersect(LinkListA,LinkListB,LinkList&C)〃在鏈表結(jié)構(gòu)上重做上題(p=A->next;q=B->next;pc=(LNode*)malloc(sizeof(LNode));C=pc;while(p&&q)(if(p->data<q->data)p=p->next;elseif(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;)}//while}//LinkList_Intersect2.27voidSqList_Intersect_True(SqList&A,SqListB)〃求元素遞增排列的線(xiàn)性表A和B的元素的交集并存直A中(i=l；j=l；k=O;while(A.elem[i]&&B.elem[j])(if(A.elem[i]<B.elem[j])i++;elseif(A.elem[i]>B.elem[j])j++;elseif(A.elemfi]!=A.elemfk])(A.elem[++k]=A.elem[i];〃當(dāng)發(fā)現(xiàn)了一個(gè)在A,B中都存在的元素i++;j++;〃且C中沒(méi)有,就添加到C中)else{i++;j++;}}//whilewhile(A.elem[k])A.elem[k++J=0;}//SqList_Intersect_True2.28voidLinkList_Intersect_True(LinkList&A,LinkListB)〃在鏈表結(jié)構(gòu)上重做上題(p=A->next;q=B->next;pc=A;while(p&&q)(if(p->data<q->data)p=p->next;elseif(p->data>q->data)q=q->next;elseif(p->data!=pc->data)(pc=pc->next;pc->data=p->data;p=p->next;q=q->next;)}//while}//LinkList_Intersect_True2.29voidSqList_Intersect_Delete(SqList&A,SqListB,SqListC)(i=0；j=0；k=0;m=0;//i指示A中元素原來(lái)的位置,m為移動(dòng)后的位置while(i<A.length&&j<B.length&&k<C.length)(if(B.elem[j]<C.elem[kJ)j++;elseif(B.elem|j]>C.elem[k])k++;else{same=B.elem[j]; 〃找至リ了相同元素samewhile(B.elem[jj==same)j++;while(C.elem[kJ==same)k++;//j,k后移到新的元素while(i<A.length&&A.elem[i]<same)A.elem[m++]=A.elem[i++]; 〃需保留的元素移動(dòng)到新位置while(i<A.length&&A.elem[i]==same)i++;〃跳過(guò)相同的元素}}//whilewhile(i<A.length)A.elem[m++l=A.elem[i++];//A的剩余元素重新存儲(chǔ)。A.length=m;}//SqList_Intersect_Delete分析:先從B和C中找出共有元素,記為same,再在A中從當(dāng)前位置開(kāi)始,凡小于same的元素均保留(存到新的位置),等于same的就跳過(guò),到大于same時(shí)就再找下ー個(gè)same.2.30voidLinkList_Intersect_Delete(LinkList&A,LinkListB,LinkListC)〃在鏈表結(jié)構(gòu)上重做上題(p=B->next;q=C->next;r=A-next;while(p&&q&&r)(if(p->data<q->data)p=p->next;elseif(p->data>q->data)q=q->next;else{u=p->data;〃確定待冊(cè)リ除元素uwhile(r->next->data<u)r=r->next;〃確定最后ー個(gè)小于u的元素指針rif(r->next->data==u)(s=r->next;while(s->data==u)(t=s;s=s->next;free⑴;〃確定第一個(gè)大于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_Delete2.31StatusDelete_Pre(CiLNode*s)〃刪除單循環(huán)鏈表中結(jié)點(diǎn)s的直接前驅(qū)(p=s；while(p->next->next!=s)p=p?>next;〃找至リs的前驅(qū)的前驅(qū)pp->next=s;returnOK;}//Delete_Pre2.32StatusDuLNode_Pre(DuLinkList&L)〃完成雙向循環(huán)鏈表結(jié)點(diǎn)的pre域fbr(p=L;!p->next->pre;p=p->next)p->next->pre=p;returnOK;}//DuLNode_Pre2.33StatusLinkList_Divide(LinkList&L,CiList&A,CiList&B,CiList&C)〃把單鏈表L的元素按類(lèi)型あ為三個(gè)循環(huán)鏈表CiList為帶頭結(jié)點(diǎn)的單循環(huán)鏈表類(lèi)型.{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é)點(diǎn)while(s)(if(isalphabet(s->data))(p->next=s;p=s;)elseif(isdigit(s->data))(q->next=s;q=s;}else{r->next=s;r=s;)}//whilep?>next=A;q?>next=B;r?>next二C;〃完成循環(huán)鏈表}//LinkList_Divide2.34voidPrint_XorLinkedList(XorLinkedListL)〃從左向右輸出異或鏈表的元素值(p=L.left;pre=NULL;while(p)(printfV'%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_XorLinkedList2.35StatusInsert_XorLinkedList(XorLinkedList&L,intx,inti)〃在異或鏈表L的第i個(gè)元素前插入元素x(p=L.left;pre=NULL;r=(XorNode*)malloc(sizeof(XorNode));r->data=x;if(i==l)〃當(dāng)插入點(diǎn)在最左邊的情況(p->LRPtr=XorP(p.LRPtr,r);r->LRPtr=p;L.left=r;returnOK;)j=l;q=p->LRPtr;〃當(dāng)插入點(diǎn)在中間的情況while(++j<i&&q)(q=XorP(p->LRPtr,pre);pre=p;p=q;}//while//在p,q兩結(jié)點(diǎn)之間插入if(!q)returnINFEASIBLE;//i不可以超過(guò)表長(zhǎng)p->LRPtr=XorP(XorP(p->LRPtr,q),r);q->LRPtr=XorP(XorP(q->LRPtr,p),r);r?>LRPtr=XorP(p,q);〃修改指針returnOK;}//Insert_XorLinkedList2.36StatusDelete_XorLinkedList(XorlinkedList&L,inti)〃刪除異或鏈表L的第i個(gè)元素(p=L.left;pre=NULL;if(i==l)〃刪除最左結(jié)點(diǎn)的情況(q=p->LRPtr;q->LRPtr=XorP(q->LRPtr,p);L.left=q;free(p);returnOK;)j=l；q=p->LRPtr;while(++j<i&&q)q=XorP(p->LRPtr,pre);pre=p;p=q;}//while//找到待刪結(jié)點(diǎn)qif(!q)returnINFEASIBLE;//i不可以超過(guò)表長(zhǎng)if(L.right==q)//q為最右結(jié)點(diǎn)的情況(p->LRPtr=XorP(p->LRPtr,q);L.right=p;free(q);returnOK;)匸XorP(q->LRPtr,p);〃q為中間結(jié)點(diǎn)的情況,此時(shí)p,r分別為其左右結(jié)點(diǎn)p->LRPtr=XorP(XorP(p->LRPtr,q),r);r->LRPtr=XorP(XorP(r->LRPtr,q),p);〃修改指針free(q);returnOK;}//Delete_XorLinkedList2.37voidOEReform(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)i出p->next==L)p->next=L->pre->pre;elsep->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;レ〉pre=p;//調(diào)整pre鏈的結(jié)構(gòu),同2.32方法}//OEReform分析:next鏈和pre鏈的調(diào)整只能分開(kāi)進(jìn)行.如同時(shí)進(jìn)行調(diào)整的話(huà),必須使用堆棧保存偶數(shù)結(jié)點(diǎn)的指針,否則將會(huì)破壞鏈表結(jié)構(gòu),造成結(jié)點(diǎn)丟失.2.38DuLNode*Locate_DuList(DuLinkedList&L,intx)〃帶freq域的雙向循環(huán)鏈表上的查找p=L.next;while(p.data!=x&&p!=L)p=p->next;if(p==L)returnNULL;〃沒(méi)找到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;〃調(diào)整位置)returnp;}//Locate_DuList2.39floatGetValue_SqPoly(SqPolyP,intx0)〃求升轅順序存儲(chǔ)的稀疏多項(xiàng)式的值(PolyTerm*q;xp=l;q=P.data;sum=0;ex=0;while(q->coef)(while(ex<q->exp)xp*=xO;sum+=q->coef*xp;q++；}returnsum;}//GetValue_SqPoly2.40voidSubtract_SqPoly(SqPolyPl,SqPolyP2,SqPoly&P3)〃求稀疏多項(xiàng)式Pl減P2的差式P3(PolyTerm*p,*q,*r;Create_SqPoly(P3);〃建立空多項(xiàng)式P3p=Pl.data;q=P2.data;r=P3.data;while(p->coef&&q->coef)(if(p->exp<q->exp)(r->coef=p->coef;r->exp=p->exp;p++；r++;}elseif(p->exp<q->exp)(r->coefi=-q->coef;r->exp=q->exp;q++;r++;}else(if((p->coef.q->coef)!=0)〃只有同次項(xiàng)相減不為零時(shí)オ需要存入P3中{r->coefep->coef-q->coef;r->exp=p->exp;r++;}//ifp++;q++;}//else}//whilewhile(p?>coef)〃處理P!或P2的剩余項(xiàng){r->coef=p->coef;r->exp=p->exp;p++;r++;)while(q->coef){r->coef=-q->coef;r->exp=q->exp;q++;r++;)}//Subtract_SqPoly2.41voidQiuDao_LinkedPoly(LinkedPoly&L)〃對(duì)有頭結(jié)點(diǎn)循環(huán)鏈表結(jié)構(gòu)存儲(chǔ)的稀疏多項(xiàng)式L求錄(p=レ〉next;if(!p->data.exp){L?>next=p?>next;p=p->next;〃為K過(guò)常數(shù)項(xiàng))while(p!=L){p->data.coef*=p->data.exp--;/ノ對(duì)每ー項(xiàng)求導(dǎo)p=p->next;)}//QiuDao_LinkedPoly2.42voidDivide_LinkedPoly(LinkedPoly&L,&A,&B)〃把循環(huán)鏈表存儲(chǔ)的稀疏多項(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;)p=p->next;}//whilepa->next=A;pb->next=B;}//Divide_LinkedPoly第三章棧與隊(duì)列3.15typedefstruct{Elemtype*base[2];Elemtype*top[2J;}BDStacktype;〃雙向棧類(lèi)型StatusInit_Stack(BDStacktype&tws,intm)〃初始化一個(gè)大小為m的雙向棧tws(tws.base[OJ=(Elemtype*)malloc(sizeof(Elemtype));tws.base[1J=tws.base[O]+m;tws.top[0]=tws.base[0];tws.topf1]=tws.base[1];returnOK;}//Init_StackStatuspush(BDStacktype&tws,inti,Elemtypex)//x入棧,i=0表不低端棧,i=l表不高端棧(if(tws.top[0]>tws.topll])returnOVERFLOW;〃注意此時(shí)的棧滿(mǎn)條件if(i==0)*tws.top[01++=x;elseif(i==l)*tws.top[l]—=x;elsereturnERROR;returnOK;}//pushStatuspop(BDStacktype&tws,inti,Elemtype&x)//x出棧,i=0表示低端棧,i=l表示高端棧(if(i==0)(if(tws.top[0]==tws.base[OJ)returnOVERFLOW;x=*-tws.top[0];)elseif(i==l)(if(tws.top[1]==tws.base[1J)returnOVERFLOW;x=*+-i-tws.top[l];}elsereturnERROR;returnOK;}〃pop3.16voidTrain_arrange(char*train)〃這里用字符串train表示火車(chē),'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_arrange3.17intIsReverse()〃判斷輸入的字符串中&前和，&后部分是否為逆串,是則返回1,否則返回〇{InitStack(s);while((e=getchar())!=,&')(if(e=ゴ@りreturn0;〃不允許在‘&'之前出現(xiàn)‘@push(s,e);)while((e=getchar())!=*@*)(if(StackEmpty(s))return0;pop(s,c);if(e!=c)return0;}if(!StackEmpty(s))return0;return1;}//IsReverse3.18StatusBracket_Test(char*str)〃判別表達(dá)式中小括號(hào)是否匹配(count=0;for(p=str;*p;p++)(if(*p==*(*)count++;elseif(*p==')')count--;if(count<0)returnERROR;)if(count)returnERROR;〃注意括號(hào)不匹配的兩種情況returnOK;}//Bracket_Test3.19StatusAllBrackets_Test(char*str)〃判別表達(dá)式中三種括號(hào)是否匹配(InitStack(s);fbr(p=str;*p;p++)if(*p=="('ll*p=='['ll*p=='{')push(s,*p);elseif(*p==)'||*p==TII*p==丁)(if(StackEmpty(s))returnERROR;pop(s,c);if(*p==')'&&c!='(')returnERROR;if(*p==']'&&c!='[')returnERROR;if(*p=='}'&&c!='{')returnERROR;〃必須與當(dāng)前棧頂括號(hào)匹配)}//forif(!StackEmpty(s))returnERROR;returnOK;}//AllBrackets_Test3.20typedefstruct{. intx;inty;}coordinate;voidRepaint_Color(intg[m][n],inti,intj,intcolor)〃把點(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;if(x>l)if(g[x-l][y]==old){g[x-l][yl=color;EnQueue(Q,{x-l,y});〃修改左鄰點(diǎn)的顏色)if(y>Dif(g[x][y-l]=old){g[x][y-l]=color;EnQueue(Q,{x,y-l});〃修改上鄰點(diǎn)的顏色|if(x<m)if(g[x+l][y]==old)(g[x+l][y]=color;EnQueue(Q,(x+1,y});〃修改右鄰點(diǎn)的顏色}jf(y<n)if(g[x][y+l]==old)g[x]ly+l]=color;EnQueue(Q,{x,y+l});〃修改下鄰點(diǎn)的顏色}}//while}//Repaint_Color分析:本薪采用了類(lèi)似于圖的廣度優(yōu)先遍歷的思想,用兩個(gè)隊(duì)列保存相鄰?fù)c(diǎn)的橫坐標(biāo)和縱坐標(biāo).遞歸形式的算法該怎么寫(xiě)呢?3.21voidNiBoLan(char*str,char*new)〃把中綴表達(dá)式str轉(zhuǎn)換成逆波蘭式new(p=str;q=new;〃為方便起見(jiàn),設(shè)str的兩端都加上了優(yōu)先級(jí)最低的特殊符號(hào)InitStack(s);//s為運(yùn)算符棧while(*p)(if(*p是字母))*q++=*p;〃直接輸出else(c=gettop(s);if(*p優(yōu)先級(jí)比c高)push(s,*p);else(while(gettop(s)優(yōu)先級(jí)不比*p低){pop(s,c);*(q++)=c;}//whilepush(s,*p);〃運(yùn)算符在棧內(nèi)遵循越往棧頂優(yōu)先級(jí)越高的原則}//else}//elseP++；}//while}//NiBoLan〃參見(jiàn)編譯原理教材intGetValue_NiBoLan(char*str)〃對(duì)逆波蘭式求值(p=str;InitStack(s);//s為操作數(shù)棧while(*p)(if(*p是數(shù))push(s,*p);else(pop(s,a);pop(s,b);r=compute(b,*p,a);〃假設(shè)compute為執(zhí)行雙目運(yùn)算的過(guò)程push(s,r);}//elseP++；}//whilepop(s,r);returnr;}//GetValue_NiBoLan3.23StatusNiBoLan_to_BoLan(char*str,stringtype&new)〃把逆波蘭表達(dá)式str轉(zhuǎn)換為波蘭式new(p=str;Initstack(s);〃s的元素為stringtype類(lèi)型while(*p)(if(*p為字母)push(s,*p);else(if(StackEmpty(s))returnERROR;pop(s,a);if(StackEmpty(s))returnERROR;pop(s,b);c=link(link(*p,b),a);push(s,c);}//elseP++；}//whilepop(s,new);if(!StackEmpty(s))returnERROR;returnOK;}//NiBoLan_to_BoLan分析:基本思想見(jiàn)書(shū)后注釋.本題中暫不考慮串的具體操作的實(shí)現(xiàn),而將其看作一種抽象數(shù)據(jù)類(lèi)型stringtype,對(duì)其可以進(jìn)行連接操作:c=link(a,b).Statusg(intm,intn,int&s)〃求遞歸函數(shù)g的值s(一if(m==0&&n>=0)s=0;elseif(m>0&&n>=0)s=n+g(m-l,2*n);elsereturnERROR;returnOK;}//g3.25StatusF_recursive(intn,int&s)〃遞歸算法(if(n<0)returnERROR;if(n==0)s=n+l;else{F_recurve(n/2,r);s=n*r;)returnOK;}//F_recursiveStatusF_nonrecursive(intn,ints)〃非遞歸算法(if(n<0)returnERROR;if(n==0)s=n+1;else(InitStack(s);//s的元素類(lèi)型為struct{inta;intb;}while(n!=0)(a=n;b=n/2;push(s,{a,b});n=b;}//whiles=l;while(!StackEmpty(s))(pop(s,t);s*=t.a;}//while)returnOK;}//F_nonrecursive3.26floatSqrt_recursive(floatA,floatp,floate)〃求平方根的遞歸算法(if(abs(pA2-A)<=e)returnp;elsereturnsqrt_recurve(A,(p+A/p)/2,e);}//Sqrt_recurvefloatSqrt_nonrecursive(floatA,floatp,floate)〃求平方根的非遞歸算法(while(abs(pA2-A)>=e)p=(p+A/p)/2;returnp;}//Sqrt_nonrecursive3.27這ー題的所有算法以及棧的變化過(guò)程請(qǐng)參見(jiàn)《數(shù)據(jù)結(jié)構(gòu)(pascal版)》,作者不再詳細(xì)寫(xiě)出.3.28voidInitCiQueue(CiQueue&Q)〃初始化循環(huán)鏈表表示的隊(duì)列Q(Q=(CiLNode*)malloc(sizeof(CiLNode));Q->next=Q;}//InitCiQueuevoidEnCiQueue(CiQueue&Q,intx)〃把元素x插入循環(huán)鏈表表示的隊(duì)列Q,Q指向隊(duì)尾元素,Q->next指向頭結(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;〃修改尾指針)StatusDeCiQueue(CiQueue&Q,intx)〃從循環(huán)鏈表表示的隊(duì)列Q頭部刪除元素x(if(Q==Q->next)returnINFEASIBLE;〃隊(duì)歹!］已空p=Q->next->next;x=p->data;Q->next->next=p->next;free(p);returnOK;}//DeCiQueue3.29StatusEnCyQueue(CyQueue&Q,intx)〃帶tag域的循環(huán)隊(duì)列入隊(duì)算法(if(Q.front==Q.rear&&Q.tag==l)//tag域的值為〇表示”空",1表示”滿(mǎn)“returnOVERFLOW;Q.base[Q.rear]=x;Q.rear=(Q.rear+1)%MAXSIZE;if(Q.front==Q.rear)Q.tag=l;//隊(duì)列滿(mǎn)}//EnCyQueueStatusDeCyQueue(CyQueue&Q,int&x)〃帶tag域的循環(huán)隊(duì)列出隊(duì)算法(if(Q.front==Q.rear&&Q.tag==0)returnINFEASIBLE;Q.front=(Q.front+l)%MAXSIZE;x=Q.base[Q.front];if(Q.front==Q.rear)Q.tag=l;//隊(duì)列空returnOK;}//DeCyQueue分析:當(dāng)循環(huán)隊(duì)列容量較小而隊(duì)列中每個(gè)元素占的空間較多時(shí),此種表示方法可以節(jié)約較多的存儲(chǔ)空間,較有價(jià)值.3.30StatusEnCyQueue(CyQueue&Q,intx)〃帶!ength域的循環(huán)隊(duì)列入隊(duì)算法(if(Q.length==MAXSIZE)returnOVERFLOW;Q.rear=(Q.rear+1)%MAXSIZE;Q.base[Q.rear]=x;Q.length++;returnOK;}//EnCyQueueStatusDeCyQueue(CyQueue&Q,int&x)〃帶!ength域的循環(huán)隊(duì)列出隊(duì)算法(if(Q.length==O)returnINFEASIBLE;head=(Q.rear-Q.length+l)%MAXSIZE;//詳見(jiàn)書(shū)后注釋x=Q.base[head];Q.length—;}//DeCyQueueintPalindrome_Test()〃判別輸入的字符串是否回文序歹!J,是則返回1,否則返回〇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)returnERROR;)returnOK;}//Palindrome_Test3.32voidGetFib_CyQueue(intk,intn)〃求k階斐波那契序列的前n+1項(xiàng)(InitCyQueue(Q);〃其MAXSIZE設(shè)置為kfor(i=0;i<k-l;i++)Q.base[i]=0;Q.base[k-l]=l;〃給前k項(xiàng)賦初值for(i=0;i<k;i++)printf("%d",Q.base[i]);for(i=k;i<=n;i++)(m=i%k;sum=0;for(j=0;j<k;j++)sum+=Q.base[(m+j)%k];Q.base[m]=sum;〃求第i項(xiàng)的值存入隊(duì)列中并取代已無(wú)用的第一項(xiàng)printf("%d",sum);)}//GetFib_CyQueue3.33StatusEnDQueue(DQueue&Q,intx)〃輸出受限的雙端隊(duì)列的入隊(duì)操作(if((Q.rear+l)%MAXSIZE==Q.front)returnOVERFLOW;〃隊(duì)歹リ滿(mǎn)avr=(Q.base[Q.rear-lJ+Q.base[Q.fiont])/2;if(x>=avr)〃根據(jù)x的值決定插入在隊(duì)頭還是隊(duì)尾(Q.base[Q.rear]=x;Q.rear=(Q.rear+l)%MAXSIZE;}〃插入在隊(duì)尾elseQ.front=(Q.front-l)%MAXSIZE;Q.base[Q.frontJ=x;}〃插入在隊(duì)頭returnOK;}//EnDQueueStatusDeDQueue(DQueue&Q,int&x)〃輸出受限的雙端隊(duì)列的出隊(duì)操作(if(Q.front==Q.rear)returnINFEASIBLE;〃隊(duì)歹リ空x=Q.base[Q.front];Q.front=(Q.front+1)%MAXSIZE;returnOK;}//DeDQueue3.34voidTrain_Rearrange(char*train)〃這里用字符串train表示火車(chē)表示硬座,H表示硬臥,S展示軟臥,最終按PSH的順序排列(r=train;InitDQueue(Q);while(*r){if(*r==P)(printf("E")；printf("D");〃實(shí)際上等于不入隊(duì)列,直接輸出P車(chē)廂}elseif(*r=="S')(printf("E");EnDQueue(Q,*r,O);//0表示把S車(chē)廂從頭端入隊(duì)列)else{printf("A");EnDQueue(Q,*r,l);//I表示把H車(chē)廂從尾端入隊(duì)列}}//whilewhile(!DQueueEmpty(Q)){printf("D");DeDQueue(Q);"/while〃從頭端出隊(duì)列的車(chē)廂必然是先S后H的順序}//Train_Rearrange4.10voidString_Reverse(Stringtypes,Stringtype&r)〃求s的逆串r(StrAssign(rJ);〃初始化r為空串for(i=Strlen(s);i;i—){StrAssign(c,SubString(s,i,1));StrAssign(r,Concat(r,c));//把s的字符從后往前添加到r中)