回文判斷的算法實驗報告

1、.實驗題目一、一、 需求分析需求分析.回文判斷的算法.1程序的功能:實現(xiàn)對字符序列是否是一個回文序列的判斷2輸入輸出的要求:從鍵盤讀入一組字符序列， 判斷是否是回文， 并將結(jié)果顯示在屏幕上3測試數(shù)據(jù):回文字符序列輸入：非回文字符序列輸入：二、二、 概要設(shè)計概要設(shè)計1本程序所用的抽象數(shù)據(jù)類型的定義:typedef struct char itemstacksize; int top;.sqstack;typedef struct qnode char data; struct qnode *next;lqnode, *pqnode;typedef struct pqnode front,rear

2、; linkqueue;2主程序的流程及各程序模塊之間的層次關(guān)系。（1）int initstack(sqstack *s)：棧初始化模塊，即初始化一個空棧，隨后對該空棧進(jìn)行數(shù)據(jù)的寫入操作；（2）int push(sqstack *s, char data) ：入棧操作，即給空棧中寫入數(shù)據(jù)，數(shù)據(jù)長度有宏定義給出；（3）int pop(sqstack *s, char *data) ：出棧操作，即將棧中的數(shù)據(jù)輸出，由于棧的操作是先進(jìn)后出，因此，出棧的數(shù)據(jù)是原先輸入數(shù)據(jù)的逆序；（4）int initqueue(linkqueue *q)：隊列初始化，即初始化一個空隊列，最后對該空隊列進(jìn)行數(shù)據(jù)的寫入操

3、作；（5）int enqueue(linkqueue *q, char item)：入隊操作， 即給空隊列中寫入數(shù)據(jù)， 數(shù)據(jù)長度一樣有宏定義給出；.（6）int dequeue(linkqueue *q, char *item) ：出隊操作， 即將隊列中的數(shù)據(jù)輸出， 由于隊列的操作是先進(jìn)先出，因此，出隊的數(shù)據(jù)室原先輸入數(shù)據(jù)的正序；（7）int main()：主函數(shù)，用于調(diào)用前面的模塊，進(jìn)行出隊數(shù)據(jù)與出棧數(shù)據(jù)的比較， 判斷輸入的序列是否是回文序列。模塊之間關(guān)系及其相互調(diào)用的圖示：三、三、 詳細(xì)設(shè)計詳細(xì)設(shè)計1采用 c 語言定義相關(guān)的數(shù)據(jù)類型.整形，字符型，指針類型，聚合類型，自定義類型2寫出各模塊

4、的偽碼算法:參照源程序（1）int initstack(sqstack *s)（2）int push(sqstack *s, char data)（3）int pop(sqstack *s, char *data)（4）int initqueue(linkqueue *q)（5）int enqueue(linkqueue *q, char item)（6）int dequeue(linkqueue *q, char *item)四、四、 調(diào)試分析調(diào)試分析1調(diào)試中遇到的問題及對問題的解決方法:問題：程序出現(xiàn)未知錯誤。方法： 在感覺容易出錯的地方或者是已經(jīng)出錯的地方前面打斷點，進(jìn)一步調(diào)試。2算法的

5、時間復(fù)雜度和空間復(fù)雜度。時間復(fù)雜度：t（n） = o（n）五、五、 使用說明及測試結(jié)果使用說明及測試結(jié)果回文字符輸入：非回文字符輸入：.六、六、 源程序（帶注釋）源程序（帶注釋）#include #include #include #define stacksize 100typedef struct char itemstacksize; int top;sqstack;/*順序棧的定義*/typedef struct qnode char data; struct qnode *next;lqnode, *pqnode;typedef struct. pqnode front,rear;

6、linkqueue;/*鏈隊列的定義*/int initstack(sqstack *s);/*初始化順序棧*/int stackempty(sqstack s);/*判斷是否為空棧*/int push(sqstack *s, char data);/*入棧*/int pop(sqstack *s, char *data);/*出棧*/int initqueue(linkqueue *q);/*初始化鏈隊列*/int queueempty(linkqueue q);/*判斷是否為空隊列*/int enqueue(linkqueue *q, char item);/*入隊*/int dequeu

7、e(linkqueue *q, char *item);/*出隊*/int traversequeue(linkqueue q);/*遍歷*/int initstack(sqstack *s) /*初始化順序棧*/s-top = -1; return 1;int stackempty(sqstack s)/*判斷是否為空棧*/. if(s.top = -1) return 1; else return 0;int push(sqstack *s, char data)/*入棧*/ if(s-top = stacksize - 1) printf(n 棧已滿，不能完成入棧操作！); return

8、 0; s-top+; s-items-top = data; return 1;int pop(sqstack *s, char *data)/*出棧*/ if (s-top = -1) printf(n 堆棧已空，不能完成出棧操作！);. return 0; *data = s-items-top; s-top-; return 1;int initqueue(linkqueue *q)/*初始化鏈隊列*/ q-front=q-rear(pqnode)malloc(sizeof(lqnode); if(!q-front)printf(n 初始化隊列失?。?;return 0; q-fron

9、t-next = null; return 1;.=.int queueempty(linkqueue q)/*判斷是否為空隊列*/ if (q.front = q.rear)printf(n 隊列為空！);return 1; else return 0;int enqueue(linkqueue *q, char item)/*入隊*/ pqnode p; p = (pqnode)malloc(sizeof(lqnode); if(!p) printf(n 內(nèi)存分配失敗); return 0; p-data = item;. p-next = null; q-rear-next = p; q

10、-rear = p; return 1;int dequeue(linkqueue *q, char *item)/*出隊*/ pqnode p; if(q-front = q-rear) printf(n 隊列已空，不能出隊); return 0; p = q-front-next; *item = p-data; q-front-next = p-next; free(p); if(q-rear = p) /*若刪除的為最后一個結(jié)點，移動隊尾指針*/ q-front = q-rear;. return 1;int traversequeue(linkqueue q)/*遍歷*/ pqnod

11、e pos; if(q.front = q.rear) printf(n 隊列為空！); return 0; pos = q.front-next; printf(nhere is the string:); while(pos != null) printf(%c, pos-data); pos = pos-next; printf(n); return 1;.int main() int i,len,count1 = 0; char str1100,ch,ch1; linkqueue lq1,lq2; sqstack sq; printf(請輸入字符:); scanf(%s, &str1); len = strlen(str1); initqueue(&lq1); initqueue(&lq2); initstack(&sq); for(i=0;ilen;i+) enqueue(&lq1,str1i); traversequeue(lq1); for(i=0;ilen;i+) . dequeue(&lq1,&ch); push(&sq,ch); enqueue(&lq1,ch); for(i=0;ilen;i+) pop(&sq,&ch); enqueue(&lq2,c