中科大地图导航(实验报告).docx

中科大地图导航一， 科大西区地图的构建与表示：（1）、物理地图的抽象表达地图选择:科大西区地图节点数：12边数：15 1地点信息：地点名，时间，简介，街道名，街道长度(权值)4抽象地图: 11109 8 7 6 532注释：该图为对科大地图抽象的结果。各顶点信息（地点信息和边信息严格按原地图制作，故直接见地图）：1 ：北门 2：圆盘岔路口 3：东路岔路口 4：核科学院 5：生命科学院 6：西区学生活动中心 7：校车站 8：电三楼 9：火灾重点实验室 10：南环路岔路口 11：国家同步实验室 。（计算机中表示顶点号要减去1）（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*nextarc;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_VERTEX_NUM; /科大地图的邻接表int Ustcvexnum=0; /邻接表的顶点数int Ustcarcnum=0 ; /邻接表的边数有四个全局函数：void InititaVex(); /初始化顶点信息void InititaNode(); /初始化中科大地图邻接表int Findword(char *p); /根据顶点名找到相应的顶点号char* Findchar(char i); /根据顶点号找到相应的顶点名开始时，采用了很原始的复制粘贴的方式处理重复的数据，可是像这样有一定规模的数据，采用这样低级的方式处理，查询与修改时带来了很多的麻烦，于是设计了四个宏将处理简单化。 DECLEARE_ VEREXTYPE 宏：使用于InititaVex()函数中，定义如下:#define DECLEARE_VEREXTYPE(dname,dtime,dscribe) i = Findword(dname); VexI =dname; VexInfoi.scribe =dtime; VexInfoi.time =dscribe;于是有InititaVex()函数定义如下：Void InititaVex()int i;DECLEARE_VEREXTYPE(“北门”,”无“，”无“)DECLEARE_VEREXTYPE(圆盘岔路口,”无“，”无“)DECLEARE_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 = Findword(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 = (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;Ustcarcnum+;#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().于是在主函数里调用ustc: 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();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 TSPnum(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 = -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，b2; /临时保存各路径字符串，如”012”，就是从0号顶点到1号再到2号顶点。 char *p; /用于生成最终要保存的路径字符串空间，更改其值。/遍历生成i号顶点与其他顶点之间的最短距离，与最短路径字符串 for(j = 1;j vexnum;j+) p = (char*) malloc(10 * sizeof(char); /先在i顶点里找出其能直接到达，且记录数组未记录的最近顶点 /FindMin函数找出a顶点能直接到达，且Minlengthi没有记录/的最近顶点，返回该顶点号（如果都已记录则返回-1），长度记录在/min里，稍后给出源码。if( (minx = FindMin(i,i,min) = -1)min = MAXINT; /如周边都已记录，初始化min为MAXINT。else*p = (char) i + 0x30;*(p+1) = (char) minx + 0x30;*(p+2) = 0;for(k=0;k vexnum;k+) /接下来，分析已记录的顶点if(k = i) continue;if(Minlengthik != -1) temp = Minlengthik; /长度加上已记录的顶点strcpy(a,Enumtraceik); /路径加上已记录路径/找到该顶点里能直接到达，未记录且最近的顶点if( (g = FindMin(k,i,temp1) = -1) continue; b0 = (char) g + 0x30;b1 = 0;strcat(a,b);temp += temp1;if(temp adjvex = -1 & PN1-info-length adjvex != i)min = PN1-adjvex;temp = PN1-info-length;PN1 = PN1-nextarc;if(min = MAXINT) return -1;elsem = temp;return min;（3） 各种外部接口，完成相应功能：int MinlengthPrint(int i,int j);/返回顶点i与j之间的最短距离，并打印其路径。void PrintNode(int i); /打