数据结构中的迷宫问题

数据结构中的迷宫问题

作者:**pp2009-5-21 22:26:00

解题思路解析：

在迷宫问题中，一个迷宫用二维数组maze[size] [size]来存储，对当前位置（探索过程中某一时刻所在的位置）记为maze[curpos.row][curpos.line]，如果maze[curpos.row][curpos.line]=0则有通路，如果maze[curpos.row][curpos.line]=1则无通路。从入口star出发，可沿四个方向前进。

试探方向的变化

N(i-1,j)

W(i,j-1)

位置（i,j）

E(i,j+1)

S(i+1,j)

0表示E、1表示S、2表示W、三表示N。如果遇到0则可前进，遇1责受阻；按此规则求入口到某一确定出口的一条路径。算法的基本思想是：从迷宫的入口出发，进行判断，若当前位置可通（未走过的），则将当前位置插入栈顶，然后判断此位置是否为出口位置，如果是则结束整个运算，否则，改变当前位置到他的东临位置（即0方向）；否则如果当前位置不通，这时若栈不空且栈顶位置尚有其他位置未搜索，则设定新的当前位置为栈顶位置的下一邻块，若栈不空且栈顶位置四周不通，则删去栈顶位置，若栈不空，则重新测试新的栈顶位置，直到找到一个可通的邻块或栈空，如此重复判断，直到找到一条从入口到出口的一条路径或得到无路径的信息。

(1)需求分析

问题描述：以一个size*size的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定输入的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。在迷宫中求出从入口到出口的路径。经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。

求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。

假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置"可通"，则纳入"当前路径"，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。

a、输入的形式和输入值的范围：以0，1输入表示迷宫，0为通路，1为障碍。向电脑输入由0和1组成的二维数组，数组的行号列号相同且都为size（1=

b、输出的形式：首先输出迷宫“#”表示墙壁，“0”表示通道，“1”表示障碍。然后输出走出迷宫的路径，“#”表示墙壁，“0”表示迷宫通路，由于时间仓促不免会有些瑕疵，当好多“0”紧挨在一起的时候，有顺时针方向表示迷宫通道（由右方开始）。

c、程序所能达到的功能：实现输出迷宫通道，当迷宫无通道时显示“找不到通路”。

d、测试数据：由后面调试分析详细说明。

(2)概要设计

1．数据结构的定义

为实现输出迷宫路径需用到栈，下面定义栈的抽象数据类型：

