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

1、课程设计（论文）题目名称迷宫求解课程名称学生姓名学号系、专 业 信息工程系、电气信息类（信息类）指导教师申寿云2010年1月3日摘要设计一个简单迷宫程序，从入口出发找到一条通路到达出口。编制程序给 出一条通过迷宫的路径或报告一个“无法通过”的信息。首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递 归程序。用“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若 能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口 位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设 定的迷宫没有通路。可以用二维数组存储迷宫数据，通常设定入口点的下标为(1 ,

2、 1),出口点的下标为(n , n)。为处理方便起见，可在迷宫的四周加一 障碍。对于迷宫任一位置，均可约定有东、南、西、北四个方向可通。 关键词：迷宫；栈；链表；二维数组目录1 问题描述 12 需求分析 13 概要设计 131 抽象数据类型定义 132 模块划分 24 详细设计 241 数据类型的定义 242 主要模块的算法描述 35 测试分析 66 课程设计总结 7参考文献 7附录（源程序清单） 91 问题描述迷宫是一个 M 行 N 列的 0-1 矩阵，其中 0 表示无障碍， 1 表示有障碍。 设入口为 （1 ，1）出口为 （M，N） 每次移动只能从一个无障碍的单元移到其周围8个方向上任一无

3、障碍的单元，编制程序给出一条通过迷宫的路径或报告一个 “无法通过”的信息。2 需求分析（1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i, j, d ）的形式输出，其中：（i, j）指示 迷宫中的一个坐标， d 表示走到下一坐标的方向。否则报告一个无法通过的信 息。（ 2）建立 InitStack 函数，用于构造一个空栈。（ 3 ）建立 DestroyStack 函数，用于销毁栈。（ 4）建立 Pop 函数，用于删除栈顶元素，返回栈顶元素的值。（ 5）建立 Push 函数，用于插入新的栈顶元素。（ 6 ）建立 NextPos 函数，用于定位下一

4、个位置。3 概要设计3 1 抽象数据类型定义（ 1 ）栈的抽象数据类型定义 InitStack（ LStack *S ） 操作结果：构造一个空栈 S。DestroyStack（ LStack *S ） 操作结果：栈 S 被销毁。Pop（ LStack *S ， ElemType *e ）操作结果：删除S的栈顶元素。用e返回栈顶元素的值。若栈为空则返回Push( LStack *S ， ElemType e )操作结果：在栈顶之上插入元素 e 为新的栈顶元素。若栈 S 为空栈，则返 回 0 。（2）迷宫的抽象数据类型定义NextPos（unsigned *x ，unsigned *y ， sho

5、rt 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 maze1010 ；（2）栈类型typedef struct Node ElemType data ；struct Node* next Node,

6、 *L in kList;typedef struct Lin kList top ; un sig ned len gth 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 0结束图4.1函数寻找下一个位置流程图4.2函数销毁栈流程图此函数的功能是销毁栈，首先建立单链表q，判断top

7、指针是否为空，若为空则释放s的空间，否则出栈，直到top指针为空，释放s的空间。见图 4.2LinkList q ；出栈;释放栈s的空间;图4.2函数销毁栈流程图4.3函数出栈流程图此函数的功能是出栈。 首先建立单链表q ,如果栈s为空则返回0,若栈s 不为空，则出栈，修改指针。返回1。见图4.3 oLinkList q ;Retqrn 0;4 1/ 21出栈;Retur n 1 ;图4.3函数出栈流程图4.4函数入栈流程图此函数的功能是入栈。首先在链表中生成结点p，判断p是否为空。若为空则返回0，若非空，则入栈，修改指针，返回0。见图4.4 o生成结点p;Retur n 0;入栈;Retur

8、 n 1 ;图4.4函数入栈流程图4.5主函数流程图主函数实现了求解迷宫，首先建立栈s和t，输出迷宫图形，然后探索路径，实现迷宫求解，最后输出出迷宫顺序。如果有完整路径则输出完整路径， 如果没有完整路径则输出无法通过信息。见图4.5 o图4.5主函数流程图5测试分析(1 )有一条完整路径通过迷宫的测试数据与结果。见图5.1图5.1有一条完整路径通过迷宫的测试数据与结果从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则 沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。输出通 路的坐标，即出迷宫的顺序。(2) 没有路径能通过迷宫的测试数据与结果。见图5.2 o5.2没有

