func.c

这是在ADIdsp上实现的A型算法和链表程序以及无线通讯的源程序

	{ return  (min_fn);}

 }

if(pnode->f_n<=min_fn->f_n)					    /* 谁小谁标记为min_fn */
		{
		  min_fn=pnode;
		} 
 return  (min_fn);
}
//======================================================================= 
// 函数名称 ：  son_fn(volatile struct node   temp,int dg)
// 功能		：  迷宫A*搜索算法中的重新计算子孙节点的fn值
// 参数		：  
//				volatile struct node   temp：当前节点；
//				int dg： 费用值的变化
// 返回值   ：  链表的表头结点；
// 说明		：  无 
//======================================================================== 
volatile struct node   * son_fn(volatile struct 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;
		temp=temp->son4;
		son_fn(temp,dg);
	}
	return NULL;
}
//======================================================================= 
// 函数名称 ：  Destroy(volatile struct node  list_head1)
// 功能		：  删除链表
// 参数		：  volatile struct node  list_head1：链表表头
// 返回值   ：  成功，返回1，失败返回0；
// 说明		：  无 
//======================================================================== 
int  Destroy(volatile struct node * list_head1)
{
	volatile struct node *  ptmp1;	
	ptmp1=list_head1->prior;

	volatile struct node *  ptmp2;
	if(list_head1==NULL)
	{
		//	不能删除空节点");
		return false;
	}
	while(list_head1!=ptmp1)
	{
	
		ptmp2=list_head1->next;
	//	list_head1->prior=ptmp->prior;
	//	ptmp->prior->next = list_head1; 
		free((void *)list_head1);
		list_head1=ptmp2;
	}
	free((void *)list_head1);
 return (TRUE);

}

