《中科大地图导航(实验报告)参考》由会员分享，可在线阅读，更多相关《中科大地图导航(实验报告)参考（11页珍藏版）》请在金锄头文库上搜索。
1、中科大地图导航一， 科大西区地图的构建与表示：（1）、物理地图的抽象表达地图选择:科大西区地图节点数：12边数：15 1地点信息：地点名，时间，简介，街道名，街道长度(权值)4抽象地图: 11109 8 7 6 532注释：该图为对科大地图抽象的结果。各顶点信息（地点信息和边信息严格按原地图制作，故直接见地图）：1 ：北门 2：圆盘岔路口 3：东路岔路口 4：核科学院 5：生命科学院 6：西区学生活动中心 7：校车站 8：电三楼 9：火灾重点实验室 10：南环路岔路口 11：国家同步实验室 。（计算机中表示顶点号要减去1）（2）、地图信息的计算机信息表达图文件节点代码（采用邻接表方式存储）：图
2、信息定义于“节点定义.h”中，用于底层数据类型支持，其中重载了图的输入输出运算符，图中的节点和边的比较与赋值运算符等。#define MAX_VERTEX_NUM 20typedef struct InfoType /边信息int length;char*name;InfoType;typedef struct VertexType /地点信息char*name; char*time;char*scribe;VertexType& operator =(VertexType& b);VertexType;typedef struct ArcNode /边intadjvex;ArcNode*ne
3、xtarc;InfoType *info;ArcNode& operator =(ArcNode& b);ArcNode;typedef struct VNode /图的邻接表VertexType* data;ArcNode *firstarc;VNode& operator=(VNode& a);VNode,AdjListMAX_VERTEX_NUM;科大地图的初始化（宏处理方式）：科大地图的初始化在“中科大地图.h”中完成，其中定义了ustc的namespace,在该namespace里有四个全区变量：VertexType VexInfo11; /节点信息矩阵VNode nodeMAX_V
4、ERTEX_NUM; /科大地图的邻接表int Ustcvexnum=0; /邻接表的顶点数int Ustcarcnum=0 ; /邻接表的边数有四个全局函数：void InititaVex(); /初始化顶点信息void InititaNode(); /初始化中科大地图邻接表int Findword(char *p); /根据顶点名找到相应的顶点号char* Findchar(char i); /根据顶点号找到相应的顶点名开始时，采用了很原始的复制粘贴的方式处理重复的数据，可是像这样有一定规模的数据，采用这样低级的方式处理，查询与修改时带来了很多的麻烦，于是设计了四个宏将处理简单化。 DEC
5、LEARE_ VEREXTYPE 宏：使用于InititaVex()函数中，定义如下:#define DECLEARE_VEREXTYPE(dname,dtime,dscribe) i = Findword(dname); VexInfoi.name =dname; VexInfoi.scribe =dtime; VexInfoi.time =dscribe;于是有InititaVex()函数定义如下：Void InititaVex()int i;DECLEARE_VEREXTYPE(“北门”,”无“，”无“)DECLEARE_VEREXTYPE(圆盘岔路口,”无“，”无“)DECLEARE_
6、VEREXTYPE(东路岔路口,”无“，”无“) BEGIN_ARCMAP,ADD_ARCMAP,END_ARCMAP三宏：这三宏使用于InititaNode()中，使用模式如下：BEGIN_ARCMAP(,.)ADD_ARCMAP(,)END_ARCMAP()其定义如下:#define BEGIN_ARCMAP(sname,dname,aname,alength) i = Findword(sname);nodei.data = &VexInfoi;PArcpresent = (ArcNode *) malloc(sizeof(ArcNode);PArcpresent -adjvex = F
7、indword(dname);PArcpresent -nextarc = NULL;PInfoType = (InfoType*)malloc(sizeof(InfoType);PArcpresent -info = PInfoType;PArcpresent -info-length =a length;PArcpresent -info-name =aname;nodei.firstarc = PArcpresent;PArclast = PArcpresent;Ustcarcnum+;#define ADD_ARCMAP(dname,aname,alength)PArcpresent
8、= (ArcNode *) malloc(sizeof(ArcNode);PArcpresent -adjvex = Findword(dname);PArcpresent -nextarc = NULL;PInfoType = (InfoType*)malloc(sizeof(InfoType);PArcpresent -info = PInfoType;PArcpresent -info-length = alength;PArcpresent -info-name =aname;PArclast-nextarc = PArcpresent;PArclast = PArcpresent;U
9、stcarcnum+;#define END_ARCMAP() Ustcvexnum+;i = -1;由以上三宏，InititaVex()函数定义如下：void InititaNode() InititaVex();int i;ArcNode *PArcpresent,*PArclast;InfoType *PInfoType;BEGIN_ARCMAP(“北门”,”圆盘岔路口”,”济慈路”,10)END_ARCMAP()BEGIN_ARCMAP(”圆盘岔路口”,”北门”,”济慈路”,10)ADD_ARCMAP(“东路岔路口”,”东路”,21).END_ARCMAP().于是在主函数里调用ust
10、c: InititaVex()函数即可完成对中科大地图的初始化。二， 图的算法支持：图的各种算法支持定义在CGraph类中，CGraph类声明文件如下:#include 节点定义.h#define VERTEX_NUM 10class CGragh private:AdjList vertices;int vexnum,arcnum; int MinlengthMAX_VERTEX_NUMMAX_VERTEX_NUM; /两顶点之间的最短距离数组char* EnumtraceMAX_VERTEX_NUMMAX_VERTEX_NUM; /记录任意两点之间最短的路径public:CGragh();
11、CGragh(AdjList& a,int vex,int arc);virtual CGragh();protected:void PrintArc(int i,int j); /找到并打印直接相连的i,j顶点之间的路径。int FindMin(int a,int i,int& m); /Dijkstra算法使用函数void Dijkstra(int i);void Dijkstrall();public:int MinlengthPrint(int i,int j);/返回顶点i与j之间的最短距离，并打印其路径。void PrintNode(int i); /打印顶点i的信息void TS
12、Pnum(int n); /选择图中n个顶点，进行TSP求解;各种函数的说明均在其中，该类按如下过程完成对多种功能的支持:（1） 构造函数读入过程:构造函数，完成读入过程，较为简单，代码如下:CGragh:CGragh(AdjList& a,int vex,int arc)int i,j;for(i=0;iMAX_VERTEX_NUM;i+) /读入各种数据,邻接表verticesi = ai;arcnum = arc;vexnum = vex;for(i=0;iMAX_VERTEX_NUM;i+)/初始化两记录数组for(j=0;jMAX_VERTEX_NUM;j+)Minlengthij
13、= -1;Enumtraceij = NULL;Dijkstrall();（2） Dijkstrall算法记录过程:Dijkstra算法是图算法的核心，以后所有的各种操作均是以算法完成后的记录的数组为基础的，为这个算法支持类的核心，故详细列出讲解：Dijkstrall()函数：void CGragh:Dijkstrall()int i;for(i =0 ;ivexnum;i+)Dijkstra(i); /调用Dijkstra(int i)函数对各顶点进行运算Dijkstra(int i)函数(函数写得匆忙，故变量命名没有太注意)：void CGragh:Dijkstra(int i) int k,j,minx,g=0; /临时保存顶点的变量 int temp,temp1,min; /临时保存路径长度的变量 char a10，b
