实验5：链栈的基本操作
一、实验目的
1）熟悉栈的定义和栈的基本操作。 2）掌握链式存储栈的基本运算。
3）加深对栈数据结构的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋的计算机。 本次实验共计2学时。
三、实验内容
必做内容： 链栈的基本操作
编写栈的基本操作函数
1． 栈类型的定义，数据域使用char型 typedef char ElemType;
typedef struct node{
ElemType data;
struct node *next; } LinkStack;
2．初始化空栈：函数原型如下：
void InitLinkStack（ LinkStack * & s）
其中函数参数为LinkStack * & 类型，表示指向创建的空栈的指针，并且用引用方式传入。
3. 判断是否空栈：函数原型如下：
int IsEmptyLinkStack（LinkStack *s ）
其中函数参数为栈指针；返回值为int型，1表示是空栈，0表示不是空栈。
4. 入栈：函数原型如下：
void PushLinkStack（LinkStack* &s , ElemType x） 其中函数参数s为栈指针，x为入栈的数据。
5. 出栈：函数原型如下：
int PopLinkStack (LinkStack* & s, ElemType &x)
其中函数参数s为栈指针，x为出栈的数据的引用；返回值为int型，1表示出栈成功，0
表示出栈失败。
6．取栈顶元素：(栈保持不变)函数原型如下：
int GetLinkStackTop (LinkStack* s, ElemType &x)
其中函数参数s为栈指针，x存放栈顶元素值；返回值为int型，1表示成功，0表示失败。
编写主函数
调用上述函数实现下列操作。 1．初始化空栈。
2. 键盘输入字符，使得输入的字符依次入栈（结束符号自定，例如回车键(值为10)或'#'） 每插入一个元素，必须输出当时的栈顶元素(调用GetLinkStackTop函数)。 3．判断链栈是否为空。输出判断结果。
4．调用出栈函数，打印出栈元素的值；反复此步骤，直至栈为空。 5．判断链栈是否为空。输出判断结果。 6．释放链栈。
选做内容（一）：判断对称字符串
设计一个算法，调用栈的基本运算，判断一个字符串是否为对称字符串。若是返回1；否则返回0。 例如：“abcba”和“abba”都是对称字符串。
实验6：队列的基本操作
一、实验目的
1）熟悉队列的定义和队列的基本操作。
2）掌握顺序循环队列和链式存储队列的基本运算。
3）加深对队列数据结构的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋的计算机。 本次实验共计2学时。
三、实验内容
队列的基本操作
队列的存储结构从顺序循环队列或者链队任选一种。
编写一个程序，实现队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能： （1） 初始化队列q （2） 判断q是否非空
（3） 依次进队元素a，b，c
（4） 出队一个元素，输出该元素 （5） 输出队列q的元素个数 （6） 依次进队列元素d，e，f （7） 输出队列q的元素个数 （8） 输出出队序列 （9） 释放队列
实验7：栈和队列综合实验
一、实验目的
（1）能够利用栈和队列的基本运算进行相关操作。 （2）进一步熟悉文件的应用
（3）加深队列和栈的数据结构理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋的计算机。 本次实验共计4学时。
三、实验内容
以下两个实验任选一个。
1、 迷宫求解
设计一个迷宫求解程序，要求如下：
以M × N表示长方阵表示迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
能任意设定的迷宫
（选作）如果有通路，列出所有通路 提示：
以一个二维数组来表示迷宫，0和1分别表示迷宫中的通路和障碍，如下图迷宫数据为：
11 01 01 01 01 01 01 01 01 11
入口位置：1 1
出口位置：8 8
探索过程可采用如下算法，设定当前位置的初值为入口位置；
do {
若当前位置可通， 则｛
将当前位置插入栈顶；
若该位置是出口位置，则结束；
否则切换当前位置的东邻方块为新的当前位置；
｝
否则， ｛
若栈不空且栈顶位置尚有其他方向未经探索，
则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；
栈
顶
位
置
；
若栈不空但栈顶位置的四周均不可通，
（1） 则｛删去
1 0 3 0 0 1 0 0 0 0 1 0 0 0 1 0 3 0 0 0 0 4 0 0 0 0 1 0 0 0 0 2 1 1 2 4 1 2 3 5 2 3 4 6 4 5 6 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
实验指导手册
