[毕业设计精品]迷宫问题.doc
课 程 设 计题 目迷宫问题学 院计算机科学与技术学院专 业计算机科学与技术班 级计算机科学与技术0909班姓 名指导教师2011年7月2日课程设计任务书题 目: 迷宫问题 初始条件： 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1,1,1），（1,2,2），（2,2,2），（3,2,3），（3,1,2），。 测试用例见题集p105。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容： 1、 问题描述简述题目要解决的问题是什么。2、 设计存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计；3、 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、 经验和体会（包括对算法改进的设想）5、 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，6、 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。时间安排：1、第19周完成。2、7月1 日14：00到计算中心检查程序、交课程设计报告、源程序（CD盘）。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日目录1、问题描述与需求分析31.1 问题描述312 需求分析32、设计32.1 设计原理32.2 储存结构设计42.2.1 设定栈的抽象数据类型定义：42.2.2 设定迷宫的抽象数据类型为：62.3 详细设计72.3.2、栈模块：82.3.3 主程序模块：122.3.4 函数调用关系的层次结构框图：142.4 测试用例设计143、调试报告153.1 遇到的问题及解决办法153.2 对设计和编码的讨论与分析154、经验和体会165、源程序和运行结果165.1 源程序165.2 运行结果216、参考文献23题目：迷宫问题1、问题描述与需求分析1.1 问题描述 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1,1,1），（1,2,2），（2,2,2），（3,2,3），（3,1,2），12 需求分析 （1）以二维数组Mazem+2n+2表示迷宫，其中：Maze0j和Mazem+1j(0<=j<=n+1)及Mazei0和Mazein+1 (0<=i<=n+1)为添加的一圈障碍。数组中一元素值为0表示通路，1表示障碍。（2）其中迷宫的入口位置和出口位置可由用户随时设定。（3）迷宫内墙的编写，用1表示内墙，0表示通路。（4）以链表作存储结构的栈类型，实现求解迷宫的非递归程序。（5）本程序只求出一条成功的通路，然而，只需要对迷宫求解的函数作小量修改，便可求得全部路径。2、设计2.1 设计原理主要采取三大模块：主程序模块、栈模块和迷宫模块栈模块：实现迷宫数据的抽象化和对迷宫数据的处理； 迷宫模块：实现迷宫数据抽象类型；主程序模块：初始化迷宫模块。栈模块实现栈抽象数据类型迷宫模块实现迷宫抽象数据类型主程序模块：Void main() 初始化； do 接受命令； 处理命令； while(命令！=“退出”)；各模块之间的调用关系如下：主程序模块迷宫模块栈模块2.2 储存结构设计2.2.1 设定栈的抽象数据类型定义：ADT Stack 数据对象：D= ai|ai CharSet,i=1,2,n,n0 数据关系：R1=<ai-1, ai>| ai-1 , ai D,i=2,n 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈S已存在。 操作结果：销毁栈S。 ClearStack(&S) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackLength(S)初始条件：栈S已存在。 操作结果：返回栈S的长度。 StackEmpty(S) 初始条件：栈S已存在。 操作结果：若S为空栈，则返回TRUE,否则返回FALSE。 GetTop(S,&e) 初始条件：栈S已存在。 操作结果：若栈S不空，则以e返回栈顶元素。 Push(&S,e) 初始条件：栈S已存在。 操作结果：在栈S的栈顶插入信的栈顶元素e。 Pop(&S,&e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。 StackTraverse(S,visit() 初始条件：栈S已存在。 操作结果：从栈底到栈顶一次对S中的每个元素调用函数visit（）。ADT Stack2.2.2 设定迷宫的抽象数据类型为：ADT maze 数据对象：D=ai,j | ai,j 0,1,0im+1,0jn+1,m,n10 数据关系：R=ROW,COL ROW= <ai-1,j, ai,j >| ai-1,j , ai-1D,i=1,m+1,j=0,n+1 COL= <ai,j-1, ai,j >| ai,j-1 , ai-1D,i=1,m+1,j=0,n+1 InitMaze (&M ,a ,row , col )初始条件：二维数组arow+2col+2已经存在，其中自第一行至第row+1行、每行中自第1列至第col+1列的元素已经有值，并且以值0表示通路，以值1表示障碍。操作结果：构成迷宫的字符型数组，并在迷宫四周加上一圈障碍。 MazePath (&M)初始条件：迷宫M已被赋值。操作结果：若迷宫M中存在一条通路，则按照所走的步骤，从小到大依次排列。 PrintMaze (M)初始条件：迷宫M已存在。操作结果：已字符形式输出迷宫。ADT maze;2.2.3 寻找公共路径的思想图如下：设定当前为出始值的入口：do 若当前位置可通， 则将当前位置插入栈顶； 若该位置是出口位置，则结束； 否则切换当前位置的东邻方块为新的当前位置； 否则 若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一邻块； 若栈不为空且栈顶位置的四周均不可通， 则删除栈顶位置； 若栈不为空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； 2.3 详细设计2.3.1迷宫模块：以二维数组Mazem+2n+2表示迷宫，其中：Maze0j和Mazem+1j(0<=j<=n+1)及Mazei0和Mazein+1 (0<=i<=n+1)为添加的一圈障碍。数组中一元素值为0表示通路，1表示障碍，限定迷宫的大小m,n<=10。其中迷宫的入口位置和出口位置可由用户随时设定。(1)坐标位置类型:struct PosType /* 迷宫坐标位置类型 */ int x; /* 行值 */ int y; /* 列值 */ (2)迷宫类型:#define MAXLENGTH 25 /* 设迷宫的最大行列为25 */ typedef int MazeTypeMAXLENGTHMAXLENGTH; 3.记录坐标的三个一元数组： int aMAXLENGTH; int bMAXLENGTH; int cMAXLENGTH;2.3.2、栈模块：(1)栈类型SElemType:struct SElemType/* 栈的元素类型 */ int ord; /* 通道块在路径上的序号 */ PosType seat; /* 通道块在迷宫中的坐标位置 */ int di; /* 从此通道块走向下一通道块的方向(03表示东北) */ (2)构造一个栈SElmType: struct SqStack /SqStack SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */ SElemType *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位 */ ; /* 顺序栈 */ 其中基本操作如下：栈的初始化：bool InitStack(SqStack *S) /* 构造一个空栈S */ (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!(*S).base) exit(1); /* 存储分配失败 */ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return true; 元素进栈：bool Push(SqStack *S,SElemType e) /* 插入元素e为新的栈顶元素 */ if(*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */ (*S).base=(SElemType *)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(SElemType); if(!(*S).base) exit(1); /* 存储分配失败 */ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; *(*S).top)+=e; return true; 判断栈是否为空： bool StackEmpty(SqStack S) /* 若栈S为空栈，则返回true，否则返回false*/ if(S.top=S.base) return true; else return false; 删除栈顶元素使之为空：bool Pop(SqStack *S,SElemType *e) /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回true；否则返回false */ if(*S).top=(*S).base) return false; *e=*-(*S).top; return true; bool MazePath(PosType start,PosType end) /* 算法3.3 */ /* 若迷宫maze中存在从入口start到出口end的通道，则求得一条 */ /* 存放在栈中(从栈底到栈顶)，并返回TRUE；否则返回FALSE */ SqStack S; PosType curpos; SElemType e; InitStack(&S); curpos=start; do if(Pass(curpos) /* 当前位置可以通过，即是未曾走到过的通道块 */ FootPrint(curpos); /* 留下足迹 */ e.ord=curstep; acurstep=e.seat.x=curpos.x; bcurstep=e.seat.y=curpos.y; ccurstep=e.di=0; Push(&S,e); /* 入栈当前位置及状态 */ curstep+; /* 足迹加1 */ if(curpos.x=end.x&&curpos.y=end.y) /* 到达终点(出口) */ return true; curpos=NextPos(curpos,e.di); else /* 当前位置不能通过 */ if(!StackEmpty(S) Pop(&S,&e); /* 退栈到前一位置 */curpos=e.seat;-curstep; while(e.di=3) && (!StackEmpty(S) / 前一位置处于最后一个方向(北) MarkPrint(e.seat); /* 留下不能通过的标记(-1) */ Pop(&S,&e); /* 退回一步 */ curstep-; if(e.di<3) /* 没到最后一个方向(北) */ e.di+; /* 换下一个方向探索 */ Push(&S,e); acurstep=e.seat.x=curpos.x; bcurstep=e.seat.y=curpos.y; ccurstep=e.di; curstep+; curpos=NextPos(e.seat,e.di); / 设定当前位置是该新方向上的相邻块 while(!StackEmpty(S); return false; 2.3.3 主程序模块：Void main()Do 接受命令；处理命令；while(命令!=“退出”)程序如下：void main() PosType begin,end; int i,j,x,y,x1,y1; cout<<"请输入迷宫的行数,列数(包括外墙)：" cin>>x>>y; for(i=0;i<x;i+) /* 定义周边值为1(同墙) */ m0i=1; /* 行周边 */ mx-1i=1; for(j=0;j<y;j+) mj0=1; /* 列周边 */ mjy-1=1; for(i=1;i<x-1;i+) for(j=1;j<y-1;j+) mij=0; /* 定义通道初值为0 */ cout<<"请输入迷宫内墙单元数：" cin>>j; cout<<"请依次输入迷宫内墙每个单元的行数,列数："<<endl; for(i=1;i<=j;i+) cin>>x1>>y1; mx1y1=1; /* 定义墙的值为1 */ cout<<"迷宫结构如下:"<<endl; Print(x,y); cout<<"请输入起点的行数,列数：" cin>>begin.x>>begin.y; cout<<"请输入终点的行数,列数：" cin>>end.x>>end.y; if(MazePath(begin,end) /* 求得一条通路 */ cout<<"此迷宫从入口到出口的一条路径如下:"<<endl; Print(x,y); /* 输出此通路 */ cout<<"迷宫所走过路径的坐标及方向(0代表右,1代表下,2代表左,3代表上):"<<endl; for(i=1;i<curstep;i+) cout<<"("<<ai<<","<<bi<<","<<ci<<")"<<endl; else cout<<"此迷宫没有从入口到出口的路径"<<endl;2.3.4 函数调用关系的层次结构框图：主程序SameNextPosMarkPrintPassFootPrintPushInitStackInitMazeInitializationReadCommandInterpretMazePathPrintMazePopStackEmptyStackTraverse 2.4 测试用例设计 1 2 3 4 5 6 7 8001000100010001000001101011100100001000001000101011110011100010111000000上面的测试数据是没有加边墙的，在本程序中要加上四周的边墙。另外，本程序是运用内墙的数量来定位的，本测试设计内墙总共有26（有26个1）。3、调试报告3.1 遇到的问题及解决办法（1）这次的课程设计程序大多来自于教科书和练习册，相对比较容易。但也会出现很多错误，在定义外墙时，粗心地将循环初始值j定为1，在刚开始调试时用了一个简单的例子，没发现这个错误，以至于到后面查看要求的示例时，出现了最后一行外墙为0的状况。解决这种状况只需将其初始值变为0，并把控制条件改为jy即可。（2）在编写MazePath函数时，当遇到墙（即遇到下一位置为1）时，直接从现在墙位置进行往南跳转。以至有许多应该走的通路位置没有走，而且使总共走的步数变短。在测试前期怎么也想不明白，出栈操作也有，curstep退位也有，但就是不进行退到上一位置的操作。最后发现，少了一步把出栈的数进行赋值的操作。只要进行curpos=e.seat的操作，上面的问题就迎刃而解了。（3）在进行对迷宫的输出时，变成按行输出，得不到预期的迷宫结果，更不用说验证其正确性。这就是粗心造成的，本来为简洁，就不用在下行再写cout了，直接就在cout<<mij后加了endl，这使得每出一个数就会换行，而导致输出的迷宫出错。（4）在编写do while 语句时，另一种情况（即当前位置不能通过时）也同样出现在墙节点就直接往南走的情况，综合上面的情况，同样的，也是退位没有赋值。这种错误比较难发现，往往只有在复杂的迷宫求解过程中才能发现。这类错误属于逻辑错误，调试不会显示，需要自己拙句地查看和分析，并能充分的理解程序每一步的认识，才能发现并解决这样的问题。3.2 对设计和编码的讨论与分析（1）刚着手这个迷宫问题，首先要解决的就有两大问题，如何储存这样的迷宫，如何实现求解迷宫？由于我们用的计算机的高计算特点，我们可以用穷举法来寻找迷宫的解。于是，又有问题了，如何穷举？该怎么穷举就不会出错？根据习题册上的实例，可以分为四个方向挨个探索。至于，如何储存并实现这个迷宫，就得依赖于栈和二维数组。（2）在具体编码时，也会遇到很多问题，譬如根据书上的一些代码的运用会出现错误，需要自己动手，动脑亲自编写。这样有助于对数据结构的理解，同时也达到了这门课程设计的实验目的。4、经验和体会通过这次的数据结构课程设计，让我学会了很多，譬如迷宫的实现，面对问题时应该怎样解决。同时，也让我对栈这一章节有更深的体会，以及用不同的方法解决同意问题。相比较得出较好的解决方案。拿实现迷宫解的通路来说，按照题目的要求要实现三位数代表通路的路径和方向。通过对题目的研究，我们可以得出三位数的前两位是这个节点的坐标，另一个数则是表示方向的，同时我们也可以让第一个数据表示方向，后两位表示节点坐标。这样，为实现这个要求，我们可以定义三个一维数组。分别表示不同的数，在解决路径上标识每一步的序号，通过这个序号来实现不同数组的赋值。同时也是对栈的应用。数据结构课程设计的主要目的是介绍一些常用的数据结构，阐明数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，并结合各种数据结构，讨论对他们实行的各种运算的实现算法。通过本次数据结构课程设计，让我学到了很多有用的知识，在实际操作中也犯了很多错误，这些错误同时也让我意外的收获了很多。对我所学的数据结构知识理论也得到巩固。通过实际的设计和分析，让我学会了编程的基本步骤和方法，同时也开发了自己的逻辑思维能力，培养了份额系问题、解决问题的能力。在不断的遇到问题，不断的解决问题的过程中，培养的专业的思维是最重要的，也是这次课程设计所要达到的目的，我很庆幸我做到了。5、源程序和运行结果5.1 源程序#include<iostream>using namespace std;struct PosType /迷宫坐标位 int x; /行值 int y; / 列值 ;#define MAXLENGTH 25 typedef int MazeTypeMAXLENGTHMAXLENGTH; /* 迷宫数组行列 */ MazeType m; / 迷宫数组 int curstep=1; /当前足迹,初值为1 int aMAXLENGTH; int bMAXLENGTH; int cMAXLENGTH; struct SElemType/* 栈的元素类型 */ int ord; /* 通道块在路径上的序号 */ PosType seat; /* 通道块在迷宫中的坐标位置 */ int di; /* 从此通道块走向下一通道块的方向(03表示东北) */ ;#define STACK_INIT_SIZE 10 #define STACKINCREMENT 2 struct SqStack SElemType *base; SElemType *top; int stacksize; ; /* 顺序栈 */ bool Pass(PosType b) /* 当迷宫m的b点的序号为0(可通过路径)，return true, 否则，return false。 */ if(mb.xb.y=0) return true; else return false; void FootPrint(PosType a) /使迷宫m的a点的序号变为足迹(curstep) ma.xa.y=curstep; PosType NextPos(PosType c,int di) /* 根据当前位置及移动方向，返回下一位置 */ PosType direc4=0,1,1,0,0,-1,-1,0; /* 行增量,列增量 */ /* 移动方向,依次为东南西北 */ c.x+=direcdi.x; c.y+=direcdi.y; return c; void MarkPrint(PosType b) /* 使迷宫m的b点的序号变为-1(不能通过的路径) */ mb.xb.y=-1; bool InitStack(SqStack *S) /* 构造一个空栈S */ (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!(*S).base) exit(1); /* 存储分配失败 */ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return true; bool Push(SqStack *S,SElemType e) /* 插入元素e为新的栈顶元素 */ if(*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */ (*S).base=(SElemType *)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(SElemType); if(!(*S).base) exit(1); /* 存储分配失败 */ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; *(*S).top)+=e; return true; bool StackEmpty(SqStack S) /* 若栈S为空栈，则返回TRUE，否则返回FALSE */ if(S.top=S.base) return true; else return false; bool Pop(SqStack *S,SElemType *e) /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ if(*S).top=(*S).base) return false; *e=*-(*S).top; return true; bool MazePath(PosType start,PosType end) /* 若迷宫maze中存在从入口start到出口end的通道，则求得一条 存放在栈中(从栈底到栈顶)，并返回TRUE；否则返回FALSE */ /int curstep=1;SqStack S; PosType curpos; SElemType e; InitStack(&S); curpos=start; do if(Pass(curpos) /* 当前位置可以通过，即是未曾走到过的通道块 */ FootPrint(curpos); /* 留下足迹 */ e.ord=curstep; /cout<<curstep; acurstep=e.seat.x=curpos.x; bcurstep=e.seat.y=curpos.y; ccurstep=e.di=0; /cout<<acurstep<<" "<<bcurstep<<" "<<ccurstep<<endl; Push(&S,e); /* 入栈当前位置及状态 */ curstep+; /* 足迹加1 */ if(curpos.x=end.x&&curpos.y=end.y) /* 到达终点(出口) */ return true; curpos=NextPos(curpos,e.di); else /* 当前位置不能通过 */ if(!StackEmpty(S) Pop(&S,&e); /* 退栈到前一位置 */ curpos=e.seat; curstep-; while(e.di=3) && (!StackEmpty(S) /* 前一位置处于最后一个方向(北) */ MarkPrint(e.seat); /* 留下不能通过的标记(-1) */ Pop(&S,&e); /* 退回一步 */ curpos=e.seat; curstep-; if(e.di<3) /* 没到最后一个方向(北) */ e.di+; /* 换下一个方向探索 */ Push(&S,e); acurstep=e.seat.x=curpos.x; bcurstep=e.seat.y=curpos.y; ccurstep=e.di; curstep+; curpos=NextPos(e.seat,e.di); /* 设定当前位置是该新方向上的相邻块 */ while(!StackEmpty(S); return false; void Print(int x,int y) /* 输出迷宫的解 */ int i,j; for(i=0;i<x;i+) for(j=0;j<y;j+) cout<<mij<<" " cout<<endl; void main() PosType begin,end; int i,j,x,y,x1,y1; cout<<"请输入迷宫的行数,列数(包括外墙)：" cin>>x>>y; for(i=0;i<x;i+) /* 定义周边值为1(同墙) */ m0i=1; /* 行周边 */ mx-1i=1; for(j=0;j<y;j+) mj0=1; /* 列周边 */ mjy-1=1; for(i=1;i<x-1;i+) for(j=1;j<y-1;j+) mij=0; /* 定义通道初值为0 */ cout<<"请输入迷宫内墙单元数：" cin>>j; cout<<"请依次输入迷宫内墙每个单元的行数,列数："<<endl;待添加的隐藏文字内容2 for(i=1;i<=j;i+) cin>>x1>>y1; mx1y1=1; /* 定义墙的值为0 */ cout<<"迷宫结构如下:"<<endl; Print(x,y); cout<<"请输入起点的行数,列数：" cin>>begin.x>>begin.y; cout<<"请输入终点的行数,列数：" cin>>end.x>>end.y; if(MazePath(begin,end) /* 求得一条通路 */ cout<<"此迷宫从入口到出口的一条路径如下:"<<endl; Print(x,y); /* 输出此通路 */ for(i=1;i<curstep;i+) cout<<ai<<" "<<bi<<" "<<ci<<endl; else cout<<"此迷宫没有从入口到出口的路径"<<endl;5.2 运行结果输入上述测试用例：每两位数为内墙的坐标，总共26个内墙节点。输入后自动得出迷宫的结构：其中四周为外墙，内墙为1，通路为0.自己定迷宫的入口和出口：得出解决迷宫问题的一条路径：同上述迷宫一样，只是这个通路显示出每一步的路径来，总共走了20步。用三位数表示的路径：6、参考文献数据结构（C语言版）严蔚敏 吴伟民 编著 清华大学出版社数据结构题集（C语言版）严蔚敏 吴伟民 编著 清华大学出版社本科生课程设计成绩评定表班级：计科0909班姓名
