栈和队列实验报告

数据结构实验报告一、实验目的1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。2、会用栈和队列解决简单的实际问题。二、实验内容题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。题目二、编程模拟队列的管理，主要包括：出队列、入队、统计队列的长度、查找队列某个元素e、及输出队列中元素。实验步骤1.回文序列：㈠、数据结构与核心算法的设计描述typedefintSElemType;//元素类型定义typedefcharElemType;typedefstruct{ElemType*base;ElemType*top;}SqStack;//栈的定义//通过栈的“后进先出”特性输出序列的逆序typedefstructQNode///队列的定义{ElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;//通过队列的“先进先出”特性，输出序列的正序栈的函数定义voidInitStack(SqStack&S)//构造一个空栈intPush(SqStack&S,SElemTypee)//入栈intPop(SqStack&S,SElemType&e)//出栈intStackEmpty(SqStackS)//将栈置空//队列函数定义intInitQueue(LinkQueue&Q)//构造一个空队intEnQueue(LinkQueue&Q,QElemTypee)//插入元素e为新队尾元素intDeQueue(LinkQueue&Q,QElemType&e)//删除对为元素，用e返回其值intIsReverse()(LinkStack*S,SqQueueQ)//判断回文序列㈡、函数调用及主函数设计回文序列判断函数关系图：main()函数main()函数栈函数判断回文函数队列函数构造栈Initstack()

入栈push()

出栈pop()

将栈置空stackempty()入栈入队Push(S,c);

EnQueue(&Q,c);出栈出队Pop(S,e)

DeQueue(&Q,e)

