A星算法代码和相关注释.docVIP

#includestdio.h #includestdlib.h #includemath.h //八数码状态对应的节点结构体 struct Node{ int s[3][3]; //保存八数码状态，0代表空格 int f,g; //启发函数中的f和g值 struct Node * next; //保存下一个节点 struct Node *previous; //previous是用来存放地址的 //保存其父节点 }; int open_N=0; //记录Open列表中节点数目 int inital_s[3][3]={ 2,8,3,1,0,4,7,6,5 }; //八数码初始状态 int final_s[3][3]={ 1,2,3,8,0,4,7,6,5 }; //八数码目标状态 //------------------------------------------------------------------------ //添加节点函数入口，通过插入排序向指定表添加 //------------------------------------------------------------------------ void Add_Node( struct Node *head, struct Node *p) //这里的p和inital指向的是同一个 //添加节点方法，里面的参数为指向头节点和指向p节点的指针 { struct Node *q; if(head-next) //考虑链表为空 { q = head-next; //q为头指针指向的，p为要插入的 if(p-f head-next-f){ //考虑插入的节点值比链表的第一个节点值小 p-next = head-next; head-next = p; //如果条件满足，把指针p所指的结点插入到队列头上 } else { while(q-next) //head指向open的头结点，后继为空，走else。 //考虑插入节点x，形如a= x =b { if((q-f p-f ||q-f == p-f) (q-next-f p-f || q-next-f == p-f)){ p-next = q-next; q-next = p; break; //p后面增加一个q节点 } q = q-next; } if(q-next == NULL) //考虑插入的节点值比链表最后一个元素的值更大 q-next = p; //如果q下一个节点为空，下一个节点就等于p } } else head-next = p; //否则头节点的下一个节点为p } //------------------------------------------------------------------------ //删除节点函数入口 //------------------------------------------------------------------------ void del_Node(struct Node * head, struct Node *p ) //添加删除节点的方法 { struct Node *q; q = head; //定义头节点为q while(q-next) { if(q-next == p){ q-next = p-next; p-next = NULL; //遍历以q指向（有附加头结点）的单向链表的一个循环 if(q-next == NULL) return; // free(p); //如果q的下一个节点为空，返回并且释放该节点 } q = q-next; //q的下一个节点变为q节点 } } //------------------------------------------------------------------------ //判断两个数组是否相等函数入口 //------------------------------------------------------------------------ int equal(int s1[3][3], int s2[3][3]) //对表1和表2的三行三列进行比较 { int i,j,flag=0; for(i=0; i 3 ; i++) for(j=0; j 3 ;j++) if(s1[i][j] != s2[i][j]