回文判斷的算法實(shí)驗(yàn)報(bào)告

1、需求分析實(shí)驗(yàn)題目回文判斷的算法1 程序的功能實(shí)現(xiàn)對(duì)字符序列是否是一個(gè)回文序列的判斷2 輸入輸出的要求 :從鍵盤(pán)讀入一組字符序列， 判斷是否是回文， 并將結(jié)果 顯示在屏幕上3 測(cè)試數(shù)據(jù) :回文字符序列輸入：非回文字符序列輸入：概要設(shè)計(jì)1 本程序所用的抽象數(shù)據(jù)類(lèi)型的定義typedef structchar itemSTACKSIZE; int top;SqStack;typedef struct QNode char data;struct QNode *next;LQNode, *PQNode;typedef structPQNode front,rear; LinkQueue;2 主程序的流程

2、及各程序模塊之間的層次關(guān)系。(1) int InitStack(SqStack *S) ：棧初始化模塊，即初 始化一個(gè)空棧，隨后對(duì)該空棧進(jìn)行數(shù)據(jù)的寫(xiě)入操作；(2) int Push(SqStack *s, char data)：入棧操作，即給空棧中寫(xiě)入數(shù)據(jù)，數(shù)據(jù)長(zhǎng)度有宏定義給出；(3) int Pop(SqStack *s, char *data)：出棧操作，即將棧中的數(shù)據(jù)輸出，由于棧的操作是先進(jìn)后出， 因此，出 棧的數(shù)據(jù)是原先輸入數(shù)據(jù)的逆序；(4) int InitQueue(LinkQueue *q) ：隊(duì)列初始化，即初 始化一個(gè)空隊(duì)列，最后對(duì)該空隊(duì)列進(jìn)行數(shù)據(jù)的寫(xiě)入操作；(5) int E

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

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)試分析1 調(diào)試中遇到的問(wèn)題及對(duì)問(wèn)題的解決方法 : 問(wèn)題：程序出現(xiàn)未知錯(cuò)誤。方法：在感覺(jué)容易出錯(cuò)的地方或者是已經(jīng)出錯(cuò)的地方前 面打斷點(diǎn)，進(jìn)一步調(diào)試。2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度。時(shí)間復(fù)

5、雜度： T（n） = O （n）五、使用說(shuō)明及測(cè)試結(jié)果回文字符輸入：非回文字符輸入：六、源程序（帶注釋?zhuān)?include #include #include #define STACKSIZE 100 typedef structchar itemSTACKSIZE;int top;SqStack;/* 順序棧的定義 */typedef struct QNodechar data; struct QNode *next;LQNode, *PQNode;typedef structPQNode front,rear; LinkQueue;/* 鏈隊(duì)列的定義 */int InitStack(SqS

6、tack *S);/*初始化順序棧 */int StackEmpty(SqStack S);/*判斷是否為空棧 */int Push(SqStack *s, char data);/*入棧 */int Pop(SqStack *s, char *data);/*出棧 */int InitQueue(LinkQueue *q);/*初始化鏈隊(duì)列 */int QueueEmpty(LinkQueue q);/*判斷是否為空隊(duì)列 */int EnQueue(LinkQueue *q, char item);/*入隊(duì) */int DeQueue(LinkQueue *q, char *item);/*

7、出隊(duì) */初始化順序棧 */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 棧已滿(mǎn)，不能完成入棧操作！ ); return 0;s-top+;s-items-top = da

8、ta;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)/* 初始化鏈隊(duì)列 */ q-front = q-rear (PQNode)malloc(sizeof(LQNode);if(!q-front)printf(n 初始化隊(duì)列失敗！ ); return 0;q-front-next = NULL;return 1;int Qu

9、eueEmpty(LinkQueue q)/* 判斷是否為空隊(duì)列 */ if (q.front = q.rear)printf(n 隊(duì)列為空！ ); return 1;else return 0;入隊(duì) */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-rear = p;return 1;int DeQueue(Lin

10、kQueue *q, char *item)/*出隊(duì) */PQNode p;if(q-front = q-rear)printf(n 隊(duì)列已空，不能出隊(duì) ); return 0;p = q-front-next;*item = p-data;q-front-next = p-next;free(p);if(q-rear = p) /* 若刪除的為最后一個(gè)結(jié)點(diǎn)，移 動(dòng)隊(duì)尾指針 */q-front = q-rear;return 1;int TraverseQueue(LinkQueue q)/*遍歷 */PQNode pos;if(q.front = q.rear)printf(n 隊(duì)列為空！

11、); 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( 請(qǐng)輸入字符 :); 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,&