題3.17題3.19題3.22題3.28題3.31題3.32題3.19intmatching(SqListexp){//順序表exp中存有數(shù)據(jù)元素為字符的表達(dá)式,//若表達(dá)式中三種括弧正確嵌套，則返回1,//否則返回0。}state=1;i=1;InitStack(S);while(i<=exp.length&&

state){}if(state

&&StackEmpty(S))return1;elsereturn0;

……switchofexp.elem[i]{

case

左括弧:{Push(S,exp.elem[i]);i++;break;}

case

):{

if(NOTStackEmpty(S)&&GetTop(S)=(){Pop(S,e);i++;}

elsestate=0;

break;}case

]:{

if(NOTStackEmpty(S)&&GetTop(S)=[){Pop(S,e);i++;}

elsestate=0;

break;}case

}:……識(shí)別讀入的一個(gè)字符序列是否為反對(duì)稱的字符序列。例如:abcd&dcba@

是反對(duì)稱字符序列;

abc&@

或abc&abc@

或

ab&bac@都不是反對(duì)稱字符序列。題3.17則這個(gè)算法和“判別括弧是否正確匹配”的算法極其相似。同樣，在算法過程中需要用到一個(gè)棧，由于序列中必定出現(xiàn)字符

&

，則可將在字符&出現(xiàn)之前的所有字符均入棧，濾去字符&之后再讀入的字符則應(yīng)和棧頂?shù)淖址嗟龋?dāng)然，首先必須判別此時(shí)的“?！笔欠駷椤翱諚！薄４祟}的參數(shù)僅為一個(gè)字符序列，可以設(shè)為元素為字符的數(shù)組。intsymmetry(charCh[]){//若Ch[]為反對(duì)稱字符序列，則返回1,//

否則返回0。}p=Ch;InitStack(S);while(*p!=‘&’){Push(S,*p);p++;}state=1;p++;//濾去字符‘&’

while(*p!=‘@’&&state){

if(NOTStackEmpty(S)&&GetTop(S)==*p)

{Pop(S,e);p++;}

elsestate=0;}return(StackEmpty(S)&&state)題3.22intvaluation(SqListsuffixal){IniStack(S);p=suffixal.elem;ch=*p;

while(ch!=#){

if(!IN(ch,OP))Push(S,ch);

else{Pop(S,b);Pop(S,a);x=value(a,ch,b);e=setvar(x);//e為其值=x的變量名

Push(S,e);}ch=*p++;}Pop(S,e);return(val(e));//返回變量e的值}題3.28typedefQueuePtrCLQueue;//指向隊(duì)尾結(jié)點(diǎn)的指針StatusInitQueue(CLQueue&Q){//構(gòu)造空隊(duì)列

Q=newQnode;//生成頭結(jié)點(diǎn)

if(!Q)exit(OVERFLOW);//存儲(chǔ)分配失敗

Q->next=Q;//自成循環(huán)

returnOK;}定義循環(huán)鏈隊(duì)列初始化操作StatusEnQueue(CLQueue&Q,QElemTypee){//插入元素e為新的隊(duì)尾元素

p=newQnode;//生成新的結(jié)點(diǎn)

if(!p)exit(OVERFLOW);//存儲(chǔ)分配失敗

p->data=e;p->next=Q->next;Q->next=p;//插入隊(duì)尾

Q=p;//修改隊(duì)尾指針

returnOK;}入隊(duì)列操作StatusDeQueue(CLQueue&Q,QElemType&e){//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，以e帶回

//其值，并返回OK，否則返回ERROR

if(Q->next==Q)return(ERROR);//空隊(duì)列

p=Q->next->next;e=p->data;Q->next->next=p->next;//刪除隊(duì)頭元素

if(p==Q)Q=Q->next;

deletep;returnOK;//釋放被刪結(jié)點(diǎn)}出隊(duì)列操作判別讀入的字符序列是否為“回文”。例如:abcdedcba

或abccba

是回文。

由于回文的字符序列中的分界線不明確，因此無法判定字符序列的“中間位置”，即只能按照回文的定義從字符的兩頭出發(fā)進(jìn)行判別。題3.31算法的基本思想是:將依次讀入的字符分別插入棧和隊(duì)列，然后依次比較“棧頂”和“隊(duì)頭”的字符。然而，按照題目的要求，這個(gè)字符序列是從外部環(huán)境輸入的。為了在輸入結(jié)束的時(shí)候，同時(shí)能得到序列的“頭”和“尾”，因此算法中，除了需要用一個(gè)棧之外，還需要一個(gè)隊(duì)列。Statusex331(){//若從終端依次輸入的字符序列是“回文”，//則返回TRUE,否則返回FALSEInitStack(S);InitQueue(Q);

scanf(ch);

while(ch!=@){Push(S,ch);EnQueue(Q,ch);

scanf(ch);}state=TRUE;

while(!StackEmpty&&state){

if(GetTop(S)==GetHead(Q)){Pop(S);DeQueue(Q);}

elsestate=FALSE;}

returnstate;}題3.32k階斐波那契函數(shù)的定義:f0=f1=……=fk-2=0，fk-1=1，

fn=fn-1+fn-2+……+fn-kn≥k

由于題目要求循環(huán)隊(duì)列的容量為k,即當(dāng)前隊(duì)列中k個(gè)元素之和為下一個(gè)函數(shù)值。

利用公式fn=2fn-1-fn-k-1可以簡(jiǎn)化計(jì)算，但需要隊(duì)列的容量為k+1。voidk_Fib(CQueueQ,intk,intmax){

for(i=0;i<k-1;i++)Q.elem[i]=0;//賦初值

Q.elem[k-1]=1;Q.rear=0;f=1;

while(f<=max){

cout<<Q.elem[Q.rear];//輸出隊(duì)頭元素

Q.elem[Q.rear]=f;//插入新的隊(duì)尾元素

Q.rear++;//隊(duì)尾指針增1f=0;//計(jì)算下一個(gè)函數(shù)值

for(i=0;i<k;i++)f+=Q.elem[i];}

繼續(xù)輸出循環(huán)隊(duì)列中的其余函數(shù)值;}voidk_Fib(intk,intmax){InitQueue(Q);//

附設(shè)含k+1個(gè)分量的循環(huán)隊(duì)列

for(i=0;i<k-1;i++)EnQueue(Q,0);EnQueue(Q,1);f=1;//賦初值

while(f<=max){DeQueue(Q,e);

cout<<e<<‘,’;//輸出隊(duì)頭元素

EnQueue(Q,