传教士与野人过河问题

choice=toupper(choice); if(choice=='Y') {

printf(\请输入传教士人数\ for(;;) {

scanf(\ if(x>0) {

unopened -> pr = x; break; }

else printf(\输入值应大于0！\\n请重新输入\ }

printf(\请输入野人人数\ for(;;) {

scanf(\ if(x>0) {

unopened -> sr = x; break; }

else printf(\输入值应大于0！\\n请重新输入\ }

break; }

if(choice=='N')break; }

}

int search() {

int flag;

struct SPQ *ntx; /* 提供将要扩展的结点的指针 */ for( ;; ) {

ntx = unopened; /* 从待扩展链表中提取最前面的一个 */ if(ntx->loop == maxloop) return 0;

addtoopened(ntx); /* 将ntx加入已扩展链表，并将这个节点从待扩展链表中去掉 */ flag = stretch(ntx); /* 对ntx进行扩展,返回-1,0,1 */ if(flag == 1) return 1; }

}

int stretch(struct SPQ *ntx) {

int fsr , fpr ; /* 在右岸上的人数 */ int fsl , fpl ; /* 在左岸上的人数 */

int sst , spt ; /* 出发时在船上的人数 */ int ssr , spr ; /* 返回时船上的人数 */ struct SPQ *newnode;

for (sst = 0 ; sst <= 2 ; sst++) /* 讨论不同的可能性并判断是否符合条件 */ {

fsr = ntx -> sr; fpr = ntx -> pr; fsl = ntx -> sl; fpl = ntx -> pl;

if ((sst <= fsr) && (( 2 - sst) <= fpr))/* 满足人数限制 */ {

spt = 2 - sst; fsr = fsr - sst; fpr = fpr - spt;

if((fpr == 0) && (fsr == 0))/* 搜索成功 */ {

newnode = (struct SPQ*) malloc (sizeof(spq)); if(newnode==NULL) {

printf(\内存不够！\\n\ exit(0); }

newnode -> upnode = ntx; /* 保存父结点的地址以成链表 */ newnode -> nextnode = NULL; newnode -> sr = 0; newnode -> pr = 0;

newnode -> sl = opened -> sr; newnode -> pl = opened -> pr; newnode -> sst = sst; newnode -> spt = spt; newnode -> ssr = 0; newnode -> spr = 0;

newnode -> loop = ntx -> loop + 1; oend -> nextnode = newnode; oend = newnode; openednum++; return 1; }

else if ((fpr - fsr) * fpr >= 0) /* 判断是否满足传教士人数必须大于或等于野人人数 */

{

fsl = fsl + sst; fpl = fpl + spt;

for (ssr = 0 ; ssr <= 1 ; ssr++) /* 返回 */ {

int ffsl , ffpl;

if ((ssr <= fsl) && ((1 - ssr) <= fpl)) {

spr = 1 - ssr; ffsl = fsl - ssr; ffpl = fpl - spr;

if ((ffpl - ffsl) * ffpl >= 0)

{ /* 若符合条件则分配内存并付值 */ int ffsr , ffpr; ffsr = fsr + ssr; ffpr = fpr + spr;

newnode = (struct SPQ*) malloc (sizeof(spq)); if(newnode==NULL) {

printf(\内存不够！\\n\ exit(0); }

newnode -> upnode = ntx; /* 保存父结点的地址以成链表 */ newnode -> sr = ffsr; newnode -> pr = ffpr; newnode -> sl = ffsl; newnode -> pl = ffpl; newnode -> sst = sst; newnode -> spt = spt; newnode -> ssr = ssr; newnode -> spr = spr;

newnode -> loop = ntx -> loop + 1; uend -> nextnode = newnode; uend = newnode; unopenednum++; } } } } } }

return 0; }