数据结构迷宫问题课程设计.doc

数据结构课程设计报告设计题目： 迷宫问题数据结构课程设计 _ 班 级： 计科152 学 号： 19215225 姓 名： 徐昌港 南京农业大学计算机系数据结构课程设计报告内容1 课程设计题目迷宫问题以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。二算法设计思想1.需求分析（1）迷宫数据用一个二维数组int mazerowcol来存储，在定义了迷宫的行列数后，用两个for循环来录入迷宫数据，并在迷宫周围加墙壁。 （2）迷宫的入口位置和出口位置可以由用户自己决定。2.概要设计（1）主程序模块：void main()int mazerowcol;struct mark start,end; /出入口的坐标int dir42=0,1,1,0,0,-1,-1,0; /方向，依次是东西南北built_maze(maze);printf(请输入入口的横纵坐标：);scanf(%d,%d,&start.a,&start.b);printf(请输入出口的横纵坐标：);scanf(%d,%d,&end.a,&end.b);printf(0为东，1为南，2为西，3为北，-1为出路n);maze_path(maze,dir,start,end);getchar();（2） 栈模块实现栈抽象数据类型（3） 迷宫模块实现迷宫抽象数据类型，建立迷宫，找出迷宫的一条通路3.详细设计（1）坐标位置类型struct markint a,b; /迷宫a行b列为位置;（2） 迷宫类型void built_maze(int mazerowcol)/按照用户输入的row行和col列的二维数组（元素值为0和1）/设置迷宫maze的初值，包括边上边缘一圈的值void maze_path(int mazerowcol,int dir42,struct mark start,struct mark end)/求解迷宫maze中，从入口start到出口end的一条路径，/若存在，则返回TRUE；否则返回FALSE（3）栈类型struct elementint i,j,d; /坐标与方向;typedef struct Linkstackelement elem;struct Linkstack *next;*SLinkstack;4. 求迷宫路径为伪码算法void maze_path(int mazerowcol,int dir42,struct mark start,struct mark end)int i,j,d;int x,y;element elem,E;SLinkstack L1,L2;initstack(L1);initstack(L2);mazestart.astart.b=2;elem.i=start.a;elem.j=start.b;elem.d=-1; /d=-1表示无方向push_stack(L1,elem);while(!stack_empty(L1)pop(L1,elem);i=elem.i;j=elem.j;d=elem.d+1; /下一个方向while(d4) /探索东西南北各个方向x=i+dird0;y=j+dird1;if(x=end.a&y=end.b&mazexy=0) /这里表示已经到了出口elem.i=i;elem.j=j;elem.d=d;push_stack(L1,elem);elem.i=x;elem.j=y;elem.d=-1;push_stack(L1,elem);while(L1) /逆置序列，输出迷宫路径pop(L1,E);push_stack(L2,E);while(L2)pop(L2,E);printf(%3d%3d%3dn,E.i,E.j,E.d);return;if(mazexy=0)mazexy=2; /标记走过这个点elem.i=i;elem.j=j;elem.d=d;push_stack(L1,elem);i=x;j=y;d=-1;d+;printf(此迷宫无出路);5. 主函数和其他函数的伪码算法void main()int mazerowcol;struct mark start,end; /出入口的坐标int dir42=0,1,1,0,0,-1,-1,0; built_maze(maze); /方向，依次是东西南北printf(请输入入口的横纵坐标：);scanf(%d,%d,&start.a,&start.b);printf(请输入出口的横纵坐标：);scanf(%d,%d,&end.a,&end.b);printf(0为东，1为南，2为西，3为北，-1为出路n);maze_path(maze,dir,start,end);getchar();3 程序结构 main() 定义方向二维数组初始化链栈，并将入口，出口信息入栈是栈是否为空否当前坐标周围是否有方向可以探索否是删除栈中此步信息换个方向搜索坐标移动是此坐标周围有无障碍否迷宫无出路此坐标信息入栈此坐标是否为出口是栈逆置并输出路线 结束 主程序 maze_path built_maze push_stack stack_empty pop initstack四 实验结果与分析1.用户使用说明（1）本程序的运行环境为debug运行环境，执行文件为：19215225.cpp；（2）用VC+运行文件后出现以下窗口：点击运行程序（3） 出现以下窗口后输入迷宫的行列数，回车；再继续输入迷宫的数据，1表示障碍，0表示通路；再输入入口坐标和出口坐标，回车。就可以显示出迷宫路径。2. 测试结果（1） 输入行列数：5,5 输入迷宫数据为：0 0 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 出口位置：1,1 出口位置：5,5 （2）输入行列数：4,9 输入迷宫数据为：0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 0 0 输入入口坐标：1,1 输入出口坐标：4,9 （3）输入行列数：9,8 输入迷宫数据为：0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 输入入口坐标：1,1 输入出口坐标：9,83. 调试分析 （1） 在刚开始写完代码后，运行发现程序只能运行简单的一条直线的迷宫，在运行复杂的迷宫时，不会碰到死路（周围没有可探索的道路）就删除坐标往回到前坐标换方向探索。最后我和同寝室同学一起探讨才发现程序中探索过的坐标没有标记，后来我将mazexy=2将它作为标记才解决问题。（2） 程序中主要的两个算法：initmaze和maze_path的时间复杂度为O(m*n)，空间复杂度也为O(m*n)。 五 总结（收获与体会）通过这段时间的课程设计，我对数据结构和C语言的理解更加深刻了。在实践过程中我遇到了不少问题，但通过阅读相关书籍、求问老师同学，最终也解决了不少问题。这些问题也给了我相当多的收获。但通过这段时间的学习和解决的这么多问题，我觉得我对这些知识的掌握比以前好了许多。求解迷宫问题用的是“穷举求解”的方法。从入口出发，沿着某一方向探索（这里我选择优先探索的是东面），若无障碍，继续往前走，否则眼原路返回，换个方向继续探索，直到将所有可能的通道都探索完为止。所以需要用栈来保存从入口到当前位置的路径。但因为之前在学习栈这一节的时候没学扎实，现在有很多知识都忘了。所以在编写求解迷宫路径的算法的时候我觉得有些困难，后来经过一步步分析和借鉴书上的穷举法才把算法写出来。但我还是除了许多错误，其中大部分是语法错误，这些最后都还是一一解决了。而且除了加深了栈的学习，我还复习了以前大一学的C语言中的二维数组和for，while循环。这次课程设计不仅是让我们加深了解数据结构的理论知识，更重要的是培养我们解决实际问题的能力，能在不断地遇到问题，不断地解决问题的过程中培养自己的专业思维。所以我相信通过这次课程设计我们能够提升自己的分析、设计程序和编写程序的能力。六 源程序#include#include#define row 100#define col 100struct markint a,b;struct elementint i,j,d; /坐标与方向;typedef struct Linkstackelement elem;struct Linkstack *next;*SLinkstack;int initstack(SLinkstack &L)L=NULL;return 1;int stack_empty(SLinkstack L)if(L=NULL)return 1;elsereturn 0;int push_stack(SLinkstack &L,element E)SLinkstack P;P=(SLinkstack)malloc(sizeof(Linkstack);P-elem=E;P-next=L;L=P;return 1;int pop(SLinkstack &L,element &E)SLinkstack P;if(!stack_empty(L)E=L-elem;P=L;L=L-next;free(P);return 1;elsereturn 0;void built_maze(int mazerowcol)/建立迷宫int x,y;int m,n;printf(请输入迷宫的行列数（用逗号隔开）：);scanf(%d,%d,&m,&n);printf(请输入迷宫各行各列的数据（用空格隔开）：n);for(x=0;xm+2;x+)for(y=0;yn+2;y+)if(x=0|x=m+1|y=0|y=n+1)/迷宫周围加墙壁mazexy=1;elsescanf(%d,&mazexy);printf(迷宫生成中n);printf(迷宫显示为：n);for(x=0;xm+2;x+)for(y=0;yn+2;y+)printf(%3d,mazexy);printf(n);void maze_path(int mazerowcol,int dir42,struct mark start,struct mark end)int i,j,d;int x,y;element elem,E;SLinkstack L1,L2;initstack(L1);initstack(L2);mazestart.astart.b=2; /标记起点坐标elem.i=start.a;elem.j=start.b;elem.d=-1; /d=-1表示无方向push_stack(L1,elem);while(!stack_empty(L1)pop(L1,elem);i=elem.i;j=elem.j;d=elem.d+1; /下一个方向while(d4) /探索东西南北各个方向x=i+dird0;y=j+dird1;if(x=end.a&y=end.b&mazexy=0) /这里表示已经到了出口elem.i=i;elem.j=j;elem.d=d;push_stack(L1,elem);elem.i=x;elem.j=y;elem.d=-1;push_stack(L1,elem);while(L1) /逆置序列，输出迷宫路径pop(L1,E);push_stack(L2,E);while(L2)pop(L2,E);printf(%d,%d,%d)n,E.i,E.j,E.d);return;if(mazexy=0)mazexy=2; /标记走过这个点elem.i=i;elem.j=j;elem.d=d;push_stack(L1,elem);i=x;j=y;d=-1;d+;printf(此迷宫无出路);void main()int mazerowcol;struct mark start,end; /出入口的坐标int dir42=0,1,1