《数据结构课程设计报告-迷宫求解》由会员分享，可在线阅读，更多相关《数据结构课程设计报告-迷宫求解（11页珍藏版）》请在金锄头文库上搜索。
1、- 数据构造课程设计 迷宫求解 学院：工业大学计算机学院 教师：华教师 班级：12网络工程1班 *：1210322118 ：饶进阳 时间：2021年12月22日 目 录问题描述 . 2思路解析 . 3程序流程 . 4核心代码 . 5源程序代码 . 6程序运行实例 . 12课设总结 . 141迷宫求解问题描述：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：在上交资料中请写明：存储构造、根本算法可以使用程序流程图、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改良方法；比方这是一个迷宫电脑找出的出路 2 思 路设定当前位置的初值为入口位置：
2、do假设当前位置可通，则将当前位置插入栈顶；假设该位置是出口位置，则完毕；否则切换当前位置的东邻块为新的当前位置；否则假设栈不空且栈顶位置还有其他方向未被探索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；假设栈不空但栈顶位置的四周均不可通，则删去栈顶位置；假设栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；while(栈不空)栈空说明没有路径存在PS：类似动态求解方法 3 程序流程 第一次用visio做程序框图，所以只把程序的大概流程画出来了。 4 核心代码/栈相关操作int initlStack(Stack *S)int pushStack(Stac
3、k 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 passNe*t(Maze *m, int i, int j)/求迷宫路径int solveMaze(Maze *m, Stack S)/模拟出路径void showRoad(Maze m, Stack S) 5程序源码：*
4、include *include *define MA* 100*define SIZE sizeof(Node)/*/栈typedef struct int *;/行int y;/列coordinate;/坐标typedef struct nodecoordinate data;struct node *ne*t;Node, *Stack;/栈的相关操作/栈初始化/带头结点的链栈int initlStack(Stack *S) (*S) = (Node *)malloc(SIZE);if(*S) = NULL) return 1;(*S)-ne*t = NULL;return 0;/入栈in
5、t pushStack(Stack S, coordinate e) Node *p;p = (Node *)malloc(SIZE);p-data.* = e.*;p-data.y = e.y;p-ne*t = S-ne*t;S-ne*t = p;return 0;/出栈int popStack(Stack S, coordinate *e) Node *p;if(S-ne*t = NULL) printf(nStack is empty!n);return 2;e-* = S-ne*t-data.*;e-y = S-ne*t-data.y;p = S-ne*t;S-ne*t = p-ne*
6、t;free(p);return 0;/读取栈顶int getTop(Stack S, coordinate *e) e-* = S-ne*t-data.*;e-y = S-ne*t-data.y;return 0;/显示void show(Stack S) Node *p;p = S-ne*t;while(p != NULL) printf(%d %d data.*, p-data.y);p = p-ne*t;printf(startn);/*/*/迷宫typedef struct int row;int col;int arrMA*MA*;Maze;/创立一个迷宫int creatMaze
7、(Maze *m) int i, j;printf(nplease input Mazes row and col:n);scanf(%d%d, &(m-row), &(m-col);printf(nplease input the Mazes message:(0 is ok), (1 is no)n);for(i = 0; i = MA* - 1; i+) for(j = 0; j arrij = 1;for(i = 1; i row; i+) for(j = 1; j col; j+) scanf(%d, &(m-arrij);return 0;/显示迷宫信息void showMaze(
8、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-arrij);printf(n);printf(nlike this:n);for(i = 1; i row; i+) for(j = 1; j col; j+) if(m-arrij != 0) printf( );else printf( );printf(n);/求当前结点的下个通路/顺时针找coordinate passNe*t(Maze *m, int i, int
9、 j) coordinate k;if(m-arrij+1 = 0) /东k.* = i;k.y = j+1;return k; if(m-arri+1j = 0) /南k.* = i+1;k.y = j;return k;if(m-arrij-1 = 0) /西k.* = i;k.y = j-1;return k;if(m-arri-1j = 0) /北k.* = i-1;k.y = j;return k;else /不存在k.* = -1;k.y = -1;return k;/求解迷宫int solveMaze(Maze *m, Stack S) int i, j;int boolean;
10、coordinate a;i = 1;j = 1;do if(m-arrij = 0) a.* = i;a.y = j;m-arrij = 2;pushStack(S, a);if(i = m-row & j = m-col) return 0; a = passNe*t(m, i, j); if(a.* != -1) i = a.*; j = a.y; continue; else if(a.* = -1) boolean = popStack(S, &a);if(2 = boolean) return 0;getTop(S, &a); i = a.*; j = a.y;while(S-ne*t != NULL);return 0;/模拟出路径void showRoad(Maze m, Stack S) coordinate e;int i, j;if(S-ne*t = NULL) printf(nSorry! you cant go out the Maze!n);while(S-ne*t !=
