实验二栈和队列基本操作与应用

实验二

第三章 栈和队列上机实验

实验时间与地点

第一组和第二组

时间： 2011-4-13，星期三， 3，4 节 10： 10— 11： 50； 地点：信息学院实验中心，弘毅楼 班级：信息 091-3 第一和第二小组； 实验内容

【实验目的 】 深入理解栈和队列的特性，领会它的应用背景。熟练掌握在不同存储结构、不同的约定 中，其基本操作的实现方法与差异。并体会以下几点（注意你所做的约定） ：

1、顺序栈（初始化、栈空 / 栈满条件，入栈 / 出栈）；

2、链栈（初始化、栈空条件，入栈 / 出栈）；

3、顺序队列

4、链队列

【实验选题 】 选题一、栈的基本操作的实现 （1 人 / 组） 实验 1 要求

1． 会定义顺序栈和链栈的结点类型。

2． 掌握栈的插入和删除结点在操作上的特点。

3． 熟悉对栈的一些基本操作和具体的函数定义。

具体内容

程序 1 该程序的功能是实现顺序栈的定义和操作。该程序包括定义的栈结构类型以及对每一种 栈操作的具体的函数定义和主函数。

选题二、 队列基本操作的实现 （1 人 / 组）

实验 2 要求

4． 会定义顺序队列和链队的结点类型。

5． 掌握队列的插入和删除结点在操作上的特点。

6． 熟悉对队列的一些基本操作和具体的函数定义。

具体内容

程序 1：链队列表示和实现

程序 2：队列运算在顺序存储结构上的实现

假定采用 Queue 记录类型的对象 Q 来表示顺序存储的队列，则在 Q 上进行各种队列运算

实验过程要求

1、 分组形式 ：学生自行分组，每组 3 人，汇总到课代表处，课代表在本周末前 mail 告 诉我；

2、 组内分工与协作 ：

1）同一小组的同学在上机前讨论确定问题可以采用的数据结构、流程的安排、模块 的划分等，共同完成上机前的准备工作，并对要编制的代码进行分工；

2） 每个同学上机时完成自己那部分程序模块的编制和调试

3） 同组同学在单体测试通过后，完成整个程序的联调；

4） 联调通过后，检查上机结果，并可以进一步讨论该程序可以改进的地方或扩展的 功能及其方法。 四、实验报告的要求：

每人交一份实验报告，实验报告的内容包括：

D406、407。

（单体测试）;

1）实验报告中的需求分析、数据结构选择、模块及流程设计等是大家共同讨论的结果；

2）实验报告中需要注明组内人员的具体分工（编码和文档写作）和作业投入时间；

3）实验报告中必须附上每个同学的实验体会（协同设计、编程、单体调试、联调、程序的可

改进和可扩展的说明、栈的使用总结、对本课程的教学与实验的建议等）；

4）以上实验报告内容装订成册，在本次实验上机结束后一周内交给老师。

五、选作实验

选题一、算术表达式求值演示（3人/组）

程序1用顺序栈实现算术表达式求值。

将表达式看成字符串序列，输入语法正确、不含有变量的整数表达式（表达式中的数字限为单位数），利用算符的优先关系，把中序表达式转换为后序表达式后输出，然后求出该后序表达式的值。

程序2用链栈实现算术表达式求值。（与程序1的基本要求相同）

同学必须完成选题中“基本要求”规定的内容，对于“选作内容”可以根据自己小组的实际情况进行分析、设计或实现。

六、参考源程序

1、部分程序见教材中相关章节！

2、下面给出一个顺序栈基本操作的完整程序，链队列的核心部分参考程序:

链队列表示和实现：

//存储表示 typ edef struct QNode{

QEIemT ype data;

struct QNode *n ext;

}QNode,*Queue Ptr;

typ edef struct{

Queue Ptr front;

QueuePtr rear;

}LinkQueue;

Status InitQueue(LinkQueue &Q) { // 构造一个空队列 Q

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)exit(OVERFLOW);

Q.front->next=NULL;

return OK;}

Status Destroyqueue(LinkQueue &Q) { // 队列 Q 存在则销毁 Q while(Q.front){

Q.rear=Q.front->next;

free(Q.front);

Q.front=Q.rear;

return OK;}

Status EnQueue(LinkQueue &Q,QElemType e) { //队列Q存在,插入元素e为Q的队尾元素

p=(QueuePtr)malloc(sizeof(QNode));

if(!p) exit(OVERFLOW);

p->data=e;p->next=NULL;

Q.rear->next=p;

Q.rear=p;

return OK;}

Status DeQueue(LinkQueue &Q,QElemType &e) { 〃Q为非空队列，删除Q的队头元素,并用e返回其值if(Q.front==Q.rear)return ERROR;

p=Q.front->next;

e=p->data;

Q.front->next=p->next;

if(Q.rear==p)Q.rear=Q.front;

free(p);

return OK;}

栈运算在顺序存储结构上的实现

#include