1、1、程序源代碼#include <stdio.h>#include<malloc.h> struct nodeint a33;/ 用二維數組存放 8 數碼int hx;函數h (x)的值，表示與目標狀態(tài)的差距struct node *parent;/ 指向父結點的指針 struct node *next;/ 指向鏈表中下一個結點的指針 ;/hx函數/int hx(int s33)/ 函數說明：計算 s 與目標狀態(tài)的差距值int i,j;int hx=0;int sg33=1,2,3,8,0,4,7,6,5;for(i=0;i<3;i+)for(j=0;j<3

2、;j+)if(sij!=sgij)hx+;return hx;/hx函數 end/extend擴展函數 /struct node *extend(node *ex) /函數說明：擴展ex指向的結點，并將擴展所得結點組成一條/ 單鏈表， head 指向該鏈表首結點，并且作為返回值int i,j,m,n; / 循環(huán)變量int t; / 臨時替換變量int flag=0;int x33;/ 臨時存放二維數組struct node *p,*q,*head;head=(node *)malloc(sizeof(node);/headp=head;q=head;head->next=NULL;/ 初

3、始化for(i=0;i<3;i+)/ 找到二維數組中 0 的位置for(j=0;j<3;j+) if(ex->aij=0) flag=1; break; if(flag=1) break;for(m=0;m<3;m+)/ 將 ex->a 賦給 xfor(n=0;n<3;n+)xmn=ex->amn;/ 根據 0 的位置的不同，對 x 進行相應的變換/ 情況 1if(i-1>=0)t=xij;xij=xi-1j;xi-1j=t;flag=0;for(m=0;m<3;m+)/ 將 x 賦給 a for(n=0;n<3;n+) if(xmn

4、=ex->parent->amn) flag+;if(flag!=9)q=(node *)malloc(sizeof(node);for(m=0;m<3;m+)/ 將 x 賦給 a for(n=0;n<3;n+)q->amn=xmn;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+)xmn=ex->amn;if(

5、i+1<=2)t=xij;xij=xi+1j;xi+1j=t;flag=0;for(m=0;m<3;m+)for(n=0;n<3;n+) if(xmn=ex->parent->amn) flag+;if(flag!=9)q=(node *)malloc(sizeof(node);for(m=0;m<3;m+)/ 將 x 賦給 a for(n=0;n<3;n+)q->amn=xmn;q->parent=ex;q->hx=hx(q->a);q->next=NULL; p->next=q; p=p->next;/ 情

6、況 3for(m=0;m<3;m+)/ 將 ex->a 重新賦給 x ，即還原 xfor(n=0;n<3;n+)xmn=ex->amn;if(j-1>=0)t=xij;xij=xij-1;xij-1=t;flag=0;for(m=0;m<3;m+)for(n=0;n<3;n+) if(xmn=ex->parent->amn) flag+;if(flag!=9)q=(node *)malloc(sizeof(node);for(m=0;m<3;m+)/ 將 x 賦給 a for(n=0;n<3;n+)q->amn=xmn;q

7、->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 ，即還原 x for(n=0;n<3;n+)xmn=ex->amn;if(j+1<=2)t=xij;xij=xij+1;xij+1=t;flag=0;for(m=0;m<3;m+)for(n=0;n<3;n+) if(xmn=ex->parent->amn) flag+;if(flag!=9)q=(node *)

8、malloc(sizeof(node);for(m=0;m<3;m+) for(n=0;n<3;n+) q->amn=xmn;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 表中的結點按

9、從小到大排序。函數返回 open 指針 node *p,*q;/p 、 q 均指向 open 表中的結點， p 指向 q 所指的前一個結點 int i,j;int flag=0;if(open=NULL)/ 初始狀態(tài)， 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=

10、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 前一個結點w

11、hile(q->next!=NULL) / 將 head 的一個結點插入到鏈表中(非表尾的位置) if(q->hx<head->hx)q=q->next;p=p->next;elsep->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;

12、else q->next=head; head=head->next; q->next->next=NULL;/if /while return open;函數 end/insert/insert/main/void main()int i,j;node s0;node *open,*close;node *p,*q;node *newlist;printf(" 請輸入初始狀態(tài)的 8數碼(按每行從左往右依次輸入 ,用 0表示空格) ：n"); for(i=0;i<3;i+)for(j=0;j<3;j+) scanf("%d&qu

13、ot;,&s0.aij);s0.parent=(node *)malloc(sizeof(node);s0.parent->hx=9; s0.hx=hx(s0.a);open=&s0;p=&s0;if(open->hx=0)printf(" 該狀態(tài)已為最終狀態(tài)！ 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(”擇優(yōu)搜索過程如下：n&q