农夫过河实验报告——数据结构

数据结构实验报告实验四农夫过河的求解本实验的目的是进一步理解顺序表和队列的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。一、【问题描述】一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过河的方案。二、【数据结构设计】求解这个问题的简单的方法是一步一步进行试探，每一步搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。要模拟农夫过河问题，首先需要对问题中每个角色的位置进行描述。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。用0表示农夫或者某东西在河的南岸，1表示在河的北岸。例如整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。现在问题变成：从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸)为最终目标，并且在序列中的每一个状态都可以从前一状态到达。为避免瞎费功夫，要求在序列中不出现重复的状态。实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first) 搜索，另一种是深度优先(depth_first) 搜索。本书只介绍在广度优先搜索方法中采用的数据结构设计。广度优先就是在搜索过程中总是首先搜索下面一步的所有可能状态，再进一步考虑更后面的各种情况。要实现广度优先搜索，可以使用队列。把下一步所有可能的状态都列举出来，放在队列中，再顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里。由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。这样，具体算法中就需要用一个整数队列moveTo，它的每个元素表示一个可以安全到达的中间状态。另外还需要一个数据结构记录已被访问过的各个状态，以及已被发现的能够到达当前这个状态的路径。由于在这个问题的解决过程中需要列举的所有状态（二进制0000 1111）一共16种，所以可以构造一个包含16个元素的整数顺序表来实现。顺序表的第i个元素记录状态i是否已被访问过，若已被访问过则在这个顺序表元素中记入前驱状态值，把这个顺序表叫做route。route的每个分量初始值均为-1。route的一个元素具有非负值表示这个状态已访问过，或是正被考虑。最后可以利用route顺序表元素的值建立起正确的状态路径。于是得到农夫过河问题的广度优先算法。在具体应用时，采用链队和顺序队均可，为叙述的方便，不妨设为使用顺序队。三、【功能（函数）设计】1、确定农夫、狼、羊和白菜位置的功能模块。用整数location表示上述四位二进制描述的状态，由于采用四位二进制的形式表示农夫、狼、白菜和羊，所以在要使用位操作的“与”操作来考察每个角色所在位置的代码是0还是1。函数返回值为真表示所考察的角色在河的北岸，否则在南岸。例如某个状态和1000做“与”操作后所得结果为0，则说明农夫的位置上的二进制数为0，即农夫在南岸，如果所得结果为1，则说明农夫的位置上的二进制数为1，即农夫在北岸。狼、羊和白菜的处理办法以此类推。可以如下设计函数：int farmer(int location) return (0 != (location & 0x08);int wolf(int location) return (0 != (location & 0x04);int cabbage(int location) return (0 != (location & 0x02);int goat(int location) return (0 !=(location & 0x01);2、确定安全状态的功能模块。此功能模块通过位置分布的代码来判断当前状态是否安全。若状态安全返回1，状态不安全返回0。可以如下设计函数：int safe(int location)/ 若状态安全则返回1 if(goat(location) = = cabbage(location) &&(goat(location)!=farmer(location) return (0); / 羊吃白菜 if(goat(location) = = wolf(location) && (goat(location)!= farmer(location) return (0); / 狼吃羊return (1);/ 其他状态是安全的3、将各个安全状态还原成友好的提示信息的功能模块。由于程序中route表中最终存放的是整型的数据，如果原样输出不利于最终用户理解问题的解决方案，所以要把各个整数按照4位二进制的各个位置上的0、1代码所表示的含义输出容易理解的文字。4、输出路径 将二进制的表示转化为文字表示输出，输出过河的各个步骤四、【界面设计】如果能力和时间允许，可以使用动画设计将运送的过程演示出来。一般情况下可以使用最终的状态表描述出来就可以了。五、【编码实现】#include<iostream.h>#include<stdio.h>#define MAXNUM 20 typedef struct /顺序队列类型定义 int f, r; /f表示头，r 表示尾int qMAXNUM;/顺序队SeqQueue ,*PSeqQueue;PSeqQueue createEmptyQueue_seq( ) /创建队列 PSeqQueue paqu = new SeqQueue; if (paqu = NULL) cout<<"Out of space!"<<endl; else paqu->f=paqu->r=0; return (paqu); int isEmptyQueue_seq( PSeqQueue paqu ) /判断 paqu 所指是否是空队列 return paqu->f=paqu->r; void enQueue_seq(PSeqQueue paqu,int x) /在队列中插入一元素 xif (paqu->r+1)%MAXNUM=paqu->f) cout<<"队列已满."<<endl;else paqu->qpaqu->r=x;paqu->r=(paqu->r+1)%MAXNUM; void deQueue_seq(PSeqQueue paqu) /删除队列头部元素 if( paqu->f=paqu->r) cout<<"队列为空"<<endl; else paqu->f=(paqu->f+1)%MAXNUM; int frontQueue_seq( PSeqQueue paqu ) /对非空队列,求队列头部元素 return (paqu->qpaqu->f); int farmer(int location) /判断农夫位置对0做与运算，还是原来的数字，用来判断位置return 0 != (location & 0x08); int wolf(int location) /判断狼位置 return 0 != (location & 0x04); int cabbage(int location) /判断白菜位置 return 0 != (location & 0x02); int goat(int location) /判断羊的位置return 0 !=(location & 0x01); int safe(int location) / 若状态安全则返回 true if (goat(location) = cabbage(location) && (goat(location) != farmer(location) ) return 0; if (goat(location) = wolf(location) && (goat(location) != farmer(location) return 0;return 1; /其他状态是安全的 void farmerProblem( ) int movers, i, location, newlocation; int route16; /记录已考虑的状态路径 int printMAXNUM; PSeqQueue moveTo; moveTo = createEmptyQueue_seq( );/新的队列判断路径 enQueue_seq(moveTo, 0x00); /初始状态为0 for (i = 0; i < 16; i+) routei = -1; /-1表示没有记录过路径 route0=0; while (!isEmptyQueue_seq(moveTo)&&(route15 = -1)/队列不为空，路径未满时循环 location = frontQueue_seq(moveTo); /从队头出队 deQueue_seq(moveTo); for (movers = 1; movers <= 8; movers<<= 1) if (0 != (location & 0x08) = (0 != (location & movers) newlocation = location(0x08|movers);/或运算 if (safe(newlocation) && (routenewlocation = -1)/判断是否安全，以及路径是否可用 routenewlocation = location; enQueue_seq(moveTo, newlocation); /* 打印出路径 */ if(route15 != -1) cout<<"过河步骤是 : "<<endl; i=0; for(location = 15; location >= 0; location = routelocation) printi=location; i+; if (location = 0) break; int num=i-1; int temp204; int