农夫过河数据结构

郑州轻工业学院 课 程 设 计 任 务 书

题目 农夫过河 专业、班级 计算机科学与技术 学号 姓名 主要内容：

一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会 吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而 狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。 基本要求:

编写求解该问题的算法程序，并用此程序上机运行、调试，屏幕显示结果，能结合程序进行分析。

主要参考资料:

数据结构 严蔚敏

完 成 期 限： 2012/6/21 指导教师签名： 课程负责人签名：

年 月 日

郑州轻工业学院

本科

数据结构课程设计总结报告

设计题目：农夫过河 学生姓名：

系 别：计算机与通信工程学院 专 业：计算机科学与技术 班 级：计算机科学与技术 学 号： 指导教师：

2012年 6 月 21 日

2

一， 设计题目 问题描述：

一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。 二， 运行环境（软、硬件环境）

VC6.0 Windows7系统 三， 算法设计的思想

对于这个问题，我们需要先自动生成图的邻接矩阵来存储，主要方法是先生成各种安全状态结点，存放在顶点向量中；再根据判断两个结点间状态是否可以转换来形成顶点之间的所有边，并把它们保存在邻接矩阵中。在建立了图的邻接矩阵存储结构后，利用递归深度优先搜索求出从顶点（0，0，0，0）到顶点（1，1，1，1）的一条简单路径，这样做只能搜到一种合理方法，因为深度优先搜索遍历一个图的时候每一个结点只能被访问一次。 四， 算法的流程图

要写算法的流程图，必须要先很了解自己的函数结构，我先在纸上手动的把整个过程在纸上画一遍，了解它的大体流程，然后把各个函数给分开，下面是我自己根据我的代码中画的各个函数画的流程图，希望老师满意。 主函数的流程图：

开始

初始化图 结束 调用DFSpath 输出路径 3

初始化图函数的流程图： 开始 返回主函数 读取4个整型变量 初始化邻接矩阵 判断状态判断它们 是否安全 是否连接 初始化图的顶点 读入两个顶点 DFSpath函数的流程图：

开始 入栈 判断是否 被访问过 退栈

调用DFSpath 返回主函数

4