栈（stack）是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有特殊含义，称为栈顶（top）,相应的，表头端称为栈底（bottom）。不含元素的空表称为空栈。假设栈S=（a1,a2,…，an），则称a1为栈底元素，an为栈顶元素。栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（List In First Out）的线性表。（简称LIFO结构）ADT Stack{

数据对象：D={ai|ai∈ElemSet,i=1,2,…,n, n>=0}

数据关系：R1={|ai-1,ai∈D,i=2,…,n,}

约定an端为栈顶，a1端为栈底。

在迷宫问题中，假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入可以走的路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。

2．程序模块

(1)迷宫和栈的定义：

typedef enum { ERROR, OK } Status;

typedef struct

{

int row; //row表示“行”号

int line; //line表示“列”号

}PosType; //位置的元素类型

typedef struct

{ int ord; //该通道在路径上的“序号”

PosType seat; //通道块在迷宫中的“坐标位置”

int di; //从此通道走向下以通道块的“方向”

}SElemType; //栈的元素类型

typedef struct

{

SElemType * base; //在构造之前和销毁之后，base的值为NULL

SElemType * top; //栈顶指针

int stacksize; //当前已分配的存储空间

}SqStack;

(2)构造一个空栈S：

Status InitStack(SqStack &S)

{

S.base=(SElemType *)malloc(100*sizeof(SElemType));

if(!S.base)return ERROR; //存储分配失败

S.top=S.base;

S.stacksize=100;

return OK;

}

(3)进栈：

Status Push（SqStack &S，SElemType &e）

{ //插入元素e为新的栈顶元素

if (S.top-S.base>=S.stacksize){ //栈满，追加存储空间

S.base=(ElemType*) realloc (S.base,(S.stacksize+STACKINCREMENT)*sizeof (ElemType));

If(!S.base) exit (overflow) //存储分配失败

S.top=S.base+S.stacksize;

S.stacksize+= STACKINCREMENT;

}

*S.top++=e;

Return OK;

}

由于本题中在为栈分配存储空间的时候S.stacksize=100，为迷宫最大的元素数，因此不存在栈满的情况。

(4)删除栈顶元素：

Status Pop(SqStack &S,SElemType &a)

{ //若栈不空，则删除S的栈顶元素，用a返回其值，并返回OK，否则返回ERROR

if(S.top==S.base)return ERROR;

a=*--S.top;

return OK;

}

(5)判栈空：

Status StackEmpty(SqStack S)

{

if(S.top==S.base) return OK;

return ERROR;

}

3、各模块之间的调用关系:

(1)本程序主要包括以下函数：

(1)主函数main()

(2)初始化迷宫函数Initmaze()

(3)显示所创建的迷宫函数printmaze ()

(4)进入下一个位置函数NextPos()

(5)创建空栈函数InitStack()

(6)检查是否为空栈函数StackEmpty()

(7)插入栈元素函数push ()

(8)删除栈元素函数pop ()

(9) 寻找到路径函数mazepath ()

(10) 输出路径函数printpath()

(11)标记当前位置函数Markfoot()

(12)判断当前位置是否可通函数Pass()

（2）各种函数之间的调用关系如下：

main()

Initmaze()

printmaze ()

mazepath ()

initStack()

push()

stackempty()

pop

nextpos()

printpath()

(3)详细设计：

解决迷宫问题最重要的程序段是找到通路，并存储在栈里，现只分析实现这一过程的函数MazePath()：

do {

若当前位置可通，

则{ 将当前位置插入栈顶；

若该位置是出口位置，则结束；

否则切换当前位置的东邻方块为新的当前位置；

}

否则，

若栈不空且栈顶位置尚有其他方向未经探索，

则设定的新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；

若栈不空但栈顶位置的四周均不可通，

则{ 删去栈顶位置；

若栈不空，则重新测试新的栈顶位置，

直到找到一个可通的相邻块或出栈至栈空；

}

}while（栈不空）；

在此，尚需说明一点的是，所谓当前位置可通，指的是未曾走到过的通道块，即要求该方块位置不仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经纳入过路径的通道块（否则只能在死胡同内转圈）。

Status MazePath (MazeType maze,PosType start, PsoType end) {

//若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中(从栈底到//栈顶)，并返回TURE；否则返回FALSE

InitStack(S); curpos=start; //设定“当前位置”位“入口位置”

curstep=1; //探索第一步

do{

if (Pass(curpos)) { //当前位置可以通过，即是未曾走到过的通道块

FootPrint(curpos); //留下足迹

e=(curstep,curpos,1);

Push(S,e); //加入路径

if (curpos==end) return (TRUE); //到达终点(出口)

curpos=NextPos(curpos,1); //下一位置是当前位置的东邻

curstep++; //探索下一步

}

else { //if

if (!StackEmpty(S)) { //当前位置不能通过

Pop (S,e);

while (e.di==4 && !StackEmpty(S)) {

MarkPrint(e.seat); Pop(S,e); //留下不能通过的标记，并退回一步}

if (e.di<4) {

e.di++; Push (S,e); //换下一个方向探索

curpos=NextPos (e.seat e.di); //设定当前位置是该新方向上的相邻块

} //if

} //if

} //else

}while (!StackEmpty(S));

return (FALSE);

} //MazePath

(4)调试分析：

a、调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析：

遇到的问题：

（1）首先是对实现迷宫由当前方向转向下一方向时应当怎样实现遇到了困难，具体解析见解题思路。

（2）然后是当前位置不可通，即当前位置的四周方向都试探过后发现不是通路，如何实现退向后一位置。如果当前位置不通，则留下足迹即把当前位置标记为1，再把当前位置从栈顶位置删除，这样此位置就不会循环往复的再次被走到。

（3）如何实现输出迷宫通路的问题。

当当前位置坐标和迷宫终点坐标相同时，即迷宫走到出口。这时迷宫里所有元素还是由“0”和“1”组成，把栈中元素标记为“2”以示和别的元素区别。把数组中所有为“2”的元素输出“0”,不是2的元素输出“ ”，围墙由“#”输出。这样就解决了迷宫路径的输出问题。

在这个问题上由于输入数据的时候是输入一个0或1，然后再输入一个空格，这样会比较美观。但是最初想到的是用“ ”即一个空格代表不是通路的元素，这样最终输出的时候就出现问题了，迷宫的围墙“#”会不在最后一列出现，输出错误的通道或者就显示不出通道。最后反复思考后发现问题出在这“ ”一个空格上，只要把一个空格改为“ ”两个空格就会很好的解决了。

（4）迷宫的初始化问题：

经过小组成员讨论决定给用户多种选择，既可由计算机自动生成迷宫也可用户自己手动输入迷宫。这个问题事先并不难，只要知道rand(void)用于产生一个伪随机unsigned int 整数就可以简单实现。rand()%2就可以实现随机抽取一个0或1。

（5）如何实现迷宫的美观化：

经过小组讨论要给用户一个良好的使用界面，用“#”表示墙壁以示和迷宫的的区别。输入计算机数据是要在第一行最后一行（size+1列）和第一列最后一列（size+1列）全部输入1，因为1表示障碍。然后输出迷宫式用两个for循环就可以吧第一行和最后一行的围墙输出，然后每一行的第一个位置和最后一个位置再分别输出“#”就可以达到生成围墙的效果，同时

美化了迷宫。

b、算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想：

求解迷宫通路问题基本操作要数进栈了，现来分析进栈最大次数，如果迷宫大小为size，则最大进栈次数也应当为size，即栈里存储了整个迷宫的路径。若size为奇数则入口位置定位（1，1），出口位置定位（2，size-1），则首先探索第一行，然后是最后一列，紧接着是最后一行，然后逐层向上，最终到达（2，size-1），整个过程把整个迷宫全部试探了一遍。如果size是偶数则入口位置定位（1，1），出口位置定位（2，1），则也是整个迷宫要全部探索完才能够最终到达（2，1）。时间复杂度为O(size*size).

改进设想：可以先对迷宫进行改进，比如迷宫中有些通道是形如：

1 0 1

1

的形式，显而易见中间的元素0肯定是不通的，可以在穷举迷宫中元素之前先把此类元素全部置为1，这样就可以减少好多不必要的入栈和出栈，从而减少了时间复杂度。

c、经验和体会：

这是我们小组成员第一次以团队合作的形式参与程序设计这样的实验。由于数据结构这门课本身就比较晦涩和难以理解，我们从刚开始选题就陷入了僵局。经过我们几次的讨论和商讨，最终决定选择这个符合我们小组成员实际能力的选题——迷宫。在确定下选题了之后，我们就着手开始准备实现程序的各个步骤。我们依据实验报告的要求和步骤一项项进行规划，期间在图书馆查阅了很多资料，小组成员之间也相互学习，不懂的地方大家一起讨论。至于最后代码的实现，也是我们小组成员共同努力的结果。我们不断改进和完善代码中繁琐和冗余的部分，力图写出一个最简洁明了又不脱离实际的程序，尽可能做到和现实相贴近。在上机实际操作中，也并不是从一开始就顺利的，代码中出现了不少错误，虽然我们一一调试改正，但在最后还是遇到了瓶颈，大家也都纷纷绞尽脑汁思考问题所在。当然，错误最后被我们查找了出来。而后便是收尾工作，成员们依旧尽心尽力，最终，经过我们一周多的努力，我们有了实验成果。

在这次团队合作中，我们都深深体会到学好专业知识的重要性，老师上课所教授的基本知识是非常必要的，在真正应用到实际选题的时候就凸显了出来，就以我们小组的选题为例，迷宫问题的基本思想就是栈的问题，如果对栈的知识比较了解，在实现迷宫问题时是不会太吃力的。其次，通过团队合作，我们每个人都感觉到了团队精神的重要性，它不是说将每个人的想法叠加或简单拼凑起来，而是需要我们每个人协调，汲取每个人的专长和想法的独到之处，进而整合起来，确定一个完备的方案。其中非常重要的是，在相互讨论和商榷中，争执是不可避免的。成员们并没有因此动怒，而是耐心倾听和思考，说出每个人的意见，做到了让每个人都信服。所以说，通过这次实验，也使我们小组成员之间的关系更加和谐和亲密。

(5)用户使用说明：

1.运行环境，执行文件

1编制，调试和运行程序总是依赖所使用的语言环境，当然也令支持语言的系统程序的基础环境即操作系统环境的影响，此课程设计以Visual C++6.0为依据，作为运行环境。

2.用户界面

Visual C++6.0的集成化环境

3.操作过程如下:

一．程序名为maze.exe，运行环境为DOS。程序执行后显示：

创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于10)

接着用户可输入一个大于等于1且小于等于10的数字，若输入的数字小于1或者大于

10, 则会显示：

输入错误！

然后用户可继续输入，直到输入的数字在规定的范围内则程序才会继续运行。

二．输入了数字，执行了以后，将显示：

选择创建方式A:自动生成B:手动创建

1。若输入A或者a，则系统会自动生成一个迷宫模型。

2．若输入B或者b，则显示：

按行输入size*size数据,0代表可通,1代表不可通(每行以Enter结束):

然后用户则可自行输入所需的迷宫模型，输入0将表示此处可以通过，输入1将表示此处不能通过。且注意每行输入size个数字，输入完一行以后按Enter键表示该行输入完毕。3．若按下Enter键，则程序不会继续，直到正确输入符合1，2点要求的字母时程序才能继续运行。

4。若输入除以上3点以外的其它字符，则显示：

输入错误！

然后用户需继续按照正确规则输入程序才能继续运行。

三．迷宫模型设置好以后，将显示：

显示所建的迷宫(#表示外面的墙)

接着，设置好的迷宫模型将被显示出来。

四．迷宫显示出来以后，系统会继续显示：

输入入口行坐标和列坐标：

此时用户可自定入口的行列坐标，注意所输入的的数字必须大于等于1且小于等于第一步中自定的迷宫大小。如果不在此范围内则找不到迷宫通路。出口和入口处必须为0，否则肯定是找不到通路的。完成后显示：

输入出口行坐标和列坐标：

此时用户可自定出口的行列坐标，注意所输入的的数字必须大于等于1且小于等于第一步中自定的迷宫大小。如果不在此范围内则找不到迷宫通路。出口和入口处必须为0，否则肯定是找不到通路的。

五．前几步都完成后，若迷宫有通路，则会将通路显示出来，若迷宫没有通路，则显示：找不到通路！

程序至此结束。

(6)测试结果：

（1）自动生成迷宫且有通路：

（2）自动生成迷宫且无通路：

（3）手动生成迷宫且无通路：

（4）手动生成迷宫且有通路：

(7)附录

程序代码：

实现方法一：栈求解

＃i nclude

＃i nclude

/***************数据定义****************/

typedef enum { ERROR, OK } Status;

typedef struct

{

int row; //row表示“行”号

int line; //line表示“列”号

}PosType; //位置的元素类型

typedef struct

{

int ord; //该通道在路径上的“序号”

PosType seat; //通道块在迷宫中的“坐标位置”

int di; //从此通道走向下以通道块的“方向”

}SElemType; //栈的元素类型

typedef struct

{

SElemType * base;

SElemType * top;

int stacksize;

}SqStack;

/***********函数原型说明******************/

Status InitStack(SqStack &S); //创建一个空栈S

Status Push(SqStack &S,SElemType &a); //插入新元素a

Status Pop(SqStack &S,SElemType &a); //删除栈顶元素，a返回其值Status StackEmpty(SqStack S); //检查是否空栈

Status MazePath(int maze[12][12],SqStack &S, PosType start, PosType end);

//找通路

void Initmaze(int maze[12][12],int size); //初始化迷宫

void printmaze(int maze[12][12],int size); //显示迷宫

Status Pass(int maze[12][12],PosType CurPos); //判断当前位置是否可通

void Markfoot(int maze[12][12], PosType CurPos); //标记当前位置不可通PosType NextPos(PosType CurPos, int Dir); //进入下一位置

void printpath(int maze[12][12],SqStack S,int size); //显示通路

/************主函数*****************/

void main (void)

{

SqStack S;

int size,maze[12][12];

for(int n=0;n<10;n++)

{

printf("创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于10):\n");

//设置迷宫大小

scanf("%d",&size);if(size<1 || size>10){printf("输入错误!");return;}

Initmaze(maze,size); //初始化迷宫

printmaze(maze,size); //显示所创建的迷宫

PosType start,end; //设置入口和出口

printf("输入入口行坐标和列坐标:"); scanf("%d",&start.row);scanf("%d",&start.line);

printf(" 输入出口行坐标和列坐标:");

scanf("%d",&end.row);scanf("%d",&end.line);

if (MazePath(maze,S,start,end)) //若有通路，显示通路

printpath(maze,S,size);

else printf("找不到通路!\n\n");

}

}

/****若迷宫maze中从入口start到出口end的通道，则求得一条存放在栈中******/ Status MazePath(int maze[12][12],SqStack &S, PosType start, PosType end)

{

PosType curpos;

int curstep;

SElemType e;

InitStack(S);

curpos = start; // 设定"当前位置"为"入口位置

curstep = 1; // 探索第一步

do {

if (Pass(maze,curpos)) // 当前位置可通过，即是未曾走到过的通道块{

Markfoot(maze,curpos); // 留下足迹

e.di =0;

e.ord = curstep;

e.seat= curpos;

Push(S,e); // 加入路径

if (curpos.row==end.row && curpos.line==end.line)

return OK; // 到达终点（出口）

curpos = NextPos(curpos, 0); // 下一位置是当前位置的东邻

curstep++; // 探索下一步

}

else // 当前位置不能通过

{

if (!StackEmpty(S))

{

Pop(S,e);

while (e.di==3 && !StackEmpty(S))

{

Markfoot(maze,e.seat); // 留下不能通过的标记，并退回一步

Pop(S,e);

}

if (e.di<3)

{

e.di++; // 换下一个方向探索

Push(S, e);

curpos = NextPos(e.seat, e.di); // 当前位置设为新方向的相邻块} } }

} while (!StackEmpty(S));

return ERROR;

}

/***************初始化迷宫******************/

void Initmaze(int maze[12][12],int size)

{

char select;

printf("选择创建方式A:自动生成B:手动创建\n");

label:scanf("%c",&select);

if(select=='a'||select=='A') //自动生成

{

for(int i=0;i

for( i=1;i

{

maze[i][0]=1;

for(int j=1;j

maze[i][j]=rand()%2;

maze[i][size+1]=1;

}

for(i=0;i

}

else if(select=='b'||select=='B') //手动设置

{

printf("按行输入%d*%d数据,0代表可通,1代表不可通(每行以Enter结束):\n",size,size);

for(int i=0;i

for( i=1;i

{

maze[i][0]=1;

for(int j=1;j

scanf("%d",&maze[i][j]);

maze[i][size+1]=1;

}

for(i=0;i

}

else if(select=='\n')goto label; //排除Enter键的影响

else printf("输入错误!");

}

/***********显示迷宫******************/

void printmaze(int maze[12][12],int size)

{

printf("\n\n");

printf("显示所建的迷宫(#表示外面的墙):\n");

for(int i=0;i

printf("%c ",'#');printf("\n");

for(i=1;i

{

printf("%c ",'#');

for(int j=1;j

{

printf("%d ",maze[i][j]);

}

printf("%c",'#');

printf("\n");

}

for(i=0;i

}

/************输出路径******************/

void printpath(int maze[12][12],SqStack S,int size)

{

printf("\n\n通路路径为:\n");

SElemType * p=S.base;

while(p!=S.top)

{

maze[p->seat.row][p->seat.line]=2; //标记为路径中的点

p++;

}

for(int i=0;i

for(i=1;i

{

printf("%c ",'#');

for(int j=1;j

{

if(maze[i][j]==2) printf("%c ",'0');

else printf("");

}

printf("%c",'#');

printf("\n");

}

for(i=0;i

}

/************判断当前位置是否可通*******************/

Status (int maze[12][12],PosType CurPos)

{

if (maze[CurPos.row][CurPos.line]==0)

return OK; // 如果当前位置是可以通过，返回1 else return ERROR; // 其它情况返回0

}

/****************标记当前位置不可通****************/

void Markfoot(int maze[12][12],PosType CurPos)

数据结构迷宫问题实验报告

《数据结构与算法设计》迷宫问题实验报告 ——实验二 专业：物联网工程 班级：物联网1班 学号：15180118 ：刘沛航

一、实验目的 本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。 二、实验内容 用一个m*m长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 三、程序设计 1、概要设计 （1）设定栈的抽象数据类型定义 ADT Stack{ 数据对象：D={ai|ai属于CharSet，i=1、2…n，n>=0} 数据关系：R={|ai-1,ai属于D，i=2,3,…n} 基本操作： InitStack(&S) 操作结果：构造一个空栈 Push（&S，e） 初始条件：栈已经存在 操作结果：将e所指向的数据加入到栈s中 Pop（&S,&e） 初始条件：栈已经存在 操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素 Getpop（&S，&e） 初始条件：栈已经存在 操作结果：若栈不为空，用e返回栈顶元

StackEmpty(&S) 初始条件：栈已经存在 操作结果：判断栈是否为空。若栈为空，返回1，否则返回0 Destroy(&S) 初始条件：栈已经存在 操作结果：销毁栈s }ADT Stack （2）设定迷宫的抽象数据类型定义 ADT yanshu{ 数据对象：D={ai,j|ai,j属于{‘ ’、‘*’、‘’、‘#’},0<=i<=M,0<=j<=N} 数据关系：R={ROW,COL} ROW={|ai-1,j,ai,j属于D，i=1,2,…M,j=0,1,…N} COL={|ai,j-1,ai,j属于D,i=0,1,…M，j=1,2,…N} 基本操作： InitMaze(MazeType &maze, int a[][COL], int row, int col){ 初始条件：二维数组int a[][COL],已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障 碍，值1表示通路。 操作结果：构造迷宫的整形数组，以空白表示通路，字符‘0’表示障 碍 在迷宫四周加上一圈障碍 MazePath（&maze）{ 初始条件：迷宫maze已被赋值 操作结果：若迷宫maze中存在一条通路，则按如下规定改变maze的状态；以字符‘*’表示路径上的位置。字符‘’表 示‘死胡同’；否则迷宫的状态不变 } PrintMaze（M）{ 初始条件：迷宫M已存在 操作结果：以字符形式输出迷宫 } }ADTmaze （3）本程序包括三个模块

数据结构课程设计-迷宫问题的操作要点

1、课程设计目的 为了配合《数据结构》课程的开设，通过设计一完整的程序，掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法特进行题目为两个链表合并的课程设计。通过此次课程设计充分锻炼有关数据结构中链表的创建、合并等方法以及怎样通过转化成C语言在微机上运行实现等其他方面的能力。 2．课程设计的内容与要求 2.1问题描述： 迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫如下图A所示，求出一条从入口到出口的通路，或得出没有通路的结论。 图A 2.2设计要求： 要求设计程序输出如下： (1) 建立一个大小为m×n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏幕上显示出来； （2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。

3.2 概要设计 1.①构建一个二维数组maze[M+2][N+2]用于存储迷宫矩阵 ②自动或手动生成迷宫，即为二维数组maze[M+2][N+2]赋值 ③构建一个队列用于存储迷宫路径 ④建立迷宫节点struct point,用于存储迷宫中每个节点的访问情况 ⑤实现搜索算法 ⑥屏幕上显示操作菜单 2.本程序包含10个函数： (1)主函数main() (2)手动生成迷宫函数shoudong_maze()

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

数据结构课程设计报告 设计题目：迷宫问题数据结构课程设计_ 班级：计科152 学号：19215225 姓名：徐昌港 南京农业大学计算机系

数据结构课程设计报告内容 一．课程设计题目 迷宫问题 以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。 二．算法设计思想 1.需求分析 （1）迷宫数据用一个二维数组int maze[row][col]来存储，在定义了迷宫的行列数后，用两个for循环来录入迷宫数据，并在迷宫周围加墙壁。 （2）迷宫的入口位置和出口位置可以由用户自己决定。 2.概要设计 （1）主程序模块： void main() { int maze[row][col]; struct mark start,end; //出入口的坐标 int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; //方向，依次是东西南北 built_maze(maze); printf("请输入入口的横纵坐标："); scanf("%d,%d",&start.a,&start.b); printf("请输入出口的横纵坐标：");

scanf("%d,%d",&end.a,&end.b); printf("0为东，1为南，2为西，3为北，-1为出路\n"); maze_path(maze,dir,start,end); getchar(); } （2）栈模块——实现栈抽象数据类型 （3）迷宫模块——实现迷宫抽象数据类型，建立迷宫，找出迷宫的一条通路 3.详细设计 （1）坐标位置类型 struct mark{ int a,b; //迷宫a行b列为位置 }; （2）迷宫类型 void built_maze(int maze[row][col]) //按照用户输入的row行和col列的二维数组（元素值为0和1） //设置迷宫maze的初值，包括边上边缘一圈的值 void maze_path(int maze[row][col],int dir[4][2],struct mark start,struct mark end) //求解迷宫maze中，从入口start到出口end的一条路径， //若存在，则返回TRUE；否则返回FALSE （3）栈类型 struct element{ int i,j,d; //坐标与方向 }; typedef struct Linkstack{ element elem;

数据结构课程设计-迷宫问题(参考资料)

目录第一部分需求分析 第二部分详细设计 第三部分调试分析 第四部分用户手册 第五部分测试结果 第六部分附录 第七部分参考文献

一、需求分析 1、对于给定的一个迷宫，给出一个出口和入口，找一条从入口到出口的通路，并把这条通路显示出来；如果没有找到这样的通路给出没有这样通路的信息。 2、可以用一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 3、编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j， d)的形式输出，其中：(i，j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。 4、由于迷宫是任意给定的，所以程序要能够对给定的迷宫生成对应的矩阵表示，所以程序的输入包括了矩阵的行数、列数、迷宫内墙的个数、迷宫内墙的坐标、所求的通路的入口坐标、出口坐标。 二、详细设计 1、计算机解迷宫通常用的是“穷举求解“方法，即从人口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路

退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为(1，1)，出口点的下标为(n，n)。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。2、如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通。 3、所谓"走不通"不单是指遇到"墙挡路"，还有"已经走过的路不能重复走第二次"，它包括"曾经走过而没有走通的路"。 显然为了保证在任何位置上都能沿原路退回，需要用一个"后进先出"的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后，栈中保存的正是一条从入口到出口的路径。 4、若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索；若当前位置“不可通”，则应顺着“来的方向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。 所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的

数据结构-迷宫实验报告

云南大学软件学院数据结构实验报告（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C □ 实验难度 A □ B □ C □ 承担任务 （难度为C时填写） 指导教师评分（签名） 【实验题目】 实验4.数组的表示极其应用 【问题描述】 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 【基本要求】 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中:(i，j)指示迷宫中的一个坐标，d 表示走到下一坐标的方向。如；对于下列数据的迷宫，输出的一条通路为：(l，1，1)，(1，2，2)，(2，2，2)，(3，2，3)，(3，1，2)，…。?

（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%) （本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识） 本实验的目的是设计一个程序，实现手动或者自动生成一个n×m矩阵的迷宫，寻找一条从入口点到出口点的通路。我们将其简化成具体实验内容如下：选择手动或者自动生成一个n×m的迷宫，将迷宫的左上角作入口，右下角作出口，设“0”为通路，“1”为墙，即无法穿越。假设从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。如果迷宫可以走通，则用“■”代表“1”，用“□”代表“0”，用“→”代表行走迷宫的路径。输出迷宫原型图、迷宫路线图以及迷宫行走路径。如果迷宫为死迷宫，输出信息。 可以二维数组存储迷宫数据，用户指定入口下标和出口下标。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。? 二、【实验设计(Design)】(20%) （本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系） 1. 设定迷宫的抽象数据类型定义： ADT Maze { 数据对象：D = { a i, j | a i, j ∈ { ‘■’、‘□’、‘※’、‘→’、‘←’、 ‘↑’、‘↓’ } , 0≤ i≤row+1, 0≤j≤col+1, row, col≤18 } 数据关系：R = { ROW, COL } ROW = { < a i-1, j , a i, j > | a i-1, j , a i, j ∈D, i=1, … , row+1, j=0, … , col+1} COL = { < a i, j-1, a i, j > | a i, j-1 , a i, j ∈D, i=0, … , row+1, j=1, … , col+1} 基本操作： Init_hand_Maze( Maze, row, col) 初始条件：二维数组Maze[][]已存在。

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

迷宫求解 一．问题描述 对迷宫问题的求解过程实际就是从入口开始，一步一步地走到出口的过程。 基本要求： 输入一个任意大小的迷宫数据，用递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出。 二．设计思路 在本程序中用两种方法求解迷宫问题-非递归算法和递归算法。 对于非递归算法采用回溯的思想，即从入口出发，按某一方向向前探索，若能走通，并且未走过，则说明某处可以到达，即能到达新点，否则试探下一方向；若所有的方向均没有通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能到达的没一点的下标及该点前进的方向，然后通过对各个点的进出栈操作来求得迷宫通路。 对于递归算法，在当前位置按照一定的策略寻找下个位置，在下个位置又按照相同的策略寻找下下个位置…；直到当前位置就是出口点，每一步的走法都是这样的。随着一步一步的移动，求解的规模不断减小；如果起始位置是出口，说明路径找到，算法结束，如果起始位置的四个方向都走不通，说明迷宫没有路径，算法也结束。 另外，为了保证迷宫的每个点都有四个方向可以试探，简化求解

过程，将迷宫四周的值全部设为1，因此将m行n列的迷宫扩建为m+2行，n+2列，同时用数组来保存迷宫阵列。 三．数据结构设计 在迷宫阵列中每个点都有四个方向可以试探，假设当前点的坐标（x，y），与其相邻的四个点的坐标都可根据该点的相邻方位而得到，为了简化问题，方便求出新点的坐标，将从正东开始沿顺时针进行的这四个方向的坐标增量放在一个结构数组move[4]中，每个元素有两个域组成，其中x为横坐标增量，y为纵坐标增量，定义如下： typedef struct { int x,y; }item; 为到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，还要将从前一点到本点的方向压入栈中。栈中的元素由行、列、方向组成，定义如下： typedef struct { int x,y,d; }DataType; 由于在非递归算法求解迷宫的过程中用到栈，所以需定义栈的类型，本程序中用的是顺序栈，类型定义如下; typedef struct { DataType data[MAXSIZE]; int top; }SeqStack, *PSeqStack;

数据结构课程设计——迷宫问题课程设计报告

迷宫问题 ——王欣歆20080564 一．需求设计：以一个m*m 的方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口的通道，或得出没有通路的结论。二．概要设计： 存储结构： 采用了数组以及结构体来存储数据，在探索迷宫的过程中用到的栈，属于顺序存储结构。 /*八个方向的数组表示形式*/ int move[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1, 0},{-1, 1}}; /*用结构体表示位置*/ struct position { int x,y; }; position stack[m*m+1]; 基本算法： 走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、东南、南、西南、西、西北、北、东北8个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果8个方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。 每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条通路；若退回到了入口处，则说明不存在通路。 用一个字符类型的二维数组表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（1，1）处，出口点在位置（m,m）处。设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。 二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”，表示迷宫的边界；第1行第1列元素和第m行第m列元素置成“0”，表示迷宫的入口和出口；其余元素值用随机函数产生。 假设当前所在位置是（x,y）。沿某个方向前进一步，它可能到达的位置最多有8个。 如果用二维数组move记录8个方向上行下标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位置坐标可利用move数组确定： x=x+move[i][0] y=y+move[i][1] 从迷宫的入口位置开始，沿图示方向顺序依次进行搜索。在搜索过程中，每前进一步，在所到位置处做标记“ ” （表示这个位置在通路上），并将该位置的坐标压入栈中。 每次后退的时候，先将当前所在位置处的通路标记“ ”改 成死路标记“×”（表示这个位置曾到达过但走不通，以后 不要重复进入），然后将该位置的坐标从栈顶弹出。 678 51 432 x y o

数据结构试验——迷宫问题

数据结构试验——迷宫问题 （一）基本问题 1.问题描述 这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。 简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。 入口 出口 图1 迷宫示意图 迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北(为了清晰，以下称“上下左右”)。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。 2.数据结构设计 以一个m×n的数组mg表示迷宫，每个元素表示一个方块状态，数组元素0和1分别表示迷宫中的通路和障碍。迷宫四周为墙，对应的迷宫数组的边界元素均为1。根据题目中的数据，设置一个数组mg如下 int mg[M+2][N+2]= { {1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,0,0,1,1,1}, {1,0,0,1,0,0,0,1}, {1,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1} };在算法中用到的栈采用顺序存储结构，将栈定义为 Struct { int i; //当前方块的行号 int j; //当前方块的列号 int di; //di是下一个相邻的可走的方位号 }st[MaxSize];// 定义栈

int top=-1 //初始化栈 3设计运算算法 要寻找一条通过迷宫的路径，就必须进行试探性搜索，只要有路可走就前进一步，无路可进，换一个方向进行尝试；当所有方向均不可走时，则沿原路退回一步（称为回溯），重新选择未走过可走的路，如此继续，直至到达出口或返回入口（没有通路）。在探索前进路径时，需要将搜索的踪迹记录下来，以便走不通时，可沿原路返回到前一个点换一个方向再进行新的探索。后退的尝试路径与前进路径正好相反，因此可以借用一个栈来记录前进路径。 方向：每一个可通点有4个可尝试的方向，向不同的方向前进时，目的地的坐标不同。预先把4个方向上的位移存在一个数组中。如把上、右、下、左（即顺时针方向）依次编号为0、1、2、3.其增量数组move[4]如图3所示。 move[4] x y 0 -1 0 1 0 1 2 1 0 3 0 -1 图2数组move[4] 方位示意图如下： 通路：通路上的每一个点有3个属性：一个横坐标属性i、一个列坐标属性j和一个方向属性di，表示其下一点的位置。如果约定尝试的顺序为上、右、下、左（即顺时针方向），则每尝试一个方向不通时，di值增1，当d增至4时，表示此位置一定不是通路上的点，从栈中去除。在找到出口时，栈中保存的就是一条迷宫通路。 （1）下面介绍求解迷宫（xi,yj）到终点（xe,ye）的路径的函数：先将入口进栈（其初始位置设置为—1），在栈不空时循环——取栈顶方块（不退栈）①若该方块为出口，输出所有的方块即为路径，其代码和相应解释如下：

数据结构之迷宫找到路径实验报告

实验报告 课程名：数据结构（C语言版）实验名：迷宫问题I 姓名： 班级： 学号： 撰写时间：2014/10/05

一实验目的与要求 1. 了解栈的应用 2. 利用栈在迷宫中找到一条路 二实验内容 ?一个迷宫如图1所示, 是由若干个方格构成的一个矩形, 其中有唯一的一个入口(用标示), 有唯一的一个出口(用△标示). 图中深色的方格无法到达, 浅色的方格都是可以到达的. 每一次只能从当前方格前进到与当前方格有公共边的方格中(因此前进方向最多有四个). ?本次实验的迷宫问题要求求解一条从入口到出口的路. 图1：迷宫 三实验结果与分析 程序： #include #include /* run this program using the console pauser or add your own getch, system("pause") or input loop */ int Maze(int ox,int oy,int ex,int ey,int rnum,int cnum,int a[rnum][cnum]){ int b[rnum][cnum]; int i,j,Znum=0; for(i=0;i

} } int Sx[Znum+1], Sy[Znum+1], p=0; for(i=0;i0){ if(Sx[p-1]==ex && Sy[p-1]==ey){ brand = 1; break; } else{ int tb = -1; for(i=1;i<4;++i){ int tx = Sx[p-1]+dx[i]; int ty = Sy[p-1]+dy[i]; if(b[tx][ty]==0){ tb = 1; Sx[p]=tx; Sy[p]=ty; b[tx][ty]=2; p=p+1; } } if(tb<0){ b[Sx[p-1]][Sy[p-1]]=-1; p=p-1; } } } if(brand>0){ while(p>0){ printf("(%d,%d), ",Sx[p-1],Sy[p-1]); p=p-1; }

《数据结构课程设计》走迷宫游戏

信息工程学院 课程设计报告 课程名称《数据结构》 课题名称走迷宫游戏 专业 班级 学号 姓名 联系方式 指导教师 2015 年 12 月 27 日

目录 1、数据结构课程设计任务书............................................................... １ 1.1、题目........................................................................... １ 1.2、要求........................................................................... １ 2、总体设计............................................................................. １ 2.1、设计思路及总体组成框架......................................................... １ 2.2、操作流程图..................................................................... ２ 3、详细设计............................................................................. ５ 3.1、程序中所采用的数据结构及存储结构的说明......................................... ５ 3.2、函数功能模块说明............................................................... ５ 3.3、各函数的调用关系 ............................................................................................................................... ７ 4、调试与测试：......................................................................... ７ 4.1、调试方法与步骤：............................................................... ７ 4.2、测试结果的分析与讨论：......................................................... ８ 4.3、测试过程中遇到的主要问题及采取的解决措施：................................... １０ 6、源程序清单......................................................................... １０ 7、数据结构课程设计总结............................................................... １４ 8、参考文献........................................................................... １４

数据结构实验-迷宫问题汇总

实验报告 实验课名称：数据结构实验 实验名称：迷宫问题 班级：20130613 学号：16 姓名：施洋时间：2015-5-18 一、问题描述 这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。 简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。 入口 出口 图1 迷宫示意图 迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。 二、数据结构设计 以一个m×n的数组mg表示迷宫，每个元素表示一个方块状态，数组元素0和1分别表示迷宫中的通路和障碍。迷宫四周为墙，对应的迷宫数组的边界元素均为1。根据题目中的数据，设置一个数组mg如下 int mg[M+2][N+2]= { {1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,0,0,1,1,1}, {1,0,0,1,0,0,0,1}, {1,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1} };在算法中用到的栈采用顺序存储结构，将栈定义为 Struct { int i; //当前方块的行号

int j; //当前方块的列号 int di; //di是下一个相邻的可走的方位号 }st[MaxSize];// 定义栈 int top=-1 //初始化栈 三、算法设计 要寻找一条通过迷宫的路径，就必须进行试探性搜索，只要有路可走就前进一步，无路可进，换一个方向进行尝试；当所有方向均不可走时，则沿原路退回一步（称为回溯），重新选择未走过可走的路，如此继续，直至到达出口或返回入口（没有通路）。在探索前进路径时，需要将搜索的踪迹记录下来，以便走不通时，可沿原路返回到前一个点换一个方向再进行新的探索。后退的尝试路径与前进路径正好相反，因此可以借用一个栈来记录前进路径。 方向：每一个可通点有4个可尝试的方向，向不同的方向前进时，目的地的坐标不同。预先把4个方向上的位移存在一个数组中。如把上、右、下、左（即顺时针方向）依次编号为0、1、2、3.其增量数组move[4]如图3所示。 move[4] x y 0 -1 0 1 0 1 2 1 0 3 0 -1 图2数组move[4] 方位示意图如下： 通路：通路上的每一个点有3个属性：一个横坐标属性i、一个列坐标属性j和一个方向属性di，表示其下一点的位置。如果约定尝试的顺序为上、右、下、左（即顺时针方向），则每尝试一个方向不通时，di值增1，当d增至4时，表示此位置一定不是通路上的点，从栈中去除。在找到出口时，栈中保存的就是一条迷宫通路。

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

专业：计算机科学与技术

2008年10月20 日 数据结构课程设计 一、说明： 1、课程设计题目均选自《数据结构习题集》，请你根据所给页码及题目查阅相应内容，任选其一确定自己设计的题目； 2、题目一般分为基本要求和选做内容，选做内容将作为答优的基本要求； 3、课程设计的成绩分为两部分：系统演示+设计报告。 4、演示部分的检查在12教803室，在课程设计结束后一周。 5、时间：第8周周一无课时间，第8周周六、周日8:00-12:00,1:00-5:00，第9周周一无课时间。地点12教五楼机房。 二、题目： P77: 0.3-海龟作图； P80: 1.3-集合的并、交和差运算（或者1.4-长整数四则运算）； P105: 2.9-迷宫问题； P152: 5.7-表达式类型的实现； P153: 5.8-全国交通咨询模拟。 三、报告要求：完成以上实验内容并写出实验报告，报告应具有以下内容： 1、实验内容 2、概要设计 3、详细设计 4、测试数据及程序运行情况 5、实验过程中出现的问题及解决方法 6、实验体会 四、实验报告要求全部为打印稿，格式统一（见附件实验报告格式），在程序演示检查完成后一并教给老师。 五、课程设计期间有问题，请到12教803室找王永燕,周劲老师。 1、实验内容 【问题描述】 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 【基本要求】 首先实现一个链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。 【实现提示】 计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到则未能到达出口，则所设定的迷宫没有通解。 可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，可以迷宫的四周加一圈障碍。对于迷宫任一位置，均可约定有东、南、西、北四个方向可通。 【选作内容】 （１）编写递归形式的算法，求得迷宫中所有可能的通路；

迷宫问题求解汇总

课程设计报告 课题名称：迷宫问题的求解及演示姓名： 学号： 专业：计算机与信息学院 班级： 指导教师：

数据结构课程设计任务书针对本课程设计，完成以下课程设计任务书： 1.熟悉系统实现工具和上机环境。 2.根据课程设计任务，查阅相关资料。 3.针对所选课题完成以下工作： （1）需求分析 （2）概要设计 （3）详细设计 （4）编写源程序 （5）静态走查程序和上机调试程序 4.书写上述文档和撰写课程设计报告

目录 第一部分课程设计任务书 (1) 第二部分课程设计报告 (2) 第一章课程设计内容和要求 (4) 2.1 问题描述 (4) 2.2 需求分析 (4) 第二章课程设计总体方案及分析 (4) 3.1 概要设计 (7) 3.2 详细设计 (7) 3.3 调试分析 (10) 3.4 测试结果 (10) 第三章设计总结 (13) 4.1课程设计总结 (13) 4.2参考文献………………………………………………… 4.3 附录(源代码) (14)

第二部分课程设计报告 第一章课程设计内容和要求 2.1问题描述： 迷宫以16*16的矩阵存储在数据文件中（迷宫中的障碍物要占到一定比例），编写非递归的程序，求出一条从入口到出口的路径并显示之（结果若能用C的绘图函数显示更好） 2.2需求分析： 1．要求设计程序输出如下： (1) 建立一个大小为m×n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏 幕上显示出来； （2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。 （3）用一种标志（如数字8）在迷宫中标出该条通路； （4）在屏幕上输出迷宫和通路； （5）上述功能可用菜单选择。 2.迷宫的建立： 迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述， 3.迷宫的存储： 迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。

迷宫问题算法与数据结构课程设计

目录 摘要 .................................................................................... 错误！未定义书签。前言 . (1) 正文 (3) 1.采用类C语言定义相关的数据类型 (3) 2.各模块的伪码算法 (3) 3.搜索算法流程图 (6) 4.调试分析 (7) 5.测试结果 (7) 6.源程序（带注释） (10) 总结 (16) 参考文献 (17) 致谢 (18) 附件Ⅰ部分源程序代码 (19)

摘要 在现实生活中，会遇到很多很多关于迷宫这样很复杂、很难解决的问题的问题。如果人工去解决这些问题，会很麻烦，花很长的时间，甚至无法解决。假如用计算机去解决，可以通过手动生成迷宫，也可以通过计算机随机的产生迷宫，最终退出。而且可以很快的求解迷宫，找到从入口到出口的通路，或者当没有通路时，得出没有通路的结论。找出通路之后，会显示出通路路经，而且以图示的方式显示出通路，这样会使人一目了然的看清此迷宫的通路。迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。 关键词：迷宫；通路；二维数组；路径

前言 随着社会经济的发展，信息化程度的不断深入，传统的人工求解迷宫问题已不能满足生活的需要。近几年，随着迷宫问题越来越复杂、科技也越来越发达，人们逐渐的开始用计算机求解迷宫问题。迷宫问题很复杂，但是人们又不得不去研究这个问题，因为人们的生活中需要它，离不开它。在迷宫路径的搜索过程中，首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。

数据结构栈求解迷宫问题C语言版

数据结构栈求解迷宫问题(C语言版) /* 数据结构C语言版栈求解迷宫问题 P50-52 利用栈求解迷宫问题 编译环境：Dev-C++ 4.9.9.2 日期：2011年2月12日 */ /***************头文件**********************/ // 迷宫坐标位置类型 typedef struct { int x; // 行值 int y; // 列值 }PosType; #define MAXLENGTH 25 // 设迷宫的最大行列为25 typedef int MazeType[MAXLENGTH][MAXLENGTH]; // 迷宫数组[行][列] typedef struct // 栈的元素类型 { int ord; // 通道块在路径上的＂序号＂ PosType seat; // 通道块在迷宫中的＂坐标位置＂ int di; // 从此通道块走向下一通道块的＂方向＂(0～3表示东～北) }SElemType; // 全局变量 MazeType m; // 迷宫数组 int curstep=1; // 当前足迹,初值为1 #define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 // 栈的顺序存储表示P46

typedef struct SqStack { SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }SqStack; // 顺序栈 /****************实现************************/ // 构造一个空栈S int InitStack(SqStack *S) { // 为栈底分配一个指定大小的存储空间 (*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if( !(*S).base ) exit(0); (*S).top = (*S).base; // 栈底与栈顶相同表示一个空栈 (*S).stacksize = STACK_INIT_SIZE; return 1; } // 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。int StackEmpty(SqStack S) { if(S.top == S.base) return 1; else return 0; } // 插入元素e为新的栈顶元素。 int Push(SqStack *S, SElemType e) { if((*S).top - (*S).base >= (*S).stacksize) // 栈满，追加存储空间{ (*S).base = (SElemType *)realloc((*S).base , ((*S).stacksize + STACKINCREMENT) * sizeof(SElemType)); if( !(*S).base ) exit(0);

数据结构课程设计之迷宫游戏

##大学 数据结构课程设计报告题目：走迷宫游戏 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 2011-6-21 至 2011-6-30 指导教师:

2010—2011年度第 2 学期 一、需求分析 1 问题描述 走迷宫游戏 程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。 2 基本功能 1) 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动； 2) 迷宫的墙足够结实，老鼠不能穿墙而过； 3) 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败； 4) 添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙； 5) 找出走出迷宫的所有路径，以及最短路径。 利用序列化功能实现迷宫地图文件的存盘和读出等功能 3 输入输出 输入为字符型： 1， 2， 3 分别实现功能选择 w(上),s(下),a(左),d(右)控制迷宫的走向 y表示确定 n表示否定

二、 概要设计 1. 设计思路： 实现走迷宫 game （） 对迷宫地图进行修改change （） 对修改的地图数组进行保存edit （） 对修改的地图进行保存 savemap （） 实现自动搜路 Mathpath （）对搜寻的路径进行输 出 print （） 2.数据结构设计： 采用的是栈来存储数据，进栈实际是在栈中插入三元组，出栈则只数组的个数进行操作 抽象数据类型线性表的定义如下： ADT SqStack{ 数据对象：D={a i | a i ∈SElemType,i=1,2,3……，n,n ≥0} 数据关系：R1={| a i-1,a i ∈D,i=1,2,3,……，n} 基本操作： SqStack *InitStack() 操作结果：创建一个空栈 void Push(SqStack *S,SElemType data) 初始条件：栈S 已存在 操作结果：插入一个元素，并且使数据个数加一(top++) void Pop(SqStack *S) 初始条件：栈S 已存在。 操作结果：栈中元素个数减一（top--） } 2. 软件结构设计： game （）模块 函数原型： void game(int map1[h][w])//游戏函数 { #define killtime 15 clock_t start, finish; double duration; int x=1,y=1,m=0,n=0,M,N,MAP[100][100];//x->colom y->row char cCtrl='\0';