迷宫与栈问题课程设计报告.docx
《迷宫与栈问题课程设计报告.docx》由会员分享，可在线阅读，更多相关《迷宫与栈问题课程设计报告.docx（27页珍藏版）》请在冰点文库上搜索。
迷宫与栈问题课程设计报告
一、课程设计题目
迷宫与栈问题
二、课程设计内容（含技术指标）
【问题描述】
以一个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）为出口。
迷宫与栈问题
摘要
数据结构是研究与数据之间的关系，是互相之间一种或多种特定关系的数据元素的集合，我们称这一关系为数据的逻辑结构。
数据结构在计算机的表示（又称映像）称为数据的物理结构，又称存储结构。
本次课程设计是迷宫求解问题，主要是模拟从入口到出口的通路。
程序中的数据采取的是“栈”作为数据的逻辑结构，并且使用链式存储结构，即是实现一个以链表作存储结构的栈类型。
本课程设计实现了链栈的建立，入栈，出栈，判断栈是否为空的方法，关键的是迷宫通路路径的“穷举求解”和递归求解的方法。
本课程设计重要说明了系统的设计思路、概要设计以及各个功能模块的详细设计和实现方法。
本次程序的开发工具是microsoftvisualstudio2008，编程语言是C语言。
关键词：
迷宫求解链栈穷举求解递归求解
目录
摘要……………………………………………………………VI
1需求分析………………………………………………………1
1.1基本原理分析……………………………………………………1
1.2功能要求…………………………………………………………1
2概要设计………………………………………………………2
2.1数据结构及其抽象数据类型的定义……………………………2
2.1.1栈的抽象数据类型……………………………………………2
2.1.2迷宫的抽象数据类型…………………………………………2
2.1.3功能模块分解…………………………………………………3
3详细设计………………………………………………………4
3.1主函数与各功能模块……………………………………………4
3.2迷宫路径模块……………………………………………………4
3.2.1算法分析………………………………………………………4
3.2.2流程图…………………………………………………………5
4软件测试………………………………………………………6
4.1调试过程中遇到的问题的解决，以及程序设计思想的实现…6
4.2测试数据…………………………………………………………6
4.3测试结果…………………………………………………………8
4.4结果分析…………………………………………………………10
参考文献·………………………………………………………11
心得体会·………………………………………………………12
教师评语·………………………………………………………13
答辩记录表·……………………………………………………14
附录·……………………………………………………………15
1需求分析
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栈的抽象数据类型
ADTLinkStack{
数据对象：
D={ai|ai∈CharSet,i=1,2…n,n>=0}
数据关系：
R1={|ai-1,ai∈D,i=2,…n}
基本操作：
InitLinkStack（&S）
操作结果：
构造一个空栈S。
LinkStackEmpty（&S）
初始条件：
栈S已存在。
操作结果：
若S为空栈，则返回TRUE，否则返回FALSE。
PushLinkStack（&S，e）
初始条件：
栈S已存在。
操作结果：
在栈S的栈顶插入新的栈顶元素e。
PopLinkStack（&S，&e）
初始条件：
栈S已存在。
操作结果：
删除S的栈顶元素，并以e返回其值。
}ADTLinkStack
2.1.2迷宫的抽象数据类型
ADTMaze{
数据对象：
D={ai,j|ai,j∈{0,1,2,3},0<=i<=m-1,0<=j<=n-1,m,n<=10}
数据关系：
R={row,line}
基本操作：
InitMaze（&maze）
初始条件：
用迷宫类型Maze.arr[row][line]表示迷宫，迷宫的数据由用户自己定义，并且以值0表示通路，以值1表示障碍。
操作结果：
构成迷宫的数字型数组，以0表示通路，以1表示障碍。
MazePath（&maze,start,end）
初始条件：
迷宫S已被赋值。
操作结果：
若迷宫S中存在一条通路，则按如下规定改变迷宫S的状态：
以2表示路径上的位置，以3表示死胡同；否则迷宫的状态不变。
MazePath_Recursion（&maze,cur,end,curstep）
初始条件：
迷宫S已被赋值。
操作结果：
若迷宫S中存在通路，输出迷宫的可能路径。
PrintMaze（Maze）
初始条件：
迷宫M已经存在
操作结果：
以方阵形式输出迷宫。
}ADTMaze；
2.1.3功能模块分解
（1）主程序模块：
voidmain（）
{
初始化；
While
（1）{
接受命令;
处理命令;
}
}
（2）栈模块------实现栈的抽象数据类型
typedefstructStacknode{
SElemTypedata;
structStacknode*next;
}*LinkStack;
调用函数：
InitLinkStack（）,LinkStackEmpty（）,PushLinkStack（）,PopLinkStack（）
（3）迷宫模块----实现迷宫抽象数据类型
typedefstruct{
introw;
intline;
}PosType;//迷宫中row行line列的位置
typedefstructMazeType{
introw;
intline;
intarr[MAXLEN][MAXLEN];
}MazeType;//迷宫类型
typedefstruct{
intord;//当前位置在路径上的“序号”
PosTypeseat;//当前的坐标位置
intdi;//往下一坐标位置的方向
}SElemType;
调用函数：
Pass（）,FootPrint（）,MarkPrint（）,NextPos（）,MazePath（）或MazePath_Recursion（）,PrintMaze（）.
各个模块之间的调用关系如下：
主程序模块->迷宫模块 ->栈模块
3详细设计
3.1主函数与各功能模块
主函数的各函数调用关系如图3-1所示，主函数调用创建迷宫函数和求解所有路径的函数，其中创建迷宫信息的函数调用初始化迷宫和输出迷宫。
图3-1
3.2迷宫路径模块
3.2.1算法分析
解决迷宫问题最重要的程序段是找到通路，并存储在栈里，现只分析实现这一过程的函数
do{
若当前位置可通，
则{将当前位置插入栈顶；
若该位置是出口位置，则结束；
否则切换当前位置的东邻方块为新的当前位置；
}
否则，
若栈不空且栈顶位置尚有其他方向未经探索，
则设定的新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；
若栈不空但栈顶位置的四周均不可通，
则{删去栈顶位置；
若栈不空，则重新测试新的栈顶位置，
直到找到一个可通的相邻块或出栈至栈空；
}
}while（栈不空）；
3.2.2流程图
图3-2
4软件测试
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
#defineMAXLEN10//迷宫包括外墙最大行列数目
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineOVERFLOW-2
#defineSTACK_INIT_SIZE100//存储空间初始分配量
typedefintStatus;
typedefstruct{
introw;
intline;
}PosType;//迷宫中row行line列的位置
typedefstructMazeType{
introw;
intline;
intarr[MAXLEN][MAXLEN];
}MazeType;//迷宫类型
typedefstruct{
intord;//当前位置在路径上的“序号”
PosTypeseat;//当前的坐标位置
intdi;//往下一坐标位置的方向
}SElemType;
typedefstructStacknode{
SElemTypedata;
structStacknode*next;
}*LinkStack;
//构建一个空栈S
intInitLinkStack（LinkStack&S）
{
S=（LinkStack）malloc（sizeof（LinkStack））;//通过malloc函数分配空间
if（!
S）
returnERROR;//如果分配失败，则返回
S->next=NULL;
returnOK;
}
//判断栈是否为空
StatusLinkStackEmpty（LinkStack&S）
{
if（S!
=NULL）
{
if（S->next==NULL）
{
returnOK;
}
}
returnERROR;
}
//插入元素e为新的栈顶元素
StatusPushLinkStack（LinkStack&S,SElemTypee）
{
LinkStackq=S;
LinkStackm=（LinkStack）malloc（sizeof（LinkStack））;//通过malloc函数分配空间
if（S!
=NULL）
{
while（q->next!
=NULL）
{
q=q->next;
}
m->data=e;
m->next=NULL;
q->next=m;
}
returnERROR;
}
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
StatusPopLinkStack（LinkStack&S,SElemType&e）
{
LinkStackq=S;
if（S!
=NULL）
{
if（q->next!
=NULL）//若栈不是空的
{
while（q->next->next!
=NULL）
{
q=q->next;
}
e=q->next->data;
q->next=NULL;
returnOK;
}
}
returnERROR;
}
StatusPass（MazeTypeMyMaze,PosTypeCurPos）{
if（MyMaze.arr[CurPos.row][CurPos.line]==0）
returnTRUE;//如果当前位置是可以通过，返回
elsereturnFALSE;//其它情况返回
}
voidFootPrint（MazeType&MyMaze,PosTypeCurPos）{
MyMaze.arr[CurPos.row][CurPos.line]=2;
}
voidMarkPrint（MazeType&MyMaze,PosTypeCurPos）{
MyMaze.arr[CurPos.row][CurPos.line]=3;
}
PosTypeNextPos（PosTypeCurPos,intDir）{
PosTypeReturnPos;
switch（Dir）{
case1:
ReturnPos.row=CurPos.row;
ReturnPos.line=CurPos.line+1;
break;
case2:
ReturnPos.row=CurPos.row+1;
ReturnPos.line=CurPos.line;
break;
case3:
ReturnPos.row=CurPos.row;
ReturnPos.line=CurPos.line-1;
break;
case4:
ReturnPos.row=CurPos.row-1;
ReturnPos.line=CurPos.line;
break;
}
returnReturnPos;
}
StatusMazePath（MazeType&maze,PosTypestart,PosTypeend）{
//若迷宫maze中从入口start到出口end的通道，则求得一条存放在栈中
//（从栈底到栈顶），并返回TRUE；否则返回FALSE
LinkStackS,S1;
PosTypecurpos;
intcurstep;
SElemTypee;
InitLinkStack（S）;
InitLinkStack（S1）;
curpos=start;//设定"当前位置"为"入口位置"
curstep=1;//探索第一步
do{
if（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--;
}//while
if（e.di<4）{
e.di++;
PushLinkStack（S,e）;//换下一个方向探索
curpos=NextPos（e.seat,e.di）;//当前位置设为新方向的相邻块
}//if
}//if
}//else
}while（!
LinkStackEmpty（S））;
printf（"此迷宫无通路！
\n"）;
returnFALSE;
}//MazePath
//初始化迷宫
StatusInitMaze（MazeType&maze）{
inti,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.arr[i][j]）;
}
for（i=0;i<=maze.line+1;i++）{//迷宫行外墙
maze.arr[0][i]=1;
maze.arr[maze.row+1][i]=1;
}//for
for（i=1;i<=maze.row;i++）{//迷宫列外墙
maze.arr[i][0]=1;
maze.arr[i][maze.line+1]=1;
}
returnOK;
}
//以方阵形式输出迷宫及其通路
voidPrintMaze（MazeType&maze）{
//将标记路径信息的迷宫输出到终端（包括外墙）
inti,j;
for（i=0;i<=maze.row+1;i++）{
for（j=0;j<=maze.line+1;j++）
printf（"%2d",maze.arr[i][j]）;//输出迷宫//当前位置的标记
printf（"\n\n"）;
}
}//PrintMaze
//递归算法
LinkStackL,L1;
voidMazePath_Recursion（MazeType&maze,PosTypecur,PosTypeend,intcurstep）
{
inti;
SElemTypee;
PosTypenext;//下一个位置
//{行增量,列增量}
PosTy
升级会员 