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

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

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

3、；(2) 判断栈s是否非空；(3) 依次进栈元素a,b,c,d,e；(4) 判断栈s是否非空；(5) 输出出栈序列；(6) 判断栈s是否非空；(7) 释放栈。图3.1 Proj3_1工程组成其中包含如下函数本工程Proj3_1的组成结构如图3.1所示。本工程的模块结构如图3.2所示。图中方框 表示函数，方框中指出函数名，箭头方向表示函数间的调用关系InitStack(SqStack *&s)/ 初始化栈 SDestroyStack(SqStack *&s)/ 销毁栈 s专业 word可编辑StackEmpty(SqStack *s)/判断栈空Push(SqStack *&

4、;s,ElemType e) / 进栈Pop(SqStack *& s,ElemType &e) /出栈/取栈顶元素GetTop(SqStack *s,ElemType &e)对应的程序如下文件名：algo3-1.cpp #in clude <stdio.h> #include <malloc.h> #defi ne MaxSize 100 typedef char ElemType; typedef struct ElemType dataMaxSize;int top;栈顶指针 SqStack;void InitStack(SqStack *

5、&s)/初始化栈 S s=(SqStack *)malloc(sizeof(SqStack);s->top=-1;/栈顶指针置为-1void DestroyStack(SqStack *&s)/销毁栈 sfree(s);bool StackEmpty(SqStack *s)/ 判断栈空return(s->top=-1);bool Push(SqStack *&s,ElemType e)进栈 if (s->top=MaxSize-1) II栈满的情况，即栈上溢出 return false;s->top+;II栈顶指针增1s->datas-&g

6、t;top=e;II元素e放在栈顶指针处return true;bool Pop(SqStack *& s,ElemType &e)II 出栈 if (s->top=-1)II栈为空的情况，即栈下溢出return false;e=s->datas->top; II取栈顶指针元素的元素 s->top-;II栈顶指针减1return true;bool GetTop(SqStack *s,ElemType &e) II 取栈顶元素 if (s->top=-1)II栈为空的情况，即栈下溢出return false;e=s->datas-&g

7、t;top; II取栈顶指针元素的元素 return true;设计exp3-1.cpp程序如下/文件名:exp3-1.cpp#in elude <stdio.h>#include <malloc.h>#defi ne MaxSize 100typedef char ElemType;typedef structElemType dataMaxSize;int top;栈顶指针 SqStack;extern void In itStack(SqStack *&；s);extern void DestroyStack(SqStack *& s);exter

8、n bool StackEmpty(SqStack *s);exter n bool Push(SqStack *&s,ElemType e);extern bool Pop(SqStack *&s,ElemType & e);extern bool GetTop(SqStack *s,ElemType & e);void mai n()ElemType e;SqStack *s;printf("栈s的基本运算如下:n”);printf("(1)初始化栈 sn");In itStack(s);printf("(2)栈为 %

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

10、e (!StackEmpty(s)Pop(s,e);prin tf("%c ",e);prin tf("n");printf("(6)栈为 %sn",(StackEmpty(s)?"空":"非空");printf(" (7)释放栈 n");DestroyStack(s);运行结果如下：2)、编写一个程序algo3-2.cpp ,实现链栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：(1) 初始化链栈s;(2) 判断链栈s是否非空；(3) 依次进栈 a，b，c，d，

11、e；(4) 判断链栈s是否非空；(5) 输出链栈长度；(6) 输出从栈底到栈顶元素；(7) 输出出队序列；(8) 判断链栈s是否非空；® Workspace ,Proj3_2,: 1 projectfs H 1 Proj32Jiles -3"圍 algo3-2.cpp' Source Files園 exp3-2.cppI Header Files1 Resource Files 鲨Wew 冒 FileViEw图3.3Proj3_2工程组成(9)释放队列。本工程Proj3_2的组成结构如图3.3所示。本工程的模块结构如图3.4所示。图中方框表示函数，方框中指出函数名，

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

13、t;stdio.h>#include <malloc.h>typedef char ElemType;typedef struct li nknodeElemType data;数据域ElemType data;数据域struct linknode *n ext;指针域 LiStack;void InitStack(LiStack *&s)/初始化栈 s s=(LiStack *)malloc(sizeof(LiStack);s-> next=NULL;void DestroyStack(LiStack *&s)/ 销毁栈LiStack *p=s,*q=

14、s->n ext;while (q!=NULL) free(p);p=q;q=p->n ext;free(p); II此时p指向尾节点，释放其空间bool StackEmpty(LiStack *s) II 判断栈是否为空retur n(s->n ext=NULL);void Push(LiStack *& s,ElemType e)进栈 LiStack *p;p=(LiStack *)malloc(sizeof(LiStack);p->data=e;II新建元素e对应的节点*pp->next=s->next;II插入*p节点作为开始节点s_>

15、n ext=p;bool Pop(LiStack *&s,ElemType &e)II 出栈LiStack *p;if (s-> next=NULL)II栈空的情况return false;p=s->n ext;IIp指向开始节点e=p->data;s->n ext=p->n ext;II删除*p节点free(p);II释放*p节点return true;bool GetTop(LiStack *s,ElemType &e) II 取栈顶元素 if (s-> next=NULL)栈空的情况return false;e=s->n

16、ext->data; return true;设计exp3-2.cpp主程序/ 文件名:exp3-2.cpp#in elude <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct li nknodeElemType data;数据域struct linknode *n ext;指针域 LiStack;extern void In itStack(LiStack *&；s);extern void DestroyStack(LiStack *&s);exter n bool

17、 StackEmpty(LiStack *s);extern void Push(LiStack *& s,ElemType e);exter n bool Pop(LiStack *&s,ElemType &e);extern bool GetTop(LiStack *s,ElemType & e);void mai n()ElemType e;LiStack *s;printf("栈s的基本运算如下:n”);printf("(1)初始化栈 sn");In itStack(s);printf(" (2)栈为 %sn&qu

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

19、StackEmpty(s)Pop(s,e);prin tf("%c ",e);prin tf("n");printf(" (6)栈为 %sn",(StackEmpty(s)?"空":"非空");printf(" (7)释放栈 n");DestroyStack(s);程序运行结果如下：下nS运化空进非序宀工桟k 本勢次翼毂ny S> > > > > > > 吾 1234567 s5 <<<<<<<

20、; ea. j. h j.c j. d,c b acontinue3)、编写一个程序algo3-3.cpp ,实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序并完成如下功能(1)初始化队列q ；(2) 判断队列q是否非空；(3) 依次进队列a,b,c ；(4) 出队一个元素，输出该元素；(5) 输出队列q的元素个数；(6) 依次进队列元素d,e,f ；(7) 输出队列q的元素个数；(8) 输出出队序列；(9) 释放队列。11 Workspace31： 1 proiectfs-®IProj3_3 filesSource Files_l Header Files f Resou

21、rce Files j ClassView £ FileView图3-5 Proj3_3的工程组成本工程Proj3_3的组成结构如图3.5所示。本工程的模块结构如图3.6所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系图3.6 Proj3_3工程的程序结构图其中包含如下函数InitQueue(SqQueue *&q)/ 初始化队列DestroyQueue(SqQueue *&q)/ 销毁队列QueueEmpty(SqQueue *q)/判断队列空enQueue(SqQueue *&q,ElemType e)/ 进队deQueue(SqQu

22、eue *&q,ElemType &e)/ 出队对应的程序如下：/文件名：algo3-3.cpp#in elude <stdio.h>#include <malloc.h>#defi ne MaxSize 5typedef char ElemType;typedef structElemType dataMaxSize;int fron t,rear;/队首和队尾指针 SqQueue;void Ini tQueue(SqQueue *&q)/ 初始化队列 q=(SqQueue *)malloc (sizeof(SqQueue);q_>fro

23、n t=q->rear=0;void DestroyQueue(SqQueue *&q)/ 销毁队列free(q);bool QueueEmpty(SqQueue *q)/ 判断队列空return(q->fr on t=q->rear);bool en Queue(SqQueue *&q,ElemType e) / 进队if (q->rear+1)%MaxSize=q->fro nt)/ 队满上溢出return false;q->rear=(q->rear+1)%MaxSize;q_>dataq_>rear=e;return

24、 true;bool deQueue(SqQueue *&q,ElemType &e) / 出队if (q->fro nt=q->rear)/ 队空下溢出return false;q->fro nt=(q->fro nt+1)%MaxSize;e=q->dataq->fr on t;return true;设计exp3-3.cpp主程序#in clude <stdio.h>#include <malloc.h>#defi ne MaxSize 5typedef char ElemType;typedef structE

25、lemType elemMaxSize;int fron t,rear;/队首和队尾指针 SqQueue;exter n void In itQueue(SqQueue *&q);exter n void DestroyQueue(SqQueue *&q);exter n bool QueueEmpty(SqQueue *q);extern bool en Queue(SqQueue *& q,ElemType e); extern bool deQueue(SqQueue *& q,ElemType & e); void mai n()ElemType e;SqQueue *q;printf("环形队列基本运算如下:n");printf("(1)初始化队列 qn");In itQueue(q);prin tf("(2)依次进队列元素 a,b,c n");if (!enQueue(q,'a') printf("t 提示:队满，不能进队 n"); if (!en