数据结构c语言课程设计报告之迷宫

《数据结构c语言课程设计报告之迷宫》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、C语言与数据结构课程设计报告       学号** 姓名**课程设计题目迷宫求解  2012年5月目录1需求分析1.1功能与数据需求1.1.1题目要求的功能1.1.2扩展功能1.2界面需求1.3开发环境与运行需求2概要设计2.1主要数据结构2.2程序总体结构2.3各模块函数说明3详细设计3.1算法分析与设计3.2主要程序段设计4测试5使用说明5.1应用程序功能的详细说明5.2应用程序运行环境要求5.5输入数据类型、格式和内容限制6总结提高6.1课程设计总结6.2开发中遇到的问题和解决方法6.3对自己完成课设完成情况的评价6.4《C语言与数据结构课程设计》课程的意见与建议附录：程序源代

2、码1需求分析1.1功能与数据需求迷宫求解问题描述：以一个m×n的长方形表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。1.1.1题目要求的功能基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1,1,1）,（1,2,2）,（2,2,2）（3,2,3）,（3,1,2）,…。测试数据：迷宫的测试数据如下：左上角（1,1）为入口，右

3、下角（9,8）为出口。001000100010001000001101011100100001000001000101011110011100010111000000123456781.1.2扩展功能（1）编写递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及其通路1.2界面需求请求输入进入程序请求输入起始位置请求输入终点位置输出方阵迷宫输出路径输出方阵路径1.3开发环境与运行需求VisualC++6.02概要设计2.1主要数据结构定义模块函数模块主函数输入起始位置，终点位置判断首节点是否为通路判断路径能否走通对坐标标记是否到达迷宫出口处左边是否存在通路下边是否存在

4、通路右边是否存在通路上边是否存在通路存储路径，将路径入栈有解迷宫无解迷宫YNYNY输出迷宫选择路径2.3各模块函数说明typedefstruct{intpos_x[length];//进栈坐标intpos_y[length];inttop;intbase;}Stack;//新建结构体voidinitStack(Stack*p)//初始化栈Push(Stack*p,intx,inty,intd)//入栈具体操作Pop(Stack*p,intread[2],intd)//出栈并读出前一步的坐标initMaze(intMaze[10][9])//建立迷宫Ways(Stack*p,intMa

5、ze[10][9],intrukou_x,intrukou_y,intchukou_x,intchukou_y,intd)//具体路径的求解menu();//调用菜单函数main();//实现迷宫求解的主函数3详细设计迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按左、右、上、下4个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果4方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条合适的通路；若退回到了入口处，则说明不存在合法的通路到达出口。用

6、一个二维指针数组迷宫表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（1，1）处，出口点在位置（m,n）处。设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”，表示迷宫的外墙；第1行第1列元素和第m行第m列元素置成“0”，表示迷宫的入口和出口；假设当前所在位置是（x,y）。沿某个方向前进一步，它可能到达的位置最多有4。4测试5使用说明5.1应用程序功能的详细说明按提示输入数字1进入迷宫，输入迷宫入口，迷宫出口5.2应用程序运行环境要求MicrosoftVisualC++6

7、.05.5输入数据类型、格式和内容限制输入的数据都是整型（int），输入迷宫的数据间要用空格或回车隔开6总结提高6.1课程设计总结要能很好的掌握编程,仅仅通过简单的程序的编写是无法达成的,需要大量积累和深入研究才有可能。就从这个迷宫问题求解来说,在迷宫求路径就需要使用链表的栈,靠出栈和进栈来存取路径数据.在程序的编写中也不能一味的向已有的程序进行模仿,而要自己摸索,去寻找最好的解决方法,只有带着问题去反复进行实践,才能更熟练的掌握和运用,当然,对现有的程序