实验三 栈与队列一 实验任务1）栈的应用2）队列的表示与实现二 实验目的1）了解栈与队列的特性2）掌握栈的顺序、链式存储表示及实现3）掌握队列的顺序、链式存储表示及实现4）掌握栈与队列在实际问题中的应用三 实验原理1栈的特性栈（Stack）又称堆栈，是一种特殊的线性表，可定义为插入、删除和访问只能在某一端进行的线性数据结构。堆栈允许插入、删除和访问的一端称为栈顶（Top），另一端称为栈底（Bottom）。栈顶的第一个元素被称为栈顶元素。堆栈的性质决定它的数据是按“先进后出”的顺序被访问，即最先存储的元素最后被访问、删除，最后存储的元素最先被访问、删除，所以栈也称为“LIFO”（Last_In, First_Out）。栈的抽象数据类型定义如下：ADT Stack数据对象：D=ai | ai ElemSet, i = 1,2,n, n0数据关系：R = | ai-1, ai D, i = 2, n 约定an端为栈顶，a1端为栈底。基本操作：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 ( ) 。一旦visit ( ) 失败，则操作失败。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁 。 ADT Stack2栈的顺序表示栈的顺序存储结构，即顺序栈，是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时通过指针top指示栈顶元素在顺序栈中的位置。由于很难估计栈在使用过程中所需要的最大空间的大小，所以通常利用C语言中动态分配的一组连续的存储单元作为顺序栈所需要的存储空间。顺序栈所需要的具体数据类型描述如下：#define MAXLEN 100#define STACK_INCREASE 10 /顺序栈存储空间的动态分配增量typedef structElemType *base; /栈的存储空间的基地址，即栈底指针ElemType *top; /栈顶指针int maxsize; /栈当前分配的存储容量SqStack;其中，maxsize指示栈当前可使用的最大容量；base为栈底指针，在顺序栈中，它始终指向栈底的位置，若base=NULL，则表明栈结构不存在；top为栈顶指针，起初值为栈底指针值，即top=base，这也可作为栈空的标记。栈插入新元素时，将新元素插入到栈顶指针所指向的位置，同时指针top增1，删除栈顶元素时，指针top减1。3栈的链式存储表示栈的链式存储结构，即链栈，与线性表的链式存储结构类似，是通过由结点构成的单链表实现的，但每个结点的指针指向其前驱结点（在其之前进栈的结点）。此时，表头指针称为栈顶指针，其指向的结点即为栈顶结点。所需要的具体数据类型描述如下：typedef struct SNodeElemType data;struct SNode *prior; /prior将指向其前一次入栈的元素SNode, *SLink;4队列的特性队列（Queue）简称队，也是一种特殊的线性表，可定义为只允许在表的一端进行插入，而在表的另一端进行删除的线性结构。队列允许插入的一端称为队尾（Rear），允许删除的一端称为队首（Front）。由于队列的插入和删除分别在不同的两端进行，因而先插入者自然先从另一端删除，所以队列具有“先进先出”的特点，简称为FIFO（First-In, First-Out）。队列的抽象数据类型定义如下：ADT Queue 数据对象：D=ai | ai ElemSet, i = 1,2,n, n0数据关系：R1= | ai-1, ai D, i = 2, n 约定其中a1端为队首，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( )。一旦visit( )失败，则操作失败。ClearQueue(&Q) 初始条件：队列Q已存在。 操作结果：将Q清为空队列。DestroyQueue(&Q) 初始条件：队列Q已存在。 操作结果：队列Q被销毁，不再存在。ADT Queue5队列的顺序表示队列的顺序存储结构，用一组地址连续的存储单元依次存放从队首到队尾的元素，同时附设两个指针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）分析掌握教材4850页中的算法3-13-4，为完成实验任务1做好准备。3）分析掌握教材5760页中迷宫问题及求解算法3-13，为完成实验任务1做好准备。4）分析掌握教材7073页中的算法3-153-20，为完成实验任务2做好准备。（2）实验步骤1）问题分析。充分地分析和理解此实验任务，弄清要求作什么，限制条件是什么。2）系统的结构设计。按照以数据结构为中心的原则划分模块。最后写出每个子程序（过程或函数）的规格说明，列出它们之间的调用关系，可以使用调用关系图表示则更加清晰，这样便完成了系统结构设计。3）详细设计。详细设计的目的是对子程序（过程或函数）的进一步求精。用 IF 、WHILE和赋值语句等，以及自然语言写出算法的框架。利用自然语言的目的是避免陷入细节。4）编码。在详细设计的基础上，对详细设计的结果进一步求精，用C语言表示出来。5）在VC环境下调试程序。七 实验报告要求实验报告包含程序开发过程所形成的所有文档资料，包括如下内容：1）需求分析及规格说明：问题描述，求解的问题是什么。2）概要设计：本程序所用的数据类型定义；主程序流程；程序模块及相互关系。3）详细设计：采用C语言定义的数据结构；各模块的伪码算法；各函数调用关系。4）调试报告。5）本实验任务1、2的程序清单及运行结果。八 思考题如果一个程序中用到两个栈，为了不发生溢出错误，就必须给每个栈预先一个较大的存储空间。若每个栈都预先分配过大的存储空间，势必造成系统空间紧张，如何解决这个问题？