/***   A*算法******/

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

struct NODE
{
	char a[3][3];				//表示8數碼狀態的矩陣
	int i0;						//(i0,j0)表示0所在的位置
	int j0;						//
	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表

struct NODE g_Goal = {{{1, 2, 3}, {8, 0, 4}, {7, 6, 5}}, 
                      1, 1, 0, 0, NULL, NULL};	//初始化一個目標節點

int Equal(struct NODE *pNode1, struct NODE *pNode2)
/******************************************************
 * 功能：判斷兩個節點所表示的狀態是否相等             *
 *                                                    *
 * 入口參數：                                         *
 *   pNode1：指向節點1的指針                          *
 *   pNode2：指向節點2的指針                          *
 *                                                    *
 * 返回值：當兩個節點所表示的狀態相等時，返回1，否則  *
 *         返回0                                      *
 ******************************************************/
{
	int i, j;
	for (i = 0; i < 3; i++)
	{
		for (j = 0; j < 3; j++)
		{
			if (pNode1->a[i][j] != pNode2->a[i][j])
				return 0;
		}
	}
	return 1;
}

struct NODE *NewNode(int i00, int i01, int i02,
					 int i10, int i11, int i12,
					 int i20, int i21, int i22)
/******************************************************
 * 功能：動態產生一個節點                             *
 *                                                    *
 * 入口參數：                                         *
 *   i00~i22：給出8數碼問題的一個狀態，分別為狀態矩陣 *
 *            [0,0]~ [2,2]元素                        *
 *                                                    *
 * 返回值：指向新產生的節點的指針，或者空間不夠用時， *
 *         返回NULL                                   *
 ******************************************************/
{
	struct NODE *pNode = NULL;
	int i, j;
	int bEnd = 0;
	pNode = malloc(sizeof(struct NODE));

	if (pNode == NULL) return NULL;	//當申請不到空間時，返回NULL

	pNode->a[0][0] = i00;
	pNode->a[0][1] = i01;
	pNode->a[0][2] = i02;
	pNode->a[1][0] = i10;
	pNode->a[1][1] = i11;
	pNode->a[1][2] = i12;
	pNode->a[2][0] = i20;
	pNode->a[2][1] = i21;
	pNode->a[2][2] = i22;

	pNode->g = 0;
	pNode->f = 0;
	pNode->pFather = NULL;
	pNode->pNext = NULL;

	//找'0'所在的位置，并記錄
	for (i = 0; i < 3; i++)
	{
		for (j = 0; j < 3; j++)
		{
			if (pNode->a[i][j] == 0)
			{
				pNode->i0 = i;
				pNode->j0 = j;
				bEnd = 1;
				break;
			}
		}
		if (bEnd) break;
	}

	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 PrintNode(struct NODE *pNode)
/******************************************************
 * 功能：在屏幕上打印一個節點，用于調試程序           *
 *                                                    *
 * 入口參數：                                         *
 *   pNode：指向節點的指針                            *
 *                                                    *
 * 返回值：無                                         *
 ******************************************************/
{
	int i, j;
	for (i = 0; i < 3; i++)
	{
		printf("|");
		for (j = 0; j < 3; j++)
		{
			printf(" %1d", pNode->a[i][j]);
		}
		printf(" |\n");
	}
	printf("(i0 = %d, j0 = %d, g = %f, f = %f)\n", 
		pNode->i0, pNode->j0, pNode->g, pNode->f);
}

void PrintList(struct NODE *pList)
/******************************************************
 * 功能：在屏幕上打印一個鏈表，用于調試程序           *
 *                                                    *
 * 入口參數：                                         *
 *   pList：指向鏈表的指針                            *
 *                                                    *
 * 返回值：無                                         *
 ******************************************************/
{
	while (pList)	//依次打印鏈表
	{
		PrintNode(pList);
		pList = pList->pNext;
	}