《數(shù)據(jù)結構》后綴表達式實驗報告

1、瓊州學院實驗報告課程名稱數(shù)據(jù)結構實驗項目名稱用順序棧/鏈棧解決堆棧問題實驗項目序號2實驗類型設計性實驗地點6607專業(yè)班級09數(shù)媒實驗日期2011/3/24指導教師簽名姓名牛澤杰學號09217032成績評定一、實驗目的1、掌握接口、范型的定義及使用方法；2、掌握堆棧的定義及實現(xiàn)方法；3、運用堆棧解決問題。二、實驗內容及要求（選作1題）實驗內容1：一列貨運列車共有n節(jié)車廂，重新排列車廂，使各車廂從前至后按編號1到n的次序排列。我們在一個轉軌站里完成車廂的重排工作，在轉軌站中有一個入軌、一個出軌和k個緩沖鐵軌（位于入軌和出軌之間）。圖3.1a 有k= 3個緩沖鐵軌h1，h2和h3。開始時，n節(jié)車廂

2、的貨車從入軌處進入轉軌站，轉軌結束時各車廂從右到左按照編號1至編號n的次序離開轉軌站。 根據(jù)上面的描述，編寫程序實現(xiàn)下面的功能： 1）編寫一算法實現(xiàn)火車車箱的重排； 2）編寫程序模擬具有9節(jié)車廂的火車入軌和出軌的過程。實驗內容2：后綴表達式就是把運算符置于操作數(shù)之后的表示法。編寫程序實現(xiàn)下面的功能：1）編寫算法計算后綴表達式的值；2）顯示后綴表達式的計算過程。要求：1）使用數(shù)組或鏈表以及c#接口和范型技術實現(xiàn)通用的堆棧功能；2）利用1）實現(xiàn)堆棧，并完成相應功能。三、實驗設備環(huán)境儀器：計算機；實驗環(huán)境：microsoft visual studio 2008四、實驗原理1、堆棧接口定義及說明；i

3、nterface istack void push(t item); /入棧操作 將指定類型元素item進到棧中。 t pop(); /出棧操作 將棧中的棧頂元素取出來，并在棧中刪除棧頂元素。 t gettop(); /取棧頂元素 將棧中的棧頂元素取出來，棧中的元素不變。 int getlength(); /求棧的長度 獲得棧的長度。 bool isempty(); /判斷棧是否為空 若棧為空，返回true，否則返回flase。 void clear(); /清空操作 從棧中清除所有的數(shù)據(jù)元素。 2、范型順序棧/鏈棧實現(xiàn)堆棧接口；順序棧（seqstack）定義了三個字段:data,maxsiz

4、e,top. private int maxsize; /順序棧的容量 private t data; /數(shù)組，用于存儲順序棧中的數(shù)據(jù)元素private int top; /指示順序棧的棧頂順序棧（seqstack）的存儲結構用一維數(shù)組來表示。數(shù)組的元素使用泛型，以實現(xiàn)不同數(shù)據(jù)類型的線性棧間代碼的重用。用字段maxsize來表示順序棧（seqstack）的最大長度容量；設置一個變量top表示棧頂，top隨著插入和刪除而變化，top的范圍是0到maxsize-1，如果順序棧為空，top = -1。3、主程序流程圖。開 始初 始 化public seqsetack (int size)輸 入 串s

5、tring s1=終止printf/pop a,bpopa+bprintf*pop a,bpopa+bprintf-pop a,bpopa+bprintf+pop a,bpopa+bprintf數(shù) 字入棧 push判斷數(shù)字或操作符switch case+ - * / =五、實驗步驟及調試分析1、定義接口istackinterface istack2、定義一個可容納100個元素的順序棧seqstack。istack st = new seqstack(100);3、輸入一個字符串 console.writeline(請輸入一個字符串：); string s1 = convert.tostring

6、(console.readline();按f10的調試結果4、輸入數(shù)字12default: double d1 = convert.todouble(s1); st.push(d1); console.writeline(輸出數(shù)據(jù)是0, d1); break;經(jīng)過判斷實現(xiàn)入棧操作，將數(shù)字12 壓入棧中。并進行判斷順序棧是否為滿的操作。按f10調試結果5、輸入數(shù)字4。6、輸入符號“+”case +: console.writeline(輸入的是操作符0, s1); b = st.pop(); a = st.pop(); st.push(a + b);輸入的是符號，則完成將12,4彈出順序棧的操作

7、，并向棧中壓入12+4的結果。然后還需判斷棧是否為滿。7、輸入后面的數(shù)字和符號。操作同上。8、輸入符號“=”while (s1 != =)double c = st.pop();輸入等號后，將最后的值彈出順序棧。判斷棧是否是空，是否為滿。最后輸出結果15.六、實驗結果及分析通過利用順序棧實現(xiàn)后綴表達式。棧的主要特點“后進先出”，即后進棧的元素先出來。七、附錄：源程序namespace stackds interface istack void push(t item); /入棧操作 t pop(); /出棧操作 t gettop(); /取棧頂元素 int getlength(); /求棧的長

8、度 bool isempty(); /判斷棧是否為空 void clear(); /清空操作 console.writeline(請輸入一個字符串：); string s1 = convert.tostring(console.readline(); while (s1 != =) switch (s1) case +: console.writeline(輸入的事操作符0, s1); b = st.pop(); a = st.pop(); st.push(a + b); break; case -: console.writeline(輸入的事操作符0, s1); b = st.pop(); a = st.pop(); st.push(a - b); break; case *: console.writeline(輸入的事操作符0, s1); b = st.pop(); a = st.pop(); st.push(a * b); break; case /: console.writeline(輸入的事操作符0, s1); b = st.pop(); a = st.pop(); st.push(a / b); break; default: double d1 = convert.todouble(s1);