第三章作業(yè)答案1.簡述下列算法的功能：statusalgo(StackS){ inti,n,A[255]; n=0; while(!StackEmpty(S)){n++;Pop(S,A[n]);} for(i=1;i<=n;i++)Push(S,A[i]);}功能：將棧中的元素倒置放置。2.假設(shè)一個算術(shù)表達式中可以包含三種括號：圓括號“）”和“(”、方括號“[”和“]”和花括號“{”和“}”，而且這三種括號可以按任意的次序嵌套使用（如：…[…{…}…[…]…]…[…]…(…)…。編寫判別給定表達式中所包含是否正確配對出現(xiàn)的算法（已知表達式已存入數(shù)據(jù)元素為字符的順序表中）。StatusAllBrackets_Test(char*str)//用str代表表達式，判別表達式中三種括號是否匹配{……..}StatusAllBrackets_Test(char*str){//判別表達式中三種括號是否匹配

InitStack(S);

for(p=str;*p;p++)

{

if(*p=='('||*p=='['||*p=='{')push(S,*p);

elseif(*p==')'||*p==']'||*p=='}')

{

if(StackEmpty(S))returnERROR;

pop(S,c);

if(*p==')'&&c!='(')returnERROR;

if(*p==']'&&c!='[')returnERROR;

if(*p=='}'&&c!='{')returnERROR;//必須與當(dāng)前棧頂括號匹配

}//end

elseif

}//endfor

if(!StackEmpty(s))returnERROR;

returnOK;

}//AllBrackets_Test3.如果希望循環(huán)隊列中的元素都能得到利用，則需要設(shè)置一個標(biāo)志域tag，并以tag的值為0或1來區(qū)分尾指針和頭指針值相同時的隊列狀態(tài)是“空”還是“滿”。試編寫與此結(jié)構(gòu)相應(yīng)的入隊列和出隊列的算法，并從時間和空間角度討論和不設(shè)標(biāo)志這兩種方法的使用范圍（如當(dāng)循環(huán)隊列容量較小而隊列中每個元素占的空間較多時，哪一種方法較好）。（提示：將標(biāo)志的初值置“0”。一旦元素入隊列使得rear=front時，需要置tag為“1”：反之，一旦元素出隊列使得rear=front時，需要置tag為“0”，以便使得下一次進入隊列或出隊列操作時，此時front=rear，根據(jù)tag的值來判斷隊列的狀態(tài)。）分析:當(dāng)循環(huán)隊列容量較小而隊列中每個元素占的空間較多時,此種表示方法可以節(jié)約較多的存儲空間，較有價值。StatusEnCyQueue(CyQueue&Q,intx){//帶tag域的循環(huán)隊列入隊算法

==1)//tag域的值為0表示"空",1表示"滿"

returnERROR;

]=x;

=(Q.rear+1)%MAXSIZE;

==)=1;//隊列滿

}//EnCyQueueStatusDeCyQueue(CyQueue&Q,int&x){//帶tag域的循環(huán)隊列出隊算法

==0)//隊列空returnERROR;

x=];=(Q.front+1)%MAXSIZE;

==)=0;//隊列空

returnOK;

}//DeCyQueue

4.假設(shè)稱正讀和反讀都相同的字符序列為“回文”，例如，’abba’和’abcba’回文，’abcde’和’ababab’不是回文。試寫一個算法判別讀入的一個以’@’為結(jié)束符的字符序列是否是“回文”。intPalindrome_Test()//判別輸入的字符串是否回文序列,是則返回1,否則返回0

{…………..}

StatusPalindrome_Test()//檢查是否回文{InitStack(S);InitQueue(Q);while((c=getchar()!='@'){

Push(S,c);EnQueue(Q,c);//同時使用棧和隊列兩種結(jié)構(gòu)

}

while(!StackEmpty(S))

{

Pop(S,a);DeQueue(Q,b));

if(a!=b)returnERROR;

}

returnOK;}5.假設(shè)如題1所述火車調(diào)度站的入口處有n節(jié)硬席或軟席車廂（分別以H和S表示）等待調(diào)度，試編寫算法，輸出對這n節(jié)車廂進行調(diào)度的操作（即入?；虺鰲２僮鳎┬蛄校允顾械能浵噹急徽{(diào)到硬席車廂之前。提示：voidTrain_arrange(char*train){}//這里用字符串train表示火車,字符'H'表示硬席,'S'表示軟席，設(shè)兩個指針p和q，其中，p指向字符串train，q指向一個新的字符串，用于存放排序后的結(jié)果。voidTrain_arrange(char*train){char*p,*q;p=train;q=newtrain;

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_arrange6.假設(shè)將循環(huán)隊列定義為：以域變量rear和length分別指示循環(huán)隊列中隊尾元素的位置和內(nèi)含元素的個數(shù)。試給出此循環(huán)隊列滿的條件，并寫出相應(yīng)的入隊列和出隊列的算法（在出隊列的算法中要返回隊頭元素）。（提示：rear不是指向隊尾元素的下一個位置，而是指向隊尾元素；隊列的隊頭指針head=(Q.rear-Q.length+1)%MAXSIZE）StatusEnCyQueue(CyQueu