實(shí)驗(yàn)棧的順序表示和實(shí)現(xiàn)

1、浙江大學(xué)城市學(xué)院實(shí)驗(yàn)報(bào)告課程名稱(chēng) 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 實(shí)驗(yàn)項(xiàng)目名稱(chēng) 實(shí)驗(yàn)七 棧的順序表示和實(shí)現(xiàn) 實(shí)驗(yàn)成績(jī) 指導(dǎo)老師（簽名 ） 日期 一. 實(shí)驗(yàn)?zāi)康暮鸵?、掌握棧的存儲(chǔ)結(jié)構(gòu)及其基本操作。學(xué)會(huì)定義棧的順序存儲(chǔ)結(jié)構(gòu)及其各種基本操作的實(shí)現(xiàn)。2、掌握棧的后進(jìn)先出原則。3、通過(guò)具體的應(yīng)用實(shí)例，進(jìn)一步熟悉和掌握棧在實(shí)際問(wèn)題中的運(yùn)用。二. 實(shí)驗(yàn)內(nèi)容1、設(shè)棧采用順序存儲(chǔ)結(jié)構(gòu)（用動(dòng)態(tài)數(shù)組），請(qǐng)編寫(xiě)棧的各種基本操作的實(shí)現(xiàn)函數(shù)，并存放在頭文件test7.h中。同時(shí)建立一個(gè)驗(yàn)證操作實(shí)現(xiàn)的主函數(shù)文件test7.cpp，編譯并調(diào)試程序，直到正確運(yùn)行。 提示： 棧的動(dòng)態(tài)數(shù)組順序存儲(chǔ)結(jié)構(gòu)可定義如下： struct Stack El

2、emType *stack ;/ 存棧元素 int top; / 棧頂指示器 int MaxSize; / 棧的最大長(zhǎng)度 ; 棧的基本操作可包括： void InitStack (Stack &S); /構(gòu)造一個(gè)空棧 S int EmptyStack (Stack S); /若棧S為空棧返回1，否則返回0 void Push(Stack &S, ElemType item); /元素 item進(jìn)棧 ElemType Pop(Stack &S); /棧S的棧頂元素出棧并返回 ElemType Peek(Stack S); /取棧S的當(dāng)前棧頂元素并返回 void Clear

3、Stack (Stack &S); /清除棧s，使成為空棧2、應(yīng)用：寫(xiě)一函數(shù)，判斷給定的字符串是否中心對(duì)稱(chēng)。如字符串“abcba”、“abccba”均為中心對(duì)稱(chēng)，字符串“abcdba”不中心對(duì)稱(chēng)。要求利用test7.h中已實(shí)現(xiàn)的有關(guān)棧的基本操作函數(shù)來(lái)實(shí)現(xiàn)。請(qǐng)把該函數(shù)添加到文件test7.cpp中的主函數(shù)前，并在主函數(shù)中添加相應(yīng)語(yǔ)句進(jìn)行測(cè)試。函數(shù)原型如下： int IsReverse(char *s) /判斷字符串S是否中心對(duì)稱(chēng)，是返回1，否則返回03、填寫(xiě)實(shí)驗(yàn)報(bào)告，實(shí)驗(yàn)報(bào)告文件取名為report7.doc。4、上傳實(shí)驗(yàn)報(bào)告文件report7.doc 、源程序文件test7.cpp及te

4、st7.h到Ftp服務(wù)器上（ 40:5000 ）自己的文件夾下。三. 函數(shù)的功能說(shuō)明及算法思路 （包括每個(gè)函數(shù)的功能說(shuō)明，及一些重要函數(shù)的算法實(shí)現(xiàn)思路）函數(shù)：void InitStack (Stack &S)功能：構(gòu)造一個(gè)空棧 S思路：采用動(dòng)態(tài)數(shù)組的方式新建一個(gè)大小為10的空棧S函數(shù)：int EmptyStack (Stack S)功能：判斷是否為空棧，若棧S為空棧返回1，否則返回0思路：以top值作為判斷條件，當(dāng)top為-1時(shí)表明為空棧，其他則為非空棧函數(shù)：void Push(Stack &S, ElemType item)功能：元素 item進(jìn)

5、棧思路：首先判斷棧是否已滿，若已滿則動(dòng)態(tài)申請(qǐng)空間將數(shù)組大小擴(kuò)大一倍，通過(guò)改變top的值確定入棧位置并將item入棧 函數(shù)：ElemType Pop(Stack &S)功能：棧S的棧頂元素出棧并返回思路：以top值減1的方式進(jìn)行出棧操作，并返回出棧的棧頂元素函數(shù)：ElemType Peek(Stack S)功能：取棧S的當(dāng)前棧頂元素并返回思路：返回當(dāng)前top所指的棧頂元素值函數(shù)：void ClearStack (Stack &S)功能：清除棧s，使成為空棧思路：釋放數(shù)組空間，置top為-1表示空棧，置MaxSize為0表示無(wú)空間函數(shù)（選作）：int IsReverse(char

6、*s)功能：判斷字符串S是否中心對(duì)稱(chēng)，是返回1，否則返回0思路：將字符串的前一半字符依次入棧，再全部出棧并依次與字符串后一半字符對(duì)比，只要有一個(gè)不相同，就說(shuō)明不是中心對(duì)稱(chēng)；全部相同，表明是中心對(duì)稱(chēng)四. 實(shí)驗(yàn)結(jié)果與分析（包括運(yùn)行結(jié)果截圖、結(jié)果分析等）棧操作部分測(cè)試數(shù)據(jù)：22 30 16 36 58 80 55結(jié)果分析：棧頂元素為55，正確；3次出棧元素依次為55 80 58，正確；出棧操作完成后棧頂元素為36，證明出棧操作成功。選作部分測(cè)試數(shù)據(jù)：abcba結(jié)果分析：輸出判斷為YES，是中心對(duì)稱(chēng)，正確。棧操作部分測(cè)試數(shù)據(jù)：42 5 -2結(jié)果分析：棧頂元素為-2，正確；2次出棧元素依次為-2 5，正確；出棧操作完成后棧頂元素為42，證明出棧操作成功。選作部分測(cè)試數(shù)據(jù)：abccba結(jié)果分析：輸出判斷為YES，是中心對(duì)稱(chēng)，正確。棧操作部分測(cè)試數(shù)據(jù)：28 36 42 44 65 65 74 80結(jié)果分析：棧頂元素為80，正確；3次出棧元素依次為80 74 65，正確；出棧操作完成后棧頂元素為6