数据结构课程设计报告(农夫过河)

1目录引言...................................................21问题描述..............................................2基本要求................................................22.1为农夫过河问题抽象数据模型体会数据模型在问题求解中的重要性；........22.2设计一个算法求解农夫过河问题，并输出过河方案；......................23概要设计.............................................23.1数据结构的设计。....................................................23.1.1农夫过河问题的模型化.............................................23.1.2算法的设计......................................................34、运行与测试..........................................65、总结与心得..........................................6附录...................................................6参考文献..............................................122引言所谓农夫过河问题是指农夫带一只狼、一只羊和一棵白菜在河南岸,需要安全运到北岸。一条小船只能容下他和一件物品,只有农夫能撑船。问农夫怎么能安全过河,当然狼吃羊,羊吃白菜,农夫不能将这两种或三种物品单独放在河的一侧,因为没有农夫的照看,狼就要吃羊,而羊可能要吃白菜?这类问题的实质是系统的状态问题,要寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径。1问题描述一个农夫带一只狼、一棵白菜和一只羊要从一条河的南岸过到北岸，农夫每次只能带一样东西过河，但是任意时刻如果农夫不在场时，狼要吃羊、羊要吃白菜，请为农夫设计过河方案。2基本要求2.1为农夫过河问题抽象数据模型体会数据模型在问题求解中的重要性；2.2设计一个算法求解农夫过河问题，并输出过河方案；3概要设计3.1数据结构的设计。3.1.1农夫过河问题的模型化分析这类问题会发现以下特征:有一组状态(如农夫和羊在南,狼和白菜在北);从一个状态可合法地转到另外几个状态(如农夫自己过河或农夫带着羊过河);有些状态不安全(如农夫在北,其他东西在南);有一个初始状态(都在南);结束状态集(这里只有一个,都在北)。问题表示:需要表示问题中的状态,农夫等位于南P北(每个有两种可能)。可以采用位向量,4个二进制位的0P1情况表示状态,显而易见,共24=16种可能状态。从高位到低位分别表示农夫、狼、白菜和羊。0000(整数0)表示都在南岸,目标状态1111(即整数15)表示都到了北岸。有些状态0011,0101,0111,0001,1100,1001是不允许出3现的,因为这些状态是不安全状态。根据上述条件可以画出系统的状态图如图1所示。图1系统状态转换图其中双向的箭头表示状态可逆,即农夫可以带着某种东西过去,也可以带着该东西回来。箭头上的字母表示农夫所携带的东西:f(farmer),w(wolf),g(goat),c(cabbage)分别表示农夫自己、农夫携带狼、农夫携带羊、农夫携带菜过河。现在的问题转化为:找一条合法路径(相邻状态之间的转移合法),从开始状态到某个结束状态,途中不经过不安全状态。3.1.2算法的设计求农夫、狼、白菜和羊的当前状态的函数为每一种状态做测试,状态安全则返回0,否则返回1。安全性判断函数,若状态安全则返回0intfarmer(intlocation)//判断农夫位置对0做与运算，还是原来的数字，用来判断位置{return0!=(location&0x08);}intwolf(intlocation)//判断狼位置{return0!=(location&0x04);}intcabbage(intlocation)//判断白菜位置4{return0!=(location&0x02);}intgoat(intlocation)//判断羊的位置{return0!=(location&0x01);}intsafe(intlocation)//若状态安全则返回true{if((goat(location)==cabbage(location))&&(goat(location)!=farmer(location)))return0;if((goat(location)==wolf(location))&&(goat(location)!=farmer(location)))return0;return1;//其他状态是安全的借助于位向量和按位运算符,很容易描述过河动作,这种问题表示的设计使得程序的实现比较容易。算法的基本思想:利用队列moveTo记录可到的尚未向前探试的状态,数组元素route[i]记录状态i的路径[前一状态],-1表示尚未访问。则算法的高级抽象可描速为:{初始状态出发点入队列;所有其他点状态标记为未访问;while(!isEmptyQueueseq(moveTo)&&(route[15]==-1)){从moveTo取出一个状态;试探所有由这个状态出发可能到达的状态;if(能到达的状态安全且未访问过){记录到它的路径;压入队列;}}}精化上速算法得到问题的具体算法如下:voidfarmerProblem(){5intmovers,i,location,newlocation;introute[16];//记录已考虑的状态路径intprint[MAXNUM];PSeqQueuemoveTo;moveTo=createEmptyQueue_seq();//新的队列判断路径enQueue_seq(moveTo,0x00);//初始状态为0for(i=0;i16;i++)route[i]=-1;//-1表示没有记录过路径route[0]=0;while(!isEmptyQueue_seq(moveTo)&&(route[15]==-1))//队列不为空，路径未满时循环{location=frontQueue_seq(moveTo);//从队头出队，location表示位置，0为北岸，1为南岸deQueue_seq(moveTo);//已出队的删除for(movers=1;movers=8;movers=1)//向左移位，movers分别0001，0010，0100，1000,也就是依次判断过河的可行性{if((0!=(location&0x08))==(0!=(location&movers)))//判断农夫和要移动的物品是否在同岸{newlocation=location^(0x08|movers);//过岸if(safe(newlocation)&&(route[newlocation]==-1))//判断是否安全，以及路径是否可用{route[newlocation]=location;enQueue_seq(moveTo,newlocation);//记录路径并入队，位置改变64、运行与测试5、总结与心得“纸上得来终觉浅，绝知此事要躬行。”通过这两周的课程设计，使我对书上的的理论知识有了更深的理解，也使我对于团队合作有了新的认识，意识到团队的力量。课程设计是一个必须经历的过程，是我们理解书本知识、熟悉所学专业的一次很好实践。在这次设计过程中，体现出自己单独设计程序的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补。附录#includeiostream.h#includestdio.h#defineMAXNUM20typedefstruct//顺序队列类型定义{intf,r;//f表示头，r表示尾7intq[MAXNUM];//顺序队}SeqQueue,*PSeqQueue;PSeqQueuecreateEmptyQueue_seq()//创建队列{PSeqQueuepaqu=newSeqQueue;if(paqu==NULL)coutOutofspace!endl;elsepaqu-f=paqu-r=0;return(paqu);}intisEmptyQueue_seq(PSeqQueuepaqu)//判断paqu所指是否是空队列{returnpaqu-f==paqu-r;}voidenQueue_seq(PSeqQueuepaqu,intx)//在队列中插入一元素x{if((paqu-r+1)%MAXNUM==paqu-f)cout队列已满.endl;else{paqu-q[paqu-r]=x;paqu-r=(paqu-r+1)%MAXNUM;}}voiddeQueue_seq(PSeqQueuepaqu)//删除队列头部元素{if(paqu-f==paqu-r)cout队列为空endl;elsepaqu-f=(paqu-f+1)%MAXNUM;}intfrontQueue_seq(PSeqQueuepaqu)//对非空队列,求队列头部元素{8return(paqu-q[paqu-f]);}intfarmer(intlocation)//判断农夫位置对0做与运算，还是原来的数字，用来判断位置{return0!=(location&0x08);}intwolf(intlocation)//判断狼位置{return0!=(location&0x04);}intcabbage(intlocation)//判断白菜位置{return0!=(location&0x02);}intgoat(intlocation)//判断羊的位置{return0!=(location&0x01);}intsafe(intlocation)//若状态安全则返回true{if((goat(location)==cabbage(location))&&(goat(location)!=farmer(location)))return0;if((goat(location)==wolf(location))&&(goat(location)!=farmer(location)))return0;return1;//其他状态是安全的}voidfarmerProblem(){intmovers,i,location,newlocation;introute[16];//记录已考虑的状态路径intprint[MAXNUM];9PSeqQueuemoveTo;moveTo=createEmptyQueue_seq();//新的队列判断路径enQueue_seq(moveTo,0x00);//初始状态为0for(i=0;i16;i++)route[i]=-1;//-1表示没有记录过路径route[0]=0;while(!isEmptyQueue_seq(moveTo)&&(route[15]==-1))//队列不为空，路径未满时循环{location=frontQueue_seq(moveTo);//从队头出队，location表示位置，0为北岸，1为南岸deQueue_seq(moveTo);//已出队的删除for(movers=1;movers=8;movers=1)//向左移位，movers分别0001，0010，0100，1000,也就是依次判断过河的可行性{if((0!=(location&0x08))==(0!=(location&mover