数据结构课程设计迷宫求解由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构课程设计迷宫”。
数据结构课程设计
迷宫求解
学院：湖北工业大学计算机学院
教师：沈华老师
班级：12网络工程1班
学号：1210322118
姓名：饶进阳
时间：2013年12月22日
目录
问题描述
.........................................................思路解析
.........................................................程序流程
.........................................................核心代码
.........................................................源程序代码........................................................程序运行实例.....................................................课设总结
.........................................................4 5 6 12 14 迷宫求解
问题描述：
可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；
要求：
在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
比如这是一个迷宫
电脑找出的出路
思
路
设定当前位置的初值为入口位置： do｛
若当前位置可通，则｛
将当前位置插入栈顶；} 若该位置是出口位置，则结束；
否则切换当前位置的东邻块为新的当前位置； 否则｛
若栈不空且栈顶位置还有其他方向未被探索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；} 若{ 栈不空但栈顶位置的四周均不可通，则删去栈顶位置；} 若{ 栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；｝ ｝while(栈不空)｛栈空说明没有路径存在｝
PS：类似动态求解方法
程序流程
第一次用visio做程序框图，所以只把程序的大概流程画出来了。
核心代码
//栈相关操作 int initlStack(Stack *S)int pushStack(Stack S, coordinate e)int popStack(Stack S, coordinate *e)int getTop(Stack S, coordinate *e)void show(Stack S)
//创建一个迷宫 int creatMaze(Maze *m)
//打印出一个迷宫 void showMaze(Maze *m)
//求当前结点的下一个通路
coordinate paNext(Maze *m, int i, int j)//求迷宫路径
int solveMaze(Maze *m, Stack S)//模拟出路径
void showRoad(Maze m, Stack S)
程序源码：
#include #include
#define MAX 100
#define SIZE sizeof(Node)//**************************** //栈
typedef struct { int x;//行
int y;//列 }coordinate;//坐标
typedef struct node{ coordinate data;struct node *next;}Node, *Stack;
//栈的相关操作
//栈初始化
//带头结点的链栈
int initlStack(Stack *S){(*S)=(Node *)malloc(SIZE);if((*S)== NULL){
return 1;}(*S)->next = NULL;return 0;}
//入栈
int pushStack(Stack S, coordinate e){ Node *p;
p =(Node *)malloc(SIZE);p->data.x = e.x;p->data.y = e.y;p->next = S->next;S->next = p;return 0;}
//出栈
int popStack(Stack S, coordinate *e){ Node *p;if(S->next == NULL){
printf(“nStack is empty!n”);
return 2;} e->x = S->next->data.x;e->y = S->next->data.y;p = S->next;S->next = p->next;free(p);return 0;}
//读取栈顶
int getTop(Stack S, coordinate *e){ e->x = S->next->data.x;e->y = S->next->data.y;return 0;}
//显示
void show(Stack S){ Node *p;p = S->next;while(p!= NULL){
printf(“%d %d data.x, p->data.y);
p = p->next;} printf(”startn“);} //***************************
//*************************** //迷宫
typedef struct { int row;int col;int arr[MAX][MAX];}Maze;
//创建一个迷宫
int creatMaze(Maze *m){ int i, j;printf(”nplease input Maze's row and col:n“);scanf(”%d%d“, &(m->row), &(m->col));printf(”nplease input the Maze's meage:(0 is ok),(1 is no)n“);for(i = 0;i
m->arr[i][j] = 1;
} } for(i = 1;i row;i++){
for(j = 1;j col;j++){
scanf(”%d“, &(m->arr[i][j]));
} } return 0;}
//显示迷宫信息
void showMaze(Maze *m){ int i, j;printf(”nthe Maze you hava input:n“);for(i = 1;i row;i++){
for(j = 1;j col;j++){
printf(”%d “, m->arr[i][j]);
}
printf(”n“);}
printf(”nlike this:n“);for(i = 1;i row;i++){
for(j = 1;j col;j++){
if(m->arr[i][j]!= 0){
printf(”■ “);
}
else {
printf(”□ “);
}
}
printf(”n“);} } //求当前结点的下个通路 //顺时针找
coordinate paNext(Maze *m, int i, int j){ coordinate k;if(m->arr[i][j+1] == 0){//东
k.x = i;
k.y = j+1;
return k;}
if(m->arr[i+1][j] == 0){//南
k.x = i+1;
k.y = j;
return k;} if(m->arr[i][j-1] == 0){//西
k.x = i;
k.y = j-1;
return k;} if(m->arr[i-1][j] == 0){//北
k.x = i-1;
k.y = j;
return k;} else {//不存在k.x =-1;
k.y =-1;
return k;} }
//求解迷宫
int solveMaze(Maze *m, Stack S){ int i, j;int boolean;coordinate a;i = 1;j = 1;do {
if(m->arr[i][j] == 0){
a.x = i;
a.y = j;
m->arr[i][j] = 2;
pushStack(S, a);
if(i == m->row && j == m->col){
return 0;
}
}
a = paNext(m, i, j);
if(a.x!=-1){
i = a.x;
j = a.y;
continue;
}
else if(a.x ==-1){
boolean = popStack(S, &a);
if(2 == boolean){
return 0;
}
getTop(S, &a);
i = a.x;
j = a.y;
} }while(S->next!= NULL);return 0;}
//模拟出路径
void showRoad(Maze m, Stack S){ coordinate e;int i, j;if(S->next == NULL){
printf(”nSorry!you can't go out the Maze!n“);} while(S->next!= NULL){
popStack(S, &e);
m.arr[e.x][e.y] =-1;} for(i = 1;i
for(j = 1;j
if(m.arr[i][j] >= 0){
printf(”■ “);
}
else {
printf(”□ “);
}
}
printf(”n“);} } //*************************** //主函数 int main(){ Maze m;Stack S;printf(”※ 欢迎玩耍迷宫求解游戏 ※n“);initlStack(&S);creatMaze(&m);showMaze(&m);solveMaze(&m, S);printf(”nthe root is here:n");show(S);showRoad(m, S);return 0;}
程序运行结果：
第一步：输入迷宫行列大小
第二步：输入迷宫信息
第四步：程序会自动求出路径
课 设 总 结
敬爱的沈华老师您好，感谢您这半年对我们的教诲，说实话，很喜欢上您的课，您上课的风采深深的吸引了我，每次上您的课，我都听得特别认真。好吧，言归正传，谈谈这次课程设计的感想。
首先看到这道题的时候，真心没多少思路，我抱着试一试的态度，去网上搜索相关的算法。网上资源蛮多的，刚开始就搜索到了，严蔚敏老师的相关算法讲解视频，虽然她讲的是思想（就是他并没有源程序的实现），但是足够让我理解了基本算法流程。
其实先开始都不知道怎么下笔，但是我还是想着从基本栈开始写吧，慢慢写着，程序大概思想框架就成型了，最后在实现求解迷宫路径的时候，着手用笔在草稿纸上面模拟，然后才敲到编译器中，最好几经调试，终于得到了想要的结果。
做完这次课设后，深刻的体会到一些道理，在信息时代，解决问题的最好方法是运用现代的信息资源。并且在实际中，开始没思路的事，慢慢完成小部分，那么你的总体思维会渐渐地成型。
做事做人，平心气和的干，总会得到成功！
