数据结构迷宫问题课程设计报告

1、-. z数据构造课程设计报告设计题目： 迷宫问题数据构造课程设计 _ 班 级： 计科152 学 号： 19215225 姓 名： *昌港 农业大学计算机系-. z数据构造课程设计报告容课程设计题目迷宫问题以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。要求：首先实现一个以链表作存储构造的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组i，j，d的形式输出。其中：i，j指示迷宫中的一个坐标，d表示走到下一坐标的方向。二算法设计思想1.需求分析1迷宫数据用一个二维数组int mazerow

2、col来存储，在定义了迷宫的行列数后，用两个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(

3、0为东，1为南，2为西，3为北，-1为出路n);maze_path(maze,dir,start,end);getchar();栈模块实现栈抽象数据类型迷宫模块实现迷宫抽象数据类型，建立迷宫，找出迷宫的一条通路3.详细设计1坐标位置类型struct markint a,b; /迷宫a行b列为位置;迷宫类型void built_maze(int mazerowcol)/按照用户输入的row行和col列的二维数组元素值为0和1/设置迷宫maze的初值，包括边上边缘一圈的值void maze_path(int mazerowcol,int dir42,struct mark start,struct

4、 mark end)/求解迷宫maze中，从入口start到出口end的一条路径，/假设存在，则返回TRUE；否则返回FALSE3栈类型struct elementint i,j,d; /坐标与方向;typedef struct Linkstackelement elem;struct Linkstack *ne*t;*SLinkstack;求迷宫路径为伪码算法void maze_path(int mazerowcol,int dir42,struct mark start,struct mark end)int i,j,d;int *,y;element elem,E;SLinkstack

5、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) /探索东西南北各个方向*=i+dird0;y=j+dird1;if(*=end.a&y=end.b&maze*y=0) /这里表示已经到了出口elem.i=i;elem.j=j;elem

6、.d=d;push_stack(L1,elem);elem.i=*;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(maze*y=0)maze*y=2; /标记走过这个点elem.i=i;elem.j=j;elem.d=d;push_stack(L1,elem);i=*;j=y;d=-1;d+;printf(此迷宫无出路);主函数和其他函数的伪码算法

7、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();程序构造 main() 定义方向二

8、维数组初始化链栈，并将入口，出口信息入栈是栈是否为空否当前坐标周围是否有方向可以探索否是删除栈中此步信息换个方向搜索坐标移动是此坐标周围有无障碍否迷宫无出路此坐标信息入栈此坐标是否为出口是栈逆置并输出路线 完毕 主程序 maze_path built_maze push_stack stack_empty pop initstack四 实验结果与分析1.用户使用说明1本程序的运行环境为debug运行环境，执行文件为：19215225.cpp；2用VC+运行文件后出现以下窗口：点击运行程序出现以下窗口后输入迷宫的行列数，回车；再继续输入迷宫的数据，1表示障碍，0表示通路；再输入入口坐标和出口坐标

9、，回车。就可以显示出迷宫路径。测试结果输入行列数：5,5 输入迷宫数据为：0 0 0 1 1 1 1 0 1 10 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

10、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,8调试分析 在刚开场写完代码后，运行发现程序只能运行简单的一条直线的迷宫，在运行复杂的迷宫时，不会碰到死路周围没有可探索的道路就删除坐标往回到前坐标换方向探索。最后我和同寝室同学一起探讨才发现程序中探索过的坐标没有标记，后来我将maze*y=2将它作为标记才解决问题。程序中主要的两个算法：initmaze和maze_path的时间复杂度为O(m*n)，空间复杂度也为O(m*n)。五 总结收获与体会

11、通过这段时间的课程设计，我对数据构造和C语言的理解更加深刻了。在实践过程中我遇到了不少问题，但通过阅读相关书籍、求问教师同学，最终也解决了不少问题。这些问题也给了我相当多的收获。但通过这段时间的学习和解决的这么多问题，我觉得我对这些知识的掌握比以前好了许多。求解迷宫问题用的是“穷举求解的方法。从入口出发，沿着*一方向探索这里我选择优先探索的是东面，假设无障碍，继续往前走，否则眼原路返回，换个方向继续探索，直到将所有可能的通道都探索完为止。所以需要用栈来保存从入口到当前位置的路径。但因为之前在学习栈这一节的时候没学扎实，现在有很多知识都忘了。所以在编写求解迷宫路径的算法的时候我觉得有些困难，后来

12、经过一步步分析和借鉴书上的穷举法才把算法写出来。但我还是除了许多错误，其局部是语法错误，这些最后都还是一一解决了。而且除了加深了栈的学习，我还复习了以前大一学的C语言中的二维数组和for，while循环。这次课程设计不仅是让我们加深了解数据构造的理论知识，更重要的是培养我们解决实际问题的能力，能在不断地遇到问题，不断地解决问题的过程中培养自己的专业思维。所以我相信通过这次课程设计我们能够提升自己的分析、设计程序和编写程序的能力。六 源程序*include*include*define row 100*define col 100struct markint a,b;struct element

13、int i,j,d; /坐标与方向;typedef struct Linkstackelement elem;struct Linkstack *ne*t;*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-ne*

14、t=L;L=P;return 1;int pop(SLinkstack &L,element &E)SLinkstack P;if(!stack_empty(L)E=L-elem;P=L;L=L-ne*t;free(P);return 1;elsereturn 0;void built_maze(int mazerowcol)/建立迷宫int *,y;int m,n;printf(请输入迷宫的行列数用逗号隔开：);scanf(%d,%d,&m,&n);printf(请输入迷宫各行各列的数据用空格隔开：n);for(*=0;*m+2;*+)for(y=0;yn+2;y+)if(*=0|*=m+1

15、|y=0|y=n+1)/迷宫周围加墙壁maze*y=1;elsescanf(%d,&maze*y);printf(迷宫生成中n);printf(迷宫显示为：n);for(*=0;*m+2;*+)for(y=0;yn+2;y+)printf(%3d,maze*y);printf(n);void maze_path(int mazerowcol,int dir42,struct mark start,struct mark end)int i,j,d;int *,y;element elem,E;SLinkstack L1,L2;initstack(L1);initstack(L2);mazest

16、art.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) /探索东西南北各个方向*=i+dird0;y=j+dird1;if(*=end.a&y=end.b&maze*y=0) /这里表示已经到了出口elem.i=i;elem.j=j;elem.d=d;push_stack(L1,elem);elem.i=

17、*;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(maze*y=0)maze*y=2; /标记走过这个点elem.i=i;elem.j=j;elem.d=d;push_stack(L1,elem);i=*;j=y;d=-1;d+;printf(此迷宫无出路);void main()int mazerowcol;struct mark start,end; /出入口的坐标int dir42=0,1,1,0,0