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

PB12009002PB12009002康海濤2/11中科大地圖導(dǎo)航一，科大西區(qū)地圖的構(gòu)建與表示：、物理地圖的抽象表達(dá)地圖選擇:科大西區(qū)地圖節(jié)點(diǎn)數(shù)：12邊數(shù)：15地點(diǎn)信息：地點(diǎn)名，時(shí)間，簡(jiǎn)介，街道名，街道長(zhǎng)度(權(quán)值)抽象地圖抽象地圖:1423567910811注釋?zhuān)涸搱D為對(duì)科大地圖抽象的結(jié)果。各頂點(diǎn)信息〔地點(diǎn)信息和邊信息嚴(yán)格按原地圖制作，故直接見(jiàn)地圖〕：1：北門(mén) 2：圓盤(pán)岔路口3：東路岔路口4：核科學(xué)院5：生命科學(xué)院6：西區(qū)學(xué)生活動(dòng)中心7：校車(chē)站8：電三樓 9：火災(zāi)重點(diǎn)試驗(yàn)室10：南環(huán)路岔路口 國(guó)家同步試驗(yàn)室。〔計(jì)算機(jī)中表示頂點(diǎn)號(hào)要減去1〕、地圖信息的計(jì)算機(jī)信息表達(dá)圖文件節(jié)點(diǎn)代碼〔承受鄰接表方式存儲(chǔ)〕：算符，圖中的節(jié)點(diǎn)和邊的比較與賦值運(yùn)算符等。#defineMAX_VERTEX_NUM20typedefstructInfoType //邊信息{int length;char* }InfoType;typedefstructVertexType //地點(diǎn)信息{char* name;char* time;char* scribe;VertexType&operator=(VertexType&b);}VertexType;typedefstructArcNode //邊{int adjvex;ArcNodeInfoType*info;

*nextarc;ArcNode&operator=(ArcNode&b);}ArcNode;typedefstructVNode //圖的鄰接表{VertexType*data;ArcNode*firstarc;VNode&operator=(VNode&a);}VNode,AdjList[MAX_VERTEX_NUM];科大地圖的初始化〔宏處理方式〕：科大地圖的初始化在“中科大地圖.h”中完成，其中定義了ustcnamespace,在該namespaceVertexTypeVexInfo[11]; //節(jié)點(diǎn)信息矩陣VNodenode[MAX_VERTEX_NUM]; 科大地圖的鄰接表intUstcvexnum=0; //鄰接表的頂點(diǎn)數(shù)intUstcarcnum=0 有四個(gè)全局函數(shù)：voidInititaVex; //初始化頂點(diǎn)信息voidInititaNode; //初始化中科大地圖鄰接表intFindword(char*p);char*Findchar(chari);

//依據(jù)頂點(diǎn)名找到相應(yīng)的頂點(diǎn)號(hào)//依據(jù)頂點(diǎn)號(hào)找到相應(yīng)的頂點(diǎn)名開(kāi)頭時(shí)，承受了很原始的復(fù)制粘貼的方式處理重復(fù)的數(shù)據(jù)，可是像這樣有肯定規(guī)模的數(shù)據(jù)，承受這樣低級(jí)的方式處理，查詢(xún)與修改時(shí)帶來(lái)了很多的麻煩，于是設(shè)計(jì)了四個(gè)宏將處理簡(jiǎn)潔化。①DECLEARE_VEREXTYPE宏：InititaVex函數(shù)中，定義如下:#defineDECLEARE_VEREXTYPE(dname,dtime,dscribe)\i=Findword(dname);\VexInfo[i].name=dname;\VexInfo[i].scribe=dtime;\VexInfo[i].time=dscribe;InititaVex函數(shù)定義如下：VoidInititaVex{int i;DECLEARE_VEREXTYPE(“北門(mén)”,”無(wú)“，”無(wú)“)圓盤(pán)岔路口“,”無(wú)“，”無(wú)“)東路岔路口“,”無(wú)“，”無(wú)“)…}②BEGIN_ARCMAP,ADD_ARCMAP,END_ARCMAPInititaNode中，使用模式如下：BEGIN_ARCMAP(…,…,…,..)ADD_ARCMAP(…,…,…)END_ARCMAP其定義如下:#define BEGIN_ARCMAP(sname,dname,aname,alength)\i=Findword(sname);\node[i].data=&VexInfo[i];\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;\node[i].firstarc=PArcpresent;\PArclast=PArcpresent;\Ustcarcnum++;5/11PB12009002康海濤#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ù)定義如下：voidInititaNode{InititaVex;inti;ArcNode*PArcpresent,*PArclast;InfoType*PInfoType;BEGIN_ARCMAP(“北門(mén)”,”圓盤(pán)岔路口”,”濟(jì)慈路”,10)END_ARCMAPBEGIN_ARCMAP(”圓盤(pán)岔路口”,”北門(mén)”,”濟(jì)慈路”,10)PB12009002康海濤PB12009002康海濤6/11ADD_ARCMAP(,21)….END_ARCMAP…..}于是在主函數(shù)里調(diào)用ustc::InititaVex函數(shù)即可完成對(duì)中科大地圖的初始化。二，圖的算法支持：圖的各種算法支持定義在CGraphCGraph#include.h“#defineVERTEX_NUM10classCGragh{private:AdjListvertices;intvexnum,arcnum;數(shù)組

