数据结构课程设计报告-迷宫求解之欧阳语创编

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

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

3、除前一通道块”的操 作即为出栈。二数据结构1. 数据结构设计考虑1）建立一个二维数组表示迷宫的路径（0表示通道” 1表示 墙壁）;2）创建一个栈,用来存储当前路径，即在搜索过程 中某一时刻所在图中某个方块位置。2. 逻辑结构存储结构1）创建一个Int类型的二维数组int mazenln2/ffi来存 放0和1 （0表示通道，1表示墙壁）；2）创建一个结构体用来储存数组信息结构体：typedef struct/迷宫内咅B设置int shu1616;int row;int col;Maze;创造一个链栈struct node int row;int col;struct node *next;；三

4、、算法设计首先,创建数组的大小，此数组大小要求用户自己输入。具 体算法：printfC*输入迷宫的形状!n“)；scanf(”d%cT&x,&y);Maze m;Creatlnit(&m,x,y);函数：void CreatInit(Maze *m,int xjnt y)创建迷宫prints (please in put nu mber:n);int i,j;for(i=0;i=x;i + +)for(j=0;jshuij = 2;for(i = l;i=x;i+)for(j = l;jshuij);m-row = x;col = y;其中的0和1分别是表示通路和障碍,定义的数组其实就 是迷宫

5、的设计图其次，产生迷宫，算法:for(i = l;i=x;i + +)for(j = l;j= 1 & xl = 1 & yl next= = NULL)break;xl=p row;yl=p col;if(xl = x2 & yl 二二 y2)while(p-next != NULL)print:f(%d %dn/p-rowzp-col);pop()；elseprintfCNo Answer !H);其中要寻求所有的通路,在这里则使用了一个while循环, 这样可以找到所有的通路。图解分析:整体流程图：迷宫内部操作流程图：调试分析 第一个问题，在刚开始的调试过程中，我们遇到了，无法判 断走过

6、的路程，从而出现了死循环，导致程序不能正常进 行，但是经过我们的讨论,我们想出用标记的方法来解决, 也就是让走过的路程全给标示了，这样就不会再走重复的 路。第二个问题,就是性用菜单来实现操作,那样程序的操作性 就会更强”所以我们就要把所有的方法,给写成一个个的函 数来调用，这样就遇到了参量传递的问题，但是经过我彳门的 参考以及从书本上的实例,我们慢慢地更深的了解到了参量 传递的应用，那么这个问题也就迎刃而解了。从此我们实现 了菜单操作！五.程瘵实现及测试运行界面：开始界面体会及不足之处通过此次课程设计，是我对于数据结构有了更深的了解， 更新的认识。数据结构是一门重要的课程，只有数据结构学 得扎

7、实了,才能对于计算机有更深的应用所以学好数据结 构是很重要的。经过两周的上机设计，我实现了简单的迷宫 求解,能够简单的实现求解过程。但是还存在着不足之处， 本程序不能循环执行，只能执行一次。有待改进!七、参考文献1、数据结构（c语言版）严蔚敏清华大学出版社2、数据结构实验教程李业丽、郑良斌数据结构 高教出版社3、数据结构习题李春保清华大学出版社4、数据结构习题严蔚敏清华大学出版社5、C语言与数据结构王立柱清华大学出版社6、数据结构（C语言篇）习题与解析李春保清华大学出 版社。八、源代码#inelude #inelude typedef struct/迷宫内咅设置int shu1616;int

8、row;int col;Maze;struct node int row;int col;struct node *next;struct node *p;void push(int xl,int yl)struct node *a;a = (struct node *)malloc(sizeof(struct node); a-row=xl;a-col=yl;a-next=p;p=a；void pop(void)struct node *q;q=p；p=p-next;free(q);void CreatInit(Maze *m,int xjnt y)创建迷宫prints (please in

9、 put nu mber:n);int izj;for(i=0;i=x;i + +) for(j=0;jshuij = 2;for(i = l;i=x;i + +)for(j = l;jshuij);m-row = x; m-col = y;void menu()printf(HnprintfC*欢迎进入迷宫n”);printf(“l、进入迷宫n”);pnntf(2s 退出n”)；int main(void)int t;int x,y;int xlzyl；int x2zy2;int ij;while(l)menu();prin廿C请选择:”)；scan f(”d：&t);if(t = 2)break;printfC*输入迷宫的形状!n“); scan f(%d%d,/&x/&y); Maze m;Creatlnit(&m,x,y);for(i = l;i=x;i+)for(j = l;jrow=0;p-col=0;p-next=NULL;push(xl,yl);while(xl = 1 & xl = 1 & yl n ext= = NULL) b