//--------------A*算法------------//

#include  <malloc.h>
#include  <math.h>
#include  <stdio.h>

struct node
{int x;
int y;
int f;
int val;
int valed;
int num;
struct node *father_node;
struct node *front;
struct node *next;
};


struct node *PULL(struct node **open_head)
{struct node *temp;
temp=*open_head;
if (*open_head==NULL)
     return NULL;
else if ((*open_head)->next!=NULL)
     {*open_head=(*open_head)->next;
      return temp;
     }
else
     {*open_head=NULL;
      return NULL;
     }

};


struct node *INSERT_OPEN(struct node **open_head,struct node *insert_node,struct node **open_tail,struct node *head_open)
{if (head_open==NULL)
     {*open_head=insert_node;
      (*open_head)->front=NULL;
      (*open_head)->next=NULL;
      *open_tail=*open_tail;
      return *open_head;
     }
else
     {(*open_head)->front=insert_node;
      insert_node->next =*open_head;
      *open_head=(*open_head)->front;
      (*open_head)->front=NULL;
      return *open_head;
     }

};

struct node *INSERT_CLOSE(struct node **close_head,struct node *insert_node,struct node **close_tail,struct node *head_close)
{if(head_close==NULL)
      {*close_head=insert_node;
       (*close_head)->front=NULL;
       (*close_head)->next=NULL;
       *close_tail=*close_head;
       return *close_head;
      }
else
      {(*close_head)->front =insert_node;
       insert_node->next =*close_head;
       *close_head=(*close_head)->front;
       (*close_head)->front =NULL;
       return *close_head;
      }
};

struct node *SEARCH_OPEN(struct node **open_head,int num,int valed,struct node **open_tail,struct node *father_node)
{struct node *temp1;
struct node *temp;
temp1=*open_head;
if (*open_head==NULL)
       return NULL;
else if((*open_head)->num==num)
       {if ((*open_head)->valed>valed)
              {(*open_head)->valed=valed;
              (*open_head)->val=valed+(*open_head)->f;
               (*open_head)->father_node=father_node;}
        temp=*open_head;
        *open_head=(*open_head)->next;
        temp->next=NULL;
        if (*open_head==NULL)
                *open_tail=NULL;
        return temp;
              
       }
else if ((*open_tail)->num==num)
       {if ((*open_tail)->valed>valed)
               {(*open_tail)->valed=valed;
               (*open_head)->val=valed+(*open_head)->f;
                (*open_head)->father_node=father_node;
               }
        temp=*open_tail;
        *open_tail=(*open_tail)->front;
        temp->front=NULL;
        if(*open_tail==NULL)
                *open_head=NULL;
        return temp;
       }
else
       {while((*open_head)!=NULL)
               {if((*open_head)->num==num)
                     {if((*open_head)->valed>valed)
                          {(*open_head)->valed=valed;
                          (*open_head)->val=valed+(*open_head)->f;
                           (*open_head)->father_node=father_node;}
                       temp=*open_head;
                       ((*open_head)->front)->next=(*open_head)->next;
                       ((*open_head)->next)->front=(*open_head)->front;
                       temp->front=NULL;
                       temp->next=NULL;    
                       *open_head=temp1;
                     }               
                  *open_head=(*open_head)->next;
                 
               }
         *open_head=temp1;
         return NULL;
         }



};

struct node *SEARCH_CLOSE(struct node **close_head,int num,int valed,struct node **close_tail,struct node *father_node)
{struct node *temp1;
struct node *temp;
temp1=*close_head;
if (*close_head==NULL)
           return NULL;
else if((*close_head)->num==num)
          {if ((*close_head)->valed>valed)
                  {(*close_head)->valed=valed;
                  (*close_tail)->val=valed+(*close_tail)->f;
                    (*close_head)->father_node=father_node;
                    temp=*close_head;
                    *close_head=(*close_head)->next;
                    temp->next=NULL;
                    if(*close_head==NULL)
                   *close_tail=NULL;
                    return temp;
                  }
            else
            return NULL;
            }
else if ((*close_tail)->num==num)
           {if((*close_tail)->valed>valed)
                  {(*close_tail)->valed=valed;
                   (*close_tail)->val=valed+(*close_tail)->f;
                   (*close_tail)->father_node=father_node;
                   temp=*close_head;
                   *close_tail=(*close_tail)->front;
                   temp->front=NULL;
                   if (*close_tail==NULL)
                          *close_head=NULL;
                   return temp;
                  }
            else
            return NULL;
            }
            
else
      {while ((*close_head)!=NULL)
            {if ((*close_head)->num==num)
                  {if ((*close_head)->valed>valed)
                        {(*close_head)->valed=valed;
                         (*close_tail)->val=valed+(*close_tail)->f;
                         (*close_head)->father_node=father_node;
                         temp=*close_head;
                         (*close_head)->front->next=(*close_head)->next;
                         (*close_head)->next->front=(*close_head)->front;
                         *close_head=temp1;
                         temp->next=NULL;
                         return temp;
                        }
                    else
                    return NULL;
                   }
             *close_head=(*close_head)->next;
            }
        *close_head=temp1;
        return NULL;

      }

};

