《数据结构课程实验报告(回文篇)》由会员分享，可在线阅读，更多相关《数据结构课程实验报告(回文篇)（6页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程实验报告要求实验题目：回文判断算法班级 通信 143 姓名 刘海波 学号 2014101114 日期 2015.6.17 一、 需求分析1 程序的功能；利用栈和队列的操作来实现对字符序列是否是一个回文序列的判断。设计和验证入栈、出栈及入队、出队的算法。2 输入输出的要求；从键盘读入一组字符序列，按输入顺序入队列到链式队列 A 中。并将创建好的 A 队列中元素依次遍历，打印在屏幕上。将字符序列从 A 队列出队列，压入到一个顺序栈中。再将字符序列从顺序栈中出栈，入队到另一个链式队列 B 中。将创建好的 B 队列中元素依次遍历，打印在屏幕上。将 A，B 队列中的元素出队逐一比较，判断是否
2、一致。若一致则是回文，并将判定结果打印到屏幕上。3.测试数据：输入一组字符串进行判断。二、 概要设计1 本程序所用的抽象数据类型的定义；typedef structchar itemSTACKSIZE;int top;SqStack;typedef struct QNodechar data;struct QNode *next;LQNode, *PQNode;typedef structPQNode front,rear; LinkQueue;2 主程序的流程及各程序模块之间的层次关系。从键盘上读取一个字符，同时存储在顺序栈与链队列之中，直到字符序列的最后一个字符为*停止插入。在程序中设置了
3、一个标志位 flag，将输入的序列分别做入栈、出栈、入队、出队操作，若出栈与出队的数据完全一致，则将 flag 标志为 1，否则为零。Flag 为 1，则表示该序列是回文序列，否则，为非回文序列。三、 详细设计1 采用 c 语言定义相关的数据类型；typedef structchar itemSTACKSIZE;int top;SqStack;typedef struct QNodechar data;struct QNode *next;LQNode, *PQNode;typedef structPQNode front,rear; LinkQueue;2 写出各模块的伪码算法；int In
4、itStack(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 DeQueue(LinkQueue *q, char *item)int PutOutQueue(LinkQueue q)四、 调试分析1 调试中遇到的问题及对问题的解决方法；对于语句中的一般回文单词
5、能正常输出，句末跟标点符号连在一起的回文单词也能通过程序把字符串末尾的标点给去掉并正常输出，而字符串中的连接符可以作为回文单词的组成部分一起输出。2 算法的时间复杂度和空间复杂度。时间复杂度为 O（n） ；空间复杂度为 O（n） 。五、 使用说明及测试结果程序执行后显示以下内容：请输入一字符串；对该字符串进行判断；输出原字符串与逆字符串；判断是否为回文；输出结果。六、 源程序（带注释）#include #include #include #define STACKSIZE 100typedef structchar itemSTACKSIZE; int top;SqStack;typedef
6、struct QNodechar data;struct QNode *next;LQNode, *PQNode;typedef structPQNode front,rear; LinkQueue;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 0;s-to
7、p+;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-front-next = NULL;return 1;int QueueE
8、mpty(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-rear = p;return 1;int DeQueue(LinkQueue *q, char *item)PQNode p;i
9、f(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 PutOutQueue(LinkQueue q)PQNode pos;if(q.front = q.rear)printf(n 队列为空);return 0;pos = q.front-next;printf(nHere is the strin
10、g:);while(pos != NULL)printf(%c, pos-data);pos = pos-next;printf(n);return 1;int main(void)int i,len,count1 = 0;char str1100,ch,ch1;LinkQueue lq1,lq2;SqStack sq;printf(Please input string:);scanf(%s, len = strlen(str1);InitQueue(InitQueue(InitStack(for(i=0;ilen;i+)EnQueue(PutOutQueue(lq1);for(i=0;ilen;i+)DeQueue(Push(EnQueue(for(i=0;ilen;i+)Pop(PutOutQueue(lq2);for(i=0;ilen;i+)DeQueue(DeQueue(if(ch1 != ch) count1+;if(count1 = 0)printf(n 该字符串为回文);elseprintf(n 该字符串不是回文);return 0;
