数据结构课程设计-迷宫求解.doc

《数据结构课程设计-迷宫求解.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计-迷宫求解.doc（14页珍藏版）》请在三一办公上搜索。

1、精选优质文档-倾情为你奉上 数据结构课程设计 迷宫求解 学院：湖北工业大学计算机学院 教师：沈华老师 班级：12网络工程1班 学号： 姓名：饶进阳 时间：2013年12月22日 目 录问题描述 . 2思路解析 . 3程序流程 . 4核心代码 . 5源程序代码 . 6程序运行实例 . 12课设总结 . 14 1 迷宫求解问题描述：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；比如这是一个迷宫电脑找出的出路 2 思 路设定当

2、前位置的初值为入口位置：do若当前位置可通，则将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的东邻块为新的当前位置；否则若栈不空且栈顶位置还有其他方向未被探索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则删去栈顶位置；若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；while(栈不空)栈空说明没有路径存在PS：类似动态求解方法 3 程序流程 第一次用visio做程序框图，所以只把程序的大概流程画出来了。 4 核心代码/栈相关操作int initlStack(Stack *S)int pushSta

3、ck(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 passNext(Maze *m, int i, int j)/求迷宫路径int solveMaze(Maze *m, Stack S)/模拟出路径void showRoad(Maze m, Stack S)

4、5程序源码：#include #include #define MAX 100#define SIZE sizeof(Node)/*/栈typedef struct int x;/行int y;/列coordinate;/坐标typedef struct nodecoordinate data;struct node *next;Node, *Stack;/栈的相关操作/栈初始化/带头结点的链栈int initlStack(Stack *S) (*S) = (Node *)malloc(SIZE);if(*S) = NULL) return 1;(*S)-next = NULL;return

5、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

6、= 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 arrMAXMAX;Maze;/创建一个迷宫int cr

7、eatMaze(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 = MAX - 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 sh

8、owMaze(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 passNext(Maze *m, int

9、 i, int j) coordinate k;if(m-arrij+1 = 0) /东k.x = i;k.y = j+1;return k; if(m-arri+1j = 0) /南k.x = i+1;k.y = j;return k;if(m-arrij-1 = 0) /西k.x = i;k.y = j-1;return k;if(m-arri-1j = 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 b

10、oolean;coordinate a;i = 1;j = 1;do if(m-arrij = 0) a.x = i;a.y = j;m-arrij = 2;pushStack(S, a);if(i = m-row & j = m-col) return 0; a = passNext(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;whi

11、le(S-next != NULL);return 0;/模拟出路径void showRoad(Maze m, Stack S) coordinate e;int i, j;if(S-next = NULL) printf(nSorry! you cant go out the Maze!n);while(S-next != NULL) popStack(S, &e);m.arre.xe.y = -1;for(i = 1; i = m.row; i+) for(j = 1; j = 0) printf( );else printf( );printf(n);/*/主函数int main() M

12、aze 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;程序运行结果：第一步：输入迷宫行列大小第二步：输入迷宫信息第四步：程序会自动求出路径 课 设 总 结 敬爱的沈华老师您好，感谢您这半年对我们的教诲，说实话，很喜欢上您的课，您上课的风采深深的吸引了我，每次上您的课，我都听得特别认真。好吧，言归正传，谈谈这次课程设计的感想。 首先看到这道题的

13、时候，真心没多少思路，我抱着试一试的态度，去网上搜索相关的算法。网上资源蛮多的，刚开始就搜索到了，严蔚敏老师的相关算法讲解视频，虽然她讲的是思想（就是他并没有源程序的实现），但是足够让我理解了基本算法流程。 其实先开始都不知道怎么下笔，但是我还是想着从基本栈开始写吧，慢慢写着，程序大概思想框架就成型了，最后在实现求解迷宫路径的时候，着手用笔在草稿纸上面模拟，然后才敲到编译器中，最好几经调试，终于得到了想要的结果。 做完这次课设后，深刻的体会到一些道理，在信息时代，解决问题的最好方法是运用现代的信息资源。并且在实际中，开始没思路的事，慢慢完成小部分，那么你的总体思维会渐渐地成型。 做事做人，平心气和的干，总会得到成功！专心-专注-专业