1、實(shí)驗(yàn)（二）實(shí)驗(yàn)名稱棧與隊(duì)列應(yīng)用軟件環(huán)境Windows98/2000, VC+6.0或turbo C硬件環(huán)境P以上微型計(jì)算機(jī)實(shí)驗(yàn)?zāi)康睦斫鈼：完?duì)列的邏輯特點(diǎn)，掌握棧或隊(duì)列基本操作的實(shí)現(xiàn)，能運(yùn)用棧或隊(duì)列解決實(shí)際應(yīng)用問題。實(shí)驗(yàn)內(nèi)容（應(yīng)包括實(shí)驗(yàn)題目、實(shí)驗(yàn)要求、實(shí)驗(yàn)任務(wù)等）所謂回文，是指從前向后順讀和從后向前倒讀都一樣的字符串。例如，did pop I was able,elba saw I 等等。 編寫程序，實(shí)現(xiàn)一個棧，并利用它判斷一個字符串是否是回文。實(shí)驗(yàn)過程與實(shí)驗(yàn)結(jié)果（可包括實(shí)驗(yàn)實(shí)施的步驟、算法描述、流程、結(jié)論等）實(shí)驗(yàn)步驟及算法描述和流程：1. 創(chuàng)建有關(guān)順序棧的基本運(yùn)算函數(shù)棧底的位置固定不變，棧頂?shù)?/p>

2、位置隨著進(jìn)棧和退棧操作而動態(tài)變化，所以順序棧需要一個變量top來指示當(dāng)前棧頂?shù)奈恢谩?.1 初始化棧為順序棧分配連續(xù)的?？臻g，同時置空棧；1.2 判斷棧是否為空?？諚?biāo)志為：棧頂指針=棧底指針；1.3 銷魂棧棧為空則返回1，否則返回0；1.4 進(jìn)棧操作首先判斷棧的狀態(tài)，若未滿，則top+1，然后將入棧元素置于棧頂指針top所指的存儲單元中，使之指向新的棧頂，若棧滿，發(fā)生“上溢”，程序退出。1.5 退棧操作首先判斷棧的狀態(tài)，若不空，則top-1，使其指向新的棧頂，若為空，發(fā)生“下溢”，程序退出。2. 運(yùn)用順序棧結(jié)構(gòu)實(shí)現(xiàn)回文問題使用棧，將字符串的前一半入棧，再依次出棧，與后一半進(jìn)行比較，若不相等，

3、則不是回文，否則是回文2.1 初始化棧s；2.2 利用i記錄循環(huán)次數(shù)，i的初始值為1，循環(huán)直到i=字符串的一半時結(jié)束字符串下標(biāo)為i的字符依次入棧。2.3 若字符串長度為偶數(shù)，i值不變，否則i+1；2.4 利用while循環(huán)，依次比較下標(biāo)為i的字符串中的字符與出棧元素是否相等，以j=1，作為標(biāo)志，若不等j=0并打斷循環(huán)2.5 返回j的值，j=1，則字符串是回文，否則不是回文3. 主函數(shù)3.1 首先輸入字符串的長度，然后依次輸入字符；3.2 輸出字符串；3.3 調(diào)用函數(shù)判斷字符串是否是回文。結(jié)論：實(shí)驗(yàn)中，輸入字符串長度3，輸入字符串did，輸出did是回文 輸入字符串長度21，輸入字符串I was

4、 able，elba saw I，輸出I was able，elba saw I 是回文。實(shí)驗(yàn)中曾出現(xiàn)的問題，在主函數(shù)字符串的輸入以下標(biāo)0開始，可是下標(biāo)為0的字符卻不是輸入的第一個字符，輸入是從下標(biāo)為1的字符開始，改正后，字符的輸出和入棧都從下標(biāo)為1的字符開始。附錄（可包括源程序清單或其它說明）#include#include#define StackInitSize 100typedef struct /順序棧的儲存結(jié)構(gòu)char dataStackInitSize;int top;SeqStack;SeqStack *InitStack() /棧的初始化SeqStack *s;s=(SeqS

5、tack *)malloc(sizeof(SeqStack);if(s!=NULL)s-top=-1;return s;else printf(沒有足夠的內(nèi)存空間，申請失敗，程序運(yùn)行終止！n); exit(0);int IsEmpty(SeqStack *s) /判斷棧是否為空return (s-top=-1)?1:0;void DestroyStack(SeqStack *s) /銷毀棧free(s);printf(棧已銷毀！n);void Push(SeqStack *s,char x) /進(jìn)棧if(s-top=StackInitSize)printf(棧滿！程序運(yùn)行終止！n);exit(

6、0);elses-top+;s-datas-top=x;char Pop(SeqStack *s) /退棧char temp;if(IsEmpty(s)printf(?？?！程序運(yùn)行終止！n);exit(0);elsetemp=s-datas-top;s-top-;return temp;int judge_huiwen(char a,int n) /判斷一個字符串是否是回文SeqStack *s;s=InitStack();int i=1,j=1;while(i=n/2)Push(s,ai);i+;if(n%2!=0)i+;while(i=n&j=1)if(ai=Pop(s)i+;elsej=0;break;return j;void main()char a100;int i=0,n;printf(請先輸入一個字符串的長度：);scanf(%d,&n);printf(請輸入字符串：);for(i=0;i=n;i+)scanf(%c,&ai);for(i=1;i=n;i+) printf(%c,ai);if(judge_huiwen(a,n)printf(是回文。n);else printf(不是回文。n);運(yùn)行結(jié)果： 天津理工大學(xué)計(jì)算機(jī)科學(xué)與工程系實(shí)驗(yàn)報(bào)告2011 至 20