回文判断的算法实验报告

1、需求分析实验题目回文判断的算法1 程序的功能实现对字符序列是否是一个回文序列的判断2 输入输出的要求 :从键盘读入一组字符序列， 判断是否是回文， 并将结果 显示在屏幕上3 测试数据 :回文字符序列输入：非回文字符序列输入：概要设计1 本程序所用的抽象数据类型的定义typedef structchar itemSTACKSIZE; int top;SqStack;typedef struct QNode char data;struct QNode *next;LQNode, *PQNode;typedef structPQNode front,rear; LinkQueue;2 主程序的流程

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 E

3、nQueue(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 100 typedef structchar itemSTACKSIZE;int top;SqStack;/* 顺序栈的定义 */typedef struct QNodechar data; struct QNode *next;LQNode, *PQNode;typedef structPQNode front,rear; LinkQueue;/* 链队列的定义 */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);/*初始化链队列 */int QueueEmpty(LinkQueue q);/*判断是否为空队列 */int EnQueue(LinkQueue *q, char item);/*入队 */int DeQueue(LinkQueue *q, char *item);/*

7、出队 */初始化顺序栈 */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 = 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)/* 初始化链队列 */ q-front = q-rear (PQNode)malloc(sizeof(LQNode);if(!q-front)printf(n 初始化队列失败！ ); return 0;q-front-next = NULL;return 1;int Qu

9、eueEmpty(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(Lin

10、kQueue *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 队列为空！

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( 请输入字符 :); 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,&