/*********************************************************************************
 *          程  序  說  明                                                       *
 * 功能: 用A*算法求解傳教士與野人問題。M=C=5, K=3                                *
 * 說明:                                                                         *
 *     本程序按照《人工智能導論》一書所介紹的A*算法求解傳教士與野人問題。        *
 *                                                                               *
 * 注意: 該程序盡可能用與算法一致的思路實現算法, 力求簡單明了, 注重算法的清晰性，*
 * 而沒有考慮算法的效率問題。                                                    *
 *********************************************************************************/

#include <stdio.h>
#include <stdlib.h>

#define		M	5		//傳教士總人數
#define		C	5		//野人總人數
#define		K	3		//船一次可以乘坐的最多人數

struct NODE
{
	int m;						//在左岸的傳教士人數
	int c;						//在左岸的野人人數
	int b;						//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)
/******************************************************
 * 功能：判斷兩個節點所表示的狀態是否相等             *
 *                                                    *
 * 入口參數：                                         *
 *   pNode1：指向節點1的指針                          *
 *   pNode2：指向節點2的指針                          *
 *                                                    *
 * 返回值：當兩個節點所表示的狀態相等時，返回1，否則  *
 *         返回0                                      *
 ******************************************************/
{
	if (pNode1->m == pNode2->m &&
		pNode1->c == pNode2->c &&
		pNode1->b == pNode2->b) return 1;
	else return 0;
}

struct NODE *NewNode(int m, int c, int b)
/******************************************************
 * 功能：動態產生一個節點，其狀態值由參數m，c，b給定。*
 *                                                    *
 * 入口參數：                                         *
 *   m：河左岸的傳教士人數                            *
 *   c：河左岸的野人人數                              *
 *   b：船是否在左岸，1：表示在左岸，0：表示不在左岸  *
 *                                                    *
 * 返回值：指向新產生的節點的指針，或者空間不夠時，返 *
 *         回NULL                                     *
 ******************************************************/
{
	struct NODE *pNode = NULL;
	pNode = malloc(sizeof(struct NODE));
	if (pNode == NULL) return NULL;
	pNode->m = m;
	pNode->c = c;
	pNode->b = b;
	pNode->g = 0;
	pNode->f = 0;
	pNode->pFather = NULL;
	pNode->pNext = NULL;
	return pNode;
}

void FreeList(struct NODE *pList)
/******************************************************
 * 功能：釋放動態產生的鏈表                           *
 *                                                    *
 * 入口參數：                                         *
 *   pList：指向OPEN表或者CLOSED表的指針              *
 *                                                    *
 * 返回值：無                                         *
 ******************************************************/
{
	struct NODE *pNode = NULL;
	while (pList)
	{
		pNode = pList;
		pList = pList->pNext;
		free(pNode);
	}
}

struct NODE *In(struct NODE *pNode, struct NODE *pList)
/******************************************************
 * 功能：判斷一個節點是否在一個鏈表中                 *
 *                                                    *
 * 入口參數：                                         *
 *   pNode：指向給定節點的指針                        *
 *   pList：指向給點鏈表的指針                        *
 *                                                    *
 * 返回值：當pNode在pList中時，返回以pNode為首的鏈表  *
 *         的后一部分；否則返回NULL                   *
 ******************************************************/
{
	if (pList == NULL) return NULL;
	if (Equal(pNode, pList)) return pList;
	return In(pNode, pList->pNext);
}

struct NODE *Del(struct NODE *pNode, struct NODE *pList)
/******************************************************
 * 功能：從鏈表pList中刪除節點pNode                   *
 *                                                    *
 * 入口參數：                                         *
 *   pNode：指向給定節點的指針                        *
 *   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)
/******************************************************
 * 功能：將一個節點按照f值（從小到大）插入到OPEN表中  *
 *                                                    *
 * 入口參數：                                         *
 *   pNode: 指向給定節點的指針                        *
 *   pOpen：指向OPEN表的指針                          *
 *                                                    *
 * 返回值：指向插入給定節點后OPEN表的指針             *
 *                                                    *
 * 注意：同一個節點（具有相同指針的一個節點），只能向 *
 *       表中添加一次，否則可能會造成循環鏈表         *
 ******************************************************/
{
	if (pOpen == NULL)	//OPEN表為空
	{
		pNode -> pNext = NULL;
		return pNode;	
	}
	if (pNode->f < pOpen->f)	//給定節點的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: 指向給定節點的指針                        *
 *   pClosed：指向CLOSED表的指針                      *
 *                                                    *
 * 返回值：指向插入給定節點后CLOSED表的指針           *
 *                                                    *
 * 注意：同一個節點（具有相同指針的一個節點），只能向 *
 *       表中添加一次，否則可能會造成循環鏈表         *
 ******************************************************/
{
	pNode->pNext = pClosed;
	return pNode;
}

void PrintList(struct NODE *pList)
/******************************************************
 * 功能：在屏幕上打印一個鏈表，用于調試程序           *
 *                                                    *
 * 入口參數：                                         *
 *   pList：指向鏈表的指針                            *
 *                                                    *
 * 返回值：無                                         *
 ******************************************************/
{
	while (pList)	//依次打印鏈表
	{
		printf("((%d %d %d) %f %f)\n", pList->m, pList->c, pList->b, pList->g, pList->f);
		pList = pList->pNext;
	}
}

void PrintNode(struct NODE *pNode)
/******************************************************
 * 功能：在屏幕上打印一個節點，用于調試程序           *
 *                                                    *
 * 入口參數：                                         *
 *   pNode：指向節點的指針                            *