*********************************************************************本函数是用A*算法来实现八数码的问题***算法的步骤如下：*1、初始化两个链表open和closed，将初始状态放入open表中*2、重复下列过程，直至找到目标结点为止，如果open表为空，那*么查找失败；*3、从open表中拿出具有最小f值的结点(将这一结点称为BESTNODE)，*并放入closed表中；*4、如果BESTNODE为目标结点，成功求得解,退出循环；*5、如果BESTNODE不是目标结点，那么产生它的后继结点(此后继结*点与其祖先的状态不同)，后继结点组成一个链表；*6、对每个后继结点进行以下过程：*7、建立它到BESTNODE的parent指针；*8、如果此结点在open表中，首先将open表中的结点添加进BESTNODE*的后继结点链中，然后计算两个结点的g值，如果此结点的g值小*于open表中的结点时，open表中的结点改变parent指针，同时将*此结点删除；*9、如果此结点在closed表中，首先将closed表中的结点添加进BESTNODE*的后继结点中，然后计算两个结点的g值，如果此结点的g值小于*closed表中的结点时，closed表中的结点改变parent指针；将*closed表中的结点重新放入open表中，同时将此结点删除；*10、如果此结点既不在open表中也不再closed表中，那么添加此结点至*BESTNODE的后继结点链中。***Author:转载作者不详。**2011.5.16**********************************************************************/#include"stdafx.h"#include#include#include#definesize3usingnamespacestd;//定义二维数组来存储数据表示某一个特定状态typedefintstatus[size][size];structSpringLink;//定义状态图中的结点数据结构typedefstructNode{statusdata;//结点所存储的状态Node*parent;//指向结点的父亲结点SpringLink*child;//指向结点的后继结点intfvalue;//结点的总的路径intgvalue;//结点的实际路径inthvalue;//结点的到达目标的苦难程度Node*next;//指向open或者closed表中的后一个结点}NNode,*PNode;//定义存储指向结点后继结点的指针的地址typedefstructSpringLink{Node*pointData;//指向结点的指针SpringLink*next;//指向兄第结点}SPLink,*PSPLink;//定义open表和close表PNodeopen;PNodeclosed;//开始状态与目标状态statusstartt={2,8,3,1,6,4,7,0,5};statustarget={1,2,3,8,0,4,7,6,5};//初始化一个空链表voidinitLink(PNode&Head){Head=(PNode)malloc(sizeof(NNode));Head->next=NULL;}//判断链表是否为空boolisEmpty(PNodeHead){if(Head->next==NULL)returntrue;elsereturnfalse;}//从链表中拿出一个数据，通过FNode返回voidpopNode(PNode&Head,PNode&FNode){if(isEmpty(Head)){FNode=NULL;return;}FNode=Head->next;Head->next=Head->next->next;FNode->next=NULL;}//向结点的(最终)后继结点链表中添加新的子结点voidaddSpringNode(PNode&Head,PNodenewData){PSPLinknewNode=(PSPLink)malloc(sizeof(SPLink));newNode->pointData=newData;newNode->next=Head->child;Head->child=newNode;}//释放状态图中存放结点后继结点地址的空间//注意传入参数PSPLink引用类型voidfreeSpringLink(PSPLink&Head){PSPLinktmm;while(Head!=NULL){tmm=Head;Head=Head->next;free(tmm);}}//释放open表与closed表中的资源voidfreeLink(PNode&Head){PNodetmn;tmn=Head;Head=Head->next;free(tmn);while(Head!=NULL){//首先释放存放结点后继结点地址的空间freeSpringLink(Head->child);tmn=Head;Head=Head->next;free(tmn);}}//向普通链表中添加一个结点voidaddNode(PNode&Head,PNode&newNode){newNode->next=Head->next;Head->next=newNode;}//向非递减排列的链表中添加一个结点voidaddAscNode(PNode&Head,PNode&newNode){PNodeP;PNodeQ;P=Head->next;Q=Head;while(P!=NULL&&P->fvaluefvalue){Q=P;P=P->next;}//上面判断好位置之后，下面就是简单的插入了newNode->next=Q->next;Q->next=newNode;}//计算结点额h值，当前节点与目标节点数码错位个数intcomputeHValue(PNodetheNode){intnum=0;for(inti=0;i<3;i++){for(intj=0;...
