回文判断的算法实验报告

1、.实验题目一、一、 需求分析需求分析.回文判断的算法.1程序的功能:实现对字符序列是否是一个回文序列的判断2输入输出的要求:从键盘读入一组字符序列， 判断是否是回文， 并将结果显示在屏幕上3测试数据:回文字符序列输入：非回文字符序列输入：二、二、 概要设计概要设计1本程序所用的抽象数据类型的定义: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主程序的流程及各程序模块之间的层次关系。（1）int initstack(sqstack *s)：栈初始化模块，即初始化一个空栈，随后对该空栈进行数据的写入操作；（2）int push(sqstack *s, char data) ：入栈操作，即给空栈中写入数据，数据长度有宏定义给出；（3）int pop(sqstack *s, char *data) ：出栈操作，即将栈中的数据输出，由于栈的操作是先进后出，因此，出栈的数据是原先输入数据的逆序；（4）int initqueue(linkqueue *q)：队列初始化，即初始化一个空队列，最后对该空队列进行数据的写入操

3、作；（5）int enqueue(linkqueue *q, char item)：入队操作， 即给空队列中写入数据， 数据长度一样有宏定义给出；.（6）int dequeue(linkqueue *q, char *item) ：出队操作， 即将队列中的数据输出， 由于队列的操作是先进先出，因此，出队的数据室原先输入数据的正序；（7）int main()：主函数，用于调用前面的模块，进行出队数据与出栈数据的比较， 判断输入的序列是否是回文序列。模块之间关系及其相互调用的图示：三、三、 详细设计详细设计1采用 c 语言定义相关的数据类型.整形，字符型，指针类型，聚合类型，自定义类型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)四、四、 调试分析调试分析1调试中遇到的问题及对问题的解决方法:问题：程序出现未知错误。方法： 在感觉容易出错的地方或者是已经出错的地方前面打断点，进一步调试。2算法的

5、时间复杂度和空间复杂度。时间复杂度：t（n） = o（n）五、五、 使用说明及测试结果使用说明及测试结果回文字符输入：非回文字符输入：.六、六、 源程序（带注释）源程序（带注释）#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 内存分配失败); 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) /*若删除的为最后一个结点，移动队尾指针*/ 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