山东大学《数据结构》实验指导03栈与队列.docx

实验三栈与队列
一实验任务
1)栈的应用
2)队列的表示与实现二实验目的
1)了解栈与队列的特性
2)掌握栈的顺序、链式存储表示及实现
3)掌握队列的顺序、链式存储表示及实现
4)掌握栈与队列在实际问题中的应用三实验原理
1 .栈的特性
栈(Stack)又称堆栈，是一种特殊的线性表，可定义为插入、删除和访问 只能在某一端进行的线性数据结构。堆栈允许插入、删除和访问的一端称为栈顶 (Top),另一端称为栈底(Bottom)。栈顶的第一个元素被称为栈顶元素。
堆栈的性质决定它的数据是按''先进后出〃的顺序被访问，即最先存储的元素 最后被访问、删除，最后存储的元素最先被访问、删除，所以栈也称为、'LIFO"
(Last_In, First_Out)。
栈济抽象数鬼类型定义如下：
ADT Stack{数据对象:

数据对象:
数据关系:
D={ai | a； E ElemSet, i = 1,2,…,n, n>0}R = { v an, ai > | ai-i, ai eD, i = 2,…，n }
约定dn端为栈顶，dl端为栈底。
基本操作：
InitStack(&S)操作结果：构造一个空栈S。
Push(&S, e)初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。
Pop(&S, &e)初始条件：栈S已存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。
GetTop(S, &e)初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。
StackEmpty(S)初始条件：栈S已存在。
操作结果：假设S为空栈，那么返回TRUE,否那么返回FALSE。
StackLength(S)初始条件：栈S已存在。
操作结果：返回S的元素个数，即栈的长度。
StackTraverse(S, visit())初始条件：栈S已存在且非空。
操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit ()o 一旦visit。失败，那么操作失败。
ClearStack(&S)初始条件：栈S已存在。
操作结果：将S清为空栈。
DestroyStack(&S)初始条件：栈S已存在。
操作结果：栈S被销毁。
} ADT Stack
2 .栈的顺序表示
栈的顺序存储结构，即顺序栈，是利用一组连续的存储单元依次存放自栈底 到栈顶的数据元素，同时通过指针top指示栈顶元素在顺序栈中的位置。由于很 难估计栈在使用过程中所需要的最大空间的大小，所以通常利用C语言中动态分 配的一组连续的存储单元作为顺序栈所需要的存储空间。
顺序栈所需要的具体数据类型描述如下：
#define MAXLEN 100#define STACKJNCREASE 10

#define STACKJNCREASE 10
〃顺序栈存储空间的动态分配增量

