数据结构-回文序列判断

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

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

3、表格1模块功能描述初始化模块栈、队列等初始化输入模块字母序列输入入栈模块将输入序列入栈入队模块将输入序列入队判断模块将序列正、逆比较输出模块判断结果输出2、模块之间关系及其相互调用的图示开始五、详细设计及运行结果1、设计源代码：#in clude"stdio.h"#i nclude"co ni o.h"#i nclude"malloc.h"typedef struct NODE char data; struct NODE *next;LinkStack; typedef struct Nodechar data; struct No

4、de *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

5、; 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=te

6、mp->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=(LinkQueueNod

7、e *)malloc(sizeof(LinkQueueNode); if(NewNode!=NULL)NewNode->data=a;NewNode->next=NULL; q->rear->next=NewNode; q->rear=NewNode;return(1);elsereturn(0);char OutQueue(LinkQueue *q)LinkQueueNode *temp;char a; if(q->rear=q->front)return(0); temp=q->front->next; q->front->

8、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(&quo

9、t;please input a string end of :n"); while(ai-1!=64)scanf("%c",&ai);i+; for(t=0;t<i;t+) if(at!=64)Push(top,at); EnterQueue(q,at); t=LengthStack(top); if(t%2=0)printf("Input wrong!");else for(i=0;i<t;i+) n=Pop(top); m=OutQueue(q); if(n!=m) flag1=1;if(i=t/2)&&

10、;(n!=38) flag2=1; if(flag1|flag2) printf("This is not palindrome sequence!");elseprintf("This is palindrome sequence!"); getch();2、运行结果：2.1、回文字符序列输入:E:progra m'G.回文 hiuwenxe"please input a string end of © : qwertyytrewq©This is palindrome sequence J图22.2非回文字符序列

11、输入：Fd E:program Ce文h ruv.-'en.exe"please input a string end of : qwerttreq©This is not palindzome sequence 1六、调试情况，设计技巧及体会通过这次数据结构试验，我学习了链栈的建立及其一些基本的操作方法和队 列的建立及对其的一些基本操作，充分理解了栈和区别和联系，栈和队列都可以 通过链表实现，区别在于对其操作的节点位置不同，更重要的是通过这次实践操 作学会了完成一个设计的基本方法和步骤，拿到一个问题不能急于开始书写代码 要将问题理清楚、找清思路、分好模块再开始敲代码，代码只是实现一个功能的 工具，只有好的解决问题