searchlib.h

在VC的环境下

#ifndef __SEARCHLIB_H__
#define __SEARCHLIB_H__

#define VERTEX_WIDTH 70
#define VERTEX_HEIGHT 70
#define MAX_VERTEX_NUM 4900
#define MAX_LINK_NUM 4
#define X_MARCH 10 // x轴每次增长的步长
#define RANDOM_X_SCALE 10 
#define Y_MARCH 10 // y轴每次增长的步长
#define RANDOM_Y_SCALE 10
#define WEIGHT_SCALE 40 
#define VALIDATE_WEIGHT_DOWN_LIMIT 0.0
#define R 0.0

#include <stdlib.h>
#include <math.h>
#include <LIST>
using std::list;
using std::list<int>;

struct INFOTYPE 
{
	double dDistance;
	double dWeight;
};

struct ARCNODE
{
	int  nAdjvex;  // 该弧所指向的顶点的位置
	INFOTYPE info; // 该弧的相关信息
	ARCNODE(int nIndex, double dDis, double dWeight)
	{
		nAdjvex = nIndex;
		info.dDistance = dDis;
		info.dWeight = dWeight;
	}
};
using std::list<ARCNODE>;
using std::list<ARCNODE>::iterator;

struct VERTEXTYPE
{
	double x; 
	double y;
	double g; // 当前节点到始点的距离，非负
	double h; // 当前节点到终点的估计距离，非负
	int nFatherIndex; // 父节点在邻接表上位置
	int operator < (const VERTEXTYPE & right);
	int operator == (const VERTEXTYPE & right);
	int nIndex; // 节点在邻接表表头中的位置
};
using std::list<VERTEXTYPE>;

struct VNODE
{
	VERTEXTYPE data; // 顶点信息
	list<ARCNODE> ArcList; // 弧节点链表
};

struct ALGRAPH
{
	VNODE vertices[MAX_VERTEX_NUM]; // 头节点表
	int nVexNum; // 图的当前顶点数
	int nArcNum; // 图的弧数
	int nKind;
};

struct STUDYRESULT 
{
	double dCostSumOnASelectedPath;
	int nNumberOfExpandedNode;
	int nNodeNumberOnASelectedPath;
};

int CreateRandomGraph(ALGRAPH & graph);

int Link(ALGRAPH & graph);

int SetArcWeight(ALGRAPH & graph);

int SetCoordinates(ALGRAPH & graph);

ARCNODE * FindArc(ALGRAPH & graph, int nArcStart, int nArcEnd);

void InitNodes(ALGRAPH & graph);

int Random();

double FuncG(ALGRAPH & graph, int nNi, int nFatherNode);

double FuncH(ALGRAPH & graph, int nNp, int nNg);

int ShortestPath_AStart(ALGRAPH & graph, int ns, int ng, 
						list<int> & listShortestPath, STUDYRESULT & resultPath);
int Dual_ShortestPath_AStart(ALGRAPH & graph, int ns, int ng, 
							 list<int> & listShortestPath, STUDYRESULT & resultPath);

#endif