数据结构-回文序列判断.doc

一、实验目的1、熟悉并掌握栈的的创建、入栈和出栈等基本用法并能运用栈完成一些特定的任务。2、熟悉并掌握队列的的创建、入队和出队等基本用法并能运用队列完成一些特定的任务。3、运用栈和队列实现对“回文”序列的判断。二、实验内容 编写一个算法，判断一次读入一个以结束符的字母序列，是否为形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&。且序列2是序列1的逆序列。例如，a+b&b+a是属于该模式的字符序列，a+b&b-a则不是。三、数据结构及算法思想运用栈和队列算法，在序列依次输入时将序列分别入栈和入队列，利用栈FILO和队列FIFO的特点，通过出栈和出队列实现序列顺序和逆序的比较，根据题目描述的回文序列判断并输出结果。四、模块划分1、对各个模块进行功能的描述本次设计共分为六个模块，分别是：初始化模块、输入模块、入栈模块、入队模块、判断模块、输出模块。各个模块功能如下表。表格 1模 块功能描述初始化模块栈、队列等初始化输入模块字母序列输入入栈模块将输入序列入栈入队模块将输入序列入队判断模块将序列正、逆比较输出模块判断结果输出2、模块之间关系及其相互调用的图示图1五、详细设计及运行结果1、设计源代码：#includestdio.h#includeconio.h#includemalloc.htypedef struct NODE char data; struct NODE *next;LinkStack;typedef struct Node char data; struct Node *next;LinkQueueNode;typedef struct LinkQueueNode *front; LinkQueueNode *rear;LinkQueue;void InitStack(LinkStack *top) top-next=NULL;char Push(LinkStack *top,char a) LinkStack *temp; temp=(LinkStack *)malloc(sizeof(LinkStack); if(temp=NULL) return(0); temp-data=a; temp-next=top-next; top-next=temp; return(1); char Pop(LinkStack *top) LinkStack *temp; char a; temp=top-next; if(temp=NULL) return(0); top-next=temp-next; a=temp-data; free(temp); return(a);int LengthStack(LinkStack *top) LinkStack *temp; int count=0; temp=top-next; while(temp!=NULL) count+; temp=temp-next; return(count);void InitQueue(LinkQueue *q) q-front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode);q-rear=(LinkQueueNode *)malloc(sizeof(LinkQueueNode); q-rear=q-front; q-front-next=NULL; char EnterQueue(LinkQueue *q,char a) LinkQueueNode *NewNode; NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode); if(NewNode!=NULL) NewNode-data=a; NewNode-next=NULL; q-rear-next=NewNode; q-rear=NewNode; return(1); else return(0);char OutQueue(LinkQueue *q) LinkQueueNode *temp; char a; 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-data; free(temp); return(a);void main() char a100,flag1=0,flag2=0,n,m; int i=0,t=0; LinkStack *top=(LinkStack *)malloc(sizeof(LinkStack); LinkQueue *q=(LinkQueue *)malloc(sizeof(LinkQueue); InitStack(top); InitQueue(q);printf(please input a string end of :n); while(ai-1!=64) scanf(%c,&ai); i+; for(t=0;ti;t+) if(at!=64) Push(top,at); EnterQueue(q,at); t=LengthStack(top); if(t%2=0) printf(Input wrong!); else for(i=0;it;i+) n=Pop(top); m=OutQueue(q); if(n!=m) flag1=1; if(i=t/2)&(n!=38) flag2=1; if(flag1|flag2) printf(This is not palindrome sequence!); else printf(This is palindrome sequence!); getch();2、运行结果：2.1、回文字符序列输入：图 22.2非回文字符序列输入：图 3六、调试情况，设计技巧及体会通过这次数据结构试验，我学习了链栈的建立及其一些基本的操作方法和队列的建立及对其的一些基本操作，充分理解了栈和区别和联系，栈和队列都可以通过链表实现，区别在于对其操作的节点位置不同，更重要的是通过这次实践操作学会了完成一个设计的基本方法和步骤，拿到一个问题不能急于开始书写代码要将问题理清楚、找清思路、分好模块再开始敲代码，代码只是实现一个功能的工具，只有好的解决问题的思路，才能做出好的程序。写完一个程序，只是完成一个设计