typedef struct{
ElemType *base;
Elemlype *top; int maxsize;
〃栈的存储空间的基地址，即栈底指针
〃栈顶指针〃栈当前分配的存储容量
}SqStack;
其中，maxsize指示栈当前可使用的最大容量；base为栈底指针，在顺序栈 中，它始终指向栈底的位置，假设base=NULL,那么说明栈结构不存在；top为栈顶 指针，起初值为栈底指针值，即top=base,这也可作为栈空的标记。栈插入新 元素时，将新元素插入到栈顶指针所指向的位置，同时指针top增1,删除栈顶 元素时，指针top减1。
3 .栈的链式存储表示
栈的链式存储结构，即链栈，与线性表的链式存储结构类似，是通过由结点 构成的单链表实现的，但每个结点的指针指向其前驱结点(在其之前进栈的结点)。
此时，表头指针称为栈顶指针，其指向的结点即为栈顶结点。所需要的具体数据 类型描述如下：
typedef struct SNode{ElemType data;
struct SNode *prior;"prior将指向其前一次入栈的元素}SNode, *SLink;
4 .队列的特性
队列(Queue)简称队，也是一种特殊的线性表，可定义为只允许在表的一 端进行插入，而在表的另一端进行删除的线性结构。队列允许插入的一端称为队 尾(Rear),允许删除的一端称为队首(Front) o
由于队列的插入和删除分别在不同的两端进行，因而先插入者自然先从另一 端删除，所以队列具有''先进先出〃的特点,简称为FIFO (First-In, First-Out)。
队列的抽象数据类型定义如下：
ADT Queue {数据对象：D={a( | a； G ElemSet, i = 1,2,…,n, n>0}
数据关系：Rl= { < ai-i, ai > | ai-i, ai GD, i = 2,…,n )约定其中ai端为队首，an端为队尾。
基本操作：
InitQueue(&Q)操作结果：构造一个空队列Q。
QueueEmpty(Q)初始条件：队列Q已存在。
操作结果：假设Q为空队列，那么返回TRUE,否那么FALSE。
QueueLength(Q)初始条件：队列Q已存在。
操作结果：返回Q的元素个数，即队列的长度。
EnQueue(&Q, e)初始条件：队列Q已存在。
操作结果：插入元素e为Q的新的队尾元素。
DeQueue(&Q, &e)初始条件：Q为非空队列。
操作结果：删除Q的队首元素，并用e返回其值。
GetHead(Q, &e)初始条件：Q为非空队列。
操作结果：用e返回Q的队首元素。
QueueTraverse(Q, visit())初始条件：Q已存在且非空。
操作结果：从队首到队尾，依次对Q的每个数据元素调用函数 visit( )o 一旦visit。失败，那么操作失败。
ClearQueue(&Q)初始条件：队列Q已存在。
操作结果：将Q清为空队列。
DestroyQueue(&Q)初始条件：队列Q已存在。
操作结果：队列Q被销毁，不再存在。
}ADT Queue
5 .队列的顺序表示
队列的顺序存储结构，用一组地址连续的存储单元依次存放从队首到队尾的 元素，同时附设两个指针front和rear分别指示队首元素及队尾元素的位置。
循环队列所需要的具体数据类型描述如下：
#define MAXQSIZE 100〃最大队列长度
typedef struct {ElemType * base; 〃初始化的动态分配存储空间
int front;〃头指针，假设队列不空，指向队首元素int rear;〃尾指针，假设队列不空，指向队尾元素的下一个位置
}SqQueue;
6.队列的链式存储表示
队列的链接存储结构，简称链队列。链队列所需要的具体数据类型描述如下:
typedef struct QNode {ElemType data; 〃值域
struct QNode * next; 〃链接指针域
}QNode, * QueuePtr;
typedef struct {QueuePtr front;〃头指针
QueuePtr rear;〃尾指针
}LinkQueue;四实验设备、仪器、工具与材料
微机、VC五实验内容
（1）实验任务1：栈的应用一迷宫求解
编制C程序完成迷宫问题。程序基本要求：用户输入迷宫数据初始化迷宫; 利用栈的顺序表示以及入栈、出栈等基本操作，实现迷宫路径的求解；输出求解 得到的完整路径（或提示迷宫无通路）。
（2）实验任务2：队列的表示与实现
编写一个C程序实现顺序队列的各种基本操作，并在此基础上设计一个主程 序，完成如下功能：
1）建立循环队列
2）入队列
3）出队列
4）判断队列是否为空
5）遍历队列
6）取队首元素六实验步骤
（1）实验预习
1）预习本实验原理中关于栈与队列的定义、顺序存储表示。
2）分析掌握教材48-50页中的算法3-1~3-4,为完成实验任务1做好准备。
3）分析掌握教材57~60页中迷宫问题及求解算法3-13,为完成实验任务1 做好准备。
4）分析掌握教材70~73页中的算法3-15~3-20,为完成实验任务2做好准 备。
（2）实验步骤
1）问题分析。充分地分析和理解此实验任务，弄清要求作什么，限制条件 是什么。
2）系统的结构设计。按照以数据结构为中心的原那么划分模块。最后写出每 个子程序（过程或函数）的规格说明，列出它们之间的调用关系，可以使用调用 关系图表示那么更加清晰，这样便完成了系统结构设计。
3）详细设计。详细设计的目的是对子程序（过程或函数）的进一步求精。 用IF、WHILE和赋值语句等，以及自然语言写出算法的框架。利用自然语言的 目的是防止陷入细节。
4）编码。在详细设计的基础上，对详细设计的结果进一步求精，用C语言 表示出来。
5）在VC环境下调试程序。
七实验报告要求
实验报告包含程序开发过程所形成的所有文档资料，包括如下内容：
1）需求分析及规格说明：问题描述，求解的问题是什么。
2）概要设计：本程序所用的数据类型定义；主程序流程；程序模块及相互 关系。
3）详细设计：采用C语言定义的数据结构；各模块的伪码算法；各函数调 用关系。
4）调试报告。
5）本实验任务1、2的程序清单及运行结果。
八思考题
如果一个程序中用到两个栈，为了不发生溢出错误，就必须给每个栈预先一 个较大的存储空间。假设每个栈都预先分配过大的存储空间，势必造成系统空间紧 张，如何解决这个问题？