【文章內(nèi)容簡介】 2個數(shù)據(jù)元素交換位置，......，依次類推，直到所有元素都交換了位置，則就地逆置的過程就完成了。算法簡單描述如下：templateclass Elem void AlistElem::reverlist( ){ int i。 for(i=0。 ilistSize/2。 i++) {listArray[listSize+1]=listArray[i]。//將第 listSize+1 號單元作為中間存儲單元listArray[i]=listArray[listSizei1]。listArray[listSizei1]= listArray[listSize+1]。}}思考：當基本隊列滿時應該如何處理？（2）鏈式存儲結構就地逆置為清楚對比基本線性表在逆置前后的變化，鏈式基本線性表的逆置過程可分為 4 個步驟進行：a) 創(chuàng)建包含若干個結點的鏈式基本線性表。利用 for 循環(huán)，從鍵盤上隨機輸入結點的個數(shù)和每個結點的數(shù)據(jù)域的值。b) 輸出創(chuàng)建成功的鏈式基本線性表。從表頭到表尾逐個輸出鏈表中所有結點的值。c) 逆置鏈式基本線性表。設鏈式基本線性表有一個頭結點，將鏈式基本線性表斷開成兩部分，第一部分為只有頭結點，第二部分為所有含有數(shù)據(jù)元素的結點。從第二部分中依次取出結點插入到第一部分的頭結點后；將第二部分所有結點插入到第一部分后，就完成了鏈式基本線性表的逆置（思考：問什么？）d) 輸出逆置后的鏈式基本線性表。核心算法簡單描述如下：template class Elem void class LList::reverlist(){ LinkElem* p,*q。 p=headnext。 headnext=NULL。//鏈式線性表分為兩部分 while(p!=NULL){ q=p。 p=pnext。 qnext=headnext。headnext=q。 }}[測試數(shù)據(jù)]由學生依據(jù)軟件工程的測試技術自己確定。注意測試邊界數(shù)據(jù)，如對空線性表進行逆置，以及當順序線性表表滿時進行逆置。[實現(xiàn)提示]（1） 基本線性表的輸入和輸出可以有不同的形式，但是基本線性表的特征不會改變，不管在實際問題中要求用何種形式對基本線性表進行輸入和輸出，首先必須確定基本線性表用何種存儲方式更為便利。（2） 在確定其存儲結構之后，該選用何種解決方案更容易編程實現(xiàn)、更能有效地組織數(shù)據(jù)，也是在編程之前應該考慮的事情。 [選作內(nèi)容]無。實驗項目 5——數(shù)制轉(zhuǎn)換 實驗目的僅僅認識到棧是一種特殊的線性表是遠遠不夠的，本次實習的目的在于使讀者深入了解棧的特征，以便在實際問題背景下靈活運用它們；同時還將鞏固這種結構的構造方法，接觸較復雜問題的遞歸算法設計。 實驗內(nèi)容[問題描述]十進制 N 和其它進制數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題,其解決方法很多,其中一個簡單算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div 為整除運算,mod 為求余運算) 例如 (1348)10=(2504)8，其運算過程如下：n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2從中我們可以看出，最先產(chǎn)生的余數(shù) 4 是轉(zhuǎn)換結果的最低位，這正好符合棧的特性即后進先出的特性。所以可以用順序棧來模擬這個過程。試編程實現(xiàn)將 10 進制數(shù)轉(zhuǎn)換成 N 進制數(shù)。 [基本要求] 對于鍵盤輸入的任意一個非負的十進制整數(shù)，打印輸出與其等值的八進制數(shù)。由于上述的計算過程是從低位到高位順序產(chǎn)生的八進制數(shù)的各個數(shù)位，而打印輸出，一般來說應從高位到地位進行，恰好和計算過程相反。因此可以先將計算過程中得到的八進制數(shù)的各位進棧，待相對應的八進制數(shù)的各位均產(chǎn)生以后，再使其按順序出棧，并打印輸出。即得到了與輸入的十進制數(shù)相對應的八進制數(shù)。 [算法描述]算法思想如下：當 N0 時重復 1，2 N≠0，則將 N % r 壓入棧 s 中 ，執(zhí)行 2。若 N=0，將棧 s 的內(nèi)容依次出棧，算法結束。 N / r 代替 N具體描述如下：void conversion( ) { Stackint s。 scanf (“%”,n)。 while(n){ (n%8)。 n=n/8。 } while(! (e)){ printf(“%d”,e)。 } } [測試數(shù)據(jù)]由學生依據(jù)軟件工程的測試技術自己確定。注意測試邊界數(shù)據(jù)。[實現(xiàn)提示] 無。[選作內(nèi)容]無。實驗項目 6——回文判斷 實驗目的本次實習的目的在于進一步使讀者深入了解棧和隊列的特征，以便在實際問題背景下靈活運用它們；同時還將鞏固這兩種結構的構造方法，接觸較復雜問題的遞歸算法設計。 實驗內(nèi)容[問題描述]試寫一個算法，判斷依次讀入的一個以@為結束符的字母序列，是否為形如‘序列 1amp。序列 2’模式的字符序列。其中序列 1 和序列 2 中都不含字符‘a(chǎn)mp。’，且序列 2是序列 1 的逆序列。例如，‘a(chǎn)+bamp。b+a’是屬該模式的字符序列，而‘１+３amp。３－１’則不是。 [基本要求]對于鍵盤輸入的任意一個字符串，將其進行逆置，判斷原串和逆置的串是否完全一致，完全一致則為回文，因此分別利用隊列的先進先出（FIFO）和棧的后進先出（FILO）實現(xiàn)，算法只能使用一個棧和一個隊列以及若干簡單類型變量，算法時間復雜度應為 O(n)。 [算法描述]對于鍵盤輸入的任意一個字符串，將每一個字符分別進行如棧和入隊操作，字符串輸入完后，分別從隊列和堆棧中取出字符進行比較，一旦發(fā)現(xiàn)不同則輸入字符串不是回文，如果將所有字符比較結束后沒有發(fā)現(xiàn)一對字符不同，則輸入字符串為回文。具體算法簡單描述如下：bool palindrome( ){ Queue q=new Queue。// Stack s=new Stack。// while((c=getchar())!=EOF)//字符串輸入沒有結束 { (c)。 (c)。 } while((e)amp。amp。(f)) if(e!=f) return false。 return true。 }[測試數(shù)據(jù)]由學生依據(jù)軟件工程的測試技術自己確定。注意測試邊界數(shù)據(jù)，如序列 1 和序列 2 均為空串。[實現(xiàn)提示] 利用隊列的先進先出（FIFO）和棧的后進先出（LIFO）特點，將字符串中字符分別進行入棧和入隊操作，字符串輸入結束后將隊列和棧中字符依次取出，判斷取出的一對字符是否相同。[選作內(nèi)容]無。實驗項目 7——算術表達式求值演示 實驗目的本次實習的目的在于進一步使讀者深入了解棧和隊列的特征，以便在實際問題背景下靈活運用它們；同時還將鞏固這兩種結構的構造方法，接觸較復雜問題的遞歸算法設計。 實驗內(nèi)容[問題描述]表達式求值是實現(xiàn)程序設計語言的基本問題之一，也是棧的應用的一個典型例子。設計一個程序，演示用算符優(yōu)先法對算術表達式求值的過程。 [基本要求] 以字符序列的形式從終端輸入語法正確的、不含變量的整數(shù)表達式。按照算符優(yōu)先關系，實現(xiàn)對算術四則混合運算表達式的求值，并演示求值過程中運算符棧、運算數(shù)棧、輸入字符和主要操作的變化過程。 [算法描述]達式作為一個滿足表達式語法規(guī)則的串存儲，如表達式“3*2^（4+2*2１*3）5”,它的的求值過程為：自左向右掃描表達式，當掃描到 3*2 時不能馬上計算，因為后面可能還有更高的運算，正確的處理過程是：需要兩個棧：對象棧 s1 和算符棧 s2。當自左至右掃描表達式的每一個字符時，若當前字符是運算對象，入對象棧，是運算符時，若這個運算符比棧頂運算符高則入棧，繼續(xù)向后處理，若這個運算符比棧頂運算符低則從對象棧出棧兩個運算量，從算符棧出棧一個運算符進行運算，并將其運算結果入對象棧，繼續(xù)處理當前字符，直到遇到結束符。根據(jù)運算規(guī)則，左括號“（”在棧外時它的級別最高，而進棧后它的級別則最低了。 乘方運算的結合性是自右向左，所以，它的棧外級別高于棧內(nèi)。 就是說有的運算符棧內(nèi)棧外的級別是不同的。當遇到右括號“） ”時，一直需要對運算符棧出棧，并且做相應的運算，直到遇到棧頂為左括號“(” 時，將其出棧，因此右括號“ ） ”級別最低但它是不入棧的。對象棧初始化為空，為了使表達式中的第一個運算符入棧，算符棧中預設一個最低級的運算符“（” 。根據(jù)以上分析，每個運算符棧內(nèi)、棧外的級別如下：算符 棧內(nèi)級別 棧外級別*、/ 4 3+、 2 1( 0 5） 0 0運算規(guī)則如下：設兩個運算符： ?1 ， ?2， a ?1 b ?2 c?1 ?2, ?1 優(yōu)先權低于 ?2，不能運算?1= ?2, ?1 優(yōu)先權等于 ?2，結束或退括號?1 ?2, ?1 優(yōu)先權高于 ?2，可以運算算法簡單描述如下：設置兩個棧，分別存放操作數(shù)和運算符；輸入操作數(shù)時，一定不會運算；運算過程實際就是運算符號比較的過程OpendType EvaluateExpression( ) //表達式求值{StackOPTRType OPTR。( ‘’ )。StackOPNDType OPND。c = getchar( )。while( !(c == ‘’ amp。amp。 GetTop( OPTR ) == ‘’) ){if( ! In( c, OP )) // c 是運算符？,OP 是運算符集合{(c)。c = getchar( )。}else{ (OPTRType it)。switch( Precede (it,c)){case ‘’ :(c )。c = getchar( )。 break。case ‘=‘ : // c 為’)’(x)。c = getchar( )。 break。case ‘’: OPTR .Pop(t )。( b )。( a )。(Operate( a, t, b ))。break。}// switch}// if}// while(a)。}// EvaluateExpression [測試數(shù)據(jù)]3*（72） ；8； 1+2+3+4； 881*5； 1024/4*8； 1024/（4*8） ；（20+2）*（6/2 ） ； 333； 8/（99 ） ； 2*（6+2*（3+6*（6+6） ） ）[實現(xiàn)提示]（1） 設置運算符棧和運算數(shù)棧輔助分析算符優(yōu)先關系。（2） 在讀入表達式的字符序列的同時，完成運算符和運算數(shù)（整數(shù)）的識別處理，以及相應的運算。（3） 在識別出運算數(shù)的同時，要將其字符序列形式轉(zhuǎn)換成整數(shù)形式。（4） 在程序的適當位置輸出運算符棧、運算數(shù)棧、輸入字符和主要操作的內(nèi)容。[選作內(nèi)容]（1） 擴充運算符集，如增加乘方、單目減、賦值等運算。（2） 運算量可以是變量。（3） 運算量可以是實數(shù)類型。（4） 計算器的功能和仿真界面。實驗項目 8——迷宮問題 實驗目的本次實習的目的在于進一步使讀者深入了解棧和隊列的特征，以便在實際問題背景下靈活運用它們；同時還將鞏固這兩種結構的構造方法，接觸較復雜問題的遞歸算法設計。 實驗內(nèi)容[問題描述] 以一個 mn 的長方陣表示迷宮， 0 和 1 分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。[基本要求]首先實現(xiàn)一個以鏈表作為存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮的一個坐標，d 表示走到下一坐標的方向。如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1，1，1） ， （1，2，2） ，（2，2，2） ， （3，2，3） ， （3，1，2） ，……。 [算法描述]這是實驗心理學中的一個經(jīng)典問題，心理學家把一只老鼠從一個無頂蓋的大盒子的入口處趕進迷宮。迷宮中設置很多隔壁，對前進方向形成了多處障礙，心理學家在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達出口。求解思想：回溯法是一種不斷試探且及時糾正錯誤的搜索方法。下面的求解過程采用回溯法。從入口出發(fā)，按某一方向向前探索，若能走通（未走