数据结构农夫过河项目课报告

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