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

课程设计(论文)

题 目 名 称 迷宫求解 课 程 名 称 数据结构课程设计 学 生 姓 名 学 号 系 、专 业 信息工程系、电气信息类（信息类） 指 导 教 师 申寿云

2010年 1 月 3 日

摘 要

设计一个简单迷宫程序，从入口出发找到一条通路到达出口。编制程序给出一条通过迷宫的路径或报告一个“无法通过”的信息。

首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。用“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以用二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n，

n）。为处理方便起见，可在迷宫的四周加一障碍。对于迷宫任一位置，均可约定有

东、南、西、北四个方向可通。

关键词：迷宫；栈；链表；二维数组

目 录

1 问题描述 ................................................................................................ 1 2 需求分析 ................................................................................................ 1 3 概要设计 ................................................................................................ 1 3．1抽象数据类型定义 ..................................................................... 1 3．2模块划分 ..................................................................................... 2 4 详细设计 ................................................................................................ 2 4．1数据类型的定义 ......................................................................... 2 4．2主要模块的算法描述 ................................................................. 3 5 测试分析 ................................................................................................ 6 6 课程设计总结 ........................................................................................ 7 参考文献 .................................................................................................... 7 附录（源程序清单） ................................................................................ 8

1 问题描述

迷宫是一个M行N列的0-1矩阵，其中0表示无障碍，1表示有障碍。设入口为(1，1)出口为(M，N)每次移动只能从一个无障碍的单元移到其周围8个方向上任一无障碍的单元，编制程序给出一条通过迷宫的路径或报告一个“无法通过”的信息。

2 需求分析

（1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程

序。求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。否则报告一个无法通过的信息。

（2）建立InitStack函数，用于构造一个空栈。 （3）建立DestroyStack函数，用于销毁栈。

（4）建立Pop函数，用于删除栈顶元素，返回栈顶元素的值。 （5）建立Push函数，用于插入新的栈顶元素。 （6）建立NextPos函数，用于定位下一个位置。

3 概要设计

3．1抽象数据类型定义

（1）栈的抽象数据类型定义

InitStack( LStack *S )

操作结果：构造一个空栈S。

DestroyStack( LStack *S )

操作结果：栈S被销毁。

Pop( LStack *S，ElemType *e )

操作结果：删除S的栈顶元素。用e返回栈顶元素的值。若栈为空则返回0。

Push( LStack *S，ElemType e )

操作结果：在栈顶之上插入元素e为新的栈顶元素。若栈S为空栈，则返回0。 （2）迷宫的抽象数据类型定义

NextPos(unsigned *x，unsigned *y，short di)

操作结果：找到下一个位置。

3．2模块划分

本程序包括三个模块： （1）主程序模块

void main() {

初始化； 构造迷宫； 迷宫求解； 迷宫输出；

}

（2）栈模块——实现栈的抽象数据类型 （3）迷宫模块——实现迷宫的抽象数据类型

4 详细设计

4．1数据类型的定义

（1）迷宫类型 typedef struct { unsigned ord, x, y； short di； } ElemType；

unsigned x, y, curstep,i=0； char maze[10][10]； （2）栈类型

typedef struct Node { ElemType data； struct Node* next； } Node, *LinkList； typedef struct { LinkList top； unsigned length；

} LStack； LinkList q； LStack S,T； ElemType e； 4．2主要模块的算法描述 4.1函数寻找下一个位置流程图

此函数的功能是寻找下一个位置。首先判断di的值，如果di=1，指针x++，退出。如果di=2，指针y++，退出。如果di=3，指针x--，退出。如果di=4，指针

y--，退出。如果di为其它值，则直接退出。见图4.1。

图4.1 函数寻找下一个位置流程图

此函数的功能是销毁栈，首先建立单链表q，判断top指针是否为空，若为空则释放s的空间，否则出栈，直到top指针为空，释放s的空间。见图4.2。

图4.2 函数销毁栈流程图

4.3 函数出栈流程图

此函数的功能是出栈。首先建立单链表q，如果栈s为空则返回0，若栈s不为空，则出栈，修改指针。返回1。见图4.3。

图4.3 函数出栈流程图

此函数的功能 …… 此处隐藏：5046字，全部文档内容请下载后查看。喜欢就下载吧 ……