资源描述：
《数据结构农夫过河项目课报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构-农夫过河项目课报告-计算机四班第七组《数据结构》项目课报告项目名称：农夫过河算法与数据结构设计专业班级：计算机科学与技术四班学生姓名：王喆指导教师：完成日期：2015年12月28日15数据结构-农夫过河项目课报告-计算机四班第七组农夫过河算法与数据结构设计摘要农夫过河问题即一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸,他需要把这些东西全部运到河的北岸。而他只有一条小船，且这只小船小到只能容下他和一件物品,另外只有农夫能撑船。农夫不能留下狼和羊自己离开，也不能留下白菜和羊自己离开,更不能留下狼
2、，羊和白菜而独自离开，因为没有农夫的照看,狼就要吃掉羊,而羊又要吃掉白菜。好在狼是是肉动物，它不吃白菜，问农夫应该采取什么方案才能将所有的东西安全地从河的南岸运到北岸？这类农夫问题是一个传统的数据结构问题,农夫过河问题根据图求解的搜索过程可采用两种不同的策略：一种是图的深度优先遍历搜索，另外一种是广度优先遍历搜索。如果采用深度优先遍历搜索，则需要采用递归的方式来编写程序，而这种程序的系统的开销比较大，如果采用广度优先搜索，则可以借助队列的方式，这种方式开销较小。关键字：农夫过河，广度优先遍历搜索，队列，深度
3、优先遍历搜索，递归。15数据结构-农夫过河项目课报告-计算机四班第七组目录1.前言…………………………………………………………42.设计任务与技术要求………………………………………43.总体设计方案………………………………………………44.数据结构和算法的设计……………………………………55.程序测试与调试（一）……………………………………76.程序测试与调试（二）……………………………………97.程序出现的问题及修改情况………………………………148.心得与体会…………………………………………………14参
4、考文献………………………………………………………1515数据结构-农夫过河项目课报告-计算机四班第七组1.前言课程研究项目是《数据结构》课程学习的重要方式之一，也是《数据结构》课程学习的重要组成部分之一。通过课程研究项目的实施，在掌握数据结构基本理论的基础上，结合程序设计方法，较深入地理解数据结构知识，掌握数据结构的选择与设计方法，掌握研究报告的撰写方法，提高独立设计算法和选择或设计数据结构的基本能力，提高综合应用所学知识解决算法设计问题的能力，更好地培养计算机科学与技术，软件工程专业学生的专业技能和综合素
5、质。这类农夫问题是一个传统的数据结构问题,农夫过河问题根据图求解的搜索过程可采用两种不同的策略：一种是图的深度优先遍历搜索，另外一种是广度优先遍历搜索。如果采用深度优先遍历搜索，则需要采用递归的方式来编写程序，而这种程序的系统的开销比较大，如果采用广度优先搜索，则可以借助队列的方式，这种方式开销较小。2.设计任务与技术要求农夫过河问题是指农夫需要带一只狼、一只羊和一棵白菜到河的南岸去,需要安全运到北岸。而一条小船只能容下他和一件物品,只有农夫能撑船。问农夫怎么能安全过河,问题中需要涉及到狼会吃羊,羊会吃白菜
6、,所以农夫不能将这两种或三种物品单独放在河的一侧,因为没有农夫的照看,狼就要吃掉羊,而羊可能又要吃掉白菜。这类问题的实质是系统的状态问题,要寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径。根据实际情况，对此问题分析可以得到不同的特征：一是农夫和羊在河的南岸，狼和白菜在河的北岸；二是从一个状态可转到另外一个状态，而不违反狼吃羊，羊吃草的规则（例如农夫自己过河或者农夫带着羊过河）；三是有些状态是不安全的（例如农夫一人在北岸，而其他的东西都在南岸）；四是初始状态是农夫，羊，狼，白菜都在河的南岸和
7、结束状态是农夫，羊，狼，白菜都在河的北岸。实现农夫过河问题，则需要找到一条合法的路径（相邻状态之间的转移合法），从开始状态到某个结束状态，路途中不能经过不安全的状态。3.总体设计方案利用图的有关知识来解决农夫过河问题根据图的广度（深度）优先搜索来实现实验要求15数据结构-农夫过河项目课报告-计算机四班第七组在实施此问题中，首先要为农夫，狼，白菜和羊设置求状态的函数，若某一种物品在河的南岸，则返回0，若在河的的北岸，则返回1；其次是为每一种状态做测试，状态安全则返1，否则返回0。4.数据结构和算法的设计4.1
8、算法说明农夫过河问题根据图求解的搜索过程可采用两种不同的策略：一种是图的深度优先遍历搜索，另外一种是广度优先遍历搜索。如果采用深度优先遍历搜索，则需要采用递归的方式来编写程序，而这种程序的系统的开销比较大，如果采用广度优先搜索，则可以借助队列的方式，这种方式开销较小。算法中要先各为农夫，狼，白菜和羊设置参数，这可以用枚举类型为各种物品设置参数，其中羊goat=0001,白菜cabbage=0010，狼wolf=0
