1、精選優(yōu)質(zhì)文檔-傾情為你奉上*實驗題目：棧的基本運算 實驗者信息：班級 ，姓名 龐文正，學號 實驗完成的時間 3：00*一、 實驗目的1，掌握棧的各種存儲結構及基本運算的實現(xiàn)。2，掌握堆棧后進先出的運算原則在解決實際問題中的應用。3，復習c語言中相關語句及函數(shù)的用法。二、 實驗內(nèi)容括號配對檢查。試設計一個程序對任意輸入的語句或數(shù)學表達式，判斷其括號是否匹配。若匹配，則返回1，否則返回0。調(diào)試程序并對相應的輸出作出分析；修改輸入數(shù)據(jù)，預期輸出并驗證輸出的結果。加深對算法的理解。三、 算法設計與編碼1. 本實驗用到的理論知識總結本實驗用到的理論知識，實現(xiàn)理論與實踐相結合?？偨Y盡量簡明扼要，并與本次實

2、驗密切相關，最好能加上自己的解釋。2. 算法概要設計給出實驗的數(shù)據(jù)結構描述，程序模塊、功能及調(diào)用關系首先建立一個棧結構，且初始化棧為空。然后由鍵盤上隨即輸入一個帶括號的語句或帶括號的數(shù)學表達式，同時將它們保存在一個字符型數(shù)組exps中。掃描表達式exps,當遇到“(”、“”、“”時，將其入棧。遇到“）”、“”、“”時，判斷棧頂是否有相匹配的括號。若沒有，則退出掃描過程，返回0，否則直到exps掃描完畢為止。若top為0，則返回1。#include#define MAXSIZE 100#define TRUE 1#define FALSE 0typedef int datatype; typed

3、ef struct /順序棧的結構體定義 datatype stackMAXSIZE;int top;seqstack;void setnull(seqstack *s) /置空棧-由于c語言的數(shù)組下標是從0開始的，所以置 s-top=-1; / s-top=-1; 空棧操作時將棧頂指針放在下標為0之前，即-1處。int empty(seqstack *s) /*判斷當前棧是否為空棧*/ if(s-toptop=MAXSIZE-1) printf(stack overflow!n); /*發(fā)生上溢*/ return FALSE; else s-stack+s-top=x; /*棧頂指針上移，數(shù)

4、據(jù)元素入棧*/ return TRUE; datatype pop(seqstack *s) /*彈出當前棧s的棧頂元素*/ if(s-toptop-; return(s-stacks-top+1); /由于return語句的特點，必須先使top減1，然后再執(zhí)行return語句。而此 / 時棧頂元素的表示應該為s-top+1.int judge(seqstack *s) /括號匹配檢查算法。-遇到(、時, / 將其壓 棧s中。 datatype symb,ch,store; push(s,#); symb=getchar();/*從鍵盤接受字符*/ while(symb!=#) switch(

5、symb) case (: case : case : push(s,symb);break; case ): ch=pop(s); if(ch!=() return FALSE; break; case : ch=pop(s); if(ch!=) return FALSE; break; case : ch=pop(s); if(ch!=) return FALSE; break; default: ; symb=getchar(); if(pop(s)=#) return TRUE; else return FALSE; int jinzhishuchu(seqstack *s) int

6、x,symb; scanf(%d,&symb);/*從鍵盤接受字符*/ while(symb!=0) push(s,symb%8); symb=symb/8; while (!empty(s) x=pop(s); /出棧操作 printf(%d,x); /依次輸出出棧結果 printf(n); main() seqstack q; setnull(&q); printf(please input an express end with symbol #:n); if(judge(&q) printf(yesn); /*括號匹配，則輸出yes*/ else printf(non); /*括號不匹

7、配，則輸出no*/jinzhishuchu(&q); 四、 運行與測試（1） 在調(diào)試程序的過程中遇到什么問題，是如何解決的？答：遇到很多括號不匹配（2） 設計了那些測試數(shù)據(jù)？測試結果是什么？（3） 程序運行的結果如何？成功運行！1、 預習思考題調(diào)試好上述程序后，試著完成以下拓展內(nèi)容：（1） 假定表達式不是通過getchar()函數(shù)一個個傳送的，而是存放在一個字符數(shù)組An中，程序需要做哪些改變？將while改為for（i=0;i=strlen(An);i+）switch(Ai) case (: case : case : push(s,symb);break; case ): ch=pop(s)

8、; if(ch!=() return FALSE; break; case : ch=pop(s); if(ch!=) return FALSE; break; case : ch=pop(s); if(ch!=) return FALSE; break; default: ; （2） 在judge()函數(shù)中，如果不用switch()函數(shù)，你會怎么處理？用if替代 if(symb=( | symb= | symb=) push(s,symb); if(symb=) ch=pop(s); if(ch!=() return FALSE; if(symb=) ch=pop(s); if(ch!=) return FALSE; if(symb=) ch=pop(s); if(ch!=) return FALSE; 2、 分析討論題：數(shù)制轉換問題是棧應用的一個典型實例。將十進制數(shù)轉換成其它進制的數(shù)有一種簡單的方法：例：十進制轉換成八進制：(66)10=(102)866/8=8 余 28/8=1 余 01/8=0 余 1結果為余數(shù)的逆序:102 。如果用棧的算法來實現(xiàn)，怎樣實現(xiàn)？其基本原理是什么？int jinzhishuchu(seqstack *s) /括號匹配檢查算法。-遇到(、時, int x,symb; scanf(%d,&symb);/*從鍵盤接受字符*/ while(s