2数据结构-实验报告二(栈和队列及其应用)

2数据结构-实验报告二(栈和队列及其应用)（共1篇）

2数据结构-实验报告二(栈和队列及其应用) 篇1

实验二 栈和队列及其应用

一、实验目的

1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。

2.熟练掌握栈类型的两种实现方法。

3.熟练掌握循环队列和链队列的基本操作实现算法。

二、实验内容

用队列求解迷宫问题 [问题描述] 以一个M*N的长方阵表示迷宫，0和1分别表示迷宫中的通路和墙壁。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。[基本要求] 实现一个以顺序存储结构的队列类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，pre）的形式输出，其中：（i，j）指示迷宫中的一个坐标，pre表示本路径中上一个方块在队列中的下标。

[测试数据] 由学生任意指定。

三、源代码

# include #define M 5 #define N 5

//行数 //列数

//队最多元素个数

//一个迷宫,其四周要加上均为1的外框{1,1, #define MaxSize 100 int mg[M+2][N+2]={ {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）{ void print(QuType qu, int front);->(xe,ye)

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

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”);

}

四、测试结果：

五、心得体会

做实验首先要掌握大量的理论知识，然后认真去完成实验。做实验过程会碰见较大的困难，这就要需要我们的毅力。小小的迷宫隐藏大大的奥秘。