回文实验报告.doc

_实验题目回文判断的算法班级 通信143 姓名 刘峻霖 学号2014101108 日期 2015年6月17日星期三 精品资料一、 需求分析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; 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)：队列初始化，即初始化一个空队列，最后对该空队列进行数据的写入操作； （5）int EnQueue(LinkQueue *q, char item)：入队操作，即给空队列中写入数据，数据长度一样有宏定义给出； （6）int DeQueue(LinkQueue *q, char *item)：出队操作，即将队列中的数据输出，由于队列的操作是先进先出，因此，出队的数据室原先输入数据的正序； （7）int main()：主函数，用于调用前面的模块，进行出队数据与出栈数据的比较，判断输入的序列是否是回文序列。模块之间关系及其相互调用的图示：三、 详细设计1 采用c语言定义相关的数据类型整形，字符型，指针类型，聚合类型，自定义类型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)（5）int EnQueue(LinkQueue *q, char item)（6）int DeQueue(LinkQueue *q, char *item) 四、 调试分析1 调试中遇到的问题及对问题的解决方法:问题：程序出现未知错误。方法：在感觉容易出错的地方或者是已经出错的地方前面打断点，进一步调试。2 算法的时间复杂度和空间复杂度。时间复杂度：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; 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(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-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-front-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-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)/*遍历*/ PQNode 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,ch); TraverseQueu