數據結構C語言回文判斷(運用棧以及隊列完成)

1、數據結構實驗報告回文判斷班 級：學號：學生姓名 ：指導教師：時間：2015年5月5日1實驗目的：熟悉棧和隊列的各項操作，區(qū)別棧和隊列的操作原理。2實驗內容：利用棧的操作完成讀入的一個以結尾的字符序列是否是回文序列的判斷.回文序列即正讀與反讀都一樣的字符序列;例如:123&321是; 123&4321、123&312不是算法思想：從鍵盤上讀取一個字符，同時存儲在順序棧與鏈隊列之中，直到字符序列的最后一個字符為停止輸入，因為要滿足特定的要求：序列1&序列2，故設置夜歌標記量falg=1,判斷輸入的元素個數是否為奇數個，若為偶數個則令flag=0，若為奇數個繼續(xù)判斷棧的中間元素是否為&,若不是則令f

2、lag=0，若是，將棧和隊列中的元素依次出列，判斷是否相等，若不相等則令flag=0,最后將flag的值返回給主函數，若flag被修改為0說明不是回文序列，否則反之！判斷回文序列的流程圖：初始化棧inits(&s)初始化隊列initq(&q)當ch!=時ch=getch()y ch!= nprintf(%c,ch)push(&s,ch)enter(&q,ch) m+y m%2!=0 n y s-em/2=& n flag=0 i=1當i(m+1)/2時flagpop(&s,&ch1)=0deleteq(&q,&ch2)y ch1!=ch2 nflag=0 i+retun(flag)算法實現：（

3、1）void initstack(seqstack *s)：棧初始化模塊，即初始化一個空棧，隨后對該空棧進行數據的寫入操作；（2）int push(seqstack *s,char ch)：入棧操作，即給空棧中寫入數據；（3）int pop(seqstack *s,char *x)：出棧操作，即將棧中的數據輸出，由于棧的操作是先進后出，因此，出棧的數據是原先輸入數據的逆序；（4）void initquene(linkq *q)：隊列初始化，即初始化一個空隊列，最后對該空隊列進行數據的寫入操作；（5）int enter(linkq *q,char ch)：入隊操作，即給空隊列中寫入數據；（6）i

4、nt deleteq(linkq *q,char *c)：出隊操作，即將隊列中的數據輸出，由于隊列的操作是先進先出，因此，出隊的數據室原先輸入數據的正序；（7）int huiwen(seqstack s,linkq q)：輸入序列并判斷所輸入的序列是否是回文序列；（8）void main()：主函數，用于調用前面的模塊，并輸出最終的判斷結果。3實驗感想與體會通過本次的上機，對棧的各項基本操作都有了更好的掌握，同時明白了一些小的細節(jié)問題可能會影響到整個程序的正確的運行，本次的實驗我通過了運用棧和隊列，可以說對隊列的一些基本的操作也得以了鞏固和提高！更加體會到，自己寫程序上機操作的重要性，它要比課

5、本上學的要多得多！4附錄（源代碼及運行圖）#include #include #define max 100typedef struct/棧結構體char emax;int top;seqstack;typedef struct node/隊列結構體char d;struct node *next;linkqn;typedef struct/封裝頭指針為指針linkqn *front;linkqn *rear;linkq;void initstack(seqstack *s)/初始化順序棧s-top=-1;int push(seqstack *s,char ch)/入棧if(s-top=max

6、-1)return(0);s-top+;s-es-top=ch;return(1);int pop(seqstack *s,char *x)/出棧if(s-top=-1)return(0);else*x=s-es-top;s-top-;return(1);void initquene(linkq *q)/鏈隊列初始化q-front=(linkqn *)malloc(sizeof(linkqn);if(!q-front)printf(分配空間失敗!);q-rear=q-front;q-front-next=null;int enter(linkq *q,char ch)/入隊linkqn *np

7、;np=(linkqn *)malloc(sizeof(linkqn);if(!np)return(0);np-d=ch;np-next=null;q-rear-next=np;q-rear=np;return(1);int deleteq(linkq *q,char *c)/出隊linkqn *p;if(q-front=q-rear)return(0);p=q-front-next;q-front-next=p-next;if(q-rear=p)q-rear=q-front;*c=p-d;free(p);return(0);int huiwen(seqstack s,linkq q)/回文判

8、斷int flag=1,m=0,t=1;int i;char ch1,ch2,ch;initstack(&s);initquene(&q);printf(請輸入字符序列當輸入字符時輸入結束:n);while(ch!=)ch=getchar();if(ch!=)printf(%c,ch);push(&s,ch);enter(&q,ch);m+;printf(n輸入完成!n);getchar();if(m%2)if(s.em/2=&)for(i=1;i(m+1)/2;i+)pop(&s,&ch1);deleteq(&q,&ch2);if(ch1!=ch2)flag=0;else flag=0;else flag=0