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

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

2、 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);

3、printf(" 请输入出口的横纵坐标：");scanf（"%d,%d",&end.a,&end.b）;printf（"O为东，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）

4、/按照用户输入的row行和col列的二维数组（元素值为0和 1）/设置迷宫maz啲初值，包括边上边缘一圈的值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 Linkstack element elem;struct Linkstack *next;*SLinkstack;4.求迷宫路径

5、为伪码算法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=e

6、lem.j;d=elem.d+1; / 下一个方向 while(d<4) / 探索东西南北各个方向 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);

7、 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); / 方向，

8、依次是东西南北 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();程序结构四.实验结果与分析1. 用户使用说明(1 )本程序的运行环境为

9、debug运行环境，执行文件为：19215225.cpp ；(2)用VC+运行文件后出现以下窗口：' hl«rouft Viujril C+ + - (1- XLJ File Edit Virnr Insert eje-rt Buildl Teak Vliindznv He p简|R EiB朗 (E®直殖M|mark创|All viiiBS imembfieIINu rnern >rr5 - Crrait 匚/C* M亡nib | 枣 由逋1 h世include<stdiQh h> ttinclude'Cstdl ib, h>S-3e

10、finp row 1Q0Sdefine col 100a t r j.c t ziai k -i nt a,b； w21ruet el?rc?ntint itj,d："豊.霎与肓向（3）出现以下窗口后1 - 'E：WSitDebug19215225, ext'*水*斗水*击*水*水* *拓*水*#*4；*古柑C*斗斗常*右*京*柑丸片*T*水柑C*水斗拈*店冲*：*#； 伞*伞*址枠*欢迎使用迷宫模拟程序*D)LC*if：z|L*j|c*：|i：D|C1*4：* *：(：* Z(C*z|：«|L*ZJ|c*d|C2|c+* *：4：*：4：D|iCj|c*

11、:章 *斗：*：|：唁输入迷宫的行列数(舟逗号隔开)-输入迷宫的行列数，回车；再继续输入迷宫的数据，1表示障碍，0表示通路；再输入入口坐标和出口坐标，回车。就可以显示出迷宫路径。2. 测试结果(1) 输入行列数：5,5输入迷宫数据为：0 0 0 1 11 1 0 1 10 0 0 1 0出口位置：1,1出口位置：5,5牛鼻料耳*斗沖字样4：M屮耳*冲耳平冲址辛梢“幡杆栏|*档哮字栏饲：m和:甘耳辛科:宴牛科杆栏|畔専*半耳事栏耳字*科枠阿：*甘耳*科乂牛* 才*欢 迎使 岸 迷言模牛厲程序+)：*：材*柑ht+d|*t片專乖斗耳鼻相沖护车斗沖卜卜彳本卓沖彳車*-1乂齐f卑曲平tiJl|耳骷44

12、畔鼻*斗耳鼻栏卓畔粕乂車1-11呂牛4|1£曲字和t齐幕養并耳專半半耳車札1沖菲栏H耳44卑乂車4!*辛车卓11111111D00111111A11I1D001J1101100110000U11111111,2A&,1为出路助恥111,1J) J, 2,0) 3,1) 3, 13, 3, 2) 3. N 2)、M 1, 1).4, 1, I) 5, h D) 523 D) (5, EJ) (5. 4. J)5 5厂1：(2) 输入行列数：4,9输入迷宫数据为：0 0 0 0 0 0 1 0 00 1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 10 0 1 1

13、 1 0 1 0 0输入入口坐标：1,1输入出口坐标：4,910011L010011TC1 01J011010 U Q U 1 0 0 0 1 C 1 1 1 u 0L 1 1 D 111110010 n11 U n1 otri r orit I r.lip*+#斗口卄怦甘诙训停年详宫禅电；稈序*+*+*#*甘=*半、ULh ur£昌港“D*垃o d1拒1 £玄5禄昌港£乱u '. 1呢1 5丈竝e'1 f £1 9 北pr1 s 1 L坐1 1 0 01 r111LAA-feH11W应摯 1的的崗馬 1口为出 入出1无(3) 输入行列数

