#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?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;?????????????????????