传教士和野人问题（MC问题）的A*算法实现

问题：设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？ 综合上述信息提取限制信息为： 1、修道士和野人都会划船，但船一次只能载2人； 2、在任何岸边，野人数不能超过修道士数，否则修道士将会被野人吃掉

#include 
#include 
                                        /*人工智能大作业-陈卫东-学号DY0903103*/
#define		MER	3		/*传教士总人数*/
#define		COU	3		/*野人总人数*/
#define		REN	2		/*船一次可以乘坐的最多人数*/

struct NODE
{
	int mer;						/*在左岸的传教士人数*/
	int cou;						/*在左岸的野人人数*/
	int b;						/*b的取值为1或0：当b=1表示船在左岸当b=0表示船在右岸*/
	double g;					/*该节点的g值*/
	double f;					/*该节点的f值*/
	struct NODE *pFather;		/*指向该节点的父节点*/
	struct NODE *pNext;			/*指针，在OPEN表或者CLOSED表中，指向下一个元素*/
};

struct NODE *g_pOpen = NULL;	/*OPEN表*/
struct NODE *g_pClosed = NULL;		/*CLOSED表*/


int Equal（struct NODE *pNode1 struct NODE *pNode2）             /*功能函数用于判断判断两个节点所表示的状态是否相等 ，有返回值 */         
	
{
            if （pNode1->mer == pNode2->mer &&                       /*pNode1为指向节点1的指针 ， pNode2为指向节点2的指针*/
		pNode1->cou == pNode2->cou &&
		pNode1->b == pNode2->b） return 1;
	else return 0;                                         /*当两个节点所表示的状态相等时，返回1，否则返回0*/    
 
}

struct NODE *NewNode（int mer int cou int b）                 /*功能函数用于动态产生一个节点，其状态值由参数mer，cou，b给定，有返回值 */  

{
	struct NODE *pNode = NULL;
	pNode = malloc（sizeof（struct NODE））;
	if （pNode == NULL） return NULL;
	pNode->mer = mer;
	pNode->cou = cou;
	pNode->b = b;
	pNode->g = 0;
	pNode->f = 0;
	pNode->pFather = NULL;
	pNode->pNext = NULL;
	return pNode;                                        /*当指向新产生的节点的指针，或者空间不够时，返 回NULL */ 
}

void FreeList（struct NODE *pList）                             /*功能函数用于释放动态的链表，无返回值 */  

{
	struct NODE *pNode = NULL;
	while （pList）
	{
		pNode = pList;
		pList = pList->pNext;
		free（pNode）;
	}
}

struct NODE *In（struct NODE *pNode struct NODE *pList）      /*功能函数用于判断节点是否在链表中，有返回值 */     

{
	if （pList == NULL） return NULL;                    /* pNode是指向给定节点的指针， 而pList是指向给点链表的指针 */  
	if （Equal（pNode pList）） return pList;
	return In（pNode pList->pNext）;                     /* 若pNode属于pList，返回以pNode为首的链表的后一部分；否则返回NULL */ 
}

struct NODE *Del（struct NODE *pNode struct NODE *pList）      /*功能函数用于从链表中删除不符合条件节点，有返回值 */    

{
	if （pList == NULL） return pList;
	if （Equal（pNode pList）） return pList->pNext;
	pList->pNext = Del（pNode pList->pNext）;
	return pList;                                           /*返回删除节点后的链表 */ 
}

struct NODE *AddToOpen（struct NODE *pNode struct NODE *pOpen）  /*功能函数用于将放到OPEN表中的节点函数的f值按从小到大顺序排列，有返回值 */ 

{
	if （pOpen == NULL）	                                 /*pOpen为指向OPEN表的指针*/ 
	{
		pNode -> pNext = NULL;                 /*若OPEN表为空，则pOpen=Null  */ 
		return pNode;	
	}
	if （pNode->f < pOpen->f）	/*若OPEN表非空，而给定节点的f值小于OPEN表第一个节点的f值 */ 
	{
		pNode->pNext = pOpen;	/*则排序，插入到OPEN的最前面 */ 
		return pNode;
	}
	pOpen->pNext = AddToOpen（pNode pOpen->pNext）;	/*递归函数 */ 
	return pOpen;
}

struct NODE *AddToClosed（struct NODE *pNode struct NODE *pClosed）  /*功能函数用于将符合条件的节点插入到CLOSED表中 ，有返回值 */ 

{
	pNode->pNext = pClosed;                            /*pClosed为指向CLOSED表的指针 */
	return pNode;