《数据结构课程设计-农夫过河算法与数据结构设计》由会员分享，可在线阅读，更多相关《数据结构课程设计-农夫过河算法与数据结构设计（15页珍藏版）》请在金锄头文库上搜索。
1、数据结构-农夫过河项目课报告-计算机四班第七组数据结构项目课报告项目名称：农夫过河算法与数据结构设计专业班级：计算机科学与技术四班 学生姓名： 指导教师： 完成日期：2015年12月28日 农夫过河算法与数据结构设计摘要农夫过河问题即一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸,他需要把这些东西全部运到河的北岸。而他只有一条小船，且这只小船小到只能容下他和一件物品,另外只有农夫能撑船。农夫不能留下狼和羊自己离开，也不能留下白菜和羊自己离开,更不能留下狼，羊和白菜而独自离开，因为没有农夫的照看,狼就要吃掉羊,而羊又要吃掉白菜。好在狼是是肉动物，它不吃白菜，问农夫应该采取什么方案才能将所有的
2、东西安全地从河的南岸运到北岸？这类农夫问题是一个传统的数据结构问题,农夫过河问题根据图求解的搜索过程可采用两种不同的策略：一种是图的深度优先遍历搜索，另外一种是广度优先遍历搜索。如果采用深度优先遍历搜索，则需要采用递归的方式来编写程序，而这种程序的系统的开销比较大，如果采用广度优先搜索，则可以借助队列的方式，这种方式开销较小。关键字：农夫过河，广度优先遍历搜索，队列，深度优先遍历搜索，递归。目录1.前言42.设计任务与技术要求43.总体设计方案44.数据结构和算法的设计55.程序测试与调试（一）76.程序测试与调试（二）97.程序出现的问题及修改情况148.心得与体会14参考文献151.前言课
3、程研究项目是数据结构课程学习的重要方式之一，也是数据结构课程学习的重要组成部分之一。通过课程研究项目的实施，在掌握数据结构基本理论的基础上，结合程序设计方法，较深入地理解数据结构知识，掌握数据结构的选择与设计方法，掌握研究报告的撰写方法，提高独立设计算法和选择或设计数据结构的基本能力，提高综合应用所学知识解决算法设计问题的能力，更好地培养计算机科学与技术，软件工程专业学生的专业技能和综合素质。这类农夫问题是一个传统的数据结构问题,农夫过河问题根据图求解的搜索过程可采用两种不同的策略：一种是图的深度优先遍历搜索，另外一种是广度优先遍历搜索。如果采用深度优先遍历搜索，则需要采用递归的方式来编写程序
4、，而这种程序的系统的开销比较大，如果采用广度优先搜索，则可以借助队列的方式，这种方式开销较小。2.设计任务与技术要求农夫过河问题是指农夫需要带一只狼、一只羊和一棵白菜到河的南岸去,需要安全运到北岸。而一条小船只能容下他和一件物品,只有农夫能撑船。问农夫怎么能安全过河,问题中需要涉及到狼会吃羊,羊会吃白菜,所以农夫不能将这两种或三种物品单独放在河的一侧,因为没有农夫的照看,狼就要吃掉羊,而羊可能又要吃掉白菜。 这类问题的实质是系统的状态问题,要寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径。根据实际情况，对此问题分析可以得到不同的特征：一是农夫和羊在河的南岸，狼和白菜在河的北岸
5、；二是从一个状态可转到另外一个状态，而不违反狼吃羊，羊吃草的规则（例如农夫自己过河或者农夫带着羊过河）；三是有些状态是不安全的（例如农夫一人在北岸，而其他的东西都在南岸）；四是初始状态是农夫，羊，狼，白菜都在河的南岸和结束状态是农夫，羊，狼，白菜都在河的北岸。实现农夫过河问题，则需要找到一条合法的路径（相邻状态之间的转移合法），从开始状态到某个结束状态，路途中不能经过不安全的状态。3.总体设计方案利用图的有关知识来解决农夫过河问题根据图的广度（深度）优先搜索来实现实验要求在实施此问题中，首先要为农夫，狼，白菜和羊设置求状态的函数，若某一种物品在河的南岸，则返回0，若在河的的北岸，则返回1；其次
6、是为每一种状态做测试，状态安全则返1，否则返回0。4.数据结构和算法的设计4.1算法说明农夫过河问题根据图求解的搜索过程可采用两种不同的策略：一种是图的深度优先遍历搜索，另外一种是广度优先遍历搜索。如果采用深度优先遍历搜索，则需要采用递归的方式来编写程序，而这种程序的系统的开销比较大，如果采用广度优先搜索，则可以借助队列的方式，这种方式开销较小。算法中要先各为农夫，狼，白菜和羊设置参数，这可以用枚举类型为各种物品设置参数，其中羊goat=0001,白菜cabbage=0010，狼wolf=0100,农夫farmer=1000，而且利用moveTo来记录可到的尚未向前测试的状态，数据元素rout
7、ei来记录状态i的路径前一状态，如果是-1，则表示尚未访问。4.2广度优先遍历搜索算法思想 初始化顺序表Route和安全队列moveTo 初始安全状态0（0000）入队列moveTo,Route0=0 While(IsEmpty(moveTo)&(route15=-1) OutQuere(moveTo,location); /出队当前安全状态 for(每个从location可以过渡到得状态newlocation) /农夫(附带同侧物品)移动 if(newlocation安全且未访问过) OutQueue(moveTo,newlocation);if(route15!=-1/已经到达终点了，打印
8、路径 for(location=15;location=0;location=routelocation printf (“The location is : %dn,location); if(location=0) return 1;return 1;else printf(“无解！n);4.3图形说明在程序中涉及了很多的状态，共有16种，从高位到低位分别表示农夫，狼，白菜和羊，如果是0000则表示农夫，狼，白菜和羊都在南岸，1111表示都到达了北岸。其他的状态则分别表示：0001表示羊在北岸 0010表示白菜在北岸0011表示羊和白菜在北岸 0100表示狼在北岸0101表示狼和羊在北岸
9、0110表示狼和白菜北岸0111表示狼，白菜和羊在北岸 1000表示农夫和北岸1001表示农夫，羊在北岸 1010表示农夫，白菜在北岸1011表示农夫，白菜和羊在北岸 1100表示农夫，狼在北岸1101表示农夫，狼和羊在北岸 1110表示农夫，狼和白菜在北岸其中有些状态是不允许出现的，有0011，0101，0111，0001，1100，1001，因为这些状态是不安全的，所以可以为以上的条件绘制体统的状态图：系统状态转换图其中箭头表示状态是可逆的，也就是说农夫可以带着某些东西到河的北岸，也可以把东西带回河的南岸。箭头上的字母都代表这其中的物品，f(farmer)表示农夫自己过河，w(wolf)表
10、示农夫带着狼过河，c(cabbage)表示农夫带着白菜过河，g(goat)表示农夫带着羊过河。5. 程序测试与调试（一）-深度优先遍历搜索5.1源程序#include #include #define STEP 20using namespace std;int m=0,n=0;/*m为take函数执行次数，n为for循环次数*/int aSTEP4;/*0狼 1羊 2菜 3人*/int bSTEP;int count = 0;void disp(int s, int n);void take(int step);void farmer() int i, j;for(i = 0; i STEP
11、; i+) bi = 0;for(j = 0; j 4; j+)aij = 0;/*初始化*/take(0);void disp(int s, int n) if(s = 0) /*人未过，则过去*/if(n = 0) cout 农夫自己过去;else if(n = 1) cout 把狼送过去;else if(n = 2) cout 把羊送过去;else if(n = 3) cout 把蔬菜送过去;cout n; else /*人已过，则回来*/if(n = 0) cout 农夫自己回来;else if(n = 1) cout 把狼送回来;else if(n = 2) cout 把羊送回来;e
12、lse if(n = 3) cout 把蔬菜送回来;cout n;/*输出*/void take(int step) /*44次*/*printf(n%d-%d%d%d%d-%dt,step+1,astep0,astep1,astep2,astep3,+m);*/int i;if (astep0 + astep1 + astep2 + astep3 = 4) count+;cout 第 count 种方法：n;for(i = 0; i step; i+) cout 第 i + 1 步骤： ;disp(ai3, bi + 1);cout n;return;/*若成功，则结束*/for (i =
13、0; i step; i+)if(ai0 = astep0 & ai1 = astep1 & ai2 = astep2 & ai3 = astep3)return;/*若重复，则结束，否则无限循环*/if (astep1 != astep3 & (astep2 = astep1 | astep0 = astep1)return;/*若危险，则结束*/for (i = -1; i = 2; i+) bstep = i;astep + 10 = astep0;astep + 11 = astep1;astep + 12 = astep2;astep + 13 = astep3;/*下次继承本次状态*/astep + 13 = 1 - astep + 13;/*农夫动*/*printf(%d-%d-%d%d%d%d-%d%d%d%d-%d-%dt,step+1,i+2,astep0
