1、程序源代码
#include <>
#include<>
struct node{
i nt a[3][3];//用二维数组存放8数码
int hx;//函数h（x）的值，表示与目标状态的差距
s truct node *parent;//指向父结点的指针
s truct node *next;//指向链表中下一个结点的指针
};
//------------------hx函数-------------------//
int hx(int s[3][3])
{//函数说明：计算s与目标状态的差距值
i nt i,j;
i nt hx=0;
i nt sg[3][3]={1,2,3,8,0,4,7,6,5};
f or(i=0;i<3;i++)
for(j=0;j<3;j++)
if(s[i][j]!=sg[i][j])
hx++;
return hx;
}
//-------------hx函数end----------------------//
//-------------extend扩展函数----------------//
struct node *extend(node *ex)
{ //函数说明：扩展ex指向的结点，并将扩展所得结点组成一条//单链表，head指向该链表首结点，并且作为返回值
i nt i,j,m,n; //循环变量
i nt t; //临时替换变量
i nt flag=0;
i nt x[3][3];//临时存放二维数组
s truct node *p,*q,*head;
head=(node *)malloc(sizeof(node));//head
p=head;
q=head;
h ead->next=NULL;//初始化
f or(i=0;i<3;i++)//找到二维数组中0的位置
{
for(j=0;j<3;j++)
if(ex->a[i][j]==0)
{
flag=1;
break;
}
if(flag==1)
break;
}
for(m=0;m<3;m++)//将ex->a赋给x
for(n=0;n<3;n++)
x[m][n]=ex->a[m][n];
//根据0的位置的不同，对x进行相应的变换
//情况1
if(i-1>=0)
{
t=x[i][j];x[i][j]=x[i-1][j];x[i-1][j]=t;
flag=0;
for(m=0;m<3;m++)//将x赋给a
for(n=0;n<3;n++)
if(x[m][n]==ex->parent->a[m][n])
flag++;
if(flag!=9)
{
q=(node *)malloc(sizeof(node));
for(m=0;m<3;m++)//将x赋给a
for(n=0;n<3;n++)
q->a[m][n]=x[m][n];
q->parent=ex;
q->hx=hx(q->a);
q->next=NULL;
p->next=q;
p=p->next;
}
}
//情况2
for(m=0;m<3;m++)//将ex->a重新赋给x，即还原x for(n=0;n<3;n++)
x[m][n]=ex->a[m][n];
i f(i+1<=2)
{
t=x[i][j];x[i][j]=x[i+1][j];x[i+1][j]=t;
flag=0;
for(m=0;m<3;m++)
for(n=0;n<3;n++)
if(x[m][n]==ex->parent->a[m][n])
flag++;
if(flag!=9)
{
q=(node *)malloc(sizeof(node));
for(m=0;m<3;m++)//将x赋给a
for(n=0;n<3;n++)
q->a[m][n]=x[m][n];
q->parent=ex;
q->hx=hx(q->a);
q->next=NULL;
p->next=q;
p=p->next;
}
}
//情况3
f or(m=0;m<3;m++)//将ex->a重新赋给x，即还原x
for(n=0;n<3;n++)
x[m][n]=ex->a[m][n];
i f(j-1>=0)
{
t=x[i][j];x[i][j]=x[i][j-1];x[i][j-1]=t;
flag=0;
for(m=0;m<3;m++)
for(n=0;n<3;n++)
if(x[m][n]==ex->parent->a[m][n])
flag++;
if(flag!=9)
{
q=(node *)malloc(sizeof(node));
for(m=0;m<3;m++)//将x赋给a
for(n=0;n<3;n++)
q->a[m][n]=x[m][n];
q->parent=ex;
q->hx=hx(q->a);
