栈和队列综合实验报告

栈和队列综合实验报告

一、实验目的

（1）能够利用栈和队列的基本运算进行相关操作。 （2）进一步熟悉文件的应用

（3）加深队列和栈的数据结构理解，逐步培养解决实际问题的编程能力。

二、实验环境

装有Visual C＋＋的计算机。 本次实验共计4学时。

三、实验内容

以下两个实验任选一个。

1、 迷宫求解

设计一个迷宫求解程序，要求如下：

以M × N表示长方阵表示迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

能任意设定的迷宫

（选作）如果有通路，列出所有通路 提示：

以一个二维数组来表示迷宫，0和1分别表示迷宫中的通路和障碍，如下图迷宫数据为： 11

1

01 01 01 01 01 01 01 01 11

入口位置：1 1 出口位置：8 8

四、重要数据结构

typedef struct{

int j[100];

int top;栈顶指针，一直指向栈顶

}stack;//存放路径的栈

int s[4][2]={{0,0},{0,0},{0,0},{0,0}};

//用于存放最近的四步路径坐标的数组，是即使改变的，即走一步，便将之前的坐标向前移一步，将最早的一步坐标覆盖掉，新的一步放入数组末尾其实功能和队列一样。

其作用是用来判断是否产生了由于本程序算法产生的“田”字方格内的死循环而准备的，用于帮助跳出循环。

五、实现思路分析

if(a[m][n+1]==0&&k!=3){

n++; k=1; o=0;

}else if(a[m+1][n]==0&&k!=4){

m++;

2

k=2; o=0;

}else if(a[m][n-1]==0&&k!=1){

n--; k=3; o=0;

}else if(a[m-1][n]==0&&k!=2){

m--; k=4; o=0;

}else{

o++;}

if(o>=2){

k=0;

}//向所在方格的四个方向探路，探路顺序为→↓←↑（顺时针），其中if判

断条件内的&&k!=n和每个语句块中的对k赋值是为防止其走回头路进入死循环，而最后一个else{}内语句是为了防止进入死路时，不能走回头路而造成的死循环。

if (pushf(&s[0][0],m,n)==0){

push(q,m,n);//没进行一次循环都会讲前进的路径入栈。

k=3;}//用来判断是否产生了由于本程序探路算法产生的“田”字方格内的死循环

而准备的，用于帮助跳出田字循环。同时会将路径存入用于下次判断

六、程序调试问题分析

最开始写完时是没有死路回头机制的，然后添加了两步内寻路不回头机制。

第二个是“田”字循环问题，解决方法是加入了一个记录最近四步用的数组和一个判断田字循环的函数pushf。

3

int pushf(int *a,int m,int n){

int j=0;

if(m==a[0]&&n==a[1]){//判断最新的一步是否和4步之前的走的是同一个坐标

点，//从而返回判断值，以便跳出循环。 最

//早的一步，放入最新的一步。 }

另外由于探路算法特新并不会产生3x3,4x4等的方阵循环。

想到的隐藏问题：如果是3x3方阵，但中间的一块是墙的话就会产生3x3方阵的死循环。

a[j]=a[j+2]; a[j+1]=a[j+3]; return 0; }

while(j<8){//如果没有发生田字训话，将4*2数组内的4组坐标向前移动覆盖掉

j=j+2; }

a[6]=m,a[7]=n; return 1;

七、实验总结

熟悉了栈的应用和操作。

对问题的考虑不够彻底，且写程序前所能想到的问题少。 程序整规划能力欠缺，照成可读性不高。

4