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

数据结构课程设计

一、

需求分析1、对于给定的一个迷宫，给出一个出口和入口，找一条从入口到出有这样通路的信息。2、可以用一个

的长方阵表示迷宫，0

和

1

分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。3、编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，

表示走到下一坐标的方向。对应的矩阵表示，所以程序的输入包括了矩阵的行数、列数、迷宫内墙的个数、迷宫内墙的坐标、所求的通路的入口坐标、出口坐标。

0

和

1

分别代表通道和障碍物，所以只需要随机生成0

和

1

然后再给最外围都赋值为1，就形成了新的迷宫。二、详细设计1、计算机解迷宫通常用的是“穷举求解“方法，即从人口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。点的下标为(n，n)。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。2、如果在某个位置上四个方向都走不通的话，就退回到前一个位没有走通，那就说明这个迷宫根本不通。重复走第二次"，它包括"曾经走过而没有走通的路"。显然为了保证在任何位置上都能沿原路退回，需要用一个"后进先出"的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后，栈中保存的正是一条从入口到出口的路径。，

，道块。北）上相邻的方块。假设以栈

S

“ 。“ 。5、找通路的程序的关键部分可以表示如下：do{若当前位置可通，则{将当前位置插入栈顶； //

纳入路径若该位置是出口位置，则算法结束；//

此时栈中存放的是一条从入口位置到出口位置的路径否则切换当前位置的东邻方块为新的当前位置；}否则{若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为:

沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则{

删去栈顶位置； //

从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；}}}

while

6、程序中用的数据结构解析：①

可以出栈，退回到前一个位置再继续探索通路，栈的定义如下：struct

SqStack{SElemType

*base;

//

在栈构造之前和销毁之后，base

的值为

NULLSElemType

*top;

//

栈顶指针int

stacksize;

//

当前已分配的存储空间，以元素为单位};

//

顺序栈②

栈中元素的类型结构程序中先定义了一个表示坐标的类型结构：struct

PosType

//

迷宫坐标位置类型{int

x;

//

行值int

y;

//

列值};栈中元素的类型结构如下：struct

SElemType

//

栈的元素类型{int

ord;

//

通道块在路径上的＂序号＂PosType

seat;

//

通道块在迷宫中的＂坐标位置＂int

di;

//

从此通道块走向下一通道块的＂方向＂(0～3

表示东～北)};7、主函数的流程图

三、

调试分析1、对于程序的设计由简单到复杂，先设计一个整体的轮廓然后再慢慢的增加程序的功能，这样能够有效的减少错误，功能慢慢的增加，候比较有目的性，提高写程序的效率。2、对于程序中的错误，如果遇到说变量没有定义或者数据结构没定构体之后。

printf

和

scanf

到你想要的结果。4、写程序时一定要瞻前顾后，前后一致，包括名称、数据类型等等。四、用户手册在使用程序时严格按照程序给出的提示一步一步来，下面给出程序正常执行的步骤：行列数多两行两列。的数目。”3、程序提示“请依次输入迷宫内墙每个单元的行数，列数：，此”时要输入迷宫中所有墙的坐标，我们用数组中的一个元素来表示墙。4、在输入了迷宫所有内墙的坐标后，程序会显示出迷宫的结构，”然后程序会提示“请输入起点的行数，列数：，此时需要输入所求通”路的起点坐标。”5、程序提示“请输入终点的行数，列数：，此时需要输入所求通”路的终点的坐标。6、终点坐标输入完毕之后，程序会显示出两种运行的结果，一种字表示出了通路在迷宫中是如何走的，此时迷宫中的-1

表示找通路时走过的单元但是通路不通。注意：再输入内墙单元的坐标是一定要细心，不要错输，也不要漏输。否则程序会出错。五、测试结果迷宫的测试数据如下：左上角(1，1)为入口，右下角(9，8)为出口。

程序的测试结果为： 程序的开始界面六、附录（附有完整的源程序）源程序如下：

TRUE

FALSE

ERROR

STACKINCREMENT

STACK_INIT_SIZE

//

{

x;

y;};

{

//

//

//};

{

};

S;

MAXLENGTH

//

//

//

{

OK;}

{

//

OK;}

{

ERROR;

FALSE;}

{{

*)

*

}

OK;}

{ //{

OK;}{

ERROR;}}

{}

{//

}

{}

//{

i,j;{{");");}}}

{

i,j;{{{");}

{");}

{");}}}}

{

do{

{

//

e

//

}

{{

{}

{}}}

FALSE;}

{

i,j;

}

{

i,j;

{}{}{{}}:");{}printf("**************************************************************************\n");printf("**************************************************************************\n");}

{{

}}

{

T;{{}{}}}

{

x,y;

i,j;{printf("*****************1.*****************\n");printf("*****************2.*****************