目录
-
课程设计目的
本课程目的在于充分理解队列的应用，了解队列“先进先出”以及“后进后出“，且只能从一端进入，另一端出去的特点。结合这一特性在众多路线中并行搜索，寻找到能够到达出口的最短路线，提高寻找效率。
-
课程设计内容和要求
-
问题描述
通过自身输入的d*h的迷宫图，规定入口以及出口，且不能重复行走。如果能找到出口，则正向输出从入口到出口的最短路径，反之则该迷宫无解。
2.设计要求
自己设计迷宫，利用队列求解迷宫问题，且迷宫最外层全为墙。
-
课程设计总体方案及分析
-
问题分析
需要自定义该迷宫的规模（为输入迷宫形状既为了美观，连续输入读取数据，Enter换行换行作为分隔符，只有将数据输入完并按下Enter才执行下一个程序，则使用C++中的cin进行输入迷宫形状，但也需注意C++的头文件），确定墙和路以及入口和出口的位置，将每一个路进行入队操作，且入队的路进行标记，防止重复行走，直至出口位置入队，最后将其最短路径进行正向输出。
2.概要设计
为在存储空间的使用上更加高效，选择顺序队列进行迷宫求解。迷宫中用“0“作为路，”1“作为墙， 用i和j记录每一个位置，以及用pre记录前一方块的位置（既找到该方块从哪里来）。将入口先进行入队操作,并将其值置为-1（表示该路已经走过，防止重复行走），非空则进行出队操作，记录出队的数据（i，j,pre）,如果不是目标出口则在其四周寻找路，并将其位置（i，j）以及前一方块的位置（pre）入队，并且将其值置为-1，四周入队之后再将对头进行出队操作，直至出口作为队头出队才结束。最后再通过pre寻找最短路径，并将其pre置为-1，再通过pre为-1将其路线正向输出。
3.详细设计
-
数据结构设计
typedef struct
{
int i, j, pre;
}Box;
typedef struct
{
Box data[15]; //队列中存放i，j，pre的数据
int rear, front; //队尾指针和队尾指针记录其值
}Q; //采用顺序队列，高效利用存储空间
-
函数功能设计
void InitQ(Q*& qu) //初始化队列
bool EmptyQ(Q*& qu) //用于判断队列是否为空
bool inE(Q*& qu, Box& e) //进队操作
bool outE(Q*& qu, Box& e) //出队操作
void print(Q*& qu, int k) //将找到的最短路径输出打印
bool huan(int xi, int xj, int zi, int zj) //迷宫的算法路径
void DestroyQ(Q*& qu) //使用完后进行销毁，释放空间-
调试分析
C语言中的scanf输入不能实现换行操作，为实现迷宫的换行让其更加美观，可以使用C++中的cin进行输入。
-
测试结果
-
课程设计总结
此次迷宫算法要灵活记录当前位置以及前一方块，通过记录的pre找到最短路径。但是此代码也存在不足，输出的最短路径只有一种，实际上最短路径可以是多种路径，且四个方向先后询问是否为路的顺序也会影响这该怎么走，但是都是最短路径。
附录（源代码）
#include<iostream>
#include<algorithm>
using namespace std;
#define M 100
#define N 100
typedef struct
{
int i, j, pre;
}Box;
typedef struct
{
Box data[15];
int rear, front;
}Q;
int m[M][N];
void InitQ(Q*& qu)
{
qu = (Q*)malloc(sizeof(Q));
qu->front = qu->rear = -1;
}
bool EmptyQ(Q*& qu)
{
return(qu->front == qu->rear);
}
bool inE(Q*& qu, Box& e)
{
if (qu->rear >= 15)
return 0;
qu->rear++;
qu->data[qu->rear] = e;
return 1;
}
bool outE(Q*& qu, Box& e)
{
if (EmptyQ(qu))
return 0;
qu->front++;
e = qu->data[qu->front];
return 1;
}
void DestroyQ(Q*& qu)
{
free(qu);
}
void print(Q*& qu, int k)
{
int j;
while (k != -1)
{
j = k;
k = qu->data[k].pre;
qu->data[j].pre = -1;
}
int g = 0, deng = 0;
while (g < 15)
{
if (qu->data[g].pre == -1)
{
printf("(%d,%d)-> ", qu->data[g].i, qu->data[g].j);
}
g++;
}
printf("\n");
}
bool huan(int xi, int xj, int zi, int zj)
{
Box e;
Q* qu;
InitQ(qu);
int i, j, pre;
e.i = xi, e.j = xj, e.pre = -1;
m[xi][xj] = -1;
inE(qu, e);
while (!EmptyQ(qu))
{
outE(qu, e);
i = e.i, j = e.j, pre = e.pre;
if (i == zi && j == zj)
{
print(qu, qu->front);
return 1;
}
int d =0;
int ni, nj;
while (d < 4)
{
switch (d)
{
case 0:ni = i - 1, nj = j;break;
case 1:ni = i, nj = j + 1;break;
case 2:ni = i + 1, nj = j;break;
case 3:ni = i, nj = j - 1;break;
}
if (m[ni][nj] == 0)
{
e.i = ni, e.j = nj, e.pre = qu->front;
inE(qu, e);
m[ni][nj] = -1;
}
d++;
}
}
DestroyQ(qu);
return 0;
}
int main()
{
int i, j;
int d, h;
printf("请输入迷宫规格d,h:\n");
scanf_s("%d%d", &d, &h);
printf("迷宫形状:\n");
for (i = 0;i < d;i++)
for (j = 0;j < h;j++)
cin >> m[i][j];
printf("\n");
if (huan(1, 1, d-2, h-2) == 0)
printf("无解");
printf("\t迷宫逃离出来啦！！！");
printf("\n");
return 0;
}标签：pre,Box,课程设计,qu,队列,迷宫,最短,int From： https://blog.csdn.net/2302_80115666/article/details/139213315如有不足，欢迎提出嘿嘿。