{

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; }

void addtoopened(struct SPQ *ntx) {

unopened = unopened -> nextnode; unopenednum--; if (openednum == 0 )

oend = opened = ntx; oend -> nextnode = ntx; oend = ntx; openednum++; }

void recorder() {

int i , loop;

struct SPQ *newnode; struct SPQ *ntx; loop = oend -> loop; ntx = oend; resultnum = 0;

for( i = 0 ; i <= loop ; i++ ) {

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

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

newnode -> sr = ntx -> sr; newnode -> pr = ntx -> pr;

newnode -> sl = ntx -> sl; newnode -> pl = ntx -> pl; newnode -> sst = ntx -> sst; newnode -> spt = ntx -> spt; newnode -> ssr = ntx -> ssr; newnode -> spr = ntx -> spr; newnode -> nextnode = NULL; ntx = ntx -> upnode; if(i == 0)

result = newnode;

newnode -> nextnode = result; result = newnode; resultnum++; } }

void releasemem() {

int i;

struct SPQ* nodefree;

for ( i = 1 ; i < openednum ; i++ ) {

nodefree = opened;

opened = opened -> nextnode; free(nodefree); }

for ( i = 0 ; i < unopenednum ; i++ ) {

nodefree = unopened;

unopened = unopened -> nextnode; free(nodefree); } }

void showresult() {

int i;

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

printf(\个传教士\ printf(\个野人\ printf(\个传教士\ printf(\个野人\ for ( i = 1 ; i < resultnum ; i++ ) {