数据结构课程设计.doc

1、课 程 设 计课程名称_数据结构_题目名称_农夫过河问题_学生系别_软件学院_专业班级_10 软工（专升本） _学 号_104151320015_学生姓名_王东星_指导教师_张晓民_2010 年 12 月 12 日农夫过河问题一.问题描述设一个农夫过河带着一条狼、一只羊和一棵白菜，身处河的南岸。现在他要把这些西全部运到北岸,现在问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。当农夫在场的时候,这三样东西相安无事.一旦农夫不在,狼会吃羊,羊会吃白菜。根据原题的描述我们知道，单独留下白菜和羊，或单独留下狼和羊在某一岸的状态是不安全的。白菜和狼相处没事,把它看作个重要关系的

2、,通过位置分布的代码来判断状态是否安全。然后设计一个方案, 模拟农夫能安全地将这三样东西带过河。二基本要求以队列解决农夫过河问题，用广度优先搜索实现求解的过程。用这个方法来搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。要实现广度优先搜索，一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来，放在这个队列中，然后顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里。由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。为了实现广度优先搜索，算法中需要使用了一个整数队列 moveTo

3、，它的每个元素表示一个可以安全到达的中间状态。另外还需要一个数据结构记录已被访问过的各个状态，以及已被发现的能够到达当前这个状态的路径。由于在这个问题的解决过程中需要列举的所有状态(二进制 0000 1111)一共 16 种，所以可以构造一个包含 16 个元素的整数顺序表来满足以上的要求。三测试数据要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用 0 表示农夫或者某东西在河的南岸，1 表示在河的北岸。因此整数 5(其二进制表示为 0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。确定每个角

4、色位置的函数,用整数 location 表示上述四位二进制描述的状态，用下面的四个函数从上述状态中得到每个角色所在位置的代码。函数返回值为真表示所考察的人或物在河的北岸，否则在南岸。从初始状态二进制 0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸) 为最终目标，并且在序列中的每一个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。四流程代码如下：/* 用队列解决农夫过河问题的算法*/#include#include#define MAXNUM 20typedef int DataType;struct SeqQueu

5、e /* 顺序队列类型定义 */int f, r;DataType qMAXNUM;typedef struct SeqQueue *PSeqQueue; /* 顺序队列类型的指针类型 */PSeqQueue createEmptyQueue_seq( void ) PSeqQueue paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue);if (paqu = NULL)printf(“Out of space! n“);elsepaqu-f = paqu-r = 0;确定每个角色位置， ,用整数 location表示狼、羊、农夫、白菜的二进制来描述

6、所在位置的代码 初始状态二进制 0000(全部在河的南岸) 出发。寻找一种全部由安全状态构成的状态序列。在寻找安全路径的同时，要考虑其他安全状态，若出现相同状态路径要记录下来，防止重复。本程序不断寻找安全的状态，它以二进制 1111(全部到达河的北岸) 为最终目标，程序结束。return (paqu);int isEmptyQueue_seq( PSeqQueue paqu ) return paqu-f = paqu-r;/* 在队列中插入一元素x */void enQueue_seq( PSeqQueue paqu, DataType x ) if ( (paqu-r + 1) % MAX

7、NUM = paqu-f )printf( “Full queue.n“ );else paqu-qpaqu-r = x;paqu-r = (paqu-r + 1) % MAXNUM;/* 删除队列头部元素 */void deQueue_seq( PSeqQueue paqu ) if( paqu-f = paqu-r )printf( “Empty Queue.n“ );elsepaqu-f = (paqu-f + 1) % MAXNUM;/* 对非空队列,求队列头部元素 */DataType frontQueue_seq( PSeqQueue paqu ) return (paqu-qpa

8、qu-f);int farmer(int location) return 0 != (location int wolf(int location) return 0 != (location int cabbage(int location) return 0 != (location int goat(int location) return 0 !=(location /* 若状态安全则返回true */int safe(int location) /* 羊吃白菜 */if (goat(location) = cabbage(location) /* 狼吃羊 */if (goat(lo

9、cation) = wolf(location) return 1; /* 其他状态是安全的 */void farmerProblem( ) int movers, i, location, newlocation;int route16; /*记录已考虑的状态路径*/PSeqQueue moveTo;/*准备初值*/moveTo = createEmptyQueue_seq( );enQueue_seq(moveTo, 0x00);for (i = 0; i = 0; location = routelocation) printf(“The location is : %dn“,locat

10、ion);if (location = 0) return;elseprintf(“No solution.n“);int main() farmerProblem( );return 0;截图：心得体会对于农夫过河问题的设计，很明显突出了自己能力不足！在这个过程中花费了大量时间找资料来弥补自己的缺乏的知识，自己对重新进得书本的学习，尽量使自己做得更！ 从做课程设计的过程中，我的体会挺多的。只要有信心与耐心，没有做不到的事情。因为在这个过程中写代码与调试的过程中确实需要耐心与信心，否则就不可能写完整。我也知道该课题还存在很多的漏洞，也不是很完整。由于自己本身能力的原因，也不能使之更完整。但是我已经尽我的努力写的了，同时在这些的设计中享受到了很多乐趣和知识。、2010 年 12 月 22 日教师评语0年 月 日成绩及签名年 月 日