数据结构-回文序列判断

1、西安邮电学院数据结构实验报告回文序列判断班级：班内序号：学生姓名：指导教师：时间：2011/10/13一、实验目的2二、实验内容2三、数据结构及算法思想2四、模块划分21、对各个模块进行功能的描述22、模块之间关系及其相互调用的图示3五、详细设计及运行结果31、设计源代码：32、运行结果：7六、调试情况，设计技巧及体会71、熟悉并掌握栈的的创建、入栈和出栈等基本用法并能运用栈完成一些特定的任务。2、熟悉并掌握队列的的创建、入队和出队等基本用法并能运用队列完成一些特定的任务。3、运用栈和队列实现对“回文”序列的判断。二、实验内容编写一个算法，判断一次读入一个以劭束符的字母序列，是否为形如序列18

2、序列2'模式的字符序列。其中序列1和序列2中都不含字符'&'。且序列2是序列1的逆序列。例如，'a+b&b+si是属于该模式的字符序列，'a+b&b-a'则不是。三、数据结构及算法思想运用栈和队列算法，在序列依次输入时将序列分别入栈和入队列，利用栈FILO和队列FIFO的特点，通过出栈和出队列实现序列顺序和逆序的比较，根据题目描述的回文序列判断并输出结果。四、模块划分1、对各个模块进行功能的描述本次设计共分为六个模块，分别是：初始化模块、输入模块、入栈模块、入队模块、判断模块、输出模块。各个模块功能如下表。表格1模块功能描

3、述初始化模块栈、队列等初始化输入模块字母序列输入入栈模块将输入序列入栈入队模块将输入序列入队判断模块将序列正、逆比较输出模块判断结果输出2、模块之间关系及其相互调用的图示开始五、详细设计及运行结果1、设计源代码：#include"stdio.h"#include"conio.h"#include"malloc.h"typedefstructNODEchardata;structNODE*next;LinkStack;typedefstructNode(chardata;structNode*next;LinkQueueNode;typ

4、edefstruct(LinkQueueNode*front;LinkQueueNode*rear;LinkQueue;voidInitStack(LinkStack*top)(top->next=NULL;charPush(LinkStack*top,chara)(LinkStack*temp;temp=(LinkStack*)malloc(sizeof(LinkStack);if(temp=NULL)return(0);temp->data=a;temp->next=top->next;top->next=temp;return(1);charPop(Link

5、Stack*top)(LinkStack*temp;chara;temp=top->next;if(temp=NULL)return(0);top->next=temp->next;a=temp->data;free(temp);return(a);intLengthStack(LinkStack*top)(LinkStack*temp;intcount=0;temp=top->next;while(temp!=NULL)(count+;temp=temp->next;return(count);voidInitQueue(LinkQueue*q)(q-&g

6、t;front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode);q->rear=(LinkQueueNode*)malloc(sizeof(LinkQueueNode);q->rear=q->front;q->front->next=NULL;charEnterQueue(LinkQueue*q,chara)(LinkQueueNode*NewNode;NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode);if(NewNode!=NULL)(NewNode->dat

7、a=a;NewNode->next=NULL;q->rear->next=NewNode;q->rear=NewNode;return(1);elsereturn(0);charOutQueue(LinkQueue*q)(LinkQueueNode*temp;chara;if(q->rear=q->front)return(0);temp=q->front->next;q->front->next=temp->next;if(q->rear=temp)q->rear=q->front;a=temp->da

8、ta;free(temp);return(a);)voidmain()(chara100,flag1=0,flag2=0,n,m;inti=0,t=0;LinkStack*top=(LinkStack*)malloc(sizeof(LinkStack);LinkQueue*q=(LinkQueue*)malloc(sizeof(LinkQueue);InitStack(top);InitQueue(q);printf("pleaseinputastringendof:n");while(ai-1!=64)(scanf("%c”,&ai);i+;)for(t

9、=0;t<i;t+)(if(at!=64)(Push(top,at);EnterQueue(q,at);)t=LengthStack(top);if(t%2=0)printf("Inputwrong!");else(for(i=0;i<t;i+)(n=Pop(top);m=OutQueue(q);if(n!=m)flag1=1;if(i=t/2)&&(n!=38)flag2=1;)if(flag1|flag2)printf("Thisisnotpalindromesequence!");elseprintf("Thi

10、sispalindromesequence!");)getch();2、运行结果：2.1 、回文字符序列输入:E:programC回文*hiuwenxe"pleaseinputastringendof©:qwertyytrewq©ThisispalindromesequenceJ图22.2 非回文字符序列输入：FdE:programC回文hru,'.en.exe"pleaseinputastringendof：qwerttreq©Thisisnotpalindzomesequence1六、调试情况，设计技巧及体会通过这次数据结构试验，我学习了链栈的建立及其一些基本的操作方法和队列的建立及对其的一些基本操作，充分理解了栈和区别和联系，栈和队列都可以通过链表实现，区别在于对其操作的节点位置不同，更重要的是通过这次实践操作学会了完成一个设计的基本方法和步骤，拿到一个问题不能急于开始书写代码要将问题理清楚、找清思路、分好模块再开始敲代码，代码只是实现一个功能的工具，只有好的解决问题的