数据结构栈和队列试验报告

1、一、实验目的和要求理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。(2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。(3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。(4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。二、实验环境和方法实验方法：(一)综合运用课本所学的知识，用不同的算法实现在不同的程序功能。(二)结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。(三)根据实验内容，编译程序。实验环境：WindowsxpVisualC+6.0三、实验内容及过程描述实验步骤：进入

2、VisualC+6.0集成环境。输入自己编好的程序。检查一遍已输入的程序是否有错(包括输入时输错的和编程中的错误)，如发现有错，及时改正。进行编译和连接。如果在编译和连接过程中发现错误，频幕上会出现“报错信息”根据提示找到出错位置和原因，加以改正。再进行编译，如此反复直到不出错为止。运行程序并分析运行结果是否合理。在运行是要注意当输入不同的数据时所得结果是否正确，应运行多次，分别检查在不同情况下结果是否正确实验内容：编译以下题目的程序并调试运行1)、编写一个程序algo3-1.cpp,实现顺的各种基本运算，并在此基础上设计一程序并完成如下功能：(1)初始化栈s；(2)判断栈s是否非空；Work

3、space'Proj31'：1project归gProj3Jfiles-_3SourceFiles国algo31xpip国exp3-1.cppHeaderFiles1ResourceFiles5ClassViewIHFileView序栈个主(3)依次进栈元素a,b,c,d,e；(4)判断栈s是否非空；(5)输出出栈序列；(6)判断栈s是否非空；(7)释放栈。图3.1Proj3_1工程组成其中包含如下函数:本工程Proj3_1的组成结构如图3.1所示。本工程的本K块结构如图3.2所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。图3.2Proj3_1工程的程

4、序结构图初始化栈S销毁栈s判断栈空InitStack(SqStack*&s)DestroyStack(SqStack*&s)StackEmpty(SqStack*s)/进栈出栈取栈顶元素Push(SqStack*&s,ElemTypee)Pop(SqStack*&s,ElemType&e)GetTop(SqStack*s,ElemType&e)对应的程序如下：文件名:algo3-1.cpp#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefcharElemT

5、ype;typedefstructElemTypedataMaxSize;inttop;栈顶指针SqStack;voidInitStack(SqStack*&s)初始化栈Ss=(SqStack*)malloc(sizeof(SqStack);s->top=-1;栈顶指针置为-1voidDestroyStack(SqStack*&s)销毁栈sfree(s);boolStackEmpty(SqStack*s)判断栈空return(s->top=-1);boolPush(SqStack*&s,ElemTypee)/进栈if(s->top=MaxSize-1)

6、栈满的情况，即栈上溢出returnfalse;s->top+;栈顶指针增1s->datas->top=e;/元素e放在栈顶指针处returntrue;boolPop(SqStack*&s,ElemType&e)/出栈if(s->top=-1)栈为空的情况，即栈下溢出returnfalse;e=s->datas->top;取栈顶指针元素的元素s->top-;栈顶指针减1returntrue;boolGetTop(SqStack*s,ElemType&e)取栈顶元素if(s->top=-1)栈为空的情况，即栈下溢出return

7、false;e=s->datas->top;取栈顶指针元素的元素returntrue;设计exp3-1.cpp程序如下/文件名:exp3-1.cpp#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefcharElemType;typedefstructElemTypedataMaxSize;inttop;栈顶指针SqStack;externvoidInitStack(SqStack*&s);externvoidDestroyStack(SqStack*&s);externboo

8、lStackEmpty(SqStack*s);externboolPush(SqStack*&s,ElemTypee);externboolPop(SqStack*&s,ElemType&e);externboolGetTop(SqStack*s,ElemType&e);voidmain()ElemTypee;SqStack*s;printf("栈s的基本运算如下：n");printf("(1)初始化栈sn");InitStack(s);printf("(2)栈为%sn",(StackEmpty(s)?

9、"空":"非空");printf("(3)依次进栈元素a,b,c,d,en");Push(s,'a');Push(s,'b');Push(s,'c');Push(s,'d');Push(s,'e');printf("(4)栈为%sn",(StackEmpty(s)?"空":"非空");printf("(5)出栈序列:");while(!StackEmpty(s)Pop(s,e)

10、;printf("%c",e);printf("n");printf("(6)栈为%sn",(StackEmpty(s)?"空":"非空");printf("释放栈n");DestroyStack(s);运行结果如下：*anci*bt力n*c0:ac下素d0nTJe七文s-71.一I栈空列3运化空靠序空气本蜀次程嘉强>>>>>>3百12345673e天*用F2)、编写一个程序algo3-2.cpp,实现链栈的各种基本运算，并在此基础上设计一

11、个主程序并完成如下功能：11Workspace,PfrnJ3_2l：1project(s)-1Proj3_2files(1)初始化链栈s;(2)判断链栈s是否非空；SourceFiles出algo3-2.cpp国exp3-2.cppIHeaderFiles_JResourceFilesClassView篁|FileView(3)依次进栈a,b,c,d,e;(4)判断链栈s是否非空；(5)输出链栈长度；(6)输出从栈底到栈顶元素；图3.3Proj3_2工程组成(7)输出出队序列；(8)判断链栈s是否非空；(9)释放队列。本工程Proj3_2的组成结构如图3.3所示。本工程的本K块结构如图3.4所

12、示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。图3.4Proj3_2工程的程序结构图其中包含如下函数：InitStack(LiStack*&s)初始化栈sDestroyStack(LiStack*&s)/销毁栈StackEmpty(LiStack*s)判断栈是否为空Push(LiStack*&s,ElemTypee)/进栈Pop(LiStack*&s,ElemType&e)出栈GetTop(LiStack*s,ElemType&e)取栈顶元素对应的程序如下：/文件名:algo3-2.cpp#include<stdio

13、.h>#include<malloc.h>typedefcharElemType;typedefstructlinknodeElemTypedata;/数据域structlinknode*next;/指针域LiStack;voidInitStack(LiStack*&s)初始化栈ss=(LiStack*)malloc(sizeof(LiStack);s->next=NULL;voidDestroyStack(LiStack*&s)销毁栈LiStack*p=s,*q=s->next;while(q!=NULL)free(p);p=q;q=p->

14、next;free(p);/此日p指向尾节点，释放其空间boolStackEmpty(LiStack*s)/判断栈是否为空return(s->next=NULL);voidPush(LiStack*&s,ElemTypee)/进栈LiStack*p;p=(LiStack*)malloc(sizeof(LiStack);p->data=e;新建元素e对应的节点*pp->next=s->next;插入*p节点作为开始节点s->next=p;boolPop(LiStack*&s,ElemType&e)出栈LiStack*p;if(s->ne

15、xt=NULL)栈空的情况returnfalse;p=s->next;/p指向开始节点e=p->data;s->next=p->next;删除*p节点free(p);释放*p节点returntrue;boolGetTop(LiStack*s,ElemType&e)/取栈顶元素if(s->next=NULL)/栈空的情况returnfalse;e=s->next->data;returntrue;设计exp3-2.cpp主程序/文件名:exp3-2.cpp#include<stdio.h>#include<malloc.h>

16、;typedefcharElemType;typedefstructlinknodeElemTypedata;/数据域structlinknode*next;/指针域LiStack;externvoidInitStack(LiStack*&s);externvoidDestroyStack(LiStack*&s);externboolStackEmpty(LiStack*s);externvoidPush(LiStack*&s,ElemTypee);externboolPop(LiStack*&s,ElemType&e);externboolGetTop

17、(LiStack*s,ElemType&e);voidmain()ElemTypee;LiStack*s;printf("栈s的基本运算如下：n");printf("(1)初始化栈sn");InitStack(s);printf("(2)栈为%sn",(StackEmpty(s)?"空":"非空");printf("(3)依次进栈元素a,b,c,d,en");Push(s,'a');Push(s,'b');Push(s,'c&#

18、39;);Push(s,'d');Push(s,'e');printf("(4)栈为%sn",(StackEmpty(s)?"空":"非空");printf("(5)出栈序列：")；while(!StackEmpty(s)Pop(s,e);printf("%c",e);printf("n");printf("(6)栈为%sn",(StackEmpty(s)?"空":"非空");prin

19、tf("释放栈n");DestroyStack(s);程序运行结果如下:运化空进非序空栈火基出里江S>>>>>>>?1234567S5<<<<<<<ea.j.hj.cj.d,cbacontinue3)、编写一个程序algo3-3.cpp,实现顺序环形队列的各种基本运算，并在此基础上设计一个主程(1)初始化队列q；(2)判断队列q是否非空；(3)依次进队列a,b,c;(4)出队一个元素，输出该元素;(5)输出队列q的元素个数；(6)依次进队列元素d,e,f;(7)输出队列q的元素个数；11Wo

20、rkspace'Proj3_3.:1project(s)-B)Proj3_3files一l+C£_jHeaderFilesSourceFilesIResourceFiles:CEssView凰FileView图3-5Proj3_3的工程组成序并完成如下功能:(8)输出出队序列；(9)释放队列。本工程Proj3_3的组成结构如图3.5所示。本工程的本K块结构如图3.6所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系GetTo图3.6Proj3_3工程的程序结构图其中包含如下函数：InitQueue(SqQueue*&q)初始化队列DestroyQu

21、eue(SqQueue*&q)销毁队列QueueEmpty(SqQueue*q)判断队列空enQueue(SqQueue*&q,ElemTypee)/进队deQueue(SqQueue*&q,ElemType&e)出队对应的程序如下:/文件名:algo3-3.cpp#include<stdio.h>#include<malloc.h>#defineMaxSize5typedefcharElemType;typedefstructElemTypedataMaxSize;intfront,rear;队首和队尾指针SqQueue;voidIni

22、tQueue(SqQueue*&q)/初始化队列q=(SqQueue*)malloc(sizeof(SqQueue);q->front=q->rear=0;voidDestroyQueue(SqQueue*&q)销毁队列free(q);boolQueueEmpty(SqQueue*q)/判断队列空return(q->front=q->rear);boolenQueue(SqQueue*&q,ElemTypee)/进队if(q->rear+1)%MaxSize=q->front)队满上溢出returnfalse;q->rear=(

23、q->rear+1)%MaxSize;q->dataq->rear=e;returntrue;booldeQueue(SqQueue*&q,ElemType&e)/出队if(q->front=q->rear)队空下溢出returnfalse;q->front=(q->front+1)%MaxSize;e=q->dataq->front;returntrue;设计exp3-3.cpp主程序#include<stdio.h>#include<malloc.h>#defineMaxSize5typedefc

24、harElemType;typedefstruct(ElemTypeelemMaxSize;intfront,rear;队首和队尾指针SqQueue;externvoidInitQueue(SqQueue*&q);externvoidDestroyQueue(SqQueue*&q);externboolQueueEmpty(SqQueue*q);externboolenQueue(SqQueue*&q,ElemTypee);externbooldeQueue(SqQueue*&q,ElemType&e);voidmain()(ElemTypee;SqQueue*q;printf("环形队列基本运算如下：n");printf("(1)初始化队列qn");InitQueue(q);printf("(2)依次进队列元素a,b,cn");if(!enQueue(q,'a