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

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

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

3、 s；2判断栈 s 是否非空；专业资料整理WORD格式3依次进栈元素a,b,c,d,e；专业资料整理WORD格式4判断栈s 是否非空；专业资料整理WORD格式5输出出栈序列；专业资料整理WORD格式6判断栈s 是否非空；专业资料整理WORD格式7释放栈。图 3.1Proj3_1工程组成专业资料整理WORD格式本工程Proj3_1 的组成构造如图3.1 所示。本工程的模块构造如图3.2 所示。图中方框专业资料整理WORD格式表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。mainInitStackDestroyStackStackEmptyPusPopGetTo图 3.2Proj3_1

4、 工程的程序构造图其中包含如下函数：InitStack(SqStack *&s)/初始化栈 SDestroyStack(SqStack *&s)/销毁栈 sStackEmpty(SqStack *s)/判断栈空Push(SqStack *&s,ElemType e)/进栈Pop(SqStack *&s,ElemType &e)/出栈GetTop(SqStack *s,ElemType &e)/ 取栈顶元素对应的程序如下：/文件名 :algo3-1.cpp#include <stdio.h>#include <malloc.h&g

5、t;#define MaxSize 100typedef char ElemType;typedef struct专业资料整理WORD格式ElemType dataMaxSize;int top;/栈顶指针 SqStack;void InitStack(SqStack *&s)/初始化栈Ss=(SqStack *)malloc(sizeof(SqStack);s->top=-1;/栈顶指针置为-1void DestroyStack(SqStack *&s)/销毁栈 sfree(s);bool StackEmpty(SqStack *s)/判断栈空return(s->

6、top=-1);bool Push(SqStack *&s,ElemType e)/进栈if (s->top=MaxSize-1) / 栈满的情况，即栈上溢出 return false;s->top+;/ 栈顶指针增1s->datas->top=e;/ 元素 e 放在栈顶指针处return true;bool Pop(SqStack *&s,ElemType &e)/出栈if (s->top=-1)/ 栈为空的情况，即栈下溢出return false;e=s->datas->top;/ 取栈顶指针元素的元素s->top-;

7、/ 栈顶指针减1return true;bool GetTop(SqStack *s,ElemType &e)/ 取栈顶元素if (s->top=-1)/ 栈为空的情况，即栈下溢出return false;e=s->datas->top;/ 取栈顶指针元素的元素return true;设计 exp3-1.cpp 程序如下/ 文件名 :exp3-1.cpp #include <stdio.h> #include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct专业资

8、料整理WORD格式ElemType dataMaxSize;int top;/栈顶指针 SqStack;extern void InitStack(SqStack *&s);extern void DestroyStack(SqStack *&s);extern bool StackEmpty(SqStack *s);extern bool Push(SqStack *&s,ElemType e);extern bool Pop(SqStack *&s,ElemType &e);extern bool GetTop(SqStack *s,ElemType

9、 &e);void main()ElemType e;SqStack *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&#

10、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)"" 空 &qu

11、ot;:" 非空 ");printf("(7) 释放栈 n");DestroyStack(s);运行结果如下：专业资料整理WORD格式2、编写一个程序algo3-2.cpp ，实现链栈的各种根本运算，并在此根底上设计一个主程序并完成如下功能：（ 1初始化链栈 s；（ 2判断链栈 s 是否非空；（ 3依次进栈 a， b， c， d， e；（ 4判断链栈 s 是否非空；（ 5输出链栈长度；（ 6输出从栈底到栈顶元素；（ 7输出出队序列；专业资料整理WORD格式（ 8判断链栈 s 是否非空；（ 9释放队列。图 3.3 Proj3_2 工程组成专业资料整理WOR

12、D格式本工程 Proj3_2 的组成构造如图3.3 所示。本工程的模块构造如图3.4 所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。mainInitStackDestroyStackStackEmptyPusPopGetTo图 3.4 Proj3_2 工程的程序构造图其中包含如下函数：InitStack(LiStack *&s)/初始化栈 sDestroyStack(LiStack *&s)/销毁栈StackEmpty(LiStack *s)/判断栈是否为空Push(LiStack *&s,ElemType e)/进栈Pop(LiStack *

13、&s,ElemType &e)/出栈GetTop(LiStack *s,ElemType &e) /取栈顶元素对应的程序如下：/ 文件名 :algo3-2.cpp #include <stdio.h> #include <malloc.h> typedef char ElemType; typedef struct linknodeElemType data;/数据域专业资料整理WORD格式ElemType data;/数据域struct linknode *next;/指针域 LiStack;void InitStack(LiStack *&a

