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

1、扬州大学信息工程学院数据结构-课程设计报告题目：迷宫冋题班级： 计科1301学号： 131404126姓名： 张艳指导教师：王丽爱i1课程题目2需求分析2.1功能与数据需求2.1.1题目要求的功能2.1.2扩展功能2.2界面需求2.3开发环境与运行需求3概要设计3.1主要数据结构3.2程序总体结构3.3各模块函数说明4详细设计4.1算法分析与设计4.2主要程序段设计5测试6附程序源代码13一、设计题目迷宫问题二、需求分析2.1功能与数据需求迷宫求解问题描述：以一个 mx n的长方形表示迷宫，0和1分别表示迷宫中的通路和障碍。设 计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没

2、有通路的结论。2.1.1 题目要求的功能基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d )的形式输出，其中：(i,j )指示迷宫中的一个坐标, d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：(1,1,1 )(1,2,2 ) , (2,2,2 )(3,2,3 ) ,(3,1,2 ),。测试数据：迷宫的测试数据如下：左上角(1,1 )为入口，右下角(9,8 )为出口。2.1.2扩展功能0010001000100010000011010111001000010000010001010111100111000101

3、110000001 2 3 4 5 6 7 8(1)编写递归形式的算法，求得迷宫中所有可能的通路;(2 )以方阵形式输出迷宫及其通路2.2界面需求请求输入进入程序请求输入起始位置请求输入终点位置输出方阵迷宫输出路径输出方阵路径2.3开发环境与运行需求Visual C+6.0三、概要设计3.1主要数据结构输入起始位置，终点位置课程设计判断首节点是否为通路定义模块是否到达迷宫出口 处 kiidTftchntJ判断路径能有解迷宫输岀迷宫3.3各模块函数说明typedef struct否走通 .函数模块L对坐标标记、/弋选择路径I无解迷宫左边是否存在通路下边是否存在通路右边是否存在通路T 上边是否存在

4、通路int pos_xlength;/ 进栈坐标int pos_ylength;int top;int base;Stack; / 新建结构体void initStack(Stack *p) /初始化栈Push(Stack *p,int x,int y,int d) /入栈具体操作 Pop(Stack *p,intread2,int d) /出栈并读出前一步的坐标 initMaze(int Maze109)/ 建立迷宫Ways(Stack *p,int Maze109,int rukou_x,int rukou_y,int chukou_x,intchukou_y,int d) /具体路径的求

5、解 menu();/ 调用菜单函数 main();/实现迷宫求解的主函数带头结点的单循环链表抽象数据类型 SCLinList ，其中包括基本操作的函数有：初始化 操作函数、 插入一个结点操作函数、 删除一个结点操作函数、 取一个结点数据操作函数和判 表是否非空操作函数。该抽象数据类型文件名为 SCLinList.h 。JesephRing() 函数是实现问题要求的主要函数。void SCLLDeleteAfter(SCLNode *p) ，其功能是删除带头结点的单循环链表中指针 p 所指结点的下一个结点。void JesephRing(SCLNode *head, int m)，其功能是对带头

6、结点的单循环链表 head,以 m 为初始报数上限值实现问题要求。void main(void) ，主函数，功能是给出测试数据值，建立测试数据值的带头结点单循 环链表，调用 JesephRing() 函数实现问题要求。四、详细设计 迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按左、右、上、下 4 个方向 顺序试探下一个位置；如果某方向可以通过， 并且不曾到达， 则前进一步， 在新位置上继续 进行搜索； 如果 4 方向都走不通或曾经到达过， 则退回一步， 在原来的位置上继续试探下一每前进或后退一步， 都要进行判断： 若前进到了出口处， 则说明找到了一条合适的通路； 若退回到了入口处，则说

7、明不存在合法的通路到达出口。用一个二维指针数组迷宫表示迷宫， 数组中每个元素取值 “ 0”(表示通路) 或“1”(表 示墙壁)。迷宫的入口点在位置(1, 1 )处，出口点在位置(m,n )处。设计一个模拟走迷 宫的算法，为其寻找一条从入口点到出口点的通路。二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“ 1 ” ，表示迷宫的外墙； 第1行第1列元素和第m行第m列元素置成“ 0”，表示迷宫的入口和出口； 假设当前所在 位置是( x,y )。沿某个方向前进一步，它可能到达的位置最多有 4。JesephRing（）函数作为主要函数，其算法思想是：从1至m对带头结点的单循环链表循 环计数，

8、到m时，输出该结点的编号值， 将该结点的密码作为新的 m值，再从该结点的下一 个结点起重新自1起循环计数；如此下去，直到单循环链表空时循环过程结束。（1）数据类型DataType定义如下：typedef structint nu mber;int cipher; DataType;（2） 带头结点单循环链表抽象数据类型SCL in List。（3）带头结点单循环链表抽象数据类型的结点结构定义如下：typedef struct no deDataType data;struct node *n ext; SCLNode;五、测试数据及运行结果* 欢迎进入课矍设计* 迷宫求辭槿岸*菜单；*迫岀迷吕

9、*请爺入2*磨 饉蘇孟詡代表可通过12345£781111111111100100R10110010001011000011011101116n10110001000011010801011101111011111000101111100000011111111111左、上方向J./了巴 0 13 3>>>>>>>>>>>>> -111、 )%k7)43 33 3 333333322112114 1114442222 1i/ 012211411 * * r * r *r* *r* * *>* r *

10、* r * i *>>r* m 6 5 4566544321112 334 5 56-7 88877777 8 111112223333455S& & 6 555545567899 l -J. < 歩F片歩£涉長呉快呉呉長呉快長快快貝決快呉快快炉快快呉快長決快归知快归知岀 月 才 0 1 23 456789-01234 5 678901234-567S90 大- 1 2 3 4 56789111111111122222 2 22 2 2 3 3 3 3 3 3 3 3 3 3 4 J J IF- 1Fl Ljw 3r .1 Lwa ILhw Bin-

