a_and_list.txt

利用人工智能的经典算法实现迷宫游戏；里面的A星（a*）算法可以很方便的移植到应用程序中

//=============================================================================== 
// Description : 删除当前结点。 
// Parameters  : d第一个是表头地址，第二个是要删的节点的地址 
// Returns     : 无 
// Supplement  : 无 
//use================================================================================ 
list_node  del_node2(list_node list_head1,list_node node_current) 
{  list_node ptmp;
 if (NULL == node_current) 
 { 
  printf("删除节点出现错误。:-(  \n");
  return NULL;
 } 
  if (NULL == list_head1) 
 { 
  printf("删除节点出现错误。：您企图从空表中删除元素	:-(  \n");
  return NULL;
 }
 if (node_current == list_head1)			// 若删除的是第一个节点，											
 {											// 则删后表会空或者表空时还要删，这是不符合逻辑的
   printf("你弄错了.\n");
	printf("你正在企图删除表头，请重新确定您的意图。:-（\n");
 return 0;
 }
  ptmp = node_current->prior;
  ptmp->next = node_current->next;
  ptmp->next->prior = ptmp; 
 //free(node_current); 
 return  list_head1;
}
//======================================================================= 
// Description : 构造函数，创建双向链表的一个结点，并赋值当前结点为空。 
// Parameters  : int类型的数据，由于表头结点中的数据不会被使用， 
//     因此该数据可以为任何不在后继结点中使用的数据即可。 
// Returns     : 无 
// Supplement  : 无 
//use======================================================================== 
list_node create_node(int row_1,int collum_1,int f_n_1)			//创建结点
{
 list_node pnode = (list_node )malloc(sizeof(list_node));
 pnode->row = row_1;
  pnode->collum = collum_1;
   pnode->f_n = f_n_1;
    pnode->g_n = 0;
	 pnode->h_n = 0;
	  pnode->father=NULL;
	   pnode->son1=NULL;
	    pnode->son2=NULL;
		 pnode->son3=NULL;
		  pnode->son4=NULL;
 pnode->prior = pnode->next = pnode;    //创建新结点时，让其前向和后向指针都指向自身 
 return pnode;
}
//======================================================================= 
// Description : 构造函数，创建一个双向链表,其实就是创建创建链表的头指针。 
// Parameters  : int类型的数据，由于表头结点中的数据不会被使用， 
//     因此该数据可以为任何不在后继结点中使用的数据即可。
// Supplement  : 无 
//======================================================================== 
//创建链表use
list_node create_list(int head1,int head2,int head3)			//参数给出表头结点数据 （表头结点不作为存放有意义数据的结点）
{
 list_node  pnode = (list_node  )malloc(sizeof(list_node));
  pnode->row = head1;
  pnode->collum = head2;
   pnode->f_n = head3;
 pnode->prior = pnode->next = pnode;
 return  pnode;
}
//插入新结点,总是在表尾插入; 返回表头结点use
list_node insert_node(list_node node_temp, int data1,int data2,int data3) // 参数1是链表的表头结点，参数2是要插入的结点（结点数据为data）
{
 list_node   pnode = create_node(data1,data2,data3); 
 list_node   temp = node_temp->prior;
 // 从左到右恢复链接
 node_temp->prior->next = pnode;
 pnode->next = node_temp; 
 // 从右到左恢复链接
 node_temp->prior = pnode;
 pnode->prior = temp; 
 return node_temp;
}
//插入新结点,总是在表尾插入; 返回表头结点
list_node insert_node2(list_node list_head2,list_node node_temp) // 参数1是链表的表头结点，参数2是要插入的结点（结点数据为data）
{ 
	 list_node  temp = list_head2->prior;
	if(node_temp==NULL||list_head2==NULL)
{
	printf("错误的插入空节点或表为空");
}
 // 从左到右恢复链接
 list_head2->prior->next = node_temp;
 node_temp->next =list_head2; 
 // 从右到左恢复链接
 list_head2->prior = node_temp;
 node_temp->prior = temp; 
 return list_head2;
}
// use查找结点，成功则返回满足条件的结点指针，否则返回NULL
list_node find_closed(list_node node_temp, int target1,int target2) // 参数1是链表的表头结点，参数2是要查找的结点（其中结点数据为target）
{
 list_node pnode = node_temp->next;
 while (pnode->next != node_temp && (!(pnode->row== target1&& pnode->collum==target2)))
 {
  pnode = pnode->next;
 } 
 if (pnode->next == node_temp&& (!(pnode->row== target1&& pnode->collum==target2)))  return NULL; 
 return  pnode;
}
//=============================================================================== 
// Description : 删除当前结点。 
// Parameters  : d第一个是表头地址，第二个是要删的节点的地址 
// Returns     : 无 
// Supplement  : 无 
//use================================================================================ 
list_node  del_node2(list_node list_head1,list_node node_current) 
{  list_node ptmp;
 if (NULL == node_current) 
 { 
  printf("删除节点出现错误。:-(  \n");
  return NULL;
 } 
  if (NULL == list_head1) 
 { 
  printf("删除节点出现错误。：您企图从空表中删除元素	:-(  \n");
  return NULL;
 }
 if (node_current == list_head1)			// 若删除的是第一个节点，											
 {											// 则删后表会空或者表空时还要删，这是不符合逻辑的
   printf("你弄错了.\n");
	printf("你正在企图删除表头，请重新确定您的意图。:-（\n");
 return 0;
 }
  ptmp = node_current->prior;
  ptmp->next = node_current->next;
  ptmp->next->prior = ptmp; 
 //free(node_current); 
 return  list_head1;
}
//=============================================================================== 
// Description : 该函数判断双向链表是否为空。 
// Parameters  : 无 
// Returns     : 若链表为空则返回1，否则返回0。 
// Supplement  : 无 
//use================================================================================ 
int isempty(list_node link_temp) 
{ 
 if(link_temp->next==link_temp) 
 { 
  return 1;
 }
 return 0;
}
//============================================================================ 
// Description : 该函数从链表开始位置寻找结点数据等于fn的结点。 
// Parameters  : 无 
// Returns     : 若找到满足条件的结点则返回指向该结点指针，    
// Supplement  : 无 
//use============================================================================
list_node find_fn(list_node node_temp)		// 参数1是链表的表头结点
{list_node pnode  = node_temp->next;
 list_node min_fn = node_temp->next;
 while (pnode->next != node_temp ) 
 {
	   if(pnode->f_n<=min_fn->f_n)					/* 谁小谁标记为min_fn */
  {
	  min_fn=pnode;
  }
  pnode = pnode->next;

 } 
 if(pnode->f_n<=min_fn->f_n)					    /* 谁小谁标记为min_fn */
  {
	  min_fn=pnode;
  }
 return  min_fn;
}
//======================================================================= 
// Description :  迷宫A*搜索算法中的重新计算子孙节点的fn值程序
// Parameters  :链表定义，结合状态空间的定义等，已于上面完成
// Supplement  : 无 
//======================================================================== 
list_node son_fn(list_node temp,int dg)
{
	if(temp->son1!=NULL)						/* 若有第一子节点计算其fn*/		
	{
		temp->son1->g_n=dg;
		temp->son1->f_n=temp->son1->g_n+temp->son1->h_n;
		temp=temp->son1;
		son_fn(temp,dg);
	}
		if(temp->son2!=NULL)						/* 若有第一子节点计算其fn*/		
	{
		temp->son2->g_n=dg;
		temp->son2->f_n=temp->son2->g_n+temp->son2->h_n;
		temp=temp->son2;
		son_fn(temp,dg);
	}
			if(temp->son3!=NULL)						/* 若有第一子节点计算其fn*/		
	{
		temp->son3->g_n=dg;
		temp->son3->f_n=temp->son3->g_n+temp->son3->h_n;
		temp=temp->son3;
		son_fn(temp,dg);
	}
				if(temp->son4!=NULL)						/* 若有第一子节点计算其fn*/		
	{
		temp->son4->g_n=dg;
		temp->son4->f_n=temp->son4->g_n+temp->son4->h_n;