实验二栈和队列及其应用
一、实验目的
1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。
2. 熟练掌握栈类型的两种实现方法。
3. 熟练掌握循环队列和链队列的基本操作实现算法。
二、实验内容
用队列求解迷宫问题
[问题描述]
以一个M*N的长方阵表示迷宫，0和1分别表示迷宫中的通路和墙壁。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
[基本要求]
实现一个以顺序存储结构的队列类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，pre）的形式输出，其中：（i，j）指示迷宫中的一个坐标，pre表示本路径中上一个方块在队列中的下标。
[测试数据] 由学生任意指定。
三、源代码
# include
#define M 5 //行数
#define N 5 //列数
#define MaxSize 100 //队最多元素个数
int mg[M+2][N+2]={ //一个迷宫,其四周要加上均为1的外框{1,1, {1,1,1,1,1,1,1},
{1,0,0,0,0,0,1},
{1,0,1,0,0,1,1},
{1,0,1,0,0,1,1},
{1,0,1,0,1,0,1},
{1,0,0,0,0,0,1},
{1,1,1,1,1,1,1}
};
typedef struct
{int i,j;
int pre;}
Box;
typedef struct
{
Box data[MaxSize];
int front, rear;
}QuType;
void mgpath1(int xi,int yi,int xe,int ye) //搜索路径为：（xi，yi）->(xe,ye)
{ void print (QuType qu, int front );
int i,j,find=0,di;
QuType qu; //定义顺序队
qu.front=qu.rear=-1;
qu.rear++;
qu.data[qu.rear].i=xi; //(xi,yi)进队
qu.data[qu.rear].j=yi;
qu.data[qu.rear].pre=-1;
mg[xi][yi]=-1;
while(qu.front!=qu.rear&&!find)
{qu.front++;
i=qu.data[qu.front].i;j=qu.data[qu.front].j;
if(i==xe&&j==ye)
{find=1;
print(qu,qu.front);
}
for
(di=0;di<4;di++)
{
switch(di)
{
case
0 :i=qu.data[qu.front].i-1;j=qu.data[qu.front].j;break;
case
1 :i=qu.data[qu.front].i;j=qu.data[qu.front].j+1;break; case
2 :i=qu.data[qu.front].i+1;j=qu.data[qu.front].j+1;break; case
3 :i=qu.data[qu.front].i;j=qu.data[qu.front].j-1;break;
}
if(mg[i][j]==0)
{find=1;
qu.rear++;
qu.data[qu.rear].i=i; qu.data[qu.rear].j=j;
qu.data[qu.rear].pre=qu.front;
mg[i][j]=-1;
}
}
}
}
void print (QuType qu, int front )
{
int k=front,j,ns=0;
printf("\n");
do
{j=k;
k=qu.data[k].pre;
qu.data[j].pre=-1;
}
while (k!=0);
printf("迷宫路径如下：\n");
k=0;
while(k{
if(qu.data[k].pre==-1)
{
ns++;
printf("\t(%d,%d)",qu.data[k].i,qu.data[k].j);
if(ns%5==0)printf("\n");
}
k++;
}
printf("\n");
}
void main()
{ mgpath1(1,1,M,N);
printf("迷宫所有路径如下:\n");
}
四、测试结果：
五、心得体会
做实验首先要掌握大量的理论知识，然后认真去完成实验。做实验过程会碰见较大的困难，这就要需要我们的毅力。小小的迷宫隐藏大大的奥秘。
