{
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++ ) {