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

1、数据结构课程实验报告要求实验标题：回文判断算法班级通信143人有害派学号2015.6.17一、需求分析1.程序的功能；使用堆栈和队列操作确定字符序列是否为回文序列。设计和验证堆栈、堆栈和入队、出队算法。输入和输出要求；从键盘读取一组字符序列，按输入的顺序进入队列到链队列a。依次导航创建的a队列中的元素，然后将其打印在屏幕上。将a队列中的字符序列按顺序堆栈。然后，将字符序列从顺序堆栈堆叠到另一个链队列b。依次浏览生成的b队列的元素，然后将其打印在屏幕上。a，b队列中的元素在队列中逐个比较，以确定是否匹配。如果匹配，则为传阅，并将决定结果打印在屏幕上。3.测试数据：输入要判断的字符串集。二、摘要设

2、计1.此程序使用的抽象数据类型的定义；Typedef structchar itemSTACKSIZE；Int top SqStackTypedef structqmodeChar dataStructqmode * nextLQNode，* PQNodeTypedef structPQNode front，rear链接队列；2.主程序的进程和每个程序模块之间的层次关系。从键盘读取字符，直到字符序列中的最后一个字符*插入停止，然后将其存储在顺序堆栈和链队列中。如果程序设置了标志位flag，并将输入的序列设置为堆栈、堆栈、入队、出队等操作，并且出队堆栈与出队的数据完全匹配，则将flag标志设置为

3、1，否则设置为0。如果Flag为1，则序列为环回序列，否则为非环回序列。三、详细设计1.使用c语言定义相关数据类型。Typedef structchar itemSTACKSIZE；Int top SqStackTypedef structqmodeChar dataStructqmode * nextLQNode，* PQNodeTypedef structPQNode front，rear链接队列；编写每个模块的伪代码算法。Int InitStack(SqStack *S)Int StackEmpty(SqStack S)Int Push(SqStack *s，char data)Int

4、Pop(SqStack *s，char *data)Int InitQueue(LinkQueue *q)Int QueueEmpty(LinkQueue q)Int enqueue(链接队列* q，char item)Int dequeue(链接队列* q，char * item)Int PutOutQueue(LinkQueue q)四、调试分析1.调试中出现的问题和问题的解决方法；在句末连接标点的回文单词也正常输出一般回文单词的情况下，程序可以删除字符串末的标点并正常输出，字符串内的连接词也可以作为回文单词的一部分一起输出。算法的时间复杂性和空间复杂性。时间复杂度为o (n)。空间复杂性

5、为O(n)。五、使用指南和测试结果程序运行后，显示：请输入字符串；确定字符串。输出原始字符串和反向字符串。判断是不是回文。导出结果。六、源代码(包括注释)#include#include#include#define STACKSIZE 100Typedef structchar itemSTACKSIZE；Int top SqStackTypedef structqmodeChar dataStructqmode * nextLQNode，* PQNodeTypedef structPQNode front，rear链接队列；Int InitStack(SqStack *S)s-top=-1

6、；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

7、 1；Int InitQueue(LinkQueue *q)q-front=q-rear=(pq node)malloc(size of(LQ node)；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(链接队列* q，char item)Pq节点p；p=(pq node)malloc(size of(L

8、Q node)；If(！p)printf(“ n内存分配失败”)；return 0；p-data=item；p-next=NULL；q-rear-next=p；q-rear=p；return 1；Int dequeue(链接队列* q，char * item)Pq节点p；If(q-front=q-rear)printf(“ n无法出队，因为队列为空”)；return 0；p=q-front-next；* item=p-data；q-front-next=p-next；自由(p)；If(q-rear=p) /*如果删除了最后一个节点，则移动队列尾部指针*/q-front=q-rear；return 1；Int PutOutQueue(LinkQueue q)Pq节点posIf(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(void)Int i、len、count 1=0；Char str1100，ch，ch1链接队列lq1、