int F(int x,int y,int desert_x,int desert_y,int a)
{if (a==1)
       return 9999;
else
       return abs(x-desert_x)+abs(y-desert_y);

};


int NUM(int x,int y)
{return (x-1)*12+y;
};

void HUISUO(struct node *T)
{while(T!=NULL)
     {printf(" (%d,%d)-> ",T->x,T->y);
      T=T->father_node;
     }
}

//----------------------------------------------
//以上是子函数

//以下是主函数
//----------------------------------------------

main()
{struct node *temp;
struct node *head_open;
struct node *tail_open;
struct node *head_close;
struct node *tail_close;
struct node **open_head;
struct node **open_tail;
struct node **close_head;
struct node **close_tail;
struct node *node_son[5];
struct node *best_node;
int num[5];
int a[12][12]={1,1,1,1,1,1,1,1,1,1,1,1,
            1,0,0,0,0,0,0,0,0,0,0,1,
            1,0,0,0,0,0,0,0,0,0,0,1,
            1,0,0,0,0,0,0,0,1,0,0,1,
            1,0,0,0,0,0,0,0,0,0,0,1,
            1,0,0,0,0,0,0,0,0,0,0,1,
            1,0,0,0,0,0,0,0,0,0,0,1,
            1,0,0,0,0,0,0,0,0,0,0,1,
            1,0,0,0,0,0,0,0,0,0,0,1,
            1,0,0,0,0,0,0,0,0,0,0,1,
            1,0,0,0,0,0,0,0,0,0,0,1,
            1,1,1,1,1,1,1,1,1,1,1,1       
              };
int i=1;
int j=1;

int desert_x=4;
int desert_y=7;

int start_x=2;
int start_y=4;

int valed=0;
//---以上是定义变量
//---以下是初始化open表和close表
head_open=(struct node *)malloc(sizeof(struct node));
head_open->x=start_x;
head_open->y=start_y;
head_open->num=NUM(head_open->x,head_open->y);
head_open->valed=0;
head_open->val=head_open->valed+F(head_open->x,head_open->y,desert_x,desert_y,a[head_open->x][head_open->y]);
head_open->f=F(head_open->x,head_open->y,desert_x,desert_y,a[head_open->x][head_open->y]);
head_open->father_node=NULL;
head_open->next=NULL;
head_open->front=NULL;
tail_open=head_open;
open_head=&head_open;
open_tail=&tail_open;
close_head=close_tail=NULL;
close_head=&head_close;
close_tail=&tail_close;

//----------初始化完成
best_node=PULL(open_head); //取出最优节点
while(best_node!=NULL)     //扩展节点 方向
       {valed=best_node->valed+1;
        num[1]=NUM(best_node->x+1,best_node->y);
        num[2]=NUM(best_node->x,best_node->y+1);
        num[3]=NUM(best_node->x-1,best_node->y);
        num[4]=NUM(best_node->x,best_node->y-1);
       
   for(i=1;i<=4;i++)
     {if ((node_son[i]=SEARCH_OPEN(open_head,num[i],valed,open_tail,best_node))!=NULL)
                 continue;
      else if ((node_son[i]=SEARCH_CLOSE(close_head,num[i],valed,close_tail,best_node))!=NULL)
                 continue;
      else
            {node_son[i]=(struct node *)malloc(sizeof(struct node));
             node_son[i]->x=num[i]/12;
             if (num[i]%12==0)
                      node_son[i]->y=12;
             else
                      node_son[i]->y=num[i]-num[i]/12*12;
             node_son[i]->valed=valed;
             node_son[i]->f=F(node_son[i]->x,node_son[i]->y,desert_x,desert_y,a[node_son[i]->x][node_son[i]->y]);
             node_son[i]->val=node_son[i]->valed+node_son[i]->f;
             node_son[i]->front=NULL;
             node_son[i]->next=NULL;
             node_son[i]->father_node=best_node;
            }
     
     }
   for(i=1;i<=4;i++)               //--按估价值从小到大排序
      {for (j=1;j<=i;j++)
            if (node_son[i]->f>=node_son[j]->f)
                   {temp=node_son[i];
                    node_son[i]=node_son[j];
                    node_son[j]=temp;
                   }
             
      
      }

//--------可能存在隐患  按顺序推入open表 无法释放死节点？
i=1;
while(node_son[i]->f<=999)
     {
      head_open=INSERT_OPEN(open_head,node_son[i],open_tail,head_open);
    
      if (i<=4)
      i++;
      else
      break;
     }
//---------
best_node=PULL(open_head);
if (best_node->x==desert_x && best_node->y==desert_y)//找到目标节点;
break;
}
HUISUO(best_node); //回朔
}

太长了

就是啊
不会用c++（郁闷中）

眼睛看绿了的都要

还是不看了 呵呵

哇！偶像！高手！

问一下楼主
什么是A*算法