1、程序源代码#include <stdio.h>#include<malloc.h>struct node{int a[3][3];//用二维数组存放8数码int hx;//函数h（x）的值，表示与目标状态的差距struct node *parent;//指向父结点的指针struct node *next;//指向链表中下一个结点的指针};//------------------hx函数-------------------//int hx(int s[3][3]){//函数说明：计算s与目标状态的差距值int i,j;int hx=0;int sg[3][3]={1,2,3,8,0,4,7,6,5};for(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指向该链表首结点，并且作为返回值int i,j,m,n; //循环变量int t; //临时替换变量int flag=0;int x[3][3];//临时存放二维数组struct node *p,*q,*head;head=(node *)malloc(sizeof(node));//headp=head;q=head;head->next=NULL;//初始化for(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赋给xfor(n=0;n<3;n++)x[m][n]=ex->a[m][n];//根据0的位置的不同，对x进行相应的变换//情况1if(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赋给afor(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赋给afor(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;}}//情况2for(m=0;m<3;m++)//将ex->a重新赋给x，即还原x for(n=0;n<3;n++)x[m][n]=ex->a[m][n];if(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赋给afor(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;}}//情况3for(m=0;m<3;m++)//将ex->a重新赋给x，即还原x for(n=0;n<3;n++)x[m][n]=ex->a[m][n];if(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赋给afor(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;}}//情况4for(m=0;m<3;m++)//将ex->a重新赋给x，即还原xfor(n=0;n<3;n++)x[m][n]=ex->a[m][n];if(j+1<=2){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++)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;}}head=head->next;return head;}//---------------extend函数end-----------------------////----------------insert函数-------------------------//node* insert(node *open,node * head){ //函数说明：将head链表的结点依次插入到open链表相应的位置，//使open表中的结点按从小到大排序。

函数返回open指针node *p,*q;//p、q均指向open表中的结点，p指向q所指的前一个结点int i,j;int flag=0;if(open==NULL)//初始状态，open表为空{ //首先将head表第一个结点直接放入open表中open=head;q=head;head=head->next;q->next=NULL;//再插入第二个结点if(head->hx<open->hx){//插入到首结点位置open=head;head=head->next;open->next=q;}else{ //或者第二个结点的位置q->next=head;head=head->next;q=q->next;q->next=NULL;p=open;}p=open;q=open->next;} //end ifwhile(head!=NULL){q=open;if(head->hx<open->hx) //插入到表头{open=head;head=head->next;open->next=q;continue;}else { q=q->next;p=open;} //否则，q指像第二个结点，p指向q前一个结点while(q->next!=NULL) //将head的一个结点插入到链表中（非表尾的位置）{if(q->hx<head->hx){q=q->next;p=p->next;}else{p->next=head;head=head->next;p->next->next=q;break;}}if(q->next==NULL)//将head的一个结点插入到表尾{if(q->hx>head->hx){p->next=head;head=head->next;p->next->next=q;}else{q->next=head;head=head->next;q->next->next=NULL;}}//if}//whilereturn open;}//insert//-----------------insert函数end--------------------////---------------------main-----------------------//void main(){int i,j;node s0;node *open,*close;node *p,*q;node *newlist;printf("请输入初始状态的8数码（按每行从左往右依次输入,用0表示空格）：\n");for(i=0;i<3;i++)for(j=0;j<3;j++)scanf("%d",&s0.a[i][j]);s0.parent=(node *)malloc(sizeof(node));s0.parent->hx=9;s0.hx=hx(s0.a);open=&s0;p=&s0;if(open->hx==0){printf("该状态已为最终状态！\n");return;}q=&s0;close=&s0;open=NULL;newlist=extend(q);//newlist指向新扩展出来的链表open=insert(open,newlist);//将扩展出来的结点插入到open表中while(1){q->next=open;//q始终指向close表尾结点。

将open表的第一个元素加到close表open=open->next;q=q->next;q->next=NULL;if(q->hx==0){printf("\n搜索成功！\n");break;}newlist=extend(q);//对close表最后一个结点进行扩展，扩展得到的链表接到open 表尾open=insert(open,newlist);//将扩展的结点按顺序插入到open表中}p=close;printf("择优搜索过程如下：\n");while(p!=NULL){for(i=0;i<3;i++){for(j=0;j<3;j++)printf("%d ",p->a[i][j]);printf("\n");}printf("\n");p=p->next;}}2、程序运行结果截图截图1：初始态为：2 8 31 47 6 5运行结果如右图所示：截图2：初始状态为 2 8 3 时，程序运行结果如下：1 6 47 5。