校园导航系统农夫过河问题图的遍历演示数据结构课程设计(实验报告)

广东技术师范学院天河学院数据结构与算法课程设计报告题 目 : 校园导航系统农夫过河问题图的遍历演示学 号 : 23 27_28 32 _ _班 级: 移动 121_ _ _ _小组成员:_李俊、刘锦浩、刘钦锐、潘文伟_ 指导教师: 蔡柳萍 所属系部: 计算机科学与技术系 1目录题目一：农夫过河 .3一、问题描述 .3二、基本要求 .2三、算法思想 .2四、数据结构 .3五、模块划分 .4六、源程序 .6七、测试数据 .71）运行测试 .7题目二：校园导航 .7一、问题描述 .8二、基本要求 .8三、算法思想 .8四、模块划分 .8五、源程序 .10六、运行及测试情况 .17题目二：图的遍历演示 .21一、问题描述 .21二、基本要求 .21三、算法思想 .21四、模块划分 .22五、源程序 .23六、运行及测试情况 .271、主界面 .272、输入信息运行测试（部分数据） .293、运行测试 .30课程设计总结 .332题目一：农夫过河一、问题描述有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？二、基本要求1）编程实现农夫过河的过程；2）执行结果中要体现过河的先后顺序界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在 c 语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构三、算法思想求解这个问题的简单的方法是一步一步进行试探，每一步搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。 要模拟农夫过河问题，首先需要对问题中每个角色的位置进行描述。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。用 0 表示农夫或者某东西在河的南岸，1 表示在河的北岸。例如整数 5(其二进制表示为 0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。 现在问题变成：从初始状态二进制 0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制 1111(全部到达河的北岸)为最终目标，并且在序列中的每一个状态都可以从前一状态到达。为避免瞎费功夫，要求在序列中不出现重复的状态。四、数据结构实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first) 搜索， 另一种是深度优先(depth_first) 搜索。本书只介绍在广度优先搜索方法中采用的数据结构设计。 广度优先就是在搜索过程中总是首先3搜索下面一步的所有可能状态，再进一步考虑更后面的各种情况。要实现广度优先搜索，可以使用队列。把下一步所有可能的状态都列举出来，放在队列中，再顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里。由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。这样，具体算法中就需要用一个整数队列moveTo，它的每个元素表示一个可以安全到达的中间状态。另外还需要一个数据结构记录已被访问过的各个状态，以及已被发现的能够到达当前这个状态的路径。由于在这个问题的解决过程中需要列举的所有状态（二进制 0000 1111）一共 16 种，所以可以构造一个包含 16 个元素的整数顺序表来实现。顺序表的第 i 个元素记录状态 i 是否已被访问过，若已被访问过则在这个顺序表元素中记入前驱状态值，把这个顺序表叫做 route。route 的每个分量初始值均为-1。route 的一个元素具有非负值表示这个状态已访问过，或是正被考虑。最后可以利用 route 顺序表元素的值建立起正确的状态路径。于是得到农夫过河问题的广度优先算法。在具体应用时，采用链队和顺序队均可，为叙述的方便，不妨设为使用顺序队。五、模块划分1、void BA() /农夫从 B 岸到 A 岸2、void xu() /初始化三样东西的位置3、void f() /判断农夫的位置4、int g() /判断羊的位置5、void huan () /农夫返回6、void AB() /农夫从 A 岸到 B 岸六、源程序#includeint s100,t=0;void BA(int a4,int b4);void xu(int a4) int i,j,k;for(i=0;i=t/2;i-=2) for(r=0;r#include10#define Num 13/*测试使用十三个地点，直接定义*/#define Maxedge 32760/*最大距离*/typedef struct/*定义对各个地点信息存储的结构体类型*/char name13 ;int number; char introduce100;vertex;vertex verNum;/*定义结构体数组*/int edgeNumNum;int shortestNumNum; int pathNumNum; void map()/*天河学院平面图，给使用程序者以直观认识*/printf("t 广东技术师范学院天河学院平面图(括号内为相对应的数字编号)nn");printf(" 346 总站（1）