14、：9,8输入迷宫数据为：0 0 1 0 0 0 1 00 0 1 0 0 0 1 00 0 0 1 0 0 0 00 1 0 0 0 1 0 10 1 1 1 1 0 0 11 1 0 0 0 1 0 11 1 0 0 0 0 0 0输入入口坐标：1,1输入出口坐标：9,8nrn1ii覇：屮#4*佛曲車屮申芈 4enMce*'TT3r9FK：4e?i'ara<T9t3TE4e7M<B*'KTn之細栄 之爭林井其林需齐粘*曲榊*中時榊*欢迎迷宮欖拟程序讨+甘*+4¥*忖屮*irf+'t*糾苛卡时甫打+才十+十叶*Tk+*+*Wvink+*W+

15、*+村*：+"+* 忖*浪+¥壮j D C Ls?r5S,DLcTop 1 険巧2廿存吕苕*Whi_y 1 Ml 5225 prh11 11 T±o no.o o o uooo1 o 1 o0 oo 1 rt- ooooo 1 o oo ”o1 o o 1 o ._u :oofl-o0 0 0 0-1-1T- Jx IX lx_u 11 o _o 11 11 1L 1 o 1 G o o o Q 1 o o L o 1 0 10-00 1 o o o 1 1 o 1 D 1 o 1 o o 1 o u- kD- 1X lx 1Lsmws1orid Z1 D囑 o

16、生s: lsHi1 o1 o 1- 1- 1 19U 姑 r 啟昌 Desktop19215225 昌;SDebugVl92 巧 225eh1为出路0 10 01 11,1g囂3知匕,-亠 vn轟一1-1-TI一Icontinuekey tos fpr 1的的南 牍1 口口伪 继1 ? oil 21100100 3 0011110 - 2,2>2,hm2>3.3,也5,6,7>7,7>7,7,1 瞽砒 1(1>(2,(4,5®,血血(5,3. 调试分析(1) 在刚开始写完代码后，运行发现程序只能运行简单的一条 直线的迷宫，在运行复杂的迷宫时，不会碰到死路

17、(周围没有可探 索的道路)就删除坐标往回到前坐标换方向探索。最后我和同寝室 同学一起探讨才发现程序中探索过的坐标没有标记，后来我将 mazexy=2将它作为标记才解决问题。(2) 程序中主要的两个算法：initmaze和maze_path的时间复杂 度为0(m*n)，空间复杂度也为0(m*n)。五.总结(收获与体会)通过这段时间的课程设计，我对数据结构和C语言的理解更加深刻 了。在实践过程中我遇到了不少问题，但通过阅读相关书籍、求问老师 同学，最终也解决了不少问题。这些问题也给了我相当多的收获。但通 过这段时间的学习和解决的这么多问题，我觉得我对这些知识的掌握比以前好了许多。求解迷宫问题用的是

18、“穷举求解”的方法。从入口出发，沿着某一 方向探索(这里我选择优先探索的是东面)，若无障碍，继续往前走， 否则眼原路返回，换个方向继续探索，直到将所有可能的通道都探索完 为止。所以需要用栈来保存从入口到当前位置的路径。但因为之前在学 习栈这一节的时候没学扎实，现在有很多知识都忘了。所以在编写求解 迷宫路径的算法的时候我觉得有些困难， 后来经过一步步分析和借鉴书 上的穷举法才把算法写出来。但我还是除了许多错误，其中大部分是语 法错误，这些最后都还是一一解决了。而且除了加深了栈的学习，我还 复习了以前大一学的C语言中的二维数组和for , while循环。这次课程设计不仅是让我们加深了解数据结构的

19、理论知识， 更重要 的是培养我们解决实际问题的能力，能在不断地遇到问题，不断地解决 问题的过程中培养自己的专业思维。 所以我相信通过这次课程设计我们 能够提升自己的分析、设计程序和编写程序的能力。六 源程序 #include<stdio.h> #include<stdlib.h> #define row 100 #define col 100 struct mark int a,b;struct elementint i,j,d; /坐标与方向;typedef struct Linkstackelement elem;struct Linkstack *next;*SL

20、inkstack;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)SLinkst

21、ack 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;x<m+2;x+)for(y=0;y<n+2;

22、y+) if(x=0|x=m+1|y=0|y=n+1)/ 迷宫周围加墙壁 mazexy=1;else scanf("%d",&mazexy);printf("迷宫生成中n");printf(" 迷宫显示为： n");for(x=0;x<m+2;x+) for(y=0;y<n+2;y+) printf("%3d",mazexy);printf("n");void maze_path(int mazerowcol,int dir42,struct mark start,struc

23、t 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(d<4) / 探索东西南北各个方向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);e