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

课程设计(论文)题 目 名 称 迷宫求解 课 程 名 称 数据结构课程设计 学 生 姓 名 学 号 系 、专 业 信息工程系、电气信息类（信息类） 指 导 教 师 申寿云 2010年 1 月 3 日摘 要设计一个简单迷宫程序，从入口出发找到一条通路到达出口。编制程序给出一条通过迷宫的路径或报告一个“无法通过”的信息。首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。用“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以用二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n，n）。为处理方便起见，可在迷宫的四周加一障碍。对于迷宫任一位置，均可约定有东、南、西、北四个方向可通。关键词：迷宫；栈；链表；二维数组目 录1 问题描述12 需求分析13 概要设计131抽象数据类型定义132模块划分24 详细设计241数据类型的定义242主要模块的算法描述35 测试分析66 课程设计总结7参考文献8附录（源程序清单）91 问题描述迷宫是一个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 概要设计31抽象数据类型定义（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)操作结果：找到下一个位置。32模块划分本程序包括三个模块：（1）主程序模块void main()初始化；构造迷宫；迷宫求解；迷宫输出；（2）栈模块实现栈的抽象数据类型（3）迷宫模块实现迷宫的抽象数据类型4 详细设计41数据类型的定义（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, *LinkList；typedef struct LinkList top；unsigned length； LStack；LinkList q；LStack S,T；ElemType e；42主要模块的算法描述4.1函数寻找下一个位置流程图此函数的功能是寻找下一个位置。首先判断di的值，如果di=1，指针x+，退出。如果di=2，指针y+，退出。如果di=3，指针x-，退出。如果di=4，指针y-，退出。如果di为其它值，则直接退出。见图4.1。YNYNYYNNdi=1di=2di=3di=4Break；指针x自增；Break；指针y自增；Break；指针x自减；Break；指针y自减；Break；开始结束图4.1 函数寻找下一个位置流程图4.2 函数销毁栈流程图此函数的功能是销毁栈，首先建立单链表q，判断top指针是否为空，若为空则释放s的空间，否则出栈，直到top指针为空，释放s的空间。见图4.2。YNLinkList q；判断栈的top释放栈s的空间；出栈；开 始结 束图4.2 函数销毁栈流程图4.3 函数出栈流程图此函数的功能是出栈。首先建立单链表q，如果栈s为空则返回0，若栈s不为空，则出栈，修改指针。返回1。见图4.3。YNLinkList q；栈s为空出栈；Return 1；Return 0；开 始结 束图4.3 函数出栈流程图4.4 函数入栈流程图此函数的功能是入栈。首先在链表中生成结点p，判断p是否为空。若为空则返回0，若非空，则入栈，修改指针，返回0。见图4.4。YN生成结点p；!p入栈；Return 1；Return 0；开 始结 束图4.4 函数入栈流程图4.5 主函数流程图主函数实现了求解迷宫，首先建立栈s和t，输出迷宫图形，然后探索路径，实现迷宫求解，最后输出出迷宫顺序。如果有完整路径则输出完整路径，如果没有完整路径则输出无法通过信息。见图4.5。 建立栈S和T； 输出迷宫图形； 迷宫求解； 输出出迷宫顺序；结 束 开 始图4.5 主函数流程图5 测试分析（1）有一条完整路径通过迷宫的测试数据及结果。见图5.1。图5.1 有一条完整路径通过迷宫的测试数据及结果从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。输出通路的坐标，即出迷宫的顺序。（2）没有路径能通过迷宫的测试数据及结果。见图5.2。图5.2 没有路径能通过迷宫的测试数据及结果从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至前面没有路径。输出此时无法通过，没有能够通过迷宫的路径的信息！6 课程设计总结通过这次课程设计使我充分的理解了用栈实现迷宫问题的基本原理，知道了栈存储结构的定义和算法描述，同时也学会了编写简单的迷宫问题的程序。虽然此次的程序不是很完备，但是总体还是一个比较能体现数据结构知识点能力的程序了，当然只是相对于我这个初学者来说。在刚开始编程的时候，错误百出，不知道怎么样改正，但是通过自己的仔细的分析和老师的细心的指导，在认真分析了原程序后，终于认识并理解了自己错误的地方，使自己加以改正，汲取教训。为以后知识水平的提高，做了最好的准备。在此我非常要感谢的是我们的指导老师申寿云老师，同时也要感谢我们的成娅辉老师平时上课的教导，和编程时细心认真的辅导，教给我许多知识。这次课程设计能够顺利的完成，当然有我个人的努力，但同时更离不开指导老师的答疑解惑。参考文献1 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20082 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：中国电力出版社，20083 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，20024 刘振鹏，张晓莉，郝杰数据结构M北京：中国铁道出版社，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； /* 栈中元素个数 */ 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 = 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； int Push( LStack *S，ElemType e ) /* 在栈顶之上插入元素 e 为新的栈顶元素 */LinkList p = malloc( sizeof *p )； /* 建新的结点 */if (！p ) return 0； /* 存储分配失败 */p->data = e；p->next = S->top； /* 链接到原来的栈顶 */S->top = p； /* 移动栈顶指针 */+S->length； /* 栈的长度增1 */return 1； void NextPos(unsigned *，unsigned *，short)； /* 定位下一个位置 */int main( void )LStack S，T；unsigned x，y，curstep，i=0；/* 迷宫坐标，探索步数 */ElemType e；char maze1010 = '#'，' '，'#'，'#'，'#'，'#'，'#'，'#'，'#'，'#'，'#'，' '，' '，'#'，' '，' '，' '，'#'，' '，'#'，'#'，' '，' '，'#'，' '，' '，' '，'#'，' '，'#'，'#'，' '，' '，' '，' '，'#'，'#'，' '，' '，'#'，'#'，' '，'#'，'#'，'#'，' '，' '，' '，' '，'#'，'#'，' '，' '，' '，'#'，' '，' '，' '，' '，'#'，'#'，' '，'#'，' '，' '，' '，'#'，' '，' '，'#'，'#'，' '，'#'，'#'，'#'，'#'，'#'，'#'，' '，'#'，'#'，'#'，' '，' '，' '，' '，' '，' '，' '，'#'，'#'，'#'，'#'，'#'，'#'，'#'，'#'，'#'，' '，'#'，；InitStack(&S)；InitStack(&T)；printf("迷宫图形，#号代表墙壁，空格代表通路：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'；/* 留下足迹 */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 (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.length！=0)；printf("走出迷宫路线，1代表走过的路，0代表试探过的路径n")；for ( x = 0；x < 10；x+ ) for ( y = 0；y < 10；y+ ) printf("%c"，mazexy)；if(mazexy='1')i+；printf("n")；for(x=0；x<i；x+)Pop(&S，&e)；Push(&T，e)；printf("出迷宫顺序，（X坐标，Y坐标，前进方向）：n")；while(T.length！=0)printf("(%d，%d，%d)t"，T.top->data.x，T.top->data.y，T.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；case 2：+(*y)；break；case 3：-(*x)；break；case 4：-(*y)；break；default：break；邵阳学院课程设计（论文）任务书年级专业2008级电气信息类（信息类）4班学生姓名学 号题目名称求解迷宫问题设计时间2009.12.21-2010.1.3课程名称数据结构课程设计课程编号131301302设计地点新实验楼四楼机房一、 课程设计（论文）目的学生在教师指导下运用所学课程的知识来研究、解决一些具有一定综合性问题的专业课题。通过课程设计（论文），提高学生综合运用所学知识来解决实际问题、使用文献资料、及进行科学实验或技术设计的初步能力，为毕业设计（论文）打基础。二、 已知技术参数和条件三、 任务和要求迷宫是一个M行N列的0-1矩阵，其中0表示无障碍，1表示有障碍。设入口为（1，1）出口为（M，N）每次移动只能从一个无障碍的单元移到其周围8个方向上任一无障碍的单元，编制程序给出一条通过迷宫的路径或报告一个“无法通过”的信息。注：1此表由指导教师填写，经系、教研室审批，指导教师、学生签字后生效；2此表1式3份，学生、指导教师、教研室各1份。四、参考资料和现有基础条件（包括实验室、主要仪器设备等）参考资料：数据结构M、数据结构实验指导与题解M、数据结构（C语言版）M、数据结构M。现有基础条件：本系有足够的计算机供学生上机用，每人一台计算机。五、进度安排2009.12.10-2009.12.13：课程设计选题2009.12.142009.12.16：下发任务书2009.12.172009.12.20：搜集相关参考资料2009.12.212009.12.27：编程2009.12.282010.1.3：撰写课程设计报告六、教研室审批意见教研室主任（签字）： 年 月 日七|、主管教学主任意见 主管主任（签字）： 年 月 日八、备注指导教师（签字）： 学生（签字）：邵阳学院课程设计（论文）评阅表学生姓名 学 号 系 信息工程系 专业班级2008级电气信息类（信息类）4班 题目名称 求解迷宫问题 课程名称 数据结构课程设计 一、学生自我总结回顾起此次课程设计，至今我仍感慨颇多！自从拿到题目到完成整个编程，从理论到实践，在整整半个月的日子里，不仅可以巩固了以前所学过的知识，也学到了很多在书本上所没有学到过的知识。通过这次课程设计使我们懂得了理论与实际相结合是很重要的，只有把所学的理论知识与实践相结合起来才能提高自己的实际动手能力和独立思考的能力。在设计的过程中可以说得是困难重重，但毕竟是第一次做数据结构的课程设计，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处。但通过这次课程设计之后，我把前面所学过的知识又重新温故了一遍。 学生签名： 2010年 1 月 3 日二、指导教师评定评分项目资料查阅编写规范基本技能设计能力科学素养工作量综合成绩权 重101525301010单项成绩指导教师评语： 指导教师（签名）： 年 月 日注：1、本表是学生课程设计（论文）成绩评定的依据，装订在设计说明书（或论文）的“任务书”页后面；2、表中的“评分项目”及“权重”根据各系的考核细则和评分标准确定。