9、路径能通过迷宫的测试数据与结果从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则 沿着原路退回，换一个方向继续探索，直至前面没有路径。输出此时无法通过, 没有能够通过迷宫的路径的信息！6课程设计总结通过这次课程设计使我充分的理解了用栈实现迷宫问题的基本原理，知道 了栈存储结构的定义和算法描述，同时也学会了编写简单的迷宫问题的程序。 虽然此次的程序不是很完备，但是总体还是一个比较能体现数据结构知识点能 力的程序了，当然只是相对于我这个初学者来说。在刚幵始编程的时候，错误 百出，不知道怎么样改正，但是通过自己的仔细的分析和老师的细心的指导， 在认真分析了原程序后，终于认识并理解了自己

10、错误的地方， 使自己加以改正, 汲取教训。为以后知识水平的提高，做了最好的准备。在此我非常要感谢的是我们的指导老师申寿云老师，同时也要感谢我们的 成娅辉老师平时上课的教导，和编程时细心认真的辅导，教给我许多知识。这 次课程设计能够顺利的完成，当然有我个人的努力，但同时更离不幵指导老师 的答疑解惑。参考文献1 黄同成，黄俊民，董建寅数据结构 M 北京：中国电力出版社， 20082 董建寅，黄俊民，黄同成数据结构实验指导与题解 M 北京：中国电 力出版社， 20083 严蔚敏，吴伟民.数据结构（C语言版）M.北京：清华大学出版社，20024 刘振鹏，张晓莉，郝杰数据结构 M 北京：中国铁道出版社，

11、 2003附录（源程序清单）#include <stdio.h> #include <stdlib.h> typedef struct unsigned ord ，x，y； /* 通道块在路径上的序号和在迷宫中的坐标位置*/short di ； /* 从此通道块走向下一通道块的“方向” */ ElemType ；typedef struct Node /* 定义单链表 */ElemType data ；struct Node* next Node ， *LinkList ； typedef struct LinkList top ； unsigned length/*

12、定义链栈结构 */* 栈顶指针 */* 栈中元素个数 */ LStack ；void DestroyStack( LStack *S ) /*销毁栈 */ LinkList q ；while ( S->top ) q = S->top ；S->top = S->top->next ； /* 修改栈顶指针 */ free( q ) ； /* 释放被删除的结点空间 */S->length = 0 ；void InitStack( LStack *S ) /*构造空栈 */S->top = NULL ； /* 栈顶指针初值为空 */S->length

13、= 0 ； /* 空栈中元素个数为 0 */int Pop( LStack *S ， ElemType *e ) /* 若栈不空，则删除 S 的栈顶元素，用 e 返回栈顶元素的值。 */ LinkList q ；if ( ！S->top ) return 0 ；*e = S->top->data ； /* 返回栈顶元素 */q = S->top ；S->top = S->top->next ； /* 修改栈顶指针 */-S->length ； /* 栈的长度减 1 */free( q ) ； /* 释放被删除的结点空间 */ return 1 ；

14、int Push( LStack *S ， ElemType e ) /* 在栈顶之上插入元素 e 为新的栈顶元素 */LinkList p = malloc( sizeof *p )； /* 建新的结点 */if (！p ) return 0 ； /* 存储分配失败 */* 链接到原来的栈顶 */* 移动栈顶指针 */* 栈的长度增 1 */， unsigned * ， short) ； /* 定位下一个位置 */p->data = e ； p->next = S->top S->top = p ； +S->length ； return 1 ；void Nex

