数据结构与算法 农夫过河问题.doc

/ farmerProblem.c/ 用队列解决农夫过河问题 #include #include typedef int DataType; /顺序队列：类型和界面函数声明 struct SeqQueue / 顺序队列类型定义 int MAXNUM; / 队列中最大元素个数 int f, r; DataType *q;typedef struct SeqQueue *PSeqQueue; / 顺序队列类型的指针类型 PSeqQueue createEmptyQueue_seq(int m) /创建一个空队列 PSeqQueue queue = (PSeqQueue)malloc(sizeof(struct SeqQueue); if (queue != NULL) queue-q = (DataType*)malloc(sizeof(DataType) *m); if (queue-q) queue-MAXNUM = m; queue-f = 0; queue-r = 0; return (queue); else free(queue); printf(Out of space!n); / 存储分配失败 return NULL; int isEmptyQueue_seq(PSeqQueue queue) /判断队列是否为空 return (queue-f = queue-r); void enQueue_seq(PSeqQueue queue, DataType x)/ 在队尾插入元素x if (queue-r + 1) % queue-MAXNUM = queue-f) printf(Full queue.n); else queue-qqueue-r = x; queue-r = (queue-r + 1) % queue-MAXNUM; void deQueue_seq(PSeqQueue queue)/ 删除队列头部元素 if (queue-f = queue-r) printf(Empty Queue.n); else queue-f = (queue-f + 1) % queue-MAXNUM; DataType frontQueue_seq(PSeqQueue queue) if (queue-f = queue-r) printf(Empty Queue.n); else return (queue-qqueue-f); /个体状态判断函数int farmer(int location) /判断农夫的位置 return (0 != (location &0x08); int wolf(int location) /判断狼的位置 return (0 != (location &0x04); int cabbage(int location) /判断白菜的位置 return (0 != (location &0x02); int goat(int location) /判断羊的位置 return (0 != (location &0x01); /安全状态的判断函数int safe(int location) / 若状态安全则返回true if (goat(location) = cabbage(location) & (goat(location) != farmer (location) return (0); / 羊吃白菜 if (goat(location) = wolf(location) & (goat(location) != farmer (location) return (0); / 狼吃羊 return (1); / 其他状态是安全的 main() int i, movers, location, newlocation; int route16; /用于记录已考虑的状态路径 PSeqQueue moveTo; /用于记录可以安全到达的中间状态 moveTo = createEmptyQueue_seq(20); /创建空队列 enQueue_seq(moveTo, 0x00); /初始状态进队列 for (i = 0; i 16; i+) routei = - 1; /准备数组route初值 route0 = 0; while (!isEmptyQueue_seq(moveTo) & (route15 = - 1) location = frontQueue_seq(moveTo); /取队头状态为当前状态 deQueue_seq(moveTo); for (movers = 1; movers = 8; movers = 0; location = routelocation)