数据结构回文序列判断实验报告

洛阳理工学院实验报告系别计算机班级学号姓名课程名称数据结构实验日期2016.11实验名称栈和队列的基本操作成绩实验目的：熟悉掌握栈和队列的特点，掌握与应用栈和队列的基本操作算法，训练和提高结构化程序设计能力及程序调试能力。实验条件：计算机一台VisualC++6.0实验内容：1.问题描述利用栈和队列判断字符串是否为回文。称正读与反读都相同的字符序列为“回文”序列。要求利用栈和队列的基本算法实现判断一个字符串是否为回文。栈和队列的存储结构不限。2.数据结构类型定义typedefstruct//栈结构体{chare[MAX];inttop;}SeqStack;typedefstructNODE//队列结构体{chard;structNODE*next;}LinkQN;typedefstruct//封装头指针为指针{LinkQN*front;LinkQN*rear;}LinkQ;3.模块划分1.队列部分：a./*链队列入队操作算法*/intenter(LinkQ*q,charch)b./*链队列出队操作算法*/intdeleteq(LinkQ*q,char*c)2.栈部分：a.//初始化栈voidInitStack(SeqStack*s)b.//入栈操作intPush(SeqStack*S,StackElementTypex)c.//出栈操作intPop(SeqStack*S,StackElementType*x)d.//输出栈中元素voidshowStack(SeqStack*S)4.详细设计#includestdio.h#includestdlib.h#defineMAX100typedefstruct//栈结构体{chare[MAX];inttop;}SeqStack;typedefstructNODE//队列结构体{chard;structNODE*next;}LinkQN;typedefstruct//封装头指针为指针{LinkQN*front;LinkQN*rear;}LinkQ;voidInitStack(SeqStack*s)//初始化顺序栈{s-top=-1;}intpush(SeqStack*s,charch)//入栈{if(s-top==MAX-1)return(0);s-top++;s-e[s-top]=ch;return(1);}intpop(SeqStack*s,char*x)//出栈{if(s-top==-1)return(0);else{*x=s-e[s-top];s-top--;return(1);}}voidInitQuene(LinkQ*q)//链队列初始化{q-front=(LinkQN*)malloc(sizeof(LinkQN));if(!q-front){printf(分配空间失败!);}q-rear=q-front;q-front-next=NULL;}intenter(LinkQ*q,charch)//入队{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);}intdeleteq(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);}inthuiwen(SeqStacks,LinkQq)//回文判断{intflag=1,m=0,t=1;inti;charch1,ch2,ch;InitStack(&s);InitQuene(&q);printf(请输入字符序列当输入字符@时输入结束:\n);while(ch!='@'){ch=getchar();if(ch!='@'){printf(%c,ch);push(&s,ch);enter(&q,ch);m++;}}printf(\n输入完成!\n);getchar();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;}}elseflag=0;}elseflag=0;return(flag);}intmain(){SeqStacks;LinkQq;intm;m=huiwen(s,q);printf(\n);if(m)printf(该字符序列是回文序列!\n);elseprintf(该字符序列不是回文序列!\n);}5.测试数据及结果实验总结：实验的时候应先实现栈的部分和实现队列的部分，确认他们能实现以后再组合起来使用，这样一旦出错就容易查找了。