数据结构课程实验报告(回文篇)

《数据结构课程实验报告(回文篇)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程实验报告要求实验题目：回文判断算法班级通信143妙.名刘海波学号2014101114曰期2015.6.17一、需求分析1.程序的功能；利用栈和队列的操作来实现对字符序列是否是一个回文序列的判断。没计和验证入栈、出栈及入队、出队的算法。2.输入输出的要求；从键盘读入一组字符序列，按输入顺序入队列到链式队列A中。并将创建好的A队列中元素依次遍历，打印在屏幕上。将字符序列从A队列出队列，压入到一个顺序栈中。再将字符序列从顺序栈中出栈，入队到另一个链式队列B中。将创建好的B队列中元素依次遍历，打印在屏幕上。将A，B队列屮的元素出队逐一比较

2、，判断是否一致。若一致则是回文，并将判定结果打印到屏幕上。3.测试数据：输入一组字符串进行判断。二、概要设计1.本程序所用的抽象数裾类型的定义；typedefstruct{charitem[STACKSIZE];inttop;}SqStack;typedefstructQNode{chardata;structQNode*next;}LQNode,*PQNode;typedefstruct]PQNodefront,rear;}LinkQueue;2.主程序的流程及各程序模块之间的层次关系。从键盘上读取一个字符，同时存储在顺序桟与链队列之中，直

3、到字符序列的最后一个字符为*停止插入。在程序中设置了一个标志位flag,将输入的序列分别做入栈、出栈、入队、出队操作，若出栈与出队的数据完全一致，则将flag标志为1,否则为零。Hag为1，则表示该序列是冋文序列，否则，为非冋文序列。三、详细设计1.采用C语言定义相关的数据类型；typedefstruct{charitem[STACKSIZE];inttop;}SqStack;typedefstructQNode{chardata;structQNode*next;JLQNode，*PQNode;typedefstruct{PQNodefro

4、nt，rear;}LinkQueue;1.写出各模块的伪码算法；intInitStack(SqStack*S)intStackEmpty(SqStackS)intPush(SqStackchardata)intPop(SqStack*s,char*data)intInitQueue(LinkQueue*q)intQueueEmpty(LinkQueueq)intEnQueue(LinkQueue*q，charitem)intDeQueue(LinkQueuechar*item)intPutOutQueue(LinkQueueq)U!调试分析1

5、.调试中遇到的问题及对问题的解决方法；对于语句中的一般回文单词能正常输山，句末跟标点符号连在一起的回文单词也能通过程序把字符串末尾的标点给去掉并正常输出，而字符串中的连接符可以作力回文单词的组成部分一起输出。2.算法的时间复杂度和空间复杂度。时间杂度为0(n)；空间S杂度为0(n)o五、使用说明及测试结果程序执行后显示以K内容:请输入一字符串；对该字符串进行判断；输山原字符串与逆字符串;判断是否为回文；输出结果。六、源程序(带注释)#include#include#include#de

6、fineSTACKSIZE100typedefstruct{charitem[STACKSIZE];inttop;}SqStack;typedefstructQNode{chardata;structQNode*next;}LQNode,氺PQNode;typedefstruct{PQNodefront,rear;}LinkQueue;intInitStack(SqStack*S){S-〉top=-1;return1;}intStackEmpty(SqStackS){if(S.top==-1)return1;elsereturn0;}intP

7、ush(SqStack*s，chardata){if(s-〉top==STACKSIZE-1){printf(’’栈已满，不能完成入栈操作n);return0;}s-〉top++;s->item[s->top]=data;return1;}intPop(SqStack*s，char*data){if(s-〉top-1){printff堆栈已空，不能完成出栈操作n);return0;}*data=s-〉item[s-〉top];s->top-;return1;intInitQueue(LinkQueue*q)q-〉front=q->re

8、ar=(PQNode)malloc(sizeof(LQNode));if(!q-〉front){printf("初始化队列失败n);return0;}q->fr