14、mp;s)/初始化栈ss=(LiStack *)malloc(sizeof(LiStack); s->next=NULL;专业资料整理WORD格式void DestroyStack(LiStack *&s)LiStack *p=s,*q=s->next;while (q!=NULL)free(p);p=q;q=p->next;/销毁栈专业资料整理WORD格式free(p);/ 此时 p 指向尾节点 ,释放其空间bool StackEmpty(LiStack *s) / 判断栈是否为空return(s->next=NULL);void Push(LiStack *

15、&s,ElemType e)/进栈LiStack *p;p=(LiStack *)malloc(sizeof(LiStack);专业资料整理WORD格式p->data=e;/新建元素e 对应的节点p->next=s->next;/ 插入 *p 节点作为开场节点s->next=p;*p专业资料整理WORD格式专业资料整理WORD格式bool Pop(LiStack *&s,ElemType &e)/出栈LiStack *p;专业资料整理WORD格式if (s->next=NULL)/栈空的情况专业资料整理WORD格式return false;

16、专业资料整理WORD格式p=s->next;/p指向开场节点专业资料整理WORD格式e=p->data;专业资料整理WORD格式s->next=p->next;free(p);/ 删除 *p/ 释放 *p节点节点专业资料整理WORD格式return true;bool GetTop(LiStack *s,ElemType &e) /取栈顶元素if (s->next=NULL)/栈空的情况return false;专业资料整理WORD格式e=s->next->data;return true;设计exp3-2.cpp 主程序专业资料整理WORD格

17、式/ 文件名 :exp3-2.cpp#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct linknodeElemType data;/数据域struct linknode *next;/指针域 LiStack;extern void InitStack(LiStack *&s);extern void DestroyStack(LiStack *&s);extern bool StackEmpty(LiStack *s);extern void Push(Li

18、Stack *&s,ElemType e);extern bool Pop(LiStack *&s,ElemType &e);extern bool GetTop(LiStack *s,ElemType &e);void main()ElemType e;LiStack *s;printf(" 栈 s 的根本运算如下:n");printf("(1)初始化栈 sn");InitStack(s);printf("(2)栈为 %sn",(StackEmpty(s)"" 空 ":&

19、quot; 非空 ");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,

20、e);printf("%c ",e);printf("n");printf("(6) 栈为 %sn",(StackEmpty(s)"" 空 ":" 非空 ");printf("(7) 释放栈 n");DestroyStack(s);专业资料整理WORD格式程序运行结果如下：专业资料整理WORD格式3、编写一个程序algo3-3.cpp ，实现顺序环形队列的各种根本运算，并在此根底上设计一个主程序并完成如下功能：（ 1初始化队列 q；（ 2判断队列 q 是否非空；（

21、3依次进队列 a,b,c；（ 4出队一个元素，输出该元素；（ 5输出队列 q 的元素个数；6依次进队列元素d,e,f；图 3-5Proj3_3 的工程组成（ 7输出队列 q 的元素个数；（ 8输出出队序列；（ 9释放队列。本工程 Proj3_3 的组成构造如图3.5 所示。本工程的模块构造如图3.6 所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。mainInitStackDestroyStackStackEmptyPusPopGetTo专业资料整理WORD格式图3.6Proj3_3 工程的程序构造图专业资料整理WORD格式其中包含如下函数：专业资料整理WORD格式In

22、itQueue(SqQueue *&q)/初始化队列专业资料整理WORD格式DestroyQueue(SqQueue *&q)/销毁队列专业资料整理WORD格式QueueEmpty(SqQueue *q)/判断队列空专业资料整理WORD格式enQueue(SqQueue *&q,ElemType e)/进队deQueue(SqQueue *&q,ElemType &e) / 出队专业资料整理WORD格式对应的程序如下：/ 文件名 :algo3-3.cpp #include <stdio.h> #include <malloc.h>

23、 #define MaxSize 5 typedef char ElemType; typedef structElemType dataMaxSize;int front,rear;/ 队首和队尾指针 SqQueue;void InitQueue(SqQueue *&q)/初始化队列q=(SqQueue *)malloc (sizeof(SqQueue); q->front=q->rear=0;void DestroyQueue(SqQueue *&q)/销毁队列free(q);bool QueueEmpty(SqQueue *q)/判断队列空return(q-&

24、gt;front=q->rear);专业资料整理WORD格式bool enQueue(SqQueue *&q,ElemType e)/ 进队专业资料整理WORD格式if (q->rear+1)%MaxSize=q->front)return false;q->rear=(q->rear+1)%MaxSize;q->dataq->rear=e;return true;/ 队满上溢出专业资料整理WORD格式bool deQueue(SqQueue *&q,ElemType &e) /出队if (q->front=q->r

25、ear)/队空下溢出return false;q->front=(q->front+1)%MaxSize;e=q->dataq->front;return true;设计exp3-3.cpp 主程序#include <stdio.h>#include <malloc.h>#define MaxSize 5专业资料整理WORD格式typedef char ElemType;typedef structElemType elemMaxSize;int front,rear;/队首和队尾指针 SqQueue;extern void InitQueue(

26、SqQueue *&q);extern void DestroyQueue(SqQueue *&q);extern bool QueueEmpty(SqQueue *q);extern bool enQueue(SqQueue *&q,ElemType e);extern bool deQueue(SqQueue *&q,ElemType &e);void main()ElemType e;SqQueue *q;printf(" 环形队列根本运算如下:n");printf("(1) 初始化队列qn");InitQueue(q);printf("(2) 依次进队列元素a,b,cn");if (!enQueue(q,'a') printf("t提示 :队满 ,