用顺序队列解决农夫过河问题的算法

《用顺序队列解决农夫过河问题的算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、/*用队列解决农夫过河问题的算法*/#include#include#defineMAXNUM20typedefintDataType;structSeqQueue{/*顺序队列类型定义*/intf,r;DataTypeq[MAXNUM];};typedefstructSeqQueue*PSeqQueue;/*顺序队列类型的指针类型*/PSeqQueuecreateEmptyQueue_seq(void){PSeqQueuepaqu=(PSeqQueue)malloc(sizeof(structSeqQueue));if(

2、paqu==NULL)printf("Outofspace!!");elsepaqu->f=paqu->r=0;return(paqu);}intisEmptyQueue_seq(PSeqQueuepaqu){returnpaqu->f==paqu->r;}/*在队列中插入一元素x*/voidenQueue_seq(PSeqQueuepaqu,DataTypex){if((paqu->r+1)%MAXNUM==paqu->f)printf("Fullqueue.");else{paqu->q[paqu->r]=x;paqu->r=(paqu->r+1)

3、%MAXNUM;}}/*删除队列头部元素*/voiddeQueue_seq(PSeqQueuepaqu){if(paqu->f==paqu->r)printf("EmptyQueue.");elsepaqu->f=(paqu->f+1)%MAXNUM;}/*对非空队列,求队列头部元素*/DataTypefrontQueue_seq(PSeqQueuepaqu){return(paqu->q[paqu->f]);}intfarmer(intlocation){return0!=(location&0x08);}intwolf(intlocation){ret

4、urn0!=(location&0x04);}intcabbage(intlocation){return0!=(location&0x02);}intgoat(intlocation){return0!=(location&0x01);}/*若状态安全则返回true*/intsafe(intlocation){/*羊吃白菜*/if((goat(location)==cabbage(location))&&(goat(location)!=farmer(location)))return0;/*狼吃羊*/if((goat(location)==wolf(loc

5、ation))&&(goat(location)!=farmer(location)))return0;return1;/*其他状态是安全的*/}voidfarmerProblem(){intmovers,i,location,newlocation;introute[16];/*记录已考虑的状态路径*/PSeqQueuemoveTo;/*准备初值*/moveTo=createEmptyQueue_seq();enQueue_seq(moveTo,0x00);for(i=0;i<16;i++)route[i]=-1;route[0]=0;/*开始移动*/whi

6、le(!isEmptyQueue_seq(moveTo)&&(route[15]==-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

7、movers);if(safe(newlocation)&&(r

8、oute[newlocation]==-1)){route[newlocation]=location;enQueue_seq(moveTo,newlocation);}}}}/*打印出路径*/if(route[15]!=-1){printf("Thereversepathis:");for(location=15;location>=0;location=route[location]){printf("Thelocationis:%d",location);if(location==0)return;}}elseprintf("Nosolution

9、.");}intmain(){fa