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