A_Star_8.rar_八数码_八数码C语言

/***************************************************************** * 程 序 说 明 * * 功能: 用A*算法求解8数码问题 * * 说明: * * 本程序按照《人工智能》一书所介绍的A*算法求解8数码问题。 * * 表示：用3*3矩阵表示8数码的一个状态，左上角位置为(0, 0), 右下 * * 角位置为(2, 2), 1~8表示8个数码，0表示空白位置。 * * * * 注意: 该程序尽可能用与算法一致的思路实现算法, 力求简单明了, * * 注重算法的清晰性，而没有考虑算法的效率问题。 * * * *****************************************************************/ #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 Pri