15、tPos(unsigned * int main( void )LStack S ，T；unsigned x ，y， curstep ，i=0 ；/* 迷宫坐标，探索步数 */ElemType e ；char maze1010 = '#''#' ，'#' ，'#''#' ， '#' ， '#' ， '#''#'，'#'，'#'，'#'，'#' ，'#'' '

16、，'#' ，'，'#'，' ' ，'#' ，'#'， '#' ， '#'，'#' ，'#''#' ，'#' ，'#'，'#' ，'#'，'#'，'#' ，'#' ，' '，'#'，'#'，'#' ，'#''#' ， '

17、;#' ， '#' ， '#' ， '#''#'，' ' ， '#' ，'#' ，'#' ，'#' ，'#' ， '#' ，'#' ，'#' ，'#' ，'#' ，'#' ，'#' ，' ' ， '#' ， ；InitStack(&S) ；InitStack(&T) ；p

18、rintf(" 迷宫图形， # 号代表墙壁，空格代表通路： n") ；for ( x = 0 ； x < 10 ； x+) for ( y = 0 ； y < 10 ； y+ ) printf("%c" ， mazexy) ；printf("n") ；x = 1 ； /*迷宫起点 */y = 0 ；curstep = 1 ； /* 探索第一步 */do /* 进入迷宫 */if ( mazeyx = ' ' ) /* 如果当前位置可以通过 */ mazeyx = '1' ； /* 留下足迹

19、*/ e.x = x ； e.y = y ； e.di = 1 ； e.ord = curstep ；if ( ！Push(&S ，e) ) /* 加入路径，即压栈 */fprintf( stderr ，"内存不足。 n" ) ；if ( x = 8 && y = 9 ) /*到达终点 */break ；NextPos(&x, &y, 1) ； /* 下一位置是当前位置的东邻 */ curstep+ ；else /* 如果当前位置不能通过 */if (S.length ！=0) Pop(&S ，&e) ； while

20、(e.di = 4 && S.length!=0) mazee.ye.x = '0' ； /* 留下不能通过足迹 */ Pop(&S, &e) ； /* 退回一步，即出栈 */if (e.di < 4) e.di+ ；if ( ！Push(&S ，e) ) /* 加入路径，即压栈 */ fprintf( stderr ，"内存不足。 n" ) ；x = e.x ； /* 重置坐标 */y = e.y ； NextPos(&x ， &y ， e.di) ； /* 寻找下一位置 */ while (S

21、.length ！ =0) ；printf(" 走出迷宫路线， 1 代表走过的路， 0 代表试探过的路径 n") ； for ( x = 0 ； x < 10 ； x+ ) for ( y = 0 ； y < 10 ； y+ ) printf("%c" ， mazexy) ；n") ；， T.top->data.y ，定位下一个位置 */break ；if(mazexy='1')i+ ；printf("n") ；for(x=0 ； x<i ；x+) Pop(&S ， &

22、e) ；Push(&T ， e) ；printf("出迷宫顺序，(X坐标，Y坐标，前进方向)：while(T.length ！ =0) printf("(%d ， %d ， %d)t"， T.top->data.xT.top->data.di) ；Pop(&T ， &e) ；DestroyStack(&S) ；getchar() ；return 0 ；void NextPos(unsigned *x ， unsigned *y ， short di) /*switch (di) case 1 ：+(*x) ； break

23、 ；case 2 ：+(*y) ； break ；case 3 ：-(*x) ； break ；case 4 ：-(*y) ； break ；default ：邵阳学院课程设计（论文）任务书年级专业2008级电气信息类（信息 类）4班学生 姓名学 号题目 名称求解迷宫问题设计 时间2009.12.21-2010.1.3课程名称数据结构课程 设计课程编号131301302设计地点新实验楼四楼机房一、课程设计（论文）目的学生在教师指导下运用所学课程的知识来研究、解决 些具有 定综合性问题的专业课题。通过课程设计（论文），提高学生综合运用所学知识来解决 实际问题、使用文献资料、与进行科学实验或技术设计的初步能力，为毕业 设计（论文）打基础。二、已知技术参数和条件三、任务和要求迷宫是一个M行N列的0-1矩阵，其中0表示无障碍，1表示有障碍 设入口为（1，1）出口为（M , N ）每次移动只能从一个无障碍的单元移到 其周围8个方向上任一无障碍的单元，编制程序给出一条通过迷宫的路径或 报告一个“无法通过”的信息。注：1 .