数据结构实验-农夫过河问题

《数据结构实验-农夫过河问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、农夫过河问题一、实验目的掌握广度优先搜索策略，并用队列求解农夫过河问题二、实验内容问题描述：一农夫带着一只狼，一只羊和一颗白菜，身处河的南岸，他要把这些东西全部运到北岸，遗憾的是他只有一只小船，小船只能容下他和一件物品。这里只能是农夫来撑船，同时因为狼吃羊、羊吃白菜、所以农夫不能留下羊和狼或羊和白菜在河的一边，而自己离开；好在狼属肉食动物，不吃白菜。农夫怎么才能把所有的东西安全运过河呢？实验要求如下：（1）设计物品位置的表示方法和安全判断算法；（2）设计队列的存储结构并实现队列的基本操作（建立空队列、判空、入队、出队、取对头元素），也可以使用STL中的队列进行代码的编写；（3）采用广度优

2、先策略设计可行的过河算法；（4）输出要求：按照顺序输出一种可行的过河方案；提示：可以使用STL中的队列进行代码编写。程序运行结果：二进制表示：1111011011100010101100011001，0000三、农夫过河算法流程nStep1：初始状态0000入队nStep2：当队列不空且没有到达结束状态1111时，循环以下操作：n队头状态出队n按照农夫一个人走、农夫分别带上三个物品走，循环以下操作：n农夫和物品如果在同一岸，则计算新的状态n如果新状态是安全的并且是没有处理过的，则更新path[]，并将新状态入队n当状态为1111时，逆向输出path[]数组附录一：STL中队列的使用注：队

3、列，可直接用标准模板库（STL）中的队列。需要#includeSTL中的queue，里面的一些成员函数如下（具体可以查找msdn，搜索queueclass）：front：Returnsareferencetothefirstelementatthefrontofthequeue.pop：Removesanelementfromthefrontofthequeuepush：Addsanelementtothebackofthequeueempty：Testsifthequeueisempty三、实验代码FarmerRiver.H#ifndefFARMERRIVER_H#def

4、ineFARMERRIVER_HintFarmerOnRight(intstatus);//农夫，在北岸返回1，否则返回0intWorfOnRight(intstatus);//狼intCabbageOnRight(intstatus);//白菜intGoatOnRight(intstatus);//羊intIsSafe(intstatus);//判断状态是否安全，安全返回1，否则返回0voidFarmerRiver();#endifSeqQueue.h#ifndefSEQQUEUE_H#defineSEQQUEUE_HtypedefintDataType;structQueue{int

5、Max;intf;intr;DataType*elem;};typedefstructQueue*SeqQueue;SeqQueueSetNullQueue_seq(intm);intIsNullQueue_seq(SeqQueuesqueue);voidEnQueue_seq(SeqQueuesqueue,DataTypex);voidDeQueue_seq(SeqQueue);DataTypeFrontQueue_seq(SeqQueue);#endifFarmerRiver.c#include#include#include"SeqQueue.

6、h"#include"FarmerRiver.h"intFarmerOnRight(intstatus)//判断当前状态下农夫是否在北岸{return(0!=(status&0x08));}intWorfOnRight(intstatus){return(0!=(status&0x04));}intCabbageOnRight(intstatus){return(0!=(status&0x02));}intGoatOnRight(intstatus){return(0!=(status&0x01));}intIsSafe(intstatus)//判断当前状态是否安全{if((GoatOn

7、Right(status)==CabbageOnRight(status))&&(GoatOnRight(status)!=FarmerOnRight(status)))return(0);//羊吃白菜if((GoatOnRight(status)==WorfOnRight(status))&&(GoatOnRight(status)!=FarmerOnRight(status)))return0;//狼吃羊return1;//其他