考試數據結構

題3.17題3.19題3.22題3.28題3.31題3.32題3.19intmatching(SqListexp){//順序表exp中存有數據元素為字符的表達式,//若表達式中三種括弧正確嵌套，則返回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

}:……識別讀入的一個字符序列是否為反對稱的字符序列。例如:abcd&dcba@

是反對稱字符序列;

abc&@

或abc&abc@

或

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

&

，則可將在字符&出現之前的所有字符均入棧，濾去字符&之后再讀入的字符則應和棧頂的字符相等，當然，首先必須判別此時的“棧”是否為“空?！薄４祟}的參數僅為一個字符序列，可以設為元素為字符的數組。intsymmetry(charCh[]){//若Ch[]為反對稱字符序列，則返回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;//指向隊尾結點的指針StatusInitQueue(CLQueue&Q){//構造空隊列

Q=newQnode;//生成頭結點

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

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

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

p=newQnode;//生成新的結點

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

p->data=e;p->next=Q->next;Q->next=p;//插入隊尾

Q=p;//修改隊尾指針

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

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

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

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

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

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

或abccba

是回文。

由于回文的字符序列中的分界線不明確，因此無法判定字符序列的“中間位置”，即只能按照回文的定義從字符的兩頭出發(fā)進行判別。題3.31算法的基本思想是:將依次讀入的字符分別插入棧和隊列，然后依次比較“棧頂”和“隊頭”的字符。然而，按照題目的要求，這個字符序列是從外部環(huán)境輸入的。為了在輸入結束的時候，同時能得到序列的“頭”和“尾”，因此算法中，除了需要用一個棧之外，還需要一個隊列。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階斐波那契函數的定義:f0=f1=……=fk-2=0，fk-1=1，

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

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

利用公式fn=2fn-1-fn-k-1可以簡化計算，但需要隊列的容量為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];//輸出隊頭元素

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

Q.rear++;//隊尾指針增1f=0;//計算下一個函數值

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

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

附設含k+1個分量的循環(huán)隊列

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

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

cout<<e<<‘,’;//輸出隊頭元素

EnQueue(Q,