优化后的A*算法--简洁、易懂且实用

　　我曾看过一些有关A*算法的程序，不过写得比较简洁、易懂的还是风云写的A*算法教学实例（风云工作室），但是这个算法并没有进行优化，该程序要用到实际应用中，还会有一定的限制，所以我对该算法进行了改进，并加上更详细的算法说明，使其具有更好的教学作用和实用价值。开始前我先给出A*算法的基本思路：
　　问题：求出2D的迷宫中起始点S到目标点E的最短路径？
　　算法： findpath()
　　{
　　把S点加入树根（各点所在的树的高度表示从S点到该点所走过的步数）；
　　把S点加入排序队列（按该点到E点的距离排序+走过的步数从小到大排序）；
　　1、排序队列sort_queue中距离最小的第一个点出列，并保存入store_queue中
　　2、从出列的点出发，分别向4个（或8个）方向中的一个各走出一步
　　3、并估算第2步所走到位置到目标点的距离，并把该位置加入树，
　　最后把该点按距离从小到大排序后并放入队列中。(由trytile函数实现)。
　　4、如果该点从四个方向上都不能移动，则把该点从store_queue中删除
　　5、回到第一点，直到找到E点则结束
　　从目标点回溯树，直到树根则可以找到最佳路径，并保存在path[]中
　　}
　　/*========================================================================
　　精简的A*算法 作者：添翼虎
　　网址：http://tyhweb.163.net Email:tyhweb@163.net
　　本程序参考了风云的最短路径代码(http://member.nease.com/~cloudwu)，
　　并加以改进和优化：
　　1、把原来用于存放已处理节点的堆栈改为(store_queue)队列，这样在从
　　sort_queue队列出列时可直接放入store_queue中。
　　2、解除了地图大小的限制(如果有64K内存限制时，地图大小只能是180x180)
　　3、删除了原程序中的一些冗余，见程序中的注释。
　　4、程序继续使用dis_map数组保存各点历史历史最佳距离，也包含了某点是否已经
　　经过的信息，虽然这样做可能会比使用链表多用一些内存，但是在搜索时可以
　　节省不时间。
　　5、程序更具有实用性，可直接或修改后运用于你的程序中，但请你使用该代码后
　　应该返回一些信息给我，如算法的改进或使用于什么程序等。
　　本程序可以用Borland C++或DJGPP编译，并附带有一个数据文件 map.dat,
　　保存有地图的数据，（注：该地图文件格式与风云的原代码的地图格式不一样）
　　-------------------------------------------------------------------------*/
　　//#define NDEBUG
　　#include <stdio.h>
　　#include <conio.h>
　　#include <assert.h>
　　#include <stdlib.h>
　　
　　#define tile_num(x,y) ((y)*map_w+(x)) //将 x,y 坐标转换为地图上块的编号
　　#define tile_x(n) ((n)%map_w) //由块编号得出 x,y 坐标
　　#define tile_y(n) ((n)/map_w)
　　
　　#define MAPMAXSIZE 180 //地图面积最大为 180x180，如果没有64K内存限制可以更大
　　#define MAXINT 32767
　　//树结构, 比较特殊, 是从叶节点向根节点反向链接，方便从叶节点找到根节点
　　typedef struct tree_node *TREE;
　　struct tree_node {
　　int h; //节点所在的高度，表示从起始点到该节点所有的步数
　　int tile; //该节点的位置
　　TREE father; //该节点的上一步
　　};
　　//链接结构，用于保存处理过的和没有处理过的结点
　　typedef struct link_node *LINK;
　　struct link_node {
　　TREE node;
　　int f;
　　LINK next;
　　};
　　LINK sort_queue; // 保存没有处理的行走方法的节点
　　LINK store_queue; // 保存已经处理过的节点 (搜索完后释放)
　　unsigned char * map; //地图数据
　　unsigned int * dis_map; //保存搜索路径时,中间目标地最优解
　　int map_w,map_h; //地图宽和高
　　int start_x,start_y,end_x,end_y; //地点,终点坐标
　　// 初始化队列
　　void init_queue()
　　{
　　sort_queue=(LINK)malloc(sizeof(*sort_queue));
　　sort_queue->node=NULL;
　　sort_queue->f=-1;
　　sort_queue->next=(LINK)malloc(sizeof(*sort_queue));
　　sort_queue->next->node=NULL;
　　sort_queue->next->f=MAXINT;
　　sort_queue->next->next=NULL;
　　store_queue=(LINK)malloc(sizeof(*store_queue));
　　store_queue->node=NULL;
　　store_queue->f=-1;
　　store_queue->next=NULL;
　　}
　　// 待处理节点入队列, 依靠对目的地估价距离插入排序
　　void enter_queue(TREE node,int f)
　　{
　　LINK p=sort_queue,father,q;
　　while(f>p->f) {
　　father=p;
　　p=p->next;
　　assert(p);
　　}
　　q=(LINK)malloc(sizeof(*q));
　　assert(sort_queue);
　　q->f=f,q->node=node,q->next=p;
　　father->next=q;
　　}
　　// 将离目的地估计最近的方案出队列
　　TREE get_from_queue()
　　{
　　LINK bestchoice=sort_queue->next;
　　LINK next=sort_queue->next->next;
　　sort_queue->next=next;
　　bestchoice->next=store_queue->next;
　　store_queue->next=bestchoice;
　　return bestchoice->node;
　　}
　　// 释放栈顶节点
　　void pop_stack()
　　{
　　LINK s=store_queue->next;
　　assert(s);
　　store_queue->next=store_queue->next->next;
　　free(s->node);
　　free(s);
　　}
　　// 释放申请过的所有节点
　　void freetree()
　　{
　　int i;
　　LINK p;
　　while(store_queue){
　　p=store_queue;
　　free(p->node);
　　store_queue=store_queue->next;
　　free(p);
　　}
　　while (sort_queue) {
　　p=sort_queue;
　　free(p->node);
　　sort_queue=sort_queue->next;
　　free