回文序列判断(运用栈以及队列完成).doc

回文序列判断(运用栈以及队列完成)回文序列判断实验报告系别：通信工程班级： 0905班 学号： 18 号1．实验目的：熟悉栈的各项操作2．实验内容:利用栈的操作完成读入的一个以@结尾的字符序列是否是回文序列的判断回文序列即正读与反读都一样的字符序列；例如：123&321@是； 123＆4321＠、123＆312＠不是算法思想：从键盘上读取一个字符，同时存储在顺序栈与链队列之中，直到字符序列的最后一个字符为＠停止输入，因为要满足特定的要求：序列1＆序列2，故设置夜歌标记量falg=1,判断输入的元素个数是否为奇数个，若为偶数个则令flag=0，若为奇数个继续判断栈的中间元素是否为＆,若不是则令flag=0，若是，将栈和队列中的元素依次出列，判断是否相等，若不相等则令flag=0，最后将flag的值返回给主函数,若flag被修改为0说明不是回文序列，否则反之！！判断回文序列的流程图：初始化栈InitS(&s)初始化队列InitQ(&q)当ch!='@'时ch=getch()Y ch!='@' Nprintf("%c",ch) push(&s,ch) enter(&q,ch) m++Y m%2!=0 N Y s->e[m/2]=='&' N flag=0 i=1当i<(m+1)/2时 flagpop(&s,&ch1) =0deleteq(&q,&ch2)Y ch1!=ch2 Nflag=0 i++retun(flag)3．实验感想与体会通过本次的上机，对栈的各项基本操作都有了更好的掌握，同时明白了一些小的细节问题可能会影响到整个程序的正确的运行,本次的实验我通过了运用栈和队列，可以说对队列的一些基本的操作也得以了巩固和提高！更加体会到,自己写程序上机操作的重要性，它要比课本上学的要多得多！4．附录（源代码及运行图）#include

h〉＃define MAX 100typedef struct//栈结构体｛ char e［MAX]； int top；｝SeqStack;typedef struct NODE//队列结构体｛ char d; struct NODE *next;｝LinkQN;typedef struct//封装头指针为指针{ LinkQN ＊front; LinkQN ＊rear;}LinkQ；InitS（SeqStack *s）//初始化顺序栈{ s—〉top=—1;｝int push(SeqStack *s,char ch）//入栈{ if（s—>top==MAX—1） return（0)； s—〉top++; s—〉e［s->top]=ch； return(1)；}int pop(SeqStack ＊s，char ＊x)//出栈｛ if(s->top==—1） return(0)； *x=s->e［s—>top]； s->top——; return（1）;}void InitQ(LinkQ ＊q）//链队列初始化｛ q->front=(LinkQN ＊）malloc（sizeof(LinkQN)）； if（！q-〉front） { printf(”分配空间失败!”）； ｝ q-〉rear=q-〉front； q-〉front-〉next=NULL；}int enter（LinkQ *q,char ch）//入队｛ LinkQN *np; np=（LinkQN *)malloc(sizeof(LinkQN)); if(！np） return(0)； np->d=ch； np—〉next=NULL; q-〉rear-〉next=np； q—>rear=np； return（1)；}int deleteq(LinkQ ＊q,char ＊c）//出队｛ LinkQN ＊p; if(q->front==q—>rear） return(0)； p=q—〉front-〉next; q—>front-〉next=p-〉next； if（q—>rear==p) q—〉rear=q-〉front； ＊c=p—〉d； free(p)； return（0）;｝int huiwen(SeqStack *s,LinkQ ＊q）//回文判断{ int flag=1，m=0,t=1; int i; char ch1，ch2,ch; InitS(&s); InitQ(＆q)； printf(”请输入字符序列当输入字符＠时输入结束:\n")； while（ch!='@') ｛ ch=getch(）； if（ch!='＠’） ｛ printf（"％c"，ch)； push（＆s,ch); enter(＆q，ch）; m++； ｝ } printf（"\n输入完成!\n”)； printf（”按任意键予以判断！\n"）； getch(）; if(m%2） { if（s—>e[m/2]=='&') ｛ for(i=1;i<（m+1)/2;i++) { pop(＆s，&ch1)； deleteq(＆q，&ch2）; if（ch1!=ch2) flag=0; ｝ } else flag=0; } else flag=0； return(flag）;}main(){ SeqStack ＊s; LinkQ ＊q; int m; m=huiwen(*s，＆q）； printf（"\n"）; if（m) printf(”该字符序列是回文序列！\n”）； else printf(”该字符序列不是回文序列!\n”)；｝。