启发式搜索算法解决八数码问题(C语言).doc

1、程序源代码 #include stdio.h #includemalloc.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;i3;i++) for(j=0;j3;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));//head p=head; q=head; head-next=NULL;//初始化 for(i=0;i3;i++)//找到二维数组中0的位置 { for(j=0;j3;j++) if(ex-a[i][j]==0) { flag=1; break; } if(flag==1) break; } for(m=0;m3;m++)//将ex-a赋给x for(n=0;n3;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;m3;m++)//将x赋给a for(n=0;n3;n++) if(x[m][n]==ex-parent-a[m][n]) flag++; if(flag!=9) { q=(node *)malloc(sizeof(node)); for(m=0;m3;m++)//将x赋给a for(n=0;n3;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;m3;m++)//将ex-a重新赋给x，即还原x for(n=0;n3;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;m3;m++) for(n=0;n3;n++) if(x[m][n]==ex-parent-a[m][n]) flag++; if(flag!=9) { q=(node *)malloc(sizeof(node)); for(m=0;m3;m++)//将x赋给a for(n=0;n3;n++) q-a[m][n]=x[m][n]; q-parent=ex;