11、 MP IT Lw Pk- ILiw Lw Lw. Lw Lw Lw. 3F BLU Lw Kwfi Lw ?r VIH iLw kli vil> TJ VLH续 ft 口戀 I±意3 4121212不按使用说明1应用程序功能的详细说明按提示输入数字1进入迷宫，输入迷宫入口，迷宫出口2应用程序运行环境要求Microsoft Visual C+6.03输入数据类型、格式和内容限制4输入的数据都是整型（int ），输入迷宫的数据间要用空格或回车隔开六、附程序源代码#in elude <stdio.h>#i nclude <malloe.h>#in clude

12、<stdlib.h>#in clude<c oni o.h>#define len gth 50#define d direction /用d代表所走路径的方向int n=-1;int step=0; / 记录步骤数typedef structin t pos_xle ngth;/进栈坐标int pos_yle ngth;int top;int base;Stack; /新建结构体void in itStack(Stack *p)p_>top=p_>base=O;/初始化栈.入栈具体操作Push(Stack *p,int x,int y,int d) /st

13、ep+;d=0;n=n+1;p->top=p->top+1;p->pos_xn=x;p->pos_yn=y;Pop(Stack *p,int read2,int d) /出栈并读出前一步的坐标step+;d=0;n=n-1;p->top=p->top-1;read0=p->pos_xn;read1=p->pos_yn;initMaze(int Maze109)/ 建立迷宫函数 .int i;for (i=0;i<=9;i+) Maze0i=1;for (i=0;i<=10;i+) Mazei0=1;for (i=0;i<=9;i

14、+) Maze10i=1;for (i=0;i<=10;i+) Mazei9=1;Maze11=0;Maze12=0;Maze13=1;Maze14=0;Maze15=0;Maze1 6=0;Maze17=1;Maze18=0;Maze21=0;Maze22=0;Maze23=1;Maze24=0;Maze25=0;Maze2 6=0;Maze27=1;Maze28=0;Maze31=0;Maze32=0;Maze33=0;Maze34=0;Maze35=1;Maze3 6=1;Maze37=0;Maze38=1;Maze41=0;Maze42=1;Maze43=1;Maze44=1;M

15、aze45=0;Maze4 6=0;Maze47=1;Maze48=0;Maze51=0;Maze52=0;Maze53=0;Maze54=1;Maze55=0;Maze5 6=0;Maze57=0;Maze58=0;Maze61=0;Maze62=1;Maze63=0;Maze64=0;Maze65=0;Maze6 6=1;Maze67=0;Maze68=1;Maze71=0;Maze72=1;Maze73=1;Maze74=1;Maze75=1;Maze7 6=0;Maze77=0;Maze78=1;Maze81=1;Maze82=1;Maze83=0;Maze84=0;Maze85=0;

16、Maze8 6=1;Maze87=0;Maze88=1;Maze91=1;Maze92=1;Maze93=0;Maze94=0;Maze95=0;Maze9 6=0;Maze97=0;Maze98=0;Print( )/ 打印出迷宫界面int m,n ， j,sum ；int Maze109;printf(" 迷宫 (1 代表墙即不通 ,0 代表可通过 )n");printf(" ");for(j=1;j<=8;j+) printf("%4d",j); printf("n");for(m=0;m<=10

17、;m+)for(n=0;n<=9;n+)printf("%4d",Mazemn);sum+;if(sum%10=0) printf("n");Ways(Stack *p,int Maze109,int rukou_x,int rukou_y,int chukou_x,intchukou_y,int d) /具体路径的求解函数int x,y;int read2;x=rukou_x;y=rukou_y;printf(”第 d:",step);printf("(%d,%d,%d)n",x,y,d);if(x=chukou_x

18、&&y=chukou_y)prin tf("到达出口坐标共走了 dn ",step);return 0;else if(Mazexy+1=0)y=y+1;d=1;Push(p,x,y,d);Mazexy-1=1;Mazexy=1;else if(Mazex+1y=0)x=x+1;d=2;Push(p,x,y,d);Mazex-1y=1;Mazexy=1;else if(Mazexy-1=0)y=y-1;d=3;Push(p,x,y,d);Mazexy+1=1;Mazexy=1;else if(Mazex-1y=0)x=x-1;d=4;Push(p,x,y,d

19、);Mazex+1y=1;Mazexy=1;elsePop(p,read,d);x=read0;y=read1;if(p->top=p->base) printf("找不到出口 n");return0;Ways(p,Maze,x,y,chukou_x,chukou_y,d);return 1;menu()printf("tt *n");printf("tt*欢迎进入课程设计*n");printf("tt*迷宫求解程序*n");printf("tt*菜单:*n");17printf(&

20、quot;tt*进入迷宫 * 请输入 1*n");printf("tt*退出迷宫 * 请输入 2*n");printf("tt*n");int main()Stack *p;Stack S;int Maze109; /定义迷宫int elem_11,elem_21,a,j;int rukou_x,rukou_y,d=0;int chukou_x,chukou_y;int sum=0;p=&S;initMaze(Maze);system("color 5f");/dos 窗口背景颜色函数menu();/ 调用菜单函数printf(" 请输入您的选择 :");scanf("%d",&a);if(a=1)Print( ) / 打印迷宫图 .；printf(" 请输入入口坐标 :");scanf("%d",&elem_10);scanf("%d",&elem_11);rukou_x=elem_10;rukou_y=elem_11;printf(" 请输入