農(nóng)夫過河文本文檔.doc

/ farmerProblem.c/ 用隊列解決農(nóng)夫過河問題#include #include typedef int DataType;/順序隊列：類型和界面函數(shù)聲明struct SeqQueue / 順序隊列類型定義 int MAXNUM; / 隊列中最大元素個數(shù) int f, r; DataType *q;typedef struct SeqQueue *PSeqQueue; / 順序隊列類型的指針類型PSeqQueue createEmptyQueue_seq(int m) /創(chuàng)建一個空隊列 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);/個體狀態(tài)判斷函數(shù)int farmer(int location) /判斷農(nóng)夫的位置 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);/安全狀態(tài)的判斷函數(shù)int safe(int location) / 若狀態(tài)安全則返回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); / 其他狀態(tài)是安全的main() int i, movers, location, newlocation; int route16; /用于記錄已考慮的狀態(tài)路徑 PSeqQueue moveTo; /用于記錄可以安全到達(dá)的中間狀態(tài) moveTo = createEmptyQueue_seq(20); /創(chuàng)建空隊列 enQueue_seq(moveTo, 0x00); /初始狀態(tài)進(jìn)隊列 for (i = 0; i 16; i+) routei = - 1; /準(zhǔn)備數(shù)組route初值 route0 = 0; while (!isEmptyQueue_seq(moveTo) & (route15 = - 1) location = frontQueue_seq(moveTo); /取隊頭狀態(tài)為當(dāng)前狀態(tài) deQueue_seq(moveTo); for (movers = 1; movers = 8; movers = 0; location = routelocatio