天津理工大學數據結構實驗報告

1、實驗（二）實驗名稱棧與隊列應用軟件環(huán)境Windows98/2000, VC+6.0或turbo C硬件環(huán)境P以上微型計算機實驗目的理解棧和隊列的邏輯特點，掌握?；蜿犃谢静僮鞯膶崿F，能運用?；蜿犃薪鉀Q實際應用問題。實驗內容（應包括實驗題目、實驗要求、實驗任務等）所謂回文，是指從前向后順讀和從后向前倒讀都一樣的字符串。例如，did pop I was able,elba saw I 等等。 編寫程序，實現一個棧，并利用它判斷一個字符串是否是回文。實驗過程與實驗結果（可包括實驗實施的步驟、算法描述、流程、結論等）實驗步驟及算法描述和流程：1. 創(chuàng)建有關順序棧的基本運算函數棧底的位置固定不變，棧頂的

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

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

4、 able，elba saw I，輸出I was able，elba saw I 是回文。實驗中曾出現的問題，在主函數字符串的輸入以下標0開始，可是下標為0的字符卻不是輸入的第一個字符，輸入是從下標為1的字符開始，改正后，字符的輸出和入棧都從下標為1的字符開始。附錄（可包括源程序清單或其它說明）#include#include#define StackInitSize 100typedef struct /順序棧的儲存結構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); 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) /進棧if(s-top=StackInitSize)printf(棧滿！程序運行終止！n);exit(

6、0);elses-top+;s-datas-top=x;char Pop(SeqStack *s) /退棧char temp;if(IsEmpty(s)printf(棧空！程序運行終止！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);運行結果： 天津理工大學計算機科學與工程系實驗報告2011 至 20