A*算法程序说明
一. 数据结构
1.用邻接表方式存储图信息,定义 Edge 结构存储边节点信息,VerNode 存储
顶点节点信息。定义类 Graph 来执行关于邻接表的操作:
struct Edge{
int verj;
int weight;
Edge *next;
};
struct VerNode{
int veri;
Edge *first;
};
class Graph{
private:
VerNode * NodeTable;
int numNode;
int numEdge;
public:
Graph(int nodenum,int edgenum); //初始化图的顶点数和变数
~Graph();
bool insteredge(int v1,int v2,int cost);//边插入操作
Edge *getnode(int v);//得到与顶点 V 连接边节点
int getnumnode();//得到图的定点数
int getnumedge();//得到图的边数
};
2.为了保存已扫描过且等待选择的节点信息,创建一个 OPEN 表,其中主要操作
由 List 类来完成,每一个节点信息的结构体 infor_node 确定;
struct infor_node{
int Curnode;
int Pernode;
int g_n; //实在状态空间中从初始节点到 n 节点的实际代价
int f_n; //是节点 n 的估价函数
}
struct LinkNode{
infor_node Oinfornode;
LinkNode *next;
};
class List{
private:
LinkNode *head;