第三章棧與隊(duì)列批注［嚴(yán)蔚敏1］:*basc［2］是隨批注［嚴(yán)蔚敏1］:*basc［2］是隨*base［l］而確定的，因此這里的定義改為*base更好些，否則容易仍人誤解為存在兩個(gè)數(shù)組空間。批注［嚴(yán)蔚敏1］:*basc［2］是隨批注［嚴(yán)蔚敏1］:*basc［2］是隨*base［l］而確定的，因此這里的定義改為*base更好些，否則容易仍人誤解為存在兩個(gè)數(shù)組空間。Elemtype*top[2];}BDStacktype;//雙向棧類型批注［嚴(yán)蔚敏2］:這里寫錯(cuò)了吧？只要簡(jiǎn)單?看就能看出錯(cuò)來，因?yàn)檎Z句中沒有“m”，說明參數(shù)中的批注［嚴(yán)蔚敏2］:這里寫錯(cuò)了吧？只要簡(jiǎn)單?看就能看出錯(cuò)來，因?yàn)檎Z句中沒有“m”，說明參數(shù)中的m沒有用上，可能是這位同學(xué)粗心大意，或是對(duì)C語言掌握得還不夠好。批注［嚴(yán)蔚敏引：“棧頂指針的定義”我不知道是否是這位同學(xué)寫的時(shí)候大意了。一般來說，如果對(duì)“結(jié)構(gòu)定義的完整性”的意識(shí)強(qiáng)一些的話就不容易出這種錯(cuò)誤。type))；|[1]|[1][1]1returnOK;}//Init_StackStatuspush(BDStacktype&tws,inti,Elemtypex)//x入棧,i=0表示低端棧,i=l表示高端棧([1J)returnOVERFLOW;〃注意此時(shí)的棧滿條件if(i==elsereturnERROR;returnOK;}//pushStatuspop(BDStacktype&tws,inti,Elemtype&x)//x出棧,i=0表示低端棧,i=l表示高端棧(if(i==0)elseif(i==l)([1][1])returnOVERFLOW;[1]；elsereturnERROR;returnOK;}〃popvoidTrain_Rearrange(char*train)〃這里用字符串train表示火車,'P表示硬座,H表示硬臥,S展示軟臥,最終按PSH的順序排列(r=train;InitDQueue(Q);while(*r)(if(*r=='P')(printf(HEn);printf("D");//實(shí)際上等于不入隊(duì)列，直接輸出P車廂)elseif(*r==,S,)(printf(HEn);EnDQueue(Q,*r,O);//0表示把S車廂從頭端入隊(duì)列)else(printf(nAn);EnDQueue(Q,*r,l);//I表示把H車廂從尾端入隊(duì)列)}//whilewhile(!DQueueEmpty(Q))(printf("Du);DeDQueue(Q);}〃while〃從頭端出隊(duì)列的車廂必然是先S后H的順序}//Train_RearrangevoidTrain_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_arrangeintlsReverse。//判斷輸入的字符串中&前和&后部分是否為逆串，是則返回1,否則返回0(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;}//IsReverseStatusBracket_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_TestStatusAllBrackets_Test(char*str)〃判別表達(dá)式中三種括號(hào)是否匹配(InitStack(s);for(p=str;*p;p++)(if(*p==，CII*p==,[|||*p==,{，)push(s,*p);elseif(*p=='y||*p=-]，H*p==，}')(if(StackEmpty(s))returnERROR;pop(s,c);if(*p==)&&c!±OreturnERROR;if(*p==T&&c!=T)returnERROR;if(*p==,},&&c!='{，)returnERROR;〃必須與當(dāng)前棧頂括號(hào)匹配)}//forif(!StackEmpty(s))returnERROR;returnOK;J//A11Brackets_Testtypedefstruct{.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);if(x>l)if(g[x-l][y]==old)g[x-l][y]=color;EnQueue(Q,{x-l,y});〃修改左鄰點(diǎn)的顏色if(y>i)if(g[xj[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)的顏色)if(y<n)if(g[x][y+l]==old)(g[x][y+l]=color;EnQueue(Q,{x,y+l));〃修改下鄰點(diǎn)的顏色)}//while}//Repaint_Color批注[嚴(yán)蔚敏5]:我不太明白這個(gè)提問的意思是什么？是寫廣度優(yōu)先遍歷的遞歸形式算法嗎？可能這位同學(xué)意思就是寫一個(gè)解本題的遞歸形式算法，對(duì)嗎？要提醒其它同學(xué)注意的是，由于廣度優(yōu)先遍歷是“先進(jìn)先出”的，因此不可能有遞歸形式的寫法。分析:本算法采用了類似于圖的廣度優(yōu)先遍歷的思想,用兩個(gè)隊(duì)列保存相鄰?fù)c(diǎn)的橫坐標(biāo)和縱坐標(biāo).遞歸形式的算法該怎么寫呢？|voidNiBoLan(char*str,char*new)〃把中綴表達(dá)式str批注[嚴(yán)蔚敏5]:我不太明白這個(gè)提問的意思是什么？是寫廣度優(yōu)先遍歷的遞歸形式算法嗎？可能這位同學(xué)意思就是寫一個(gè)解本題的遞歸形式算法，對(duì)嗎？要提醒其它同學(xué)注意的是，由于廣度優(yōu)先遍歷是“先進(jìn)先出”的，因此不可能有遞歸形式的寫法。(p=str;q=new;//為方便起見，設(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批注[嚴(yán)蔚敏6]:批注[嚴(yán)蔚敏6]:這個(gè)循環(huán)到什么時(shí)候結(jié)束？棧不會(huì)空嗎？while(gettop(s)優(yōu)先級(jí)不比*p低)pop(s,c);*(q++)=c;批注[嚴(yán)蔚敏7]:批注[嚴(yán)蔚敏7]:這個(gè)“入棧”有條件嗎？如果*p是最后一個(gè)優(yōu)先級(jí)最低的結(jié)束符呢？另外，加上最低級(jí)的結(jié)束符之后，while(*p)的條件還對(duì)嗎？bush(s,*p);//運(yùn)算符在棧內(nèi)遵循越往棧頂優(yōu)先級(jí)越高的原則}//else}//elseP++；}//while}//NiBoLan〃參見編譯原理教材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)算的過程push(s,r);}//elsep++；}//whilepop(s,r);returnr;}//GetValue_NiBoLanStatusNiBoLan_to_BoLan(char*str,stringtype&new)〃把逆波蘭表達(dá)式str轉(zhuǎn)換為波蘭式new{一p=str;Initstack(s);//s的元素為stringtype類型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分析:基本思想見書后注釋.本題中暫不考慮串的具體操作的實(shí)現(xiàn),而將其看作一種抽象數(shù)據(jù)類型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;}//gStatusF_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的元素類型為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)；}//while)returnOK;}//F_nonrecursivefloatSqrt_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_nonrecursive這一題的所有算法以及棧的變化過程請(qǐng)參見《數(shù)據(jù)結(jié)構(gòu)(pascal版)》，作者不再詳細(xì)寫出.voidInitCiQueue(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ì)歹U已空p=Q->next->next;x=p->data;Q->next->next=p->next;free(p);批注[嚴(yán)蔚敏8]:少考慮一種特殊情況，說明對(duì)書上的算法理解不透。批注[嚴(yán)蔚敏8]:少考慮一種特殊情況，說明對(duì)書上的算法理解不透。StatusEnCyQueue(CyQueue&Q,intx)〃帶tag域的循環(huán)隊(duì)列入隊(duì)算法returnOVERFLOW;}//EnCyQueueStatusDeCyQueue(CyQueue&Q,int&x)〃帶tag域的循環(huán)隊(duì)列出隊(duì)算法批注[嚴(yán)蔚敏9]:為什么要先移動(dòng)指針？初始化空隊(duì)列時(shí)的指針狀態(tài)是什么？returnOK;}//DeCyQueue分析:當(dāng)循環(huán)隊(duì)列容量較小而隊(duì)列中每個(gè)元素占的空間較多時(shí)，此種表示方法可以節(jié)約較多的存儲(chǔ)空間，較有價(jià)值.StatusEnCyQueue(CyQueue&Q,intx)〃帶length域的循環(huán)隊(duì)列入隊(duì)算法returnOK;}//EnCyQueueStatusDeCyQueue(CyQueue&Q,int&x)〃帶length域的循環(huán)隊(duì)列出隊(duì)