之間的最短距離char*Enumtrace[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//記錄任意兩點(diǎn)之間最短的路徑public:CGragh;CGragh(AdjList&a,intvex,intarc);virtual~CGragh;protected:voidPrintArc(inti,intj/接相連的ij點(diǎn)之間的路徑。intFindMin(inta,inti,int&m);算avoidDijkstra(inti);voidDijkstrall;public:intMinlengthPrint(intini與j之間的最短距離，并打印其路徑。打voidTSPnum(intn);選擇圖//nTSP};各種函數(shù)的說(shuō)明均在其中，該類(lèi)按如下過(guò)程完成對(duì)多種功能的支持:CGrapCGraph〔a,vex,ac調(diào)用DijkstralDijkstrDijkstrl兩個(gè)記錄數(shù)組內(nèi)。應(yīng)查詢(xún)功能。構(gòu)造函數(shù)讀入過(guò)程:構(gòu)造函數(shù)，完成讀入過(guò)程，較為簡(jiǎn)潔，代碼如下:CGragh::CGragh(AdjList&a,intvex,intarc){inti,j;for(i=0;i<MAX_VERTEX_NUM;i++) 讀入各種數(shù)//,鄰接表PB12009002PB12009002康海濤10/11{vertices[i]=a[i];}arcnum=arc;vexnum=vex;for(i=0;i<MAX_VERTEX_NUM;i++)for(j=0;j<MAX_VERTEX_NUM;j++){

//初始化兩記錄數(shù)組Minlength[i][j]=-1;Enumtrace[i][j]=NULL;}Dijkstrall;}DijkstrallDijkstra的數(shù)組為根底的，為這個(gè)算法支持類(lèi)的核心，故具體列出講解：Dijkstrall函數(shù)：voidCGragh::Dijkstrall{inti;for(i=0;i<vexnum;i++)Dijkstra(i); //Dijkstra(inti)函數(shù)對(duì)各頂點(diǎn)進(jìn)展運(yùn)算}Dijkstra(inti)函數(shù)(函數(shù)寫(xiě)得匆忙，故變量命名沒(méi)有太留意)：voidCGragh::Dijkstra(inti){intk,j,minx,g=0; //臨時(shí)保存頂點(diǎn)的變量inttemp,temp1,min; //臨時(shí)保存路徑長(zhǎng)度的變量chara[10]，b[2];//臨時(shí)保存各路徑字符串，如”012”012號(hào)頂點(diǎn)。char*p; //用于生成最終要保存的路徑字符串空間，更改其值。//i號(hào)頂點(diǎn)與其他頂點(diǎn)之間的最短距離，與最短路徑字符串for(j1;jvexnum;j++){p=(char*)malloc(10*sizeof(char));//i頂點(diǎn)里找出其能直接到達(dá)，且記錄數(shù)組未記錄的最近頂點(diǎn)//FindMin函數(shù)找出aMinlength[i]沒(méi)有記錄//的最近頂點(diǎn)，返回該頂點(diǎn)號(hào)〔假設(shè)都已記錄則返回-1〕，長(zhǎng)度記錄在//min里，稍后給出源碼。if((minx=FindMin(i,i,min))==-1){}else{

minMAXINT; // minMAXINT。*p=(char)i+0x30;*(p+1)=(char)minx+0x30;*(p+2)=”\0”;}for(k=0;kvexnum;k++) //接下來(lái)，分析已記錄的頂點(diǎn){if(k==i)continue;if(Minlength[i][k]!=-1){temp=Minlength[i][k]; //長(zhǎng)度加上已記錄的頂點(diǎn)strcpy(a,Enumtrace[i][k]); //路徑加上已記錄路徑//找到該頂點(diǎn)里能直接到達(dá)，未記錄且最近的頂點(diǎn)if((g=FindMin(k,i,temp1))==-1)continue;b[0]=(char)g+0x30;b[1]=”\0”;strcat(a,b);temp+=temp1;if(tempmin) //循環(huán)推斷找到當(dāng)前最近的頂點(diǎn){min=temp;minx=g;strcpy(p,a);}}}//記錄入數(shù)組Minlength[i][minx]=min;Enumtrace[i][minxp;}}DijkstraDijkstra很多的重復(fù)計(jì)算，造成較高的運(yùn)算時(shí)間，還有很多需要改進(jìn)的地方。FindMinintCGragh::FindMin(inta,inti,int&m){inttemp=MAXINT,min=MAXINT;ArcNode*PN1=vertices[a].firstarc;while(PN1){if(Minlength[i][PN1->adjvex]==-1&&PN1->info->length<temp&&PN1->adjvex!=i)11/11PB12009002康海濤{min=PN1->adjvex;temp=PN1->info->length;}PN1=PN1->nextarc;}if(min==MAXINT)return-1;else{m=temp;returnmin;}}各種外部接口，完