【文章內(nèi)容簡(jiǎn)介】 后退出循環(huán) */ { prelink=xor(r,NULL)。 /*將 slink 置為前后節(jié) 點(diǎn)地址之異或 */ *e=pre。 break。 } s=(dlist *)malloc(sizeof(dlist))。/*創(chuàng)建一個(gè)節(jié)點(diǎn) */ sdata=x。 if(i==1)/*是第一個(gè)節(jié)點(diǎn)的情況 */ { pre=head=s。r=NULL。/*r 為當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) */ } else { prelink=xor(r,s)。 /*將 slink 置為前后節(jié)點(diǎn)地址之異或 */ r=pre。 pre=s。 } i++。 } return head。 } void order(dlist *h,dlist *e) { dlist *pre=NULL,*pre1,*p=h。 printf(遍歷節(jié)點(diǎn)序列 : )。 if(h==NULL) printf(空表 \n)。 else { while(p!=e)/*遍歷最后一節(jié)點(diǎn)前的所有節(jié)點(diǎn) */ { printf(%d ,pdata)。 pre1=p。 p=xor(pre,plink)。/*為下一個(gè)節(jié)點(diǎn)的地址 */ pre=pre1。 17 } printf(%d ,edata)。 printf(\n)。 } } void main() { dlist *h,*e。 int i。 h=create(amp。e)。 printf(從左向右 )。 order(h,e)。 printf(從右向左 )。 order(e,h)。 } /*運(yùn)行結(jié)果 : 創(chuàng)建一個(gè)雙鏈表 (以 0 結(jié)束 ) 輸入第 1 節(jié)點(diǎn)值 :3 輸入第 1 節(jié)點(diǎn)值 :5 輸入第 1 節(jié)點(diǎn)值 :8 輸入第 1 節(jié)點(diǎn)值 :2 輸入第 1 節(jié)點(diǎn)值 :6 輸入第 1 節(jié)點(diǎn)值 :0 從左向右遍 歷節(jié)點(diǎn)序列 : 3 5 8 2 6 從右向左遍歷節(jié)點(diǎn)序列 : 6 2 8 5 3 */ 第三章 棧和隊(duì)列 實(shí)現(xiàn)?；舅惴ǖ念^文件 為： include define MaxLen 20/*順序棧存放的最多元素個(gè)數(shù)為 Maxlen1*/ typedef char elemtype。 typedef struct sqstack { elemtype data[MaxLen]。 int top。 }stack。 void init(stack *st)/*初始化棧 st*/ { sttop=0。 } int push(stack *st,elemtype x)/*入棧 */ { if(sttop==MaxLen1) { printf(棧溢出 \n)。 18 return 0。 } else { sttop++。 stdata[sttop]=x。 return 1。 } } int pop(stack *st,elemtype *x)/*退棧 */ { if(sttop==0) { printf(棧下溢出 \n)。 return 0。 } else { *x=stdata[sttop]。 sttop。 return 1。 } } int empty(stack *st)/*判斷?？?*/ { if(sttop==0) return 1。 else return 0。 } int gettop(stack *st,elemtype *x)/*獲取棧頂元素 */ { if(sttop==0) { printf(棧下溢出 \n)。 return 0。 } else { *x=stdata[sttop]。 return 1。 } } void disp(stack *st)/*輸出棧的所有元素 */ 19 { int i。 for(i=sttop。i0。i) printf(%d ,stdata[i])。 printf(\n)。 } /*練習(xí) */ /*假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三種括號(hào)，圓括號(hào) (和 )、方括號(hào) [和 ]和花括號(hào) {和 },且這三種括號(hào)可按任意的次序嵌套使用 (如 :..[..{..}..[..]..]..[..]..(..)..).編寫(xiě)判別給定表達(dá)式中所含括號(hào)是否正確配對(duì)出現(xiàn)的算法 (已知表達(dá)式已存入數(shù)據(jù)元素為字符的順序表中 */ /*輸入： {a+[b+(c+d)+e]+f}*/ include include int correct(char *str) { stack st。 char x。 int i,ok=1。 init(amp。st)。 for(i=0。str[i]!=39。\039。i++) { switch(str[i]) { case39。(39。:push(amp。st,39。(39。)。break。 case39。[39。:push(amp。st,39。[39。)。break。 case39。{39。:push(amp。st,39。{39。)。break。 case39。)39。:if(!(pop(amp。st,amp。x)amp。amp。x==39。(39。)) ok=0。break。 case39。]39。:if(!(pop(amp。st,amp。x)amp。amp。x==39。[39。)) ok=0。break。 case39。}39。:if(!(pop(amp。st,amp。x)amp。amp。x==39。{39。)) ok=0。break。 } if(!ok) break。 } if(empty(amp。st)amp。amp。ok) return 1。 else return 0。 } void main() { 20 char *str。 str=(char*)malloc(100*sizeof(char))。 printf(str: )。 scanf(%s,str)。 if(correct(str)) printf(表達(dá)式括號(hào)匹配 \n)。 else printf(表達(dá)式括號(hào)不匹配 \n)。 getch()。 }練習(xí) include define MaxLen 100 int trans(char str[],char exp[]) { int st[MaxLen]。/*作為棧使用 */ char ch。 int i=0,t=0,top=1。/*t 作為 exp 的下標(biāo)， top 作為 st的下標(biāo)， i 作為 str 的下標(biāo) */ while((ch=str[i++])!=39。\039。) { if(ch=39。039。 amp。amp。 ch=39。939。)/*判斷為數(shù)字 */ { exp[t]=ch。t++。 while ((ch=str[i++])!=39。\039。 amp。amp。 ch=39。039。 amp。amp。 ch=39。939。) { exp[t]=ch。t++。 } i。 exp[t]=39。39。t++。 } else if(ch==39。(39。)/*判斷為左括號(hào) */ { top++。st[top]=ch。 } else if(ch==39。)39。)/*判斷為右括號(hào) */ { while(st[top]!=39。(39。) { exp[t]=st[top]。top。t++。 } top。 } else if(ch==39。+39。||ch==39。39。)/*判斷為加減號(hào) */ 21 { while(top=0 amp。amp。 st[top]!=39。(39。) { exp[t]=st[top]。top。t++。 } top++。st[top]=ch。 } else if(ch==39。*39。||ch==39。/39。) { while (st[top]==39。*39。 || st[top]==39。/39。) { exp[t]=st[top]。top。t++。 } top++。st[top]=ch。 } } while(top=0) { exp[t]=st[top]。t++。top。 } exp[t]=39。\039。 return 1。 } int pvalue(char exp[],int *n) { int st[MaxLen],d。/*作為棧使用 */ char ch。 int t=0,top=1。/*t 作為 exp 的下標(biāo)， top 作為 st 的下標(biāo) */ while ((ch=exp[t+1])!=39。\039。) { if(ch=39。039。 amp。amp。 ch=39。939。)/*為數(shù)字字符時(shí)轉(zhuǎn)換為數(shù)字 */ { d=0。 do { d=10*d+ch39。039。 }while((ch=exp[t++])!=39。39。)。 top++。st[top]=d。/*數(shù)字進(jìn)棧 */ } else /*為運(yùn)算符時(shí)，計(jì)算并退棧 */ { switch(ch) { case39。+39。:st[top1]=st[top1]+st[top]。break。 22 case39。39。:st[top1]=st[top1]st[top]。break。 case39。*39。:st[top1]=st[top1]*st[top]。break。 case39。/39。:if(st[top]!=0) st[top1]=st[top1]/st[top]。 else return 0。/*除 0 錯(cuò)誤 */ break。 } top。 } } (*n)=st[top]。 return 1。 } void main() { char str[MaxLen]。/*存儲(chǔ)原算術(shù)表達(dá)式 */ char exp[MaxLen]。/*存儲(chǔ)轉(zhuǎn)換成的波蘭表達(dá)式 */ int n。 printf(算術(shù)表達(dá)式 : )。 scanf(%s,amp。str)。 if(trans(str,exp)==0) printf(原算術(shù)表達(dá)式不正確 \n)。 else { printf(波蘭表達(dá)式 : %d\n,exp)。 if(pvalue(exp,amp。n)==1) printf(計(jì)算結(jié)果 : %d\n,n)。 else printf(計(jì)算錯(cuò)誤 \n)。 } } 練習(xí) /*已知 Ackerman 函數(shù)的定義如下： Akm(m,n)=n+1(m=0),akm(m1,1)(m!=0,n=0) akm(m1),akm(m,n1))(m!=0,n!=0) ； 2。寫(xiě)出非遞歸算法； 3。根據(jù)非遞歸算法，畫(huà)出求 akm(2,1)時(shí)棧的變化過(guò)程 */ include define MaxLen 5000/*此數(shù)應(yīng)足夠大，因?yàn)?m和 n值的較小增長(zhǎng)會(huì)引起函數(shù)值的極快增長(zhǎng)，用的棧的空間也很大 */ int f1(int m,int n) { if(m==0) return n+1。 else if(n==0) return f1(m1,1)。 23 else return f1(m1,f1(m,n1))。 } int no(int m,int n) { if(m==0) return 1。 else if(n==0) return 2。 else return 3。 } int f2(int m,int n) { int st[MaxLen][4],top=1,m1,n1。 st[top][0]=no(m,n)。 st[top][1]=0。/*初值 0 進(jìn)棧 */ st[top][2]=m。/*初值 m 進(jìn)棧 */ st[top][3]=n。/*初值 n 進(jìn)棧 */ do /*開(kāi)始循環(huán) */ { if(st[top][1]==0)