题目：设有n个传教士和m个野人来到河边，打算乘一只般从右岸到左岸云。该般的负载能力为两人。在任何时候，如果野人人数超过传教士人数，野人就会把传教士吃掉。他们怎样才能用这条般安全地把所有的人都渡过河去？
题目分析：
定义节点的结构：以取般的一个来回作为一步搜索，这样节点可由下面几个量进行描述：两岸的传教士人数和野人人数、本节点距离起始节点的距离，即由初始节点搜索几步后到达本节点。需要注意的是并不是所有节点都是可达的，题目中对可达节点作出了限制，只有两大 岸上的人数必须不能为负。
定义连接：两个节点间的连接可由般从右到左岸时船上的传教士人数、野人人数、船返回时船上的传教士人数、野人人数进行描述。由于船上最多只能载两个人，因此不存在取胜制问题。
有4种连接可供选择：两个人乘船到左岸，一个人返回；两个人到左岸，两个人返回；一个人到左岸，两个人返回；一个人到左岸，一个人返回。考虑到本实例的重点在于讲述搜索算法，因此程序中只考虑了第一种连接，在后面对stretch()函数的讲解中将会给出考虑4种连接的程序的修改方法。
程序源代码及讲解：
#include<stdio.h>
#include<stdlib.h>
#define maxloop 100      //最大搜索距离
#define pristnum 3      //传教士的默认初始人数
#define slavenum 3      //野人的默认初始人数
struct SPQ
{
int sr,pr;            //船运行一个来回后河右岸的野人、传教士的人数
int sl,pl; 
int ssr,spr;
int sst,spt;
int loop;
struc SPQ *upnode,*nextnode;//本结点的父结点和同表中的下一个结点的地址
}spq;
//为了使程序更加简明，这里将节咪及达到这个节点的连接合并，由结构体SPQ表示。
int loopnum;            //记录总的扩展次数
int openednum;          //记录已扩展节点个数
int umopenedum;        //记录待扩展节点个数
int resultnum;          //记录结果链表中节点的个数
struc SPQ *opened;      //已扩展链表头
struc SPQ *oend;        //已扩展链表尾
struc SPQ *unopened;    //待扩展链表头
struc SPQ *uend;        // 待扩展链表尾
struc SPQ *result;        //结果链表头
void initiate();          //初始化搜索程序
int search();              //进行搜索
int stretch(struc SPQ* ntx);    //扩展节点
void recorder();          //记录搜索到的解
void releasemem();          //释放占用内存
void showresult();          //显示解
void addtoopened(struc SPQ *ntx);    //将节点ntx从UNOPENED链表移至OPRNENED
//链表中
void goon();        //判断是否继续搜索
void main()
{
int flag;        //标记扩展是否成功
for(;;)
{
initiate();
flag=search()
if(flag==1)
{
recorder();
releasemem();
showresult();
goon();
}
else
{
printf("无法到符合条件的解")；
releasemem();
goon();
}
}
}
void initiate()
{
int x;
char choice;
uend=unopened=(struc SPQ*)malloc(sizeof(spq));
if(uend==NULL)
{
printf("\n 内存不够?\n:);
exit(0);
}
unopenednum=1;
openednum=0;
unopened -> upnode = unopened;    //保存父结点的地址以成链表
unopened -> nextnode = unopened;
unopened -> sr = slavenum;
unopened -> pr = pristnum;
unopened -> sl = 0
unopened -> pl = 0
unopened -> sst = 0
unopened -> spt = 0
unopened -> ssr = 0
unopened -> spr = 0
unopened -> loop = 0
printf("题目：设有n个传教士和m个野人来到河边，打算乘一只船从右岸到\n","左岸去.该船的负载能力为两个.在任何时候，如果野人人数\n",
"超过传教士人数，野人就会把传教士吃掉 。他们怎样才能用\n",
"这条船安全地把所有人都渡过河去?\n");
printf("默认的n、m值皆为3");
for(;;)
{
printf("是否修改?(Y/N)");
scanf("%s",& choice);
choice = toupper (choice);
if(choice == 'Y')
{
printf("请输入传教士人数")；
for(;;)
{
scanf("%d",&x);
if(x>0)
{
unopened -> pr = x;
break;
}
else printf("\n输入值应大于0!\n请重新输入");
}
printf("请输入野人人数");
for(;;)
{
scanf("%d",&x);
if(x>0)
{
unopened -> sr = x;
break;
}
else printf("\n输入值应大于0!\n请重新输入");
}
break;
}
if(choice=='N')break;
}
}
int search()
{
int flag;
struc SPQ *ntx;      //提供将要扩展的结点的指针
for(;;)
{
ntx = unopened;    //从待扩展链表中提取最前面的一个
if(ntx->loop == maxloop)
return 0;
addtoopened(ntx);    //将加入已扩展链表，并从待扩展链表中去掉
flag = stretch(ntx);  //对ntx进行扩展
if(flag == 1)
return 1;
}
}
search()函数实现对问题解得搜索过程，它首先从待扩展链表中取出链表的第一个节点，将其放入已扩展链表的尾部，然后调用stretch()函数对这个节点进行扩展.当扩展的节点距初始节点距离已经达到事先规定的最大搜索距离时判定搜索失败.
int stretch(struc SPQ *ntx)
{
int fsr , fpr ; // 在右岸上的人
数   
int fsr , fpr ; // 在左岸上的人数 
int sst , fpr ; // 出发时在船上的人数
int sst , fpr ; // 返回时船上的人数
struc SPQ *newnode;
for (sst = 0 ; sst<= 2 ; sst++)
{  // 循环中的上限"2"代表从左岸到右岸船上的总人数，当考虑4种情况
//时可用一变量代替，取值范围为1、2.
far = ntx -> sr;
fpe = ntx -> pr;
fsl = ntx -> sl;
fpl = ntx -> pl;
if ((sst <= fsr) && ((2 -sst) <= fpr))//满足人数限制
{
spt = 2 - sst;
far = fsr - sst;
fpr = fpr - spt;
if((fpr == 0) && (fsr == 0))
{        //右岸人数为0，搜索成功
newnode = (struc SPQ*) malloc (sizeof(spq));
if(newnode==NULL)
{
printf("\n内存不够!\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;
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))
{  // 若符合条件则分配内存并赋值
int ffsr , ffpr;
ffsr = fsr + ssr;
ffpl = fpl - spr;
newnode = (struc SPQ*) malloc (sizeof(spq));
if(newnode==NULL)
{
printf("\n内存不够!\n")；
exit(0);
}
newnode -> upnode = ntx;
newnode -> sr = ffsr;
newnode -> pr = ffpr;
newnode -> sl = ffsl;
newnode -> pl = ffpl;
newnode -> sst = sst;
newnode -> spt = spr;
newnode -> ssr = ssr;
newnode -> spr = spr;
newnode -> loop = ntx -> loop + 1;
uend -> nextnode = newnode;
uend = newnode;
unopenednum++;
}
}
}
}
}
}
return 0;
}
stretch()函数负责对具体的节点进行展开，展开的过程必须满足对节点的限制条件，除
目标节点之外其他新展开的节点被依次存入UNOPENED链表的尾部，目标节点由于已没有必要再进行扩展，因此直接存入OPENED链表中.
void addtoopened(struc SPQ *ntx)
{
unopened = unopened -> nextnode;
unopenednum--;
if (openednum == 0)
oend = opened = ntx;
oend -> nextnode = ntx;
oend =ntx;
openednum++;
}
addtoopened()函数将节点ntx从UNOPENED链表中去除，将其后续节点作为UNOPENED链表的头节点，并将ntx存入OPENED链表的尾部，表示此节点已被展开.
void recorder()
{
int i , loop;
struc SPQ *newnode , *ntx;
loop = oend -> loop;
ntx = oend;
resultnum = 0;
for (i = 0 ; i <= loop ; i++)
{
newnode = (struc SPQ*) malloc (sizeof(spq));
if(newnode==NULL)
{
printf("\n内存不够!\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++;
}
}
recorder()函数在搜索成功后负责从目标节点延已扩展出的树状结构反向寻到解路径，并以压堆栈的形式存入以result节点为顶节点的链表中.
void releasemem()
{
int i;
struc 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);
左岸右岸}
}
releasemem()释放OPENED和UNOPENED两个链表所占用的内存.
void showresult()
{    int i;
int fsl , fpr ;    //在右岸上的人数
int fsl , fpr ;    //在左岸上的人数
int fsl , fpr ;    //出发时船上的人数
int fsl , fpr ;    //返回时船上的人数
struc SPQ * nodefree;
printf("河的右岸有%d个传教士" , result -> pr);
printf("%d个野人 \n" , result -> sr);
printf("河的左岸有%d个传教士" , result -> pl);
printf("%d个野人 \n" , result -> sl);
for ( i = 1 ; i < resultnum ; i++)
{
nodefree = result;
result = result -> nextnode;
free(nodefree);
printf("\n\t左岸人数 船上人数及方向 右岸人数\n");
printf("第%d轮\n",i);
fpl = result -> pl - result ->spt + result -> spr;
fpl = result -> pr - result ->spr;
fsl = result -> sl - result ->ss
t + result -> ssr;
fsr = result -> sr -result -> ssr;
spt = result -> spt;
sst = result -> sst;
printf("传教士%8d %8d \t <- \t *8d \n" , fpl, spt , fpr);
printf("野人%8d %8d \t <- \t %8d \n" , fsl, sst , fsr);
fpl = result -> pl;
fpr = result -> pr - result -> spr;
fsl =result -> sl;
fsr = result -> sr - result -> ssr;
spr = result -> spr;
ssr = result -> ssr;
printf("传教士 %8d %8d \t -> \t %8d \n" , fpl , spr ,fpr);
printf("野人 %8d %8d \t -> \t %8d \n" , fsl ,ssr ,fsr);
}
printf("\n全体传教士和野人全部到达对岸");
free(result);
}
showresult()函数负责显示搜索的结果，并同步释放RESULT链表所占用的内存.
void goon()
{
char choice;
for(;;)
{  printf("是否继续?(Y/N)\n");
scanf ("%s",&choice);
choice=toupper(choice);
if(choice=='Y')break;
if(choice=='N')exit(0);
}
}