农夫过河文本文档

《农夫过河文本文档》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、//farmerProblem.c//用队列解决农夫过河问题#include#includetypedefintDataType;//顺序队列：类型和界面函数声明structSeqQueue{//顺序队列类型定义intMAXNUM;//队列中最大元素个数intf,r;DataType*q;};typedefstructSeqQueue*PSeqQueue;//顺序队列类型的指针类型PSeqQueuecreateEmptyQueue_seq(intm){//创建一个空队列PSeqQueueq

2、ueue=(PSeqQueue)malloc(sizeof(structSeqQueue));if(queue!=NULL){queue->q=(DataType*)malloc(sizeof(DataType)*m);if(queue->q){queue->MAXNUM=m;queue->f=0;queue->r=0;return(queue);}elsefree(queue);}printf("Outofspace!!");//存储分配失败returnNULL;}intisEmptyQueue_seq(PSeqQueu

3、equeue){//判断队列是否为空return(queue->f==queue->r);}voidenQueue_seq(PSeqQueuequeue,DataTypex)//在队尾插入元素x{if((queue->r+1)%queue->MAXNUM==queue->f)printf("Fullqueue.");else{queue->q[queue->r]=x;queue->r=(queue->r+1)%queue->MAXNUM;}}voiddeQueue_seq(PSeqQueuequeue)//删除队列头部元素

4、{if(queue->f==queue->r)printf("EmptyQueue.");elsequeue->f=(queue->f+1)%queue->MAXNUM;}DataTypefrontQueue_seq(PSeqQueuequeue){if(queue->f==queue->r)printf("EmptyQueue.");elsereturn(queue->q[queue->f]);}//个体状态判断函数intfarmer(intlocation){//判断农夫的位置return(0!=(location

5、&0x08));}intwolf(intlocation){//判断狼的位置return(0!=(location&0x04));}intcabbage(intlocation){//判断白菜的位置return(0!=(location&0x02));}intgoat(intlocation){//判断羊的位置return(0!=(location&0x01));}//安全状态的判断函数intsafe(intlocation){//若状态安全则返回trueif((goat(location)==cabbage(location

6、))&&(goat(location)!=farmer(location)))return(0);//羊吃白菜if((goat(location)==wolf(location))&&(goat(location)!=farmer(location)))return(0);//狼吃羊return(1);//其他状态是安全的}main(){inti,movers,location,newlocation;introute[16];//用于记录已考虑的状态路径PSeqQueuemoveTo;//用于记录可以安全到达的中间状态mov

7、eTo=createEmptyQueue_seq(20);//创建空队列enQueue_seq(moveTo,0x00);//初始状态进队列for(i=0;i<16;i++)route[i]=-1;//准备数组route初值route[0]=0;while(!isEmptyQueue_seq(moveTo)&&(route[15]==-1)){location=frontQueue_seq(moveTo);//取队头状态为当前状态deQueue_seq(moveTo);for(movers=1;movers<=8;movers

8、<<=1)//考虑各种物品移动if((0!=(location&0x08))==(0!=(location&movers)))//农夫与移动的物品在同一侧{newlocation=location^(0x08

9、movers);//计算新状态if(safe(newlocatio