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

课程设计(论文)

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

2010年1月3日
摘要
设计一个简单迷宫程序，从入口出发找到一条通路到达出口。编制程序给出一条通过迷宫的路径或报告一个“无法通过”的信息。
首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。用“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以用二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n，n）。为处理方便起见，可在迷宫的四周加一障碍。对于迷宫任一位置，均可约定有东、南、西、北四个方向可通。
关键词：迷宫；栈；链表；二维数组
目录
TOC\o"1-2"\h\z\uHYPERLINK\l"_Toc248074613"1问题描述 PAGEREF_Toc248074613\h1
HYPERLINK\l"_Toc248074614"2需求分析 PAGEREF_Toc248074614\h1
HYPERLINK\l"_Toc248074615"3概要设计 PAGEREF_Toc248074615\h1
HYPERLINK\l"_Toc248074616"3．1抽象数据类型定义 PAGEREF_Toc248074616\h1
HYPERLINK\l"_Toc248074617"3．2模块划分 PAGEREF_Toc248074617\h2
HYPERLINK\l"_Toc248074618"4详细设计 2
HYPERLINK\l"_Toc248074619"4．1数据类型的定义 2
HYPERLINK\l"_Toc248074620"4．2主要模块的算法描述 PAGEREF_Toc248074620\h3
HYPERLINK\l"_Toc248074621"5测试分析 6
HYPERLINK\l"_Toc248074622"6课程设计总结 7
HYPERLINK\l"_Toc248074623"参考文献 PAGEREF_Toc248074623\h8
HYPERLINK\l"_Toc248074624"附录（源程序清单） PAGEREF_Toc248074624\h9

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，ElemTypee)
操作结果：在栈顶之上插入元素e为新的栈顶元素。若栈S为空栈，则返回0。
（2）迷宫的抽象数据类型定义
NextPos(unsigned*x，unsigned*y，shortdi)
操作结果：找到下一个位置。
3．2模块划分
本程序包括三个模块：
（1）主程序模块
voidmain()
{
初始化；
构造迷宫；
迷宫求解；
迷宫输出；
}
（2）栈模块——实现栈的抽象数据类型
（3）迷宫模块——实现迷宫的抽象数据类型
4详细设计
4．1数据类型的定义
（1）迷宫类型
typedefstruct{
unsignedord,x,y；
shortdi；
}ElemType；
unsignedx,y,curstep,i=0；
charmaze[10][10]；
（2）栈类型
typedefstr