c语言与数据结构课程设计报告

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

1、C语言与数据结构课程设计报告       学号2011013759 姓名俞杰课程设计题目迷宫求解小组成员俞杰安飞洪飞 2012年12月 目录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功能与数据需求1.1.1题目要求的功能以一个m×n的长方形表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。测试数据：迷宫的测试数据如下：左上角（1,1）为入口，右下角（9,8）为出口。001000100010001000001101011100100001000001000101011110011100010111000000123456781.1.2扩展功能（1）编写递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及其通路。1.2界面需

3、求输入行数和列数输入每一行中的通路（0，0）和障碍（1,1）.输入入口坐标（1,1）和出口坐标（m,n）.1.3开发环境与运行需求开发环境MicrosoftVisualC++6.0最低运行需求windowsxp;32位系统2概要设计2.1主要数据结构：typedefstruct/*用于存放迷宫的位置和该点信息*/{intx,y,d;}Datatype;typedefstruct/*该栈用于存储走过的结点*/{Datatypedata[MAXSIZE];inttop;}Sqstack,*PSqstack;typedefstruct/*用于存放当前结点可走的四个方向*/{intx,y;}i

4、tem;2.2程序总体结构输入起始位置，终点位置判断首节点是否为通路判断路径能否走通对坐标标记是否到达迷宫出口处南边是否存在通路东边是否存在通路北边是否存在通路存储路径，将路径入栈有解迷宫无解迷宫YNYNY输出迷宫选择路径西边是否存在通路打印所走的路径2.3各模块函数说明PSqstackInit_Sqstack()/*初始化空栈*/intPush_Sqstack(PSqstacks,Datatypex)/*入栈*/intPop_Sqstack(PSqstacks,Datatype*x)/*出栈*/voidDestroy_Sqstack(PSqstack*s)/*销毁栈*/intMaze

5、path(intmaze[][n+2],intx0,inty0)/*求迷宫路径函数，入口参数：指向迷宫数组的指针，开始点（x0,y0）*/Pop_Sqstack(s,&temp);Push_Sqstack(t,temp);/*栈t是栈s的逆，因为s保存的途径是反的，加t使输出的途径变为正*/3详细设计3.1算法分析与设计思路：计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。实现：假设“当前位置”指的是“

6、在收索过程中某一时刻所在图中某个方块位置”，则求迷宫中的一条路径的算法的基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”则应该顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周4个方向（东·南·西·北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“从当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径

7、上删除前一通道块”的操作即为“入栈”。3.2主要程序段设计voidmain(){inti,j;intmaze[m+2][n+2];printf("请输入迷宫矩阵:9*8");for(i=0,j=0;i