迷宫与栈问题课程设计报告.doc

二、课程设计内容（含技术指标）【问题描述】以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。【任务要求】首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），。编写递归形式的算法，求得迷宫中所有可能的通路。以方阵形式输出迷宫及其通路。【测试数据】迷宫的测试数据如下：左上角（0，1）为入口，右下角（8，9）为出口。四、基本要求1在设计时，要严格按照题意要求独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。 2在设计完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算设计部分的结束。 3设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，报告格式严格按照模板要求撰写，排版及图、表要清楚、工整。从总体来说，所设计的程序应该全部符合要求，问题模型、求解算法以及存储结构清晰；具有友好、清晰的界面；设计要包括所需要的辅助程序，如必要的数据输入、输出、显示和错误检测功能；操作使用要简便；程序的整体结构及局部结构要合理；设计报告要符合规范。 课程负责人签名： 2011年7月1日迷宫与栈问题摘 要数据结构是研究与数据之间的关系，是互相之间一种或多种特定关系的数据元素的集合，我们称这一关系为数据的逻辑结构。数据结构在计算机的表示（又称映像）称为数据的物理结构，又称存储结构。本次课程设计是迷宫求解问题，主要是模拟从入口到出口的通路。程序中的数据采取的是“栈”作为数据的逻辑结构，并且使用链式存储结构，即是实现一个以链表作存储结构的栈类型。本课程设计实现了链栈的建立，入栈，出栈，判断栈是否为空的方法，关键的是迷宫通路路径的“穷举求解”和递归求解的方法。本课程设计重要说明了系统的设计思路、概要设计以及各个功能模块的详细设计和实现方法。本次程序的开发工具是microsoft visual studio 2008，编程语言是C语言。关键词：迷宫求解 链栈 穷举求解 递归求解目 录摘要IIII1需求分析 11.1基本原理分析11.2功能要求12 概要设计22.1数据结构及其抽象数据类型的定义22.1.1栈的抽象数据类型22.1.2迷宫的抽象数据类型22.1.3功能模块分解33 详细设计43.1主函数与各功能模块43.2迷宫路径模块43.2.1算法分析43.2.2流程图54软件测试64.1调试过程中遇到的问题的解决，以及程序设计思想的实现64.2测试数据64.3测试结果84.4结果分析10参考文献11心得体会12教师评语13答辩记录表14 附录15211 需求分析1.1基本原理分析迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。定义迷宫类型来存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫任何一个位置，均约定东、南、西、北四个方向可通。1.2功能要求（1）以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫的四周有一圈障碍。（2）程序输出的结果以三元组（i,j,di）的形式输出，其中：（i,j）指示迷宫中的一个坐标，di表示走到下一坐标的方向，di的取值为1、2、3、4分别表示东、南、西、北（3）程序能够输出一个任意的迷宫从指定入口到出口的所有通路，以及以方阵形式输出迷宫（4）若设定的迷宫存在通路，则以方阵形式将迷宫及其通路输出到标准输出文件上，其中字符“1”表示障碍，“2”表示路径，“3”表示曾途经该位置但不能到达出口，其余位置用0表示。若设定迷宫不存在通路则报告相应信息2 概要设计2.1数据结构及其抽象数据类型的定义2.1.1栈的抽象数据类型ADT LinkStack数据对象：D=ai| aiCharSet,i=1,2n,n=0数据关系：R1=| ai-1, aiD,i=2,n基本操作：InitLinkStack(&S)操作结果：构造一个空栈S。LinkStackEmpty(&S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。PushLinkStack (&S，e)初始条件：栈S已存在。操作结果：在栈S的栈顶插入新的栈顶元素e。PopLinkStack (&S，&e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。 ADT LinkStack2.1.2迷宫的抽象数据类型ADT Maze数据对象：D=ai,j| ai,j0,1,2,3,0=i=m-1,0=j=n-1,m,n迷宫模块-栈模块3 详细设计3.1主函数与各功能模块主函数的各函数调用关系如图3-1所示，主函数调用创建迷宫函数和求解所有路径的函数，其中创建迷宫信息的函数调用初始化迷宫和输出迷宫。主函数求解所有路径MazePath初始化迷宫InitMaze初始化栈InitLinkStackack输出迷宫PrintMaze入栈PushLinkStack出栈PopLinkStack判断栈是否为空LinkStackEmpty留下标记MarkPrint判断方向NextPos留下足迹FootPrint判断能否通过Pass图3-13.2 迷宫路径模块3.2.1算法分析 解决迷宫问题最重要的程序段是找到通路，并存储在栈里，现只分析实现这一过程的函数do 若当前位置可通， 则 将当前位置插入栈顶； 若该位置是出口位置，则结束； 否则切换当前位置的东邻方块为新的当前位置； 否则， 若栈不空且栈顶位置尚有其他方向未经探索， 则设定的新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则 删去栈顶位置； 若栈不空，则重新测试新的栈顶位置， 直到找到一个可通的相邻块或出栈至栈空； while（栈不空）；3.2.2 流程图将入口、出口位置传入方法里判断当前位置是否可通将元素入栈是否到达迷宫出口右边是否存在通路上边是否存在通路左边是否存在通路下边是否存在通路存储结点入栈循环结束，无解迷宫有解迷宫图3-24软件测试4.1调试过程中遇到的问题的解决，以及程序设计思想的实现（1）调试过程中出现的错误有编译连接时的一些语法错误，也有由于算法存在问题而导致程序运行没有结果或者不是预期的结果。这里主要说一下自己由于算法而导致的错误：因为没有注意结点不能重复走，所以造成了死循环，程序没有结果。通过分析后把走过的结点变为不可走的结点，这样就避免了重复走到该结点。还有就是判断迷宫是否有通路的这个结果不能如预期的结果那样：有通路就输出所有的通路，没有就输出“没有路径可走!”。因为没有通路可走的时候栈是空的，但是输出所有的路径以后栈也是空的。当迷宫有通路的时候，在输出所有路径以后还是会输出“没有路径可走!”这句话。当迷宫没有通路的时候，输出“没有路径可走!”这句话。因为算法的思想是这样的，所以达不到预期的结果。解决的方法是如果迷宫有通路则输出所有的通路，如果迷宫没有通路，则没有结果输出。（2）迷宫的求解一般采用的是“穷举求解”，利用栈的思想，先将入口位置进栈，判断方向，若其方向可通，则进栈，若不通，则出栈，如此循环下去。4.2测试数据迷宫输入递归求路 非递归求路径：以方阵形式输出迷宫及其通路： 测试无通路的迷宫： 4.3测试结果迷宫输入： 求通路:以方阵形式输出迷宫及其通路：4.4结果分析本题中三个主要算法：InitMaze,MazePath和PrintMaze时间复杂度均为O（row*line），空间复杂度也为O（row*line）参考文献1 严蔚敏、吴伟民：数据结构（C语言版）M，清华大学出版社 2007年版2 谭浩强：C语言设计（第三版）M，清华大学出版社 2005年版3 曹衍龙、林瑞仲、徐慧：C语言实例解析精粹（第二版）M，人民邮电出版社心得 体会通过这段时间的课程设计，本人对计算机的应用，数据结构的作用以及C语言的使用都有了更深的了解。尤其是C语言的进步让我深刻的感受到任何所学的知识都需要实践，没有实践就无法真正理解这些知识以及掌握它们，使其成为自己的财富。在设计此程序时，刚开始感到比较迷茫，然后一步步分析，试着写出基本的算法，思路渐渐清晰，最后完成程序。当然也遇到不少的问题，也正是因为这些问题引发的思考给我带了收获。在遇到描写迷宫路径的算法时，我感到有些困难，后来经过一步步分析和借鉴书本上的穷举求解的算法，最后把算法写出来。但其要求是要输出迷宫路径的一步步位置，我通过利用两个栈的互相出入栈，达到栈的逆序输出。在利用递归方法求路径时花费了我很长时间，由于本人对递归方面的知识运用较少，导致我不熟悉它的用法，但最终还是通过询问同学、查找书本和上网了解关于递归方面的知识写出来了。这次课程设计让我更加深入了解很多方面的知识，如链结构的栈类型及其基本操作，数组的运用等等。在程序的编写中不要一味的模仿，要自己去摸索，只有带着问题反复实践，才能熟练地掌握和运用。在实际的上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力，所以相信通过此次实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。附 录程序源代码：#include #include #include #define MAXLEN 10/迷宫包括外墙最大行列数目#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#define STACK_INIT_SIZE 100 /存储空间初始分配量typedef int Status;typedef struct int row;intline;PosType;/迷宫中row行line列的位置typedef struct MazeTypeint row; int line; int arrMAXLENMAXLEN;MazeType; /迷宫类型typedef struct int ord; / 当前位置在路径上的“序号” PosType seat; /当前的坐标位置 int di; /往下一坐标位置的方向SElemType;typedef struct StacknodeSElemType data;struct Stacknode *next;*LinkStack;/构建一个空栈Sint InitLinkStack(LinkStack &S)S=(LinkStack)malloc(sizeof(LinkStack); /通过malloc函数分配空间if (!S)return ERROR; /如果分配失败，则返回S-next=NULL;return OK;/判断栈是否为空Status LinkStackEmpty(LinkStack &S)if (S!=NULL) if (S-next=NULL)return OK;return ERROR;/插入元素e为新的栈顶元素Status PushLinkStack(LinkStack &S,SElemType e)LinkStack q=S;LinkStack m=(LinkStack)malloc(sizeof(LinkStack); /通过malloc函数分配空间if (S!=NULL)while (q-next!=NULL)q=q-next;m-data=e;m-next=NULL;q-next=m;return ERROR;/若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORStatus PopLinkStack(LinkStack &S,SElemType &e)LinkStack q=S;if (S!=NULL)if (q-next!=NULL) /若栈不是空的while (q-next-next!=NULL)q=q-next;e=q-next-data;q-next=NULL;return OK;return ERROR;Status Pass(MazeType MyMaze,PosType CurPos) if(MyMaze.arrCurPos.rowCurPos.line=0)return TRUE; / 如果当前位置是可以通过，返回else return FALSE; / 其它情况返回void FootPrint(MazeType &MyMaze,PosType CurPos) MyMaze.arrCurPos.rowCurPos.line=2;void MarkPrint(MazeType &MyMaze,PosType CurPos) MyMaze.arrCurPos.rowCurPos.line=3;PosType NextPos(PosType CurPos, int Dir) PosType ReturnPos; switch (Dir) case 1:ReturnPos.row=CurPos.row;ReturnPos.line=CurPos.line+1;break;case 2:ReturnPos.row=CurPos.row+1;ReturnPos.line=CurPos.line;break;case 3:ReturnPos.row=CurPos.row;ReturnPos.line=CurPos.line-1;break;case 4:ReturnPos.row=CurPos.row-1;ReturnPos.line=CurPos.line;break;return ReturnPos;Status MazePath(MazeType &maze, PosType start, PosType end) / 若迷宫maze中从入口start到出口end的通道，则求得一条存放在栈中/ （从栈底到栈顶），并返回TRUE；否则返回FALSELinkStack S,S1;PosType curpos;int curstep;SElemType e;InitLinkStack(S);InitLinkStack(S1);curpos = start; / 设定当前位置为入口位置curstep = 1; / 探索第一步doif(Pass(maze,curpos) / 当前位置可通过，即是未曾走到过的通道块FootPrint(maze,curpos); / 留下足迹e.di =1;e.ord = curstep;e.seat= curpos;PushLinkStack(S,e); / 加入路径if(curpos.row = end.row & curpos.line=end.line)while(!LinkStackEmpty(S)PopLinkStack(S,e);PushLinkStack(S1,e);printf(迷宫的路径：);while(!LinkStackEmpty(S1)PopLinkStack(S1,e);printf(第%d步：(%d,%d,%d) ,e.ord,e.seat,e.di);return (TRUE); / 到达终点（出口）curpos = NextPos(curpos, 1); / 下一位置是当前位置的东邻curstep+; / 探索下一步else / 当前位置不能通过if (!LinkStackEmpty(S) PopLinkStack(S,e);while (e.di=4 & !LinkStackEmpty(S) MarkPrint(maze,e.seat); PopLinkStack(S,e); / 留下不能通过的标记，并退回一步curstep-; / whileif (e.di4) e.di+;PushLinkStack(S,e); / 换下一个方向探索curpos = NextPos(e.seat,e.di); / 当前位置设为新方向的相邻块 / if / if / else while (!LinkStackEmpty(S) );printf(此迷宫无通路！n);return FALSE; / MazePath/初始化迷宫Status InitMaze(MazeType &maze)int i,j;printf(请输入迷宫的行和列数: ); scanf(%d,%d,&maze.row,&maze.line);printf(请输入迷宫(以表示可走,1表示有障碍)：n);for(i=1;i=maze.row;i+)for(j=1;j=maze.line;j+)scanf(%d,&maze.arrij);for(i=0;i=maze.line+1;i+)/迷宫行外墙maze.arr0i=1; maze.arrmaze.row+1i=1;/for for(i=1;i=maze.row;i+)/迷宫列外墙maze.arri0=1;maze.arrimaze.line+1=1;return OK;/以方阵形式输出迷宫及其通路void PrintMaze(MazeType &maze)/将标记路径信息的迷宫输出到终端(包括外墙)int i,j;for(i=0;i=maze.row+1;i+) for(j=0;j=maze.line+1;j+)printf(%2d,maze.arrij);/输出迷宫/当前位置的标记 printf(nn); /PrintMaze/递归算法LinkStack L,L1;void MazePath_Recursion(MazeType &maze,PosType cur,PosType end,int curstep)int i;SElemType e;PosType next; / 下一个位置/ 行增量,列增量PosType direc4=0,1,1,0,0,-1,-1,0;/ 移动方向,依次为东南西北for(i=0;i=3;i+) / 依次试探东南西北四个方向next.row=cur.row+direci.row;next.line=cur.line+direci.line;if(maze.arrnext.rownext.line=0) / 是通路e.seat=next;PushLinkStack(L,e);maze.arrnext.rownext.line=+curstep;if(next.row != end.row | next.line != end.line) / 没到终点MazePath_Recursion(maze,next,end,1); / 试探下一点(递归调用) elseprintf(n); printf(迷宫的路径：);while(!LinkStackEmpty(L)PopLinkStack(L,e);PushLinkStack(L1,e);while(!LinkStackEmpty(L1)PopLinkStack(L1,e);printf(%d,%d ) ,e.seat);maze.arrnext.rownext.line=0; / 恢复为通路