//======================================================================= 
// 名称		:   Asearch(volatile unsigned char a[MazeHeight50][MazeWidth50],volatile uint8_t s_n[2],volatile uint8_t s_g[2])
// 功能		：	迷宫A*搜索算法
// 参数		：  
//				int a[][MOSTNUM]：迷宫
//				CPoint s_n,CPoint s_g：起始点，目标点
// 返回值	：  链表首地址，并且将路径存入ROAD中
// 说明		：	用到的链表函数在list.c中定义，但本程序有一个不影响应用的缺点：没有释放节点。
// Revision :   1.00 $
//========================================================================
volatile struct node  * Asearch(volatile unsigned char a[][MazeWidth40],volatile  int s_n[2],volatile  int s_g[2])
{
   if(Astep==0)									//若是第一次扩展则将起始节点放入open表//
   {
	   Astep++;	//步数加一
	open_list =  insert_node(open_list, s_n[0],s_n[1],0);//起始节点加入open表
	   open_list->next->f_n=abs(s_n[0]-s_g[0])+ abs(s_n[1]-s_g[1]);	// 计算起始节点的fn 
	   Asearch(a,s_n, s_g);//递归调用A*搜索算法
   }
   if(!FoundWayFlag)
   {
	  if( IsMyListEmpty(open_list))//若open表里无数据说明没有路径									/* 若open表空或者不可能的步数出现失败退出*/
	  {
//		  AfxMessageBox("没有路径！:(");//输出没有路径提示
		  FoundWayFlag=0;
		  return NULL;//退出搜索,FoundWayFlag
	  }
  else//open表中有数据说名有路径
  { 
	     best_node =  find_fn(open_list);//查找最好路径
	   if((best_node->row==s_g[0])&&(best_node->collum==s_g[1]))//若最佳节点为目标节点
		{	
			FoundWayFlag = 1; 
			HaveFoundFlag=1;
//			 Road[best_node->g_n+1][1]= GoalPos[1];
//			 Road[best_node->g_n+1][0]= GoalPos[0];
			while (!((best_node->row==s_n[0])&&(best_node->collum==s_n[1])))
			{
				Road[best_node->g_n][1]=best_node->collum;
				Road[best_node->g_n][0]=best_node->row;
				best_node = best_node->father;
			}
//			printf("%d  %d	%d\n ", best_node->row,best_node->collum,best_node->f_n);
		if(ArtificialWalkFlag==0)//自动行走方式
		{
			//AfxMessageBox("找到路径！:)");//提示找到路径,并将路径存入Road[]
		}
			return NULL;
		}
//若不是目标节点则，扩展节点bestnode生成全部子节点subnode 
//计算subnode的f（n），设置指向bestnode的指针
//子节点subnodes全部放入open表 
	   if(a[best_node->row][best_node->collum+1]==ROAD)//向右可走，（可走的条件是没超出边界且为空，下同）
		{  
		   volatile struct node   * sub_node1=  create_node(best_node->row,best_node->collum+1,0);//扩展子节点
		   volatile struct node   * temp=sub_node1;
		   sub_node1->g_n=best_node->g_n+1;
		   sub_node1->h_n=abs(sub_node1->row-s_g[0])+ abs(sub_node1->collum-s_g[1]);
		   sub_node1->f_n=sub_node1->g_n+sub_node1->h_n;
		   if((NULL==( find_closed(open_list,sub_node1->row,sub_node1->collum)))&&(NULL==( find_closed(closed_list,sub_node1->row,sub_node1->collum))))
		   {	// 若节点不在closed或open表中设置sub-node指向best-node的指针 */
		     sub_node1->father=best_node;//用于寻找路径，倒着指回去
			 best_node->son1=sub_node1;
		     open_list =  insert_node2(open_list, sub_node1);// 新节点放入open表 
		   }
		   else	//若节点在closed或open表中比较gn谁小留谁 
		   {
			   if(!(NULL==( find_closed(open_list,sub_node1->row,sub_node1->collum))))
			   {
				   temp= find_closed(open_list,sub_node1->row,sub_node1->collum);
			   }
			   else
			   {
				   temp= find_closed(closed_list,sub_node1->row,sub_node1->collum);
			   }
			   if(sub_node1->g_n<temp->g_n)	// 若新的较小泽用新的替代旧的 */
			   {
				   temp->g_n=sub_node1->g_n;
				   temp->father=best_node;
				   if(!(NULL==(temp= find_closed(closed_list,sub_node1->row,sub_node1->collum))))
				   {					// 若在closed表中重新计算subnode的子孙节点的fn */
					   dg_n=temp->g_n-sub_node1->g_n;
					    son_fn(temp,dg_n);							/* 重新计算subnode的子孙节点的fn  */
				   }					///从subnode中删除son即不宽展他*/ 
			   }
			   else											
			   {						// 若原先的较小则放弃新的，即不扩展它 */
			   }
		   }
		}
	   if(a[best_node->row+1][best_node->collum]==ROAD)//向下可走（可走的条件是没超出边界且为空，
		{  
		   volatile struct node   * sub_node2=  create_node(best_node->row+1,best_node->collum,0);
		   volatile struct node   * temp=sub_node2;
		   sub_node2->g_n=best_node->g_n+1;
		   sub_node2->h_n=abs(sub_node2->row-s_g[0])+ abs(sub_node2->collum-s_g[1]);
		   sub_node2->f_n=sub_node2->g_n+sub_node2->h_n;
		   if((NULL==(temp= find_closed(open_list,sub_node2->row,sub_node2->collum)))&&(NULL==(temp= find_closed(closed_list,sub_node2->row,sub_node2->collum))))//wenti
		   {							 //若节点不在closed或open表中设置sub-node指向best-node的指针 */
		     sub_node2->father=best_node;//用于寻找路径，倒着指回去
			 best_node->son2=sub_node2;
		     open_list =  insert_node2(open_list, sub_node2);	// 放入open表 */
		   }
		   else		// 若节点在closed或open表中比较gn谁小留谁 */
		   {
			    if(!(NULL==( find_closed(open_list,sub_node2->row,sub_node2->collum))))
			   {
				   temp= find_closed(open_list,sub_node2->row,sub_node2->collum);
			   }
			   else
			   {
				   temp= find_closed(closed_list,sub_node2->row,sub_node2->collum);
			   }
			   if(sub_node2->g_n<temp->g_n)	// 若新的较小泽用新的替代旧的 */
			   {
				   temp->g_n=sub_node2->g_n;
				   temp->father=best_node;
				   if(!(NULL==(temp= find_closed(closed_list,sub_node2->row,sub_node2->collum))))
				   {	// 若在closed表中重新计算subnode的子孙节点的fn */
					   dg_n=temp->g_n-sub_node2->g_n;
					    son_fn(temp,dg_n);	// 重新计算subnode的子孙节点的fn  */
				   }    //从subnode中删除son即不宽展他
			   }
			   else											
			   {		//若原先的较小则放弃新的，即不扩展它
			   }
		   }
		}
	   if((a[best_node->row][best_node->collum-1]==ROAD)&&((best_node->collum-1)>0))//向左可走（可走的条件是没超出边界且为空，
		{  
		   volatile struct node   * sub_node3=  create_node(best_node->row,best_node->collum-1,0);
		   volatile struct node   * temp=sub_node3;
		   sub_node3->g_n=best_node->g_n+1;
		   sub_node3->h_n=abs(sub_node3->row-s_g[0])+ abs(sub_node3->collum-s_g[1]);
		   sub_node3->f_n=sub_node3->g_n+sub_node3->h_n;
		   if((NULL==(temp= find_closed(open_list,sub_node3->row,sub_node3->collum)))&&(NULL==(temp= find_closed(closed_list,sub_node3->row,sub_node3->collum))))
		   {
			   // 若节点不在closed或open表中设置sub-node指向best-node的指针
		     sub_node3->father=best_node;//用于寻找路径，倒着指回去
			 best_node->son3=sub_node3;
		     open_list =  insert_node2(open_list, sub_node3);// 放入open表 
		   }
		   else	// 若节点在closed或open表中比较gn谁小留谁 
		   {
			    if(!(NULL==( find_closed(open_list,sub_node3->row,sub_node3->collum))))
			   {
				   temp= find_closed(open_list,sub_node3->row,sub_node3->collum);
			   }
			   else
			   {
				   temp= find_closed(closed_list,sub_node3->row,sub_node3->collum);
			   }
			   if(sub_node3->g_n<temp->g_n)	// 若新的较小泽用新的替代旧的 
			   {
				   temp->g_n=sub_node3->g_n;
				   temp->father=best_node;
				   if(!(NULL==(temp= find_closed(closed_list,sub_node3->row,sub_node3->collum))))
				   {//若在closed表中重新计算subnode的子孙节点的fn */
					   dg_n=temp->g_n-sub_node3->g_n;
					    son_fn(temp,dg_n);	// 重新计算subnode的子孙节点的fn  */
				   }//从subnode中删除son即不宽展他*/ 
			   }
			   else											
			   {	//若原先的较小则放弃新的，即不扩展它 */
			   }
		   }
		}
	   if((a[best_node->row-1][best_node->collum]==ROAD)&&((best_node->row-1)>0))//向上可走（可走的条件是没超出边界且为空，
		{  
		   volatile struct node   * sub_node4=  create_node(best_node->row-1,best_node->collum,0);
		   volatile struct node   * temp=sub_node4;
		   sub_node4->g_n=best_node->g_n+1;
		   sub_node4->h_n=abs(sub_node4->row-s_g[0])+ abs(sub_node4->collum-s_g[1]);
		   sub_node4->f_n=sub_node4->g_n+sub_node4->h_n;
		   if((NULL==(temp= find_closed(open_list,sub_node4->row,sub_node4->collum)))&&(NULL==(temp= find_closed(closed_list,sub_node4->row,sub_node4->collum))))//problem
		   {	//若节点不在closed或open表中设置sub-node指向best-node的指针 
		     sub_node4->father=best_node;//用于寻找路径，倒着指回去
			 best_node->son4=sub_node4;
		     open_list =  insert_node2(open_list, sub_node4);	//放入open表 */
		   }
		   else	// 若节点在closed或open表中比较gn谁小留谁
		   {
			    if(!(NULL==( find_closed(open_list,sub_node4->row,sub_node4->collum))))
			   {
				   temp= find_closed(open_list,sub_node4->row,sub_node4->collum);
			   }
			   else
			   {
				   temp= find_closed(closed_list,sub_node4->row,sub_node4->collum);
			   }
			   if(sub_node4->g_n<temp->g_n)	//若新的较小泽用新的替代旧的 
			   {
				   temp->g_n=sub_node4->g_n;
				   temp->father=best_node;
				   if(!(NULL==(temp= find_closed(closed_list,sub_node4->row,sub_node4->collum))))
				   {		// 若在closed表中重新计算subnode的子孙节点的fn 
					   dg_n=temp->g_n-sub_node4->g_n;
					    son_fn(temp,dg_n);	// 重新计算subnode的子孙节点的fn  */
				   }		//从subnode中删除son即不宽展他 
			   }
			   else											
			   {			// 若原先的较小则放弃新的，即不扩展它 
			   }
		   }
		}
  
// open_list=link_list(open_list,sub_nodes);
// sub_node3->father=best_node;
// 从open表中删除bestnode，放入closed表 
	    del_node2(open_list,best_node);
	   closed_list= insert_node2(closed_list,best_node);
	   Astep++;
	   if(Astep>160)
	   {return NULL;}
// 递归算法，回到第二步判断open表是否为空
	   Asearch(a,s_n,s_g);
	   }
	   return NULL;
    
  }
  return NULL;
}
// 程序结束
/*****************************************************************************/