棧和隊列實驗報告

數(shù)據(jù)結(jié)構(gòu)實驗報告一、實驗?zāi)康?、熟練掌握棧和隊列的基本操作在兩種存儲結(jié)構(gòu)上的實現(xiàn)。2、會用棧和隊列解決簡單的實際問題。二、實驗內(nèi)容題目一、試寫一個算法，判斷依次讀入的一個以@為結(jié)束符的字符序列，是否為回文。所謂“回文“是指正向讀和反向讀都一樣的一字符串,如“321123”或“ableelba”。題目二、編程模擬隊列的管理，主要包括：出隊列、入隊、統(tǒng)計隊列的長度、查找隊列某個元素e、及輸出隊列中元素。實驗步驟1.回文序列：㈠、數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計描述typedefintSElemType;//元素類型定義typedefcharElemType;typedefstruct{ElemType*base;ElemType*top;}SqStack;//棧的定義//通過棧的“后進(jìn)先出”特性輸出序列的逆序typedefstructQNode///隊列的定義{ElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;//通過隊列的“先進(jìn)先出”特性，輸出序列的正序棧的函數(shù)定義voidInitStack(SqStack&S)//構(gòu)造一個空棧intPush(SqStack&S,SElemTypee)//入棧intPop(SqStack&S,SElemType&e)//出棧intStackEmpty(SqStackS)//將棧置空//隊列函數(shù)定義intInitQueue(LinkQueue&Q)//構(gòu)造一個空隊intEnQueue(LinkQueue&Q,QElemTypee)//插入元素e為新隊尾元素intDeQueue(LinkQueue&Q,QElemType&e)//刪除對為元素，用e返回其值intIsReverse()(LinkStack*S,SqQueueQ)//判斷回文序列㈡、函數(shù)調(diào)用及主函數(shù)設(shè)計回文序列判斷函數(shù)關(guān)系圖：main()函數(shù)main()函數(shù)棧函數(shù)判斷回文函數(shù)隊列函數(shù)構(gòu)造棧Initstack()

入棧push()

出棧pop()

將棧置空stackempty()入棧入隊Push(S,c);

EnQueue(&Q,c);出棧出隊Pop(S,e)

DeQueue(&Q,e)

比較Pop(S,e)!=DeQueue(&Q,e)構(gòu)造一個隊列InitQueue(0

入隊EnQueue()

出隊DeQueue()

判斷隊列是否為空QueueEmpty()（可用函數(shù)的調(diào)用關(guān)系圖說明）㈢程序調(diào)試及運行結(jié)果分析圖-1圖-2圖-1和圖-2是分別輸入字符串“123321@”和“123@”的運行結(jié)果，由圖可以得知，該程序結(jié)果是正確的。四、主要算法流程圖及程序清單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)//判斷函數(shù){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()//主函數(shù){SqStacks;LinkQueueq;InitStack(&s);InitQueue(&q);cout<<"請輸入一行字符串，以@結(jié)束!"<<endl;if(IsReverse(&s,q)==0)cout<<"該序列不是回文序列"<<endl;else cout<<"該序列是回文序列"<<endl;return0;}隊列操作：㈠、數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計描述隊列函數(shù)定義：#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)//輸出函數(shù)intmain()//主函數(shù)㈡、函數(shù)調(diào)用及主函數(shù)設(shè)計函數(shù)的調(diào)用關(guān)系圖main()函數(shù)main()函數(shù)輸出元素隊列長度查找元素出隊列初始化隊列㈢程序調(diào)試及運行結(jié)果分析程序運行結(jié)果及操作如下：圖-3圖-4圖-3和圖-4分別是主界面和選擇操作時運行出的結(jié)果，該結(jié)果實現(xiàn)了題目中所要進(jìn)行的操作。（四）主要算法流程圖及程序清單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<<"輸入初始化隊列元素個數(shù):"<<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)//輸出函數(shù){ cout<<"隊列元素為:"; Q.rear--; while(Q.rear>0) { cout<<Q.base[Q.rear]<<""; Q.rear--; }}intmain()//主函數(shù){ SqQueueQ; intm=1; inta;cout<<"對立的模擬實現(xiàn)!:"<<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<<"請選擇所要進(jìn)行的操作:"<<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;}實驗總結(jié)本次試驗主要練習(xí)了棧和隊列的基本用法和應(yīng)用。第一題的回文通過棧和隊列的綜合應(yīng)用，讓我對它們的應(yīng)用有了更深一步的了解，也對基本的函數(shù)應(yīng)用有了更好的掌握。雖然第一題有更簡便的算法，但是那樣提高不了對棧和隊列的掌握熟練程度，此方法雖然看起來繁瑣，但結(jié)構(gòu)清