发布时间 : 星期二 文章数据结构课程设计报告（农夫过河）更新完毕开始阅读1c9c3d9f51e79b89680226f5
初始状态出发点入队列;所有其他点状态标记为未访问;
while ( ! isEmptyQueue seq ( moveTo) &&( route[ 15] == - 1) ) {
从moveTo 取出一个状态;试探所有由这个状态出发可能到达的状态; if( 能到达的状态安全且未访问过) {
记录到它的路径; 压入队列; } } }
精化上速算法得到问题的具体算法如下: void farmerProblem( ) {
int movers, i, location, newlocation; int route[16]; //记录已考虑的状态路径 int print[MAXNUM];
PSeqQueue moveTo;
moveTo = createEmptyQueue_seq( );//新的队列判断路径 enQueue_seq(moveTo, 0x00); //初始状态为0 for (i = 0; i < 16; i++)
route[i] = -1; //-1表示没有记录过路径 route[0]=0;
while (!isEmptyQueue_seq(moveTo)&&(route[15]== -1))//队列不为空，路径未 {
location = frontQueue_seq(moveTo); //从队头出队，location表示位置，0 deQueue_seq(moveTo);//已出队的删除
满时循环
为北岸，1为南岸
for (movers = 1; movers <= 8; movers<<= 1) //向左移位，movers分别0001，0010，0100，1000,也就是依次判断过河的可行性
{
if ((0 != (location & 0x08)) == (0 != (location & movers)))//判断 {
5
农夫和要移动的物品是否在同岸
newlocation = location^(0x08|movers);//过岸
if (safe(newlocation) && (route[newlocation] == -1))//判断是
否安全，以及路径是否可用
{
route[newlocation] = location;
enQueue_seq(moveTo, newlocation);//记录路径并入队，位置改
变
4、运行与测试
6
5、总结与心得
“纸上得来终觉浅，绝知此事要躬行。”通过这两周的课程设计，使我对书上的的理论知识有了更深的理解，也使我对于团队合作有了新的认识，意识到团队的力量。课程设计是一个必须经历的过程，是我们理解书本知识、熟悉所学专业的一次很好实践。 在这次设计过程中，体现出自己单独设计程序的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补。
附录
#include
typedef struct //顺序队列类型定义 { int f, r; //f表示头，r 表示尾 int q[MAXNUM];//顺序队
}SeqQueue ,*PSeqQueue;
PSeqQueue createEmptyQueue_seq( ) //创建队列 { PSeqQueue paqu = new SeqQueue; if (paqu == NULL) cout<<\ else
paqu->f=paqu->r=0; return (paqu);
}
int isEmptyQueue_seq( PSeqQueue paqu ) //判断 paqu 所指是否是空队列{
return paqu->f==paqu->r; }
void enQueue_seq(PSeqQueue paqu,int x) //在队列中插入一元素 x {
7
}
if ((paqu->r+1)%MAXNUM==paqu->f) { }
paqu->q[paqu->r]=x;
paqu->r=(paqu->r+1)%MAXNUM; cout<<\队列已满.\else
void deQueue_seq(PSeqQueue paqu) //删除队列头部元素 { }
int frontQueue_seq( PSeqQueue paqu ) //对非空队列,求队列头部元素 { }
int farmer(int location) //判断农夫位置对0做与运算，还是原来的数字，用来判断位置 {
return 0 != (location & 0x08); }
int wolf(int location) //判断狼位置 { }
int cabbage(int location) //判断白菜位置 {
return 0 != (location & 0x02); }
int goat(int location) //判断羊的位置 {
if( paqu->f==paqu->r)
cout<<\队列为空\ paqu->f=(paqu->f+1)%MAXNUM; else
return (paqu->q[paqu->f]);
return 0 != (location & 0x04);
return 0 !=(location & 0x01);
8