正文描述:《用顺序队列解决农夫过河问题的算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
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
显示全部收起
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。