中科大地圖導(dǎo)航(實(shí)驗(yàn)報(bào)告).docx

中科大地圖導(dǎo)航一， 科大西區(qū)地圖的構(gòu)建與表示：（1）、物理地圖的抽象表達(dá)地圖選擇:科大西區(qū)地圖節(jié)點(diǎn)數(shù)：12邊數(shù)：15 1地點(diǎn)信息：地點(diǎn)名，時(shí)間，簡(jiǎn)介，街道名，街道長(zhǎng)度(權(quán)值)4抽象地圖: 11109 8 7 6 532注釋：該圖為對(duì)科大地圖抽象的結(jié)果。各頂點(diǎn)信息（地點(diǎn)信息和邊信息嚴(yán)格按原地圖制作，故直接見地圖）：1 ：北門 2：圓盤岔路口 3：東路岔路口 4：核科學(xué)院 5：生命科學(xué)院 6：西區(qū)學(xué)生活動(dòng)中心 7：校車站 8：電三樓 9：火災(zāi)重點(diǎn)實(shí)驗(yàn)室 10：南環(huán)路岔路口 11：國(guó)家同步實(shí)驗(yàn)室 。（計(jì)算機(jī)中表示頂點(diǎn)號(hào)要減去1）（2）、地圖信息的計(jì)算機(jī)信息表達(dá)圖文件節(jié)點(diǎn)代碼（采用鄰接表方式存儲(chǔ)）：圖信息定義于“節(jié)點(diǎn)定義.h”中，用于底層數(shù)據(jù)類型支持，其中重載了圖的輸入輸出運(yùn)算符，圖中的節(jié)點(diǎn)和邊的比較與賦值運(yùn)算符等。#define MAX_VERTEX_NUM 20typedef struct InfoType /邊信息int length;char*name;InfoType;typedef struct VertexType /地點(diǎn)信息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里有四個(gè)全區(qū)變量：VertexType VexInfo11; /節(jié)點(diǎn)信息矩陣VNode nodeMAX_VERTEX_NUM; /科大地圖的鄰接表int Ustcvexnum=0; /鄰接表的頂點(diǎn)數(shù)int Ustcarcnum=0 ; /鄰接表的邊數(shù)有四個(gè)全局函數(shù)：void InititaVex(); /初始化頂點(diǎn)信息void InititaNode(); /初始化中科大地圖鄰接表int Findword(char *p); /根據(jù)頂點(diǎn)名找到相應(yīng)的頂點(diǎn)號(hào)char* Findchar(char i); /根據(jù)頂點(diǎn)號(hào)找到相應(yīng)的頂點(diǎn)名開始時(shí)，采用了很原始的復(fù)制粘貼的方式處理重復(fù)的數(shù)據(jù)，可是像這樣有一定規(guī)模的數(shù)據(jù)，采用這樣低級(jí)的方式處理，查詢與修改時(shí)帶來了很多的麻煩，于是設(shè)計(jì)了四個(gè)宏將處理簡(jiǎn)單化。 DECLEARE_ VEREXTYPE 宏：使用于InititaVex()函數(shù)中，定義如下:#define DECLEARE_VEREXTYPE(dname,dtime,dscribe) i = Findword(dname); VexI =dname; VexInfoi.scribe =dtime; VexInfoi.time =dscribe;于是有InititaVex()函數(shù)定義如下：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()函數(shù)定義如下：void InititaNode() InititaVex();int i;ArcNode *PArcpresent,*PArclast;InfoType *PInfoType;BEGIN_ARCMAP(“北門”,”圓盤岔路口”,”濟(jì)慈路”,10)END_ARCMAP()BEGIN_ARCMAP(”圓盤岔路口”,”北門”,”濟(jì)慈路”,10)ADD_ARCMAP(“東路岔路口”,”東路”,21).END_ARCMAP().于是在主函數(shù)里調(diào)用ustc: InititaVex()函數(shù)即可完成對(duì)中科大地圖的初始化。二， 圖的算法支持：圖的各種算法支持定義在CGraph類中，CGraph類聲明文件如下:#include 節(jié)點(diǎn)定義.h#define VERTEX_NUM 10class CGragh private:AdjList vertices;int vexnum,arcnum; int MinlengthMAX_VERTEX_NUMMAX_VERTEX_NUM; /兩頂點(diǎn)之間的最短距離數(shù)組char* EnumtraceMAX_VERTEX_NUMMAX_VERTEX_NUM; /記錄任意兩點(diǎn)之間最短的路徑public:CGragh();CGragh(AdjList& a,int vex,int arc);virtual CGragh();protected:void PrintArc(int i,int j); /找到并打印直接相連的i,j頂點(diǎn)之間的路徑。int FindMin(int a,int i,int& m); /Dijkstra算法使用函數(shù)void Dijkstra(int i);void Dijkstrall();public:int MinlengthPrint(int i,int j);/返回頂點(diǎn)i與j之間的最短距離，并打印其路徑。void PrintNode(int i); /打印頂點(diǎn)i的信息void TSPnum(int n); /選擇圖中n個(gè)頂點(diǎn)，進(jìn)行TSP求解;各種函數(shù)的說明均在其中，該類按如下過程完成對(duì)多種功能的支持:（1） 構(gòu)造函數(shù)讀入過程:構(gòu)造函數(shù)，完成讀入過程，較為簡(jiǎn)單，代碼如下:CGragh:CGragh(AdjList& a,int vex,int arc)int i,j;for(i=0;iMAX_VERTEX_NUM;i+) /讀入各種數(shù)據(jù),鄰接表verticesi = ai;arcnum = arc;vexnum = vex;for(i=0;iMAX_VERTEX_NUM;i+)/初始化兩記錄數(shù)組for(j=0;jMAX_VERTEX_NUM;j+)Minlengthij = -1;Enumtraceij = NULL;Dijkstrall();（2） Dijkstrall算法記錄過程:Dijkstra算法是圖算法的核心，以后所有的各種操作均是以算法完成后的記錄的數(shù)組為基礎(chǔ)的，為這個(gè)算法支持類的核心，故詳細(xì)列出講解：Dijkstrall()函數(shù)：void CGragh:Dijkstrall()int i;for(i =0 ;ivexnum;i+)Dijkstra(i); /調(diào)用Dijkstra(int i)函數(shù)對(duì)各頂點(diǎn)進(jìn)行運(yùn)算Dijkstra(int i)函數(shù)(函數(shù)寫得匆忙，故變量命名沒有太注意)：void CGragh:Dijkstra(int i) int k,j,minx,g=0; /臨時(shí)保存頂點(diǎn)的變量 int temp,temp1,min; /臨時(shí)保存路徑長(zhǎng)度的變量 char a10，b2; /臨時(shí)保存各路徑字符串，如”012”，就是從0號(hào)頂點(diǎn)到1號(hào)再到2號(hào)頂點(diǎn)。 char *p; /用于生成最終要保存的路徑字符串空間，更改其值。/遍歷生成i號(hào)頂點(diǎn)與其他頂點(diǎn)之間的最短距離，與最短路徑字符串 for(j = 1;j vexnum;j+) p = (char*) malloc(10 * sizeof(char); /先在i頂點(diǎn)里找出其能直接到達(dá)，且記錄數(shù)組未記錄的最近頂點(diǎn) /FindMin函數(shù)找出a頂點(diǎn)能直接到達(dá)，且Minlengthi沒有記錄/的最近頂點(diǎn)，返回該頂點(diǎn)號(hào)（如果都已記錄則返回-1），長(zhǎng)度記錄在/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+) /接下來，分析已記錄的頂點(diǎn)if(k = i) continue;if(Minlengthik != -1) temp = Minlengthik; /長(zhǎng)度加上已記錄的頂點(diǎn)strcpy(a,Enumtraceik); /路徑加上已記錄路徑/找到該頂點(diǎn)里能直接到達(dá)，未記錄且最近的頂點(diǎn)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） 各種外部接口，完成相應(yīng)功能：int MinlengthPrint(int i,int j);/返回頂點(diǎn)i與j之間的最短距離，并打印其路徑。void PrintNode(int i); /打