启发式搜索解决八数码问题.docx

#include <>
#include <>
#include <>
typedef struct Node
{//节点结构体
int data[9];
double f,g;
struct Node * parent;
}Node,*Lnode;
typedef struct Stack
{//OPEN CLOSED 表结构体
Node * npoint;
struct Stack * next;
}Stack,* Lstack;
Node * Minf(Lstack * Open)
{//选取OPEN表上f值最小的节点,返回该节点地址
Lstack temp = (*Open)->next,min = (*Open)->next,minp = (*Open);
Node * minx;
while(temp->next != NULL)
{
if((temp->next ->npoint->f) < (min->npoint->f))
{
min = temp->next;
minp = temp;
}
temp = temp->next;
}
minx = min->npoint;
temp = minp->next;
minp->next = minp->next->next;
free(temp);
return minx;
}
int Canslove(Node * suc, Node * goal)
{//判断是否可解
int a = 0,b = 0,i,j;
for(i = 1; i< 9;i++)
for(j = 0;j < i;j++)
{
if((suc->data[i] > suc->data[j]) && suc->data[j] != 0)a++;
if((goal->data[i] > goal->data[j]) && goal->data[j] != 0)b++;
}
if(a%2 == b%2)return 1;
else return 0;
}
int Equal(Node * suc,Node * goal)
{//判断节点是否相等,相等,不相等
for(int i = 0; i < 9; i ++ )
if(suc->data[i] != goal->data[i])return 0;
return 1;
}
Node * Belong(Node * suc,Lstack * list)
{//判断节点是否属于OPEN表或CLOSED表,是则返回节点地址,否则返回空地址
Lstack temp = (*list) -> next ;
if(temp == NULL)return NULL;
while(temp != NULL)
{
if(Equal(suc,temp->npoint))return temp -> npoint;
temp = temp->next;
}
return NULL;
}
void Putinto(Node * suc,Lstack