数据结构课程设计报告-迷宫求解

1、数据结构课程设计报告迷宫问题求解学号： 1315925375 姓名：刘晓龙班级： 13 移动 1 班 指导老师：钱鸽目录一、需求分析 3二、数据结构 31. 数据结构设计考虑 32. 逻辑结构存储结构 3三、算法设计 4四、调试分析 7五、程序实现及测试 8六、体会及不足之处 9七、参考文献 10八、源代码 10一、需求分析本课程设计是解决迷宫求解的问题， 从入口出发， 顺某一方向向前探索，若能走通，则继续 往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为 了保证在任何位置上都能沿原路退回， 显然需要用一个后进先出的结构来保存从入口到当前 位置的路径。 因此，在

2、求迷宫通路的算法中要应用 “栈”的思想假设 “当前位置” 指的是 “在 搜索过程中的某一时刻所在图中某个方块位置” ，则求迷宫中一条路径的算法的基本思想是： 若当前位置 “可通”，则纳入“当前路径” ，并继续朝 “下一位置”探索，即切换 “下一位置” 为“当前位置” ，如此重复直至到达出口；若当前位置“不可通” ，则应顺着“来向”退回到 “前一通道块” ，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周 4 个方 块均“不可通” ，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是当前位置 四周 4 个方向（上、下、左、右）上相邻的方块。假设以栈记录“当前路径” ，则栈顶中存

3、放的是“当前路径上最后一个通道块” 。由此，“纳入路径”的操作即为“当前位置入栈” ； “从当前路径上删除前一通道块”的操作即为“出栈” 。二、数据结构1. 数据结构设计考虑1） 建立一个二维数组表示迷宫的路径（0 表示通道， 1 表示墙壁） ；2） 创建一个栈， 用来存储“当前路径” ，即“在搜索过程中某一时刻所在图中某个方块位置”。2. 逻辑结构存储结构1） 创建一个 Int 类型的二维数组 int mazen1n2, 用来存放 0 和 1（0 表示通道，1 表示墙壁）；2） 创建一个结构体用来储存数组信息结构体：typedef struct/ 迷宫内部设置int shu1616;int

4、row;int col;Maze;创造一个链栈struct nodeint row;int col;struct node *next;三、算法设计首先，创建数组的大小，此数组大小要求用户自己输入。具体算法： printf( 输入迷宫的形状 !n);scanf(%d%d,&x,&y);Maze m;CreatInit(&m,x,y);函数：void CreatInit(Maze *m,int x,int y)/ 创建迷宫 printf(please input number:n);int i,j;for(i=0;i=x;i+)for(j=0;jshuij = 2;for(i=1;i=x;i+)

5、for(j=1;jshuij); m-row = x;m-col = y; 其中的 0 和 1 分别是表示通路和障碍，定义的数组其实就是迷宫的设计图 其次，产生迷宫，算法：for(i=1;i=x;i+)for(j=1;j= 1 & x1 = 1 & y1next=NULL) break;x1=p-row; y1=p-col;if(x1 = x2 & y1 = y2) while(p-next != NULL) printf(%d %dn,p-row,p-col);pop()；elseprin tf(No An swer !);其中要寻求所有的通路，在这里则使用了一个 while循环，这样可以找

6、到所有的通路。图解分析:整体流程图:迷宫内部操作流程图:否开始开始数据四、调试分析第一个问题，在刚开始的调试过程中，我们遇到了，无法判断走过的路程，从而出现了死循环，导致程序不能正常进行，但是经过我们的讨论，我们想出用标记的方法来解决，也就是 让走过的路程全给标示了，这样就不会再走重复的路。第二个问题，就是性用菜单来实现操作， 那样程序的操作性就会更强， 所以我们就要把所有 的方法，给写成一个个的函数来调用， 这样就遇到了参量传递的问题， 但是经过我们的参考 以及从书本上的实例，我们慢慢地更深的了解到了参量传递的应用， 那么这个问题也就迎刃 而解了。从此我们实现了菜单操作！五、程序实现及测试运

7、行界面:4l 千 Jl 卓車卓耳 *44*4*-1* 卓单 X +# *敗蜀密A迷营1. 送入迷宫2. 退肥请选聲:开始界面iiLL11O11里斗* *卓沖車宰卓*車*哮卓韋沖*卓弗章療瑟遇人迷宫1, 进扎逢宫2. 退岀输入迷宫的光輩|8 Bplease input number：1 e 11 1 0 e 11 11 o111&110 11Qe9111111ee0110111L0e1119ea011011e011e11110111110e09110输入人口便宣注4需入出口的位畫:8 4输入入口位置J 4 输人出口的位置；呂466411116Q諭A.A. 口恆盍：1 4算A.L片口的宦盍沼444

8、311111G44 44444：* t* V* V*戏迎迸人徙宫1, 迭扎噬宫 宜退岀诒选暮t六、体会及不足之处通过此次课程设计，是我对于数据结构有了更深的了解，更新的认识。数据结构是一门重 要的课程，只有数据结构学得扎实了， 才能对于计算机有更深的应用，所以学好数据结构是很重要的。经过两周的上机设计，我实现了简单的迷宫求解，能够简单的实现求解过程。但是还存在着不足之处，本程序不能循环执行，只能执行一次。有待改进！七、参考文献1、 数据结构 (c 语言版 ) 严蔚敏 清华大学出版社2、 数据结构实验教程 李业丽、郑良斌 数据结构 高教出版社3、 数据结构习题 李春保 清华大学出版社4、 数据结

9、构习题 严蔚敏 清华大学出版社5、 C 语言与数据结构 王立柱 清华大学出版社6、 数据结构 (C 语言篇 )习题与解析 李春保 清华大学出版社。八、源代码#include #include typedef struct/ 迷宫内部设置int shu1616;int row;int col;Maze;struct nodeint row;int col; struct node *next;struct node *p;void push(int x1,int y1)struct node *a; a=(struct node *)malloc(sizeof(struct node);a-ro

10、w=x1; a-col=y1; a-next=p;p=a;void pop(void)struct node *q;q=p;p=p-next; free(q);void CreatInit(Maze *m,int x,int y)/ 创建迷宫 printf(please input number:n);int i,j;for(i=0;i=x;i+)for(j=0;jshuij = 2;for(i=1;i=x;i+)for(j=1;jshuij); m-row = x;m-col = y;void menu()printf(n*n);printf（ 欢迎进入迷宫 n）;printf(1、进入迷宫

11、 n);printf(2、退出 n);int main(void) int t;int x,y;int x1,y1;int x2,y2; int i,j; while(1) menu();printf( 请选择 :);scanf(%d,&t);if(t = 2)break;printf( 输入迷宫的形状 !n); scanf(%d%d,&x,&y);Maze m;CreatInit(&m,x,y);for(i=1;i=x;i+)for(j=1;jrow=0;p-col=0; p-next=NULL;push(x1,y1);= 1 & x1 = 1 & y1 if(x1 = x2 & y1 = y2)break;if(m.shux1y1+1 = 0 ) y1=y1+1; push(x1,y1); m.shux1y1 = -1; continue;if(m.shux1-1y1=0 ) x1=x1-1; push(x1,y1); m.shux1y1 = -1; continue;if(m.shux1y1-1=0 )y1=y1-1; push(x1,y1); m.shux1y1= -1;continue;if(m.shux1+1y1=0 ) x1=x1+1; push(