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