回文实验报告.doc

实验题目回文判断的算法班级 通信143 刘峻霖08 日期 2015年6月17日星期三需求分析 程序的功能: 实现对字符序列是否是一个回文序列的判断 输入输出的要求: 从键盘读入一组字符序列，判断是否是回文，并将结果显示在屏幕上 测试数据: 回文字符序列输入： 非回文字符序列输入： 概要设计 本程序所用的抽象数据类型的定义: typedef struct{char item[STACKSIZE];int top; }SqStack; typedef struct QNode{char data;struct QNode *next; }LQNode, *PQNode; typedef struct{PQNode front,rear; } LinkQueue; 主程序的流程及各程序模块之间的层次关系。 （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)：出队操作，即将队列中的数据输出，由于队列的操作是先进先出，因此，出队的数据室原先输入数据的正序； （7）int main()：主函数，用于调用前面的模块，进行出队数据与出栈数据的比较，判断输入的序列是否是回文序列。 模块之间关系及其相互调用的图示： 详细设计 采用c语言定义相关的数据类型 整形，字符型，指针类型，聚合类型，自定义类型 写出各模块的伪码算法:参照源程序 （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) 调试分析 调试中遇到的问题及对问题的解决方法: 问题：程序出现未知错误。 算法的时间复杂度和空间复杂度。 时间复杂度：T（n） = O（n） 使用说明及测试结果 回文字符输入： 非回文字符输入： 源程序（带注释） #include stdio.h #include stdlib.h #include string.h #define STACKSIZE 100 typedef struct{char item[STACKSIZE];int top; }SqStack;/*顺序栈的定义*/ typedef struct QNode{char data;struct QNode *next; }LQNode, *PQNode; typedef struct{PQNode front,rear; } 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 DeQueue(LinkQueue *q, char *item);/*出队*/ int TraverseQueue(LinkQueue q);/*遍历*/ int InitStack(SqStack *S) /*初始化顺序栈*/ { S-top = -1;return 1; } int StackEmpty(SqS