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

1扬州大学信息工程学院《数据结构》---课程设计报告题目：迷宫问题班级：计科1301学号：131404126姓名：张艳指导教师：王丽爱2目录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附程序源代码3一、设计题目迷宫问题二、需求分析2.1功能与数据需求迷宫求解问题描述：以一个m×n的长方形表示迷宫，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）为出口。123456782.1.2扩展功能（1）编写递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及其通路2.2界面需求请求输入进入程序请求输入起始位置请求输入终点位置输出方阵迷宫输出路径输出方阵路径2.3开发环境与运行需求VisualC++6.00010001000100010000011010111001000010000010001010111100111000101110000004三、概要设计3.1主要数据结构3.3各模块函数说明typedefstruct{输入起始位置，终点位置判断首节点是否为通路判断路径能否走通对坐标标记是否到达迷宫出口处左边是否存在通路下边是否存在通路右边是否存在通路上边是否存在通路存储路径，将路径入栈有解迷宫无解迷宫YNYNY输出迷宫选择路径定义模块函数模块主函数5intpos_x[length];//进栈坐标intpos_y[length];inttop;intbase;}Stack;//新建结构体voidinitStack(Stack*p)//初始化栈Push(Stack*p,intx,inty,intd)//入栈具体操作Pop(Stack*p,intread[2],intd)//出栈并读出前一步的坐标initMaze(intMaze[10][9])//建立迷宫Ways(Stack*p,intMaze[10][9],intrukou_x,intrukou_y,intchukou_x,intchukou_y,intd)//具体路径的求解menu();//调用菜单函数main();//实现迷宫求解的主函数带头结点的单循环链表抽象数据类型SCLinList，其中包括基本操作的函数有：初始化操作函数、插入一个结点操作函数、删除一个结点操作函数、取一个结点数据操作函数和判表是否非空操作函数。该抽象数据类型文件名为SCLinList.h。JesephRing()函数是实现问题要求的主要函数。voidSCLLDeleteAfter(SCLNode*p)，其功能是删除带头结点的单循环链表中指针p所指结点的下一个结点。voidJesephRing(SCLNode*head,intm)，其功能是对带头结点的单循环链表head,以m为初始报数上限值实现问题要求。voidmain(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。6JesephRing()函数作为主要函数，其算法思想是：从1至m对带头结点的单循环链表循环计数，到m时，输出该结点的编号值，将该结点的密码作为新的m值，再从该结点的下一个结点起重新自1起循环计数；如此下去，直到单循环链表空时循环过程结束。（1）数据类型DataType定义如下：typedefstruct{intnumber;intcipher;}DataType;（2）带头结点单循环链表抽象数据类型SCLinList。（3）带头结点单循环链表抽象数据类型的结点结构定义如下：typedefstructnode{DataTypedata;structnode*next;}SCLNode;五、测试数据及运行结果78使用说明1应用程序功能的详细说明按提示输入数字1进入迷宫，输入迷宫入口，迷宫出口2应用程序运行环境要求MicrosoftVisualC++6.03输入数据类型、格式和内容限制4输入的数据都是整型（int），输入迷宫的数据间要用空格或回车隔开六、附程序源代码#includestdio.h#includemalloc.h#includestdlib.h#includeconio.h#definelength50#defineddirection//用d代表所走路径的方向intn=-1;intstep=0;//记录步骤数typedefstruct{intpos_x[length];//进栈坐标intpos_y[length];inttop;intbase;}Stack;//新建结构体voidinitStack(Stack*p){p-top=p-base=0;}//初始化栈.9Push(Stack*p,intx,inty,intd)//入栈具体操作{step++;d=0;n=n+1;p-top=p-top+1;p-pos_x[n]=x;p-pos_y[n]=y;}Pop(Stack*p,intread[2],intd)//出栈并读出前一步的坐标{step++;d=0;n=n-1;p-top=p-top-1;read[0]=p-pos_x[n];read[1]=p-pos_y[n];}initMaze(intMaze[10][9])//建立迷宫函数.{inti;for(i=0;i=9;i++){Maze[0][i]=1;}for(i=0;i=10;i++){Maze[i][0]=1;}for(i=0;i=9;i++){Maze[10][i]=1;}for(i=0;i=10;i++){Maze[i][9]=1;}Maze[1][1]=0;Maze[1][2]=0;Maze[1][3]=1;Maze[1][4]=0;Maze[1][5]=0;Maze[1][6]=0;Maze[1][7]=1;Maze[1][8]=0;Maze[2][1]=0;Maze[2][2]=0;Maze[2][3]=1;Maze[2][4]=0;Maze[2][5]=0;Maze[2][6]=0;Maze[2][7]=1;Maze[2][8]=0;Maze[3][1]=0;Maze[3][2]=0;Maze[3][3]=0;Maze[3][4]=0;Maze[3][5]=1;Maze[3][6]=1;Maze[3][7]=0;Maze[3][8]=1;10Maze[4][1]=0;Maze[4][2]=1;Maze[4][3]=1;Maze[4][4]=1;Maze[4][5]=0;Maze[4][6]=0;Maze[4][7]=1;Maze[4][8]=0;Maze[5][1]=0;Maze[5][2]=0;Maze[5][3]=0;Maze[5][4]=1;Maze[5][5]=0;Maze[5][6]=0;Maze[5][7]=0;Maze[5][8]=0;Maze[6][1]=0;Maze[6][2]=1;Maze[6][3]=0;Maze[6][4]=0;Maze[6][5]=0;Maze[6][6]=1;Maze[6][7]=0;Maze[6][8]=1;Maze[7][1]=0;Maze[7][2]=1;Maze[7][3]=1;Maze[7][4]=1;Maze[7][5]=1;Maze[7][6]=0;Maze[7][7]=0;Maze[7][8]=1;Maze[8][1]=1;Maze[8][2]=1;Maze[8][3]=0;Maze[8][4]=0;Maze[8][5]=0;Maze[8][6]=1;Maze[8][7]=0;Maze[8][8]=1;Maze[9][1]=1;Maze[9][2]=1;Maze[9][3]=0;Maze[9][4]=0;Maze[9][5]=0;Maze[9][6]=0;Maze[9][7]=0;Maze[9][8]=0;}Print()//打印出迷宫界面｛intm,n，j,sum；intMaze[10][9];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;n=9;n++){printf(%4d,Maze[m][n]);sum++;if(sum%10==0)printf(\n);}}｝Ways(Stack*p,intMaze[10][9],intrukou_x,intrukou_y,intchukou_x,intchukou_y,intd)//具体路径的求解函数{11intx,y;intread[2];x=rukou_x;y=rukou_y;printf(第%d步:,step);printf((%d,%d,%d)\n,x,y,d);if(x==chukou_x&&y==chukou_y){printf(到达出口坐标共走了%d步\n,step);return0;}elseif(Maze[x][y+1]==0){y=y+1;d=1;Push(p,x,y,d);Maze[x][y-1]=1;Maze[x][y]=1;}elseif(Maze[x+1][y]==0){x=x+1;d=2;Push(p,x,y,d);Maze[x-1][y]=1;Maze[x][y]=1;}elseif(Maze[x][y-1]==0){y=y-1;d=3;Push(p,x,y,d);Maze[x][y+1]=1;Maze[x][y]=1;}elseif(Maze[x-1][y]==0){x=x-1;d=4;Push(p,x,y,d);Maze[x+1][y]=1;Maze[x][y]=1;}else{Pop(p,read,d);x=read[0];y=read[1];if(p-top==p-base){printf(找不到出口\n);return0;}}Ways(p,Maze,x,y,chukou_x,chukou_y,d);return1;}menu(){printf(\t\t************************************\n);printf(\t\t*欢迎进入课程设计*\n);printf(\t\t*迷宫求解程序*\n);pri