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

扬州大学信息工程学院数据结构-课程设计报告题目： 迷宫问题 班级： 计科1301 学号： 131404126 姓名： 张艳 指导教师： 王丽爱 目 录1 课程题目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 附程序源代码一、设计题目迷宫问题二、需求分析2.1 功能与数据需求 迷宫求解问题描述：以一个mn的长方形表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。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）为出口。001000100010001000001101011100100001000001000101011110011100010111000000 1 2 3 4 5 6 7 82.1.2 扩展功能（1）编写递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及其通路2.2 界面需求请求输入进入程序请求输入起始位置请求输入终点位置输出方阵迷宫输出路径输出方阵路径2.3 开发环境与运行需求Visual C+6.0三、概要设计3.1主要数据结构定义模块函数模块主函数 输入起始位置，终点位置 判断首节点是否为通路判断路径能否走通对坐标标记 是否到达迷宫出口处左边是否存在通路下边是否存在通路右边是否存在通路上边是否存在通路存储路径，将路径入栈 有解迷宫 无解迷宫 YNYNY输出迷宫 选择路径 3.3各模块函数说明typedef struct 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,int read2,int d) /出栈并读出前一步的坐标 initMaze(int Maze109)/建立迷宫Ways(Stack *p,int Maze109,int rukou_x,int rukou_y,int chukou_x,int chukou_y,int d) /具体路径的求解 menu();/调用菜单函数 main();/实现迷宫求解的主函数带头结点的单循环链表抽象数据类型SCLinList，其中包括基本操作的函数有：初始化操作函数、插入一个结点操作函数、删除一个结点操作函数、取一个结点数据操作函数和判表是否非空操作函数。该抽象数据类型文件名为SCLinList.h。JesephRing()函数是实现问题要求的主要函数。void SCLLDeleteAfter(SCLNode *p)，其功能是删除带头结点的单循环链表中指针p所指结点的下一个结点。void JesephRing(SCLNode *head, int m)，其功能是对带头结点的单循环链表head,以m为初始报数上限值实现问题要求。void main(void)，主函数，功能是给出测试数据值，建立测试数据值的带头结点单循环链表，调用JesephRing()函数实现问题要求。四、详细设计迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按左、右、上、下4个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果4方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条合适的通路；若退回到了入口处，则说明不存在合法的通路到达出口。用一个二维指针数组迷宫表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（1，1）处，出口点在位置（m,n）处。设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宫的外墙；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宫的入口和出口；假设当前所在位置是（x,y）。沿某个方向前进一步，它可能到达的位置最多有4。JesephRing()函数作为主要函数，其算法思想是：从1至m对带头结点的单循环链表循环计数，到m时，输出该结点的编号值，将该结点的密码作为新的m值，再从该结点的下一个结点起重新自1起循环计数；如此下去，直到单循环链表空时循环过程结束。（1）数据类型DataType定义如下：typedef structint number;int cipher; DataType; （2）带头结点单循环链表抽象数据类型SCLinList。（3）带头结点单循环链表抽象数据类型的结点结构定义如下： typedef struct nodeDataType data;struct node *next; SCLNode; 五、测试数据及运行结果 使用说明1应用程序功能的详细说明按提示输入数字1进入迷宫，输入迷宫入口，迷宫出口2应用程序运行环境要求Microsoft Visual C+6.03输入数据类型、格式和内容限制4输入的数据都是整型（int），输入迷宫的数据间要用空格或回车隔开六、附程序源代码#include #include #include#include#define length 50#define d direction /用d代表所走路径的方向int n=-1;int step=0; /记录步骤数 typedef struct int pos_xlength;/进栈坐标int pos_ylength;int top; int base; Stack; /新建结构体void initStack(Stack *p) p-top=p-base=0; /初始化栈. Push(Stack *p,int x,int y,int d) /入栈具体操作 step+;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+) Maze10i=1; for (i=0;i=10;i+) Mazei9=1; Maze11=0;Maze12=0;Maze13=1;Maze14=0;Maze15=0;Maze16=0;Maze17=1;Maze18=0; Maze21=0;Maze22=0;Maze23=1;Maze24=0;Maze25=0;Maze26=0;Maze27=1;Maze28=0; Maze31=0;Maze32=0;Maze33=0;Maze34=0;Maze35=1;Maze36=1;Maze37=0;Maze38=1; Maze41=0;Maze42=1;Maze43=1;Maze44=1;Maze45=0;Maze46=0;Maze47=1;Maze48=0; Maze51=0;Maze52=0;Maze53=0;Maze54=1;Maze55=0;Maze56=0;Maze57=0;Maze58=0;Maze61=0;Maze62=1;Maze63=0;Maze64=0;Maze65=0;Maze66=1;Maze67=0;Maze68=1;Maze71=0;Maze72=1;Maze73=1;Maze74=1;Maze75=1;Maze76=0;Maze77=0;Maze78=1;Maze81=1;Maze82=1;Maze83=0;Maze84=0;Maze85=0;Maze86=1;Maze87=0;Maze88=1;Maze91=1;Maze92=1;Maze93=0;Maze94=0;Maze95=0;Maze96=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;m+) for(n=0;ntop=p-base) printf(找不到出口n);return 0; 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);printf(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(请输入出口坐标:); /迷宫入口坐标. scanf(%d,&elem_20); scanf(%d,&elem_21);chukou_x=elem_20;chukou_y=elem_21;/迷宫出口坐标. if(elem_1010|elem_119|elem_2010|elem_219| elem_100|elem_110|elem_200|elem_210) printf(输入的入口或出口坐标错误n); /首先判断输入坐标是否正确else printf(n); printf(说明(x,y,z)x,y代表坐标点;n);