棧和隊(duì)列實(shí)驗(yàn)報(bào)告

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

入棧push()

出棧pop()

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

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

DeQueue(&Q,e)

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

入隊(duì)EnQueue()

出隊(duì)DeQueue()

判斷隊(duì)列是否為空QueueEmpty()（可用函數(shù)的調(diào)用關(guān)系圖說(shuō)明）㈢程序調(diào)試及運(yùn)行結(jié)果分析圖-1圖-2圖-1和圖-2是分別輸入字符串“123321@”和“123@”的運(yùn)行結(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<<"請(qǐng)輸入一行字符串，以@結(jié)束!"<<endl;if(IsReverse(&s,q)==0)cout<<"該序列不是回文序列"<<endl;else cout<<"該序列是回文序列"<<endl;return0;}隊(duì)列操作：㈠、數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計(jì)描述隊(duì)列函數(shù)定義：#defineMAXQSIZE100//定義隊(duì)列的最大長(zhǎng)度typedefstruct{ int*base; intfront;intrear;}SqQueue;intInitQueue(SqQueue&Q)//隊(duì)列初始化intEnQueue(SqQueue&Q)//插入元素intDeQueue(SqQueue&Q)//出隊(duì)intQueueLength(SqQueue&Q)voidLocateElem(SqQueue&Q)//查找元素的值voidDisPlay(SqQueue&Q)//輸出函數(shù)intmain()//主函數(shù)㈡、函數(shù)調(diào)用及主函數(shù)設(shè)計(jì)函數(shù)的調(diào)用關(guān)系圖main()函數(shù)main()函數(shù)輸出元素隊(duì)列長(zhǎng)度查找元素出隊(duì)列初始化隊(duì)列㈢程序調(diào)試及運(yùn)行結(jié)果分析程序運(yùn)行結(jié)果及操作如下：圖-3圖-4圖-3和圖-4分別是主界面和選擇操作時(shí)運(yùn)行出的結(jié)果，該結(jié)果實(shí)現(xiàn)了題目中所要進(jìn)行的操作。（四）主要算法流程圖及程序清單1、主要算法流程圖：#include<iostream.h>#include<stdlib.h>#defineMAXQSIZE100typedefstruct{ int*base; intfront;intrear;}SqQueue;intInitQueue(SqQueue&Q)//隊(duì)列初始化{ intn; Q.base=(int*)malloc(MAXQSIZE*sizeof(int)); if(!Q.base)exit(0); Q.front=Q.rear=0; cout<<"輸入初始化隊(duì)列元素個(gè)數(shù):"<<endl; cin>>n; cout<<"請(qǐng)輸入要讀入的元素:"; 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)//出隊(duì){inte; if(Q.front==Q.rear)return0; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; cout<<"已出隊(duì)!"<<endl; return1;}intQueueLength(SqQueue&Q){ intn; n=(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; cout<<"隊(duì)列長(zhǎng)度為"<<n<<endl; return0;}voidLocateElem(SqQueue&Q)//查找元素的值{ inta,e; cout<<"請(qǐng)輸入要查找的元素的值:"; cin>>e;a=Q.rear; a=a-1; while(Q.base[a]!=e&&a>0) a--; if(a==0) cout<<"不存在此元素!"<<endl; else cout<<e<<"存在該隊(duì)列中"<<endl;}voidDisPlay(SqQueue&Q)//輸出函數(shù){ cout<<"隊(duì)列元素為:"; Q.rear--; while(Q.rear>0) { cout<<Q.base[Q.rear]<<""; Q.rear--; }}intmain()//主函數(shù){ SqQueueQ; intm=1; inta;cout<<"對(duì)立的模擬實(shí)現(xiàn)!:"<<endl; cout<<"1.初始化隊(duì)列!"<<endl; cout<<"2.出隊(duì)!"<<endl; cout<<"3.插入元素e!"<<endl; cout<<"4.求隊(duì)列長(zhǎng)度1"<<endl; cout<<"5.查找元素e的值!"<<endl; cout<<"6.輸出隊(duì)列中的元素!"<<endl; cout<<"7.退出程序!"<<endl; cout<<endl; while(m) { cout<<"請(qǐng)選擇所要進(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;}實(shí)驗(yàn)總結(jié)本次試驗(yàn)主要練習(xí)了棧和隊(duì)列的基本用法和應(yīng)用。第一題的回文通過(guò)棧和隊(duì)列的綜合應(yīng)用，讓我對(duì)它們的應(yīng)用有了更深一步的了解，也對(duì)基本的函數(shù)應(yīng)用有了更好的掌握。雖然第一題有更簡(jiǎn)便的算法，但是那樣提高不了對(duì)棧和隊(duì)列的掌握熟練程度，此方法雖然看起來(lái)繁瑣，但結(jié)構(gòu)清