比较Pop(S,e)!=DeQueue(&Q,e)构造一个队列InitQueue(0

入队EnQueue()

出队DeQueue()

判断队列是否为空QueueEmpty()（可用函数的调用关系图说明）㈢程序调试及运行结果分析图-1图-2图-1和图-2是分别输入字符串“123321@”和“123@”的运行结果，由图可以得知，该程序结果是正确的。四、主要算法流程图及程序清单1、主要算法流程图：#include<iostream.h>#include<stdio.h>#include<stdlib.h>#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOK1#defineERROR0typedefintElemType;typedefstruct{ ElemType*base;ElemType*top;}SqStack;typedefstructQNode{ ElemTypedata;structQNode*next;}QNode,*QueuePtr；typedefstruct{ QueuePtrfront;QueuePtrrear;}LinkQueue;voidInitStack(SqStack*S){S->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S->base)exit(0);S->top=S->base;}intStackEmpty(SqStackS){ if(S.top==S.base)return0;elsereturn1;}voidPush(SqStack*S,ElemTypee){ if(S->top-S->base<STACK_INIT_SIZE){*(S->top)=e;S->top++;}elsecout<<"\n栈满"<<endl;}intPop(SqStack*S,ElemTypee){ if(S->top>S->base)S->top--;e=*(S->top); returne;}voidInitQueue(LinkQueue*Q){ Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));if(!(Q->front))exit(0);Q->front->next=NULL;}intQueueEmpty(LinkQueueQ){ if(Q.front==Q.rear)return0;elsereturn1;}voidEnQueue(LinkQueue*Q,ElemTypee){QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(0);p->data=e;p->next=NULL;Q->rear->next=p;Q->rear=p;}intDeQueue(LinkQueue*Q,ElemTypee){QueuePtrp;if(Q->front!=Q->rear){p=Q->front->next;e=p->data;Q->front->next=p->next;if(Q->rear==p)Q->rear=Q->front;free(p);}returne;}intIsReverse(SqStack*S,LinkQueueQ)//判断函数{charc=getchar();inte;while(c!='@'){Push(S,c); EnQueue(&Q,c); c=getchar();}while(StackEmpty(*S)){if(Pop(S,e)!=DeQueue(&Q,e)) return0;}return1;}intmain()//主函数{SqStacks;LinkQueueq;InitStack(&s);InitQueue(&q);cout<<"请输入一行字符串，以@结束!"<<endl;if(IsReverse(&s,q)==0)cout<<"该序列不是回文序列"<<endl;else cout<<"该序列是回文序列"<<endl;return0;}队列操作：㈠、数据结构与核心算法的设计描述队列函数定义：#defineMAXQSIZE100//定义队列的最大长度typedefstruct{ int*base; intfront;intrear;}SqQueue;intInitQueue(SqQueue&Q)//队列初始化intEnQueue(SqQueue&Q)//插入元素intDeQueue(SqQueue&Q)//出队intQueueLength(SqQueue&Q)voidLocateElem(SqQueue&Q)//查找元素的值voidDisPlay(SqQueue&Q)//输出函数intmain()//主函数㈡、函数调用及主函数设计函数的调用关系图main()函数main()函数输出元素队列长度查找元素出队列初始化队列㈢程序调试及运行结果分析程序运行结果及操作如下：图-3图-4图-3和图-4分别是主界面和选择操作时运行出的结果，该结果实现了题目中所要进行的操作。（四）主要算法流程图及程序清单1、主要算法流程图：#include<iostream.h>#include<stdlib.h>#defineMAXQSIZE100typedefstruct{ int*base; intfront;intrear;}SqQueue;intInitQueue(SqQueue&Q)//队列初始化{ intn; Q.base=(int*)malloc(MAXQSIZE*sizeof(int)); if(!Q.base)exit(0); Q.front=Q.rear=0; cout<<"输入初始化队列元素个数:"<<endl; cin>>n; cout<<"请输入要读入的元素:"; for(inti=1;i<=n;i++) { inte; cin>>e; if((Q.rear+1)%MAXQSIZE==Q.front)return0; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; } cout<<"初始化成功!"<<endl; return1;}intEnQueue(SqQueue&Q)//插入元素{ inte; cout<<"输入元素e的值:"; cin>>e; if((Q.rear+1)%MAXQSIZE==Q.front)return0; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; cout<<"已成功插入元素e!"<<endl; return1;}intDeQueue(SqQueue&Q)//出队{inte; if(Q.front==Q.rear)return0; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; cout<<"已出队!"<<endl; return1;}intQueueLength(SqQueue&Q){ intn; n=(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; cout<<"队列长度为"<<n<<endl; return0;}voidLocateElem(SqQueue&Q)//查找元素的值{ inta,e; cout<<"请输入要查找的元素的值:"; cin>>e;a=Q.rear; a=a-1; while(Q.base[a]!=e&&a>0) a--; if(a==0) cout<<"不存在此元素!"<<endl; else cout<<e<<"存在该队列中"<<endl;}voidDisPlay(SqQueue&Q)//输出函数{ cout<<"队列元素为:"; Q.rear--; while(Q.rear>0) { cout<<Q.base[Q.rear]<<""; Q.rear--; }}intmain()//主函数{ SqQueueQ; intm=1; inta;cout<<"对立的模拟实现!:"<<endl; cout<<"1.初始化队列!"<<endl; cout<<"2.出队!"<<endl; cout<<"3.插入元素e!"<<endl; cout<<"4.求队列长度1"<<endl; cout<<"5.查找元素e的值!"<<endl; cout<<"6.输出队列中的元素!"<<endl; cout<<"7.退出程序!"<<endl; cout<<endl; while(m) { cout<<"请选择所要进行的操作:"<<endl;cin>>a; switch(a) { case1:InitQueue(Q);break; case2:DeQueue(Q);break; case3:EnQueue(Q);break; case4:QueueLength(Q);break;case5:LocateElem(Q);break; case6:DisPlay(Q);break; case7:cout<<"谢谢使用!"<<endl; m=0;break; return0; } } return0;}实验总结本次试验主要练习了栈和队列的基本用法和应用。第一题的回文通过栈和队列的综合应用，让我对它们的应用有了更深一步的了解，也对基本的函数应用有了更好的掌握。虽然第一题有更简便的算法，但是那样提高不了对栈和队列的掌握熟练程度，此方法虽然看起来繁琐，但结构清