數(shù)據(jù)結(jié)構(gòu)旅游區(qū)導(dǎo)航圖課程設(shè)計

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告內(nèi)容及其格式數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告題 目 旅游區(qū)導(dǎo)游圖 專 業(yè) 計算機科學與技術(shù) 班 級 （2）班 學 生 # 13 旅游區(qū)導(dǎo)游圖題目內(nèi)容問題描述：設(shè)某個旅游區(qū)共有n個旅游景點（n10）,每個旅游景點都和相鄰的m個旅游景點（m2，m<n）有直接的道路（有對應(yīng)的距離）相通，請設(shè)計一個簡易的旅游區(qū)導(dǎo)游系統(tǒng)。以(Vi ,Vj ,d)的形式從鍵盤輸入建立該旅游區(qū)的旅游景點圖，其中：Vi和Vj表示兩個不同的旅游景點，d表示這兩個景點之間的道路距離；該旅游景點圖采用鄰接矩陣存儲結(jié)構(gòu)(數(shù)組)。實現(xiàn)要求： 旅游景點圖的輸出：分別以鄰接矩陣、鄰接鏈表的方式輸出該旅游景點圖。 相鄰景點查詢

2、：假設(shè)對于每個景點，設(shè)置有簡易的信息查詢，要求能給出與該景點相鄰的所有景點(有直接的道路相通)及對應(yīng)的距離。 景點路線查詢：假設(shè)對于每個景點，設(shè)置有景點路線查詢，要求能給出從該景點出發(fā)到任一其它景點的最短簡單路徑及距離。 景點路線綜合查詢：對于該旅游區(qū)的任意兩個景點，找出它們之間的最短簡單路徑及距離。 最佳旅游路線確定：假設(shè)該旅游區(qū)的入口也是出口，請確定一條最佳的旅游線路，該線路必須經(jīng)過所有的旅游景點（有些景點可以重復(fù)經(jīng)過）且走的路最短。 設(shè)計一個菜單，上述操作要求都作為菜單中的主要菜單項。1 本人完成的工作 完成的工作：首先是用鄰接矩陣的存儲形式建立無向帶權(quán)圖，然后將鄰接矩陣轉(zhuǎn)換為鄰接鏈表，

3、最后用狄克斯特拉函數(shù)求出后面的三道有關(guān)最短路徑的小題，設(shè)計主函數(shù)。2 所采用的數(shù)據(jù)結(jié)構(gòu)鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)，包括（弧/邊的結(jié)構(gòu)定義、圖的結(jié)構(gòu)定義）鄰接鏈表的數(shù)據(jù)結(jié)構(gòu)，包括（弧/邊的結(jié)點定義、鄰接表頭結(jié)點定義、圖的結(jié)構(gòu)定義）數(shù)據(jù)結(jié)構(gòu)的定義/鄰接矩陣結(jié)構(gòu)體typedef struct char vex1, vex2 ; /* 弧或邊所依附的兩個頂點 */int ArcVal ; /* 弧或邊的權(quán)值 */ArcType ; /* 弧或邊的結(jié)構(gòu)定義 */typedef struct int vexnum, arcnum ; /* 圖的當前頂點數(shù)和弧數(shù) */char vexsMAXVEX ; /* 頂點向

4、量 */int adjMAXVEXMAXVEX;MGraph ; /* 圖的結(jié)構(gòu)定義 */鄰接鏈表結(jié)構(gòu)體typedef struct ANode /弧的結(jié)點結(jié)構(gòu)類型 int adjvex; /該弧的終點位置int info; /該弧的相關(guān)信息,這里用于存放權(quán)值struct ANode *nextarc; /指向下一條弧的指針 ArcNode;typedef struct Vnode /鄰接表頭結(jié)點的類型 char data; /頂點信息ArcNode *firstarc; /指向第一條弧 VNode;typedef struct VNode AdjListMAXVEX;int vexnum,a

5、rcnum; /圖中頂點數(shù)n和邊數(shù)e ALGraph; /圖的鄰接表類型3 所設(shè)計的函數(shù)對于每個主要函數(shù)必須給出所采用的算法思想和程序框圖；鄰接矩陣和鄰接鏈表初始化函數(shù)MGraph *Init_MGraph()/* 圖的初始化 */ MGraph *G;G=(MGraph *)malloc(sizeof(MGraph) ;G->vexnum=0 ; G->arcnum=0 ; /* 初始化頂點數(shù)、邊數(shù) */return(G) ; ALGraph *Init_ALGraph()/* 圖的初始化 */ ALGraph *G;G=(ALGraph *)malloc(sizeof(ALGr

6、aph) ;G->vexnum=0 ;G->arcnum=0; /* 初始化頂點數(shù) */return(G) ; 圖中頂點定位的函數(shù)，判斷頂點是否重復(fù)輸入了int LocateVex(MGraph *G, char vp) /* 圖中頂點的定位，若圖中有頂點vp，返回其在頂點數(shù)組的下標值 */ int k ;for (k=0; k<=G->vexnum; k+)if (G->vexsk=vp) return(k) ; 開始k=0返回-1k<=頂點總數(shù)？G->vexsk=vp？返回k結(jié)束k+return(-1) ; /* 圖中無此頂點 */ N N Y Y

7、 往圖中增加頂點的函數(shù)void AddVertex(MGraph *G, char vp) /* 往圖的頂點數(shù)組中增加頂點 */ int k, j ;if (G->vexnum>=MAXVEX)printf("圖中頂點數(shù)已達到最多 !n"); elseif (LocateVex(G, vp)=-1) k=G->vexnum ; G->vexsG->vexnum+=vp ;for (j=0 ; j<G->vexnum ; j+) G->adjjk=INFINITY ;G->adjkj=INFINITY ;/* 是帶權(quán)的有向

8、圖或無向圖 */開始把這個點跟其他所有點建立關(guān)系，為INFINITY，表示不存在連通關(guān)系新增加一個頂點給k賦值=頂點總數(shù)調(diào)用函數(shù)LocateVex，判斷頂點是否有重復(fù)判斷頂點數(shù)目是否已經(jīng)超過最大值結(jié)束 N Y N Y 往圖的鄰接矩陣中添加邊(弧)void AddArc(MGraph *G , ArcType *arc) /* 往圖的鄰接矩陣中添加邊(弧) */ int k=0, j=0;k=LocateVex(G, arc->vex1) ;j=LocateVex(G, arc->vex2) ;if (k=-1|j=-1)printf("邊或弧的頂點不存在，錯誤 !n&qu

9、ot;) ; else G->arcnum+ ;G->adjkj=arc->ArcVal ;G->adjjk=arc->ArcVal ;/* 是無向圖或帶權(quán)的無向圖,需對稱賦值 */開始給兩個頂點之間加上權(quán)值邊數(shù)加一判斷弧所依托的兩個頂點是否存在結(jié)束輸出圖的頂點矩陣和鄰接矩陣void output_graphic(MGraph *G) /* 輸出圖的頂點矩陣和鄰接矩陣 */ int k, j ;printf("圖的頂點如下：n") ; for (k=0; k<G->vexnum; k+)printf("%4c",

10、G->vexsk) ;printf("nn") ;printf("圖的鄰接矩陣如下：n") ; for (k=0; k<G->vexnum; k+)for (j=0; j<G->vexnum; j+)輸出*判斷兩個頂點之間是否存在連通j+輸出權(quán)值開始結(jié)束j=0k=0k+k=0輸出第k個頂點判斷j是否小于頂點總數(shù)判斷k是否小于頂點總數(shù)判斷k是否小于頂點總數(shù)k+if (G->adjkj=INFINITY) printf("%4s","*") ;else printf("%4

11、d",G->adjkj) ;printf("nn") ; Y N Y N Y以鄰接矩陣作為圖的存儲結(jié)構(gòu)建立圖MGraph *create_graph()/* 以鄰接矩陣作為圖的存儲結(jié)構(gòu)建立圖 */ char inchar100, enchar100,fvex,lvex ;int count=0;int weight ; MGraph *G;ArcType *arc ;printf("首先進行圖的初始化!nn") ;G=(MGraph *)malloc(sizeof(MGraph) ;G=Init_MGraph() ;arc=(ArcTyp

12、e *)malloc(sizeof(ArcType) ; printf("n請以(頂點,頂點,權(quán)值)的形式輸入圖的邊(或弧)，第一個頂點是?表示結(jié)束：n") ; while(1) scanf("%s",inchar) ;fvex=inchar0 ; /* 輸入第一個頂點，?結(jié)束 */ if (fvex='?') break ; else AddVertex(G, fvex) ; scanf("%s",enchar) ;lvex=enchar0 ;AddVertex(G, lvex) ; scanf("%d&q

13、uot;,&weight) ; /* 輸入第二個頂點和權(quán)值 */ arc->vex1=fvex ; arc->vex2=lvex ; arc->ArcVal=weight ; AddArc(G, arc) ; printf("n請繼續(xù)輸入下一條邊(或弧)!n") ; return(G) ;將鄰接矩陣g轉(zhuǎn)換成鄰接表GALGraph *MGraphToALGraph(MGraph *g,ALGraph *G)int i,j,n=g->vexnum; /n為頂點數(shù)ArcNode *p;G=(ALGraph *)malloc(sizeof(ALGra

14、ph);G->arcnum = g->arcnum;G->vexnum = g->vexnum;for(i=0;i<G->vexnum;i+)G->AdjListi.firstarc = NULL;for (i=0;i<n;i+) /檢查鄰接矩陣中每個元素 for (j=n-1;j>=0;j-)if (g->adjij!=INFINITY) /鄰接矩陣的當前元素不為 p=(ArcNode *)malloc(sizeof(ArcNode); /創(chuàng)建一個結(jié)點*pG->AdjListj.data=g->vexsj;p->a

15、djvex = g->vexsj;p->info=g->adjij;p->nextarc=G->AdjListi.firstarc; /將*p鏈到鏈表后G->AdjListi.firstarc=p;return G;j-給鄰接點賦上鄰接矩陣對應(yīng)的頂點i+判斷兩頂點之間是否有連通頭結(jié)點數(shù)組指針指向相連通的鄰接點給鄰接邊賦上權(quán)值結(jié)束開始返回鄰接表G把鄰接矩陣的頂點總數(shù)賦值給鄰接鏈表的頂點總數(shù)把鄰接矩陣的邊總數(shù)賦值給鄰接鏈表的邊總數(shù)把頂點總數(shù)賦值給nj=n-1i=0用循環(huán)結(jié)構(gòu)把每一個頂點的頭指針初始化j>=0?i<n?鄰接鏈表的輸出void outpu

16、t_graphic_c(MGraph *g,ALGraph *G)int i;ArcNode *p;for (i=0;i<g->vexnum;i+)printf("%c",G->AdjListi.data) ; p=G->AdjListi.firstarc;while(p!=NULL) printf("%s","->") ;printf("(%c,%d)",p->adjvex,p->info) ;p=p->nextarc ;printf("nn")

17、;相鄰景點查詢并輸出void output_Find_ALGraph(ALGraph *G) /* 相鄰景點查詢并輸出 */int j;ArcNode *p; printf("請輸入你要查詢的景點(下標值):n");scanf("%d",&j); p=G->AdjListj.firstarc;while(p)printf("景點%c到景點%c的距離是%d (該兩個景點之間有直接的道路相通)n",G->AdjListj.data,p->adjvex,p->info);p=p->nextarc;開始結(jié)

18、束輸出兩個頂點之間的距離把該景點在數(shù)組中的鄰接邊的頭指針賦值給p輸入景點對應(yīng)的下標值判斷鄰接邊單鏈表的結(jié)點指針是否為空p指向下一個結(jié)點指針printf("nn"); 景點路線查詢：假設(shè)對于每個景點，設(shè)置有景點路線查詢，要求能給出從該景點出發(fā)到任一其它景點的最短簡單路徑及距離。void Dijkstra_One(ALGraph *G, MGraph *g,int v0,int distance, int pre) / 帶權(quán)圖G從頂點v0到其他定點的最短距離distance和最短路徑前驅(qū)結(jié)點的下標preint w;int S30,i,j,k,p,min;printf("

19、;你所要開始查詢的景點是:%cn",G->AdjListv0.data);for(i=0;i<g->vexnum;i+)distancei=g->adjv0i;Si=0;if(distancei< INFINITY)prei=v0;else prei=-1; Sv0=1; /頂點v0已加入到集合S中for(i=0;i<g->vexnum;i+)min=INFINITY;for(j=0;j<g->vexnum;j+)if(!Sj&&distancej<min) min=distancej;k=j;Sk=1; /

20、將找到的頂點加入到集合S中for(w=0;w<g->vexnum;w+) / /修改集合T中頂點的距離值if(!Sw&&distancew>distancek+g->adjkw)distancew=distancek+g->adjkw;prew=k; printf("查詢結(jié)果:n");for(j=0;j<g->vexnum;j+) /輸出結(jié)果if(prej!=-1) printf("從景點%c到景點%c",G->AdjListv0.data,g->vexsj);p=prej;print

21、f("的最短距離是: %d",distancej);printf(" 途中經(jīng)過的景點有:");while(p!=-1)printf(" %c",g->vexsp);p=prep;printf("n"); else if(j!=v0) printf("n%c到%c : no path",g->vexsj,g->vexsv0);開始用循環(huán)結(jié)構(gòu)實現(xiàn)各數(shù)組的初始化輸入要查詢景點的下標值定義最短路徑的終點集數(shù)組S置S=v0求出當前最小的distj值w=0將第j個頂點放入S中結(jié)束從v0到w

22、的最短路徑中，w的前一個頂點是k判斷w是否小于頂點總數(shù)從V0出發(fā)中間只經(jīng)過集合S中的頂點而到達Vw的所有路徑中長度最小的路徑長度distancew是否大于distancew+邊adjkw的值從V0出發(fā)到w的最短距離distancew= 從V0出發(fā)到w的最短距離distancek+邊adjkw的權(quán)值w+查詢結(jié)果輸出 N Y景點路線綜合查詢：對于該旅游區(qū)的任意兩個景點，找出它們之間的最短簡單路徑及距離。void Dijkstra_Two(ALGraph *G, MGraph *g,int v0,int distance, int pre) / 帶權(quán)圖G從頂點v0到其他定點的最短距離distance

23、和最短路徑前驅(qū)結(jié)點的下標preint w;int S30,i,j,k,p,min,d;printf("你所要開始查詢的開始景點是:%cnn",G->AdjListv0.data);for(i=0;i<g->vexnum;i+)distancei=g->adjv0i;Si=0;if(distancei< INFINITY)prei=v0;else prei=-1; Sv0=1; /頂點v0已加入到集合S中for(i=0;i<g->vexnum;i+)min=INFINITY;for(j=0;j<g->vexnum;j+)i

24、f(!Sj&&distancej<min) min=distancej;k=j;Sk=1; /將找到的頂點加入到集合S中for(w=0;w<g->vexnum;w+) / /修改集合T中頂點的距離值if(!Sw&&distancew>distancek+g->adjkw)distancew=distancek+g->adjkw;prew=k; printf("輸入你要查詢的另外一個景點(下標值):");scanf("%d",&d);printf("你要查詢的另外一個景點

25、是:%cn",g->vexsd);printf("n查詢結(jié)果:n"); /輸出結(jié)果if(pred!=-1) printf("從景點%c到景點%c",G->AdjListv0.data,g->vexsd);p=pred;printf("的最短距離是: %d",distanced);printf(" 途中經(jīng)過的景點有:");while(p!=-1)printf(" %c",g->vexsp);p=prep;開始用循環(huán)結(jié)構(gòu)實現(xiàn)各數(shù)組的初始化輸入要查詢景點的下標值定義最

26、短路徑的終點集數(shù)組S置S=v0printf("n"); 求出當前最小的distj值w=0將第j個頂點放入S中結(jié)束從v0到w的最短路徑中，w的前一個頂點是k判斷w是否小于頂點總數(shù)從V0出發(fā)中間只經(jīng)過集合S中的頂點而到達Vw的所有路徑中長度最小的路徑長度distancew是否大于distancew+邊adjkw的值從V0出發(fā)到w的最短距離distancew= 從V0出發(fā)到w的最短距離distancek+邊adjkw的權(quán)值w+輸入要查詢另外一景點的下標值查詢結(jié)果輸出最佳旅游路線確定：假設(shè)該旅游區(qū)的入口也是出口，請確定一條最佳的旅游線路，該線路必須經(jīng)過所有的旅游景點（有些景點可以重

27、復(fù)經(jīng)過）且走的路最短。void dfs_path(ALGraph *g,int src,int cur,int vis,GPath *cur_path,GPath * min_path)if(vissrc)if(cur_path->count=g->vexnum)if(cur_path->value<min_path->value)memcpy(min_path,cur_path,sizeof(GPath);/*由cur_path所指內(nèi)存區(qū)域復(fù)制sizeof(GPath)個字節(jié)到min_path所指內(nèi)存區(qū)域*/return;return;ArcNode * nod

28、e =g->AdjListcur.firstarc;for(;node!=NULL; node=node->nextarc)/*起始條件為node =g->AdjListcur.firstarc*/char adj=node->adjvex;int index=LocateVex(g,adj);if(visindex=0)cur_path->vertexcur_path->count+=index;cur_path->value+=node->info;visindex=1;dfs_path(g,src,index,vis,cur_path,mi

29、n_path);cur_path->count-;cur_path->value-=node->info;結(jié)束判斷vp是否存在弧頭頂點數(shù)據(jù)元素=LocateVexx(g,adj)最小生成樹權(quán)值加遞歸開始把頂點的值vp復(fù)制給adj把鄰接表數(shù)組的頭指針賦值給node用循環(huán)結(jié)構(gòu)復(fù)制cur_pat的內(nèi)存到min_path判斷鄰接表指針是否為空node指向下一個結(jié)點visindex=0; Y N N Yvoid best_path(ALGraph *g,int src)int visMAXVEX;memset(vis,0,sizeof(vis);GPath cur_path,min_p

30、ath;memset(&cur_path,0,sizeof(GPath);/*將cur_path所指向的某一塊內(nèi)存中的每個字節(jié)的內(nèi)容全部設(shè)置為0指定的ASCII值, 塊的大小由第三個參數(shù)指定,這個函數(shù)通常為新申請的內(nèi)存做初始化工作, 其返回值為指向cur_path的指針。*/memset(&min_path,0,sizeof(GPath);/*將min_path所指向的某一塊內(nèi)存中的每個字節(jié)的內(nèi)容全部設(shè)置為0指定的ASCII值, 塊的大小由第三個參數(shù)指定,這個函數(shù)通常為新申請的內(nèi)存做初始化工作, 其返回值為指向min_path的指針。*/min_path.value=INFIN

31、ITY;dfs_path(g,src,src,vis,&cur_path,&min_path);if(min_path.value!=INFINITY)int i=0;printf("n最佳旅游路線景點下標值是:n");for(i=0; i<min_path.count; i+) printf("%d ->",min_path.vertexi);printf("n");printf("n最佳旅游路線景點是:n");for(i=0; i<min_path.count; i+) pri

32、ntf("%c-> ",g->AdjListmin_path.vertexi.data);printf("n");elseprintf("建立的圖中沒有最佳路徑n");主函數(shù)void main() int n, opse,v0,i;int distanceMAXVEX,pre2*MAXVEX,pathMAXVEX;ALGraph *G; MGraph *M; do printf("nn請選擇對圖的操作要求:nn");for (n=0; n<=30; n+)printf("* "

33、);printf("n* ");printf("1-建立圖的鄰接矩陣 ");printf(" 2-圖的鄰接矩陣的輸出 ");printf(" *n");printf("n* ");printf("3-圖的鄰接鏈表的輸出 ");printf(" 4-相鄰景點查詢 ");printf(" *n");printf("n* ");printf("5- 從某點出發(fā)到另外所有點最短簡單路徑及距離 ");pri

34、ntf(" *n");printf("n* ");printf("6- 兩個景點之間的最短距離(下標值) ");printf(" *n");printf("n* ");printf("7- 最佳路徑 ");printf("8- 退出 ");printf(" *n");for (n=0; n<=30; n+)printf("* ");printf("nn");do scanf("%d

35、",&opse);while (opse<1|opse>8);switch (opse)case 1: M=(MGraph *)malloc(sizeof(MGraph) ; M=create_graph() ; printf("nn"); break ;case 2: printf("n您所建立的圖是：n") ;output_graphic(M) ; break ;case 3: printf(" 圖G的鄰接矩陣轉(zhuǎn)換成鄰接表:n"); G = MGraphToALGraph(M,G); output_g

36、raphic_c(M,G); break ;case 4: printf("n相鄰景點是：n") ;output_Find_ALGraph(G);break ;case 5: printf("n最短簡單路徑及距離是：n") ;scanf(" %d",&v0);Dijkstra _One(G,M,v0,distance,pre);break ;case 6:printf("兩個景點之間的最短距離(下標值):");scanf(" %d",&v0);Dijkstra _Two(G,M,

37、v0,distance,pre);break;case 7:printf("最佳路徑(下標值):");Dijkstra(M,0,distance,path);printf("從結(jié)點%c到其他各結(jié)點的最短距離為:n",M->vexs0);for(i=1;i<M->vexnum;i+)printf("到結(jié)點%c的最短距離為%d:n",M->vexsi,distancei);printf("從結(jié)點%c到其他各結(jié)點最短路徑的前一結(jié)點為:n",M->vexs0);for(i=1;i<M-&

38、gt;vexnum;i+)if(pathi!=-1)printf("到結(jié)點%c的前一結(jié)點為%c:n",M->vexsi,M->vexspathi);break; while(opse!=8);開始請選擇對圖的操作要求n<=30？菜單輸出*n=0n+調(diào)用create_graph()，建立圖breakbreakbreak調(diào)用MGraphToALGraph()，把鄰接矩陣轉(zhuǎn)換為鄰接鏈表調(diào)用output_graphic()鄰接矩陣的輸出調(diào)用output_graphic_c()鄰接矩陣的輸出 結(jié)束調(diào)用output_Find_ALGraph()輸出相鄰景點breakb

39、reak調(diào)用dijkshort_Two（）函數(shù)，查找兩個景點間的最短距離調(diào)用dijkshort_One（）函數(shù)，查找最短簡單路徑和距離breakbreak調(diào)用Dijkstra（）函數(shù)，查找最佳路徑4 每個題目都必須有運行時的輸入數(shù)據(jù)（隨機產(chǎn)生的數(shù)據(jù)要求輸出顯示），運行的輸出結(jié)果。建立鄰接矩陣：鄰接矩陣輸出：鄰接鏈表輸出：相鄰景點查詢：從某點出發(fā)到另外所有點最短簡單路徑及距離：兩個景點之間的最短距離：最佳路徑：5 每個函數(shù)中應(yīng)給出盡可能詳細的中文注釋。（源程序-全）#include "stdio.h"#include "malloc.h"#include

40、"string.h"#define INFINITY 32767 /* 最大值 */* 根據(jù)圖的權(quán)值類型，分別定義為最大整數(shù)或?qū)崝?shù) */#define MAXVEX 30 /* 最大頂點數(shù)目 */鄰接矩陣結(jié)構(gòu)體typedef struct char vex1, vex2 ; /* 弧或邊所依附的兩個頂點 */int ArcVal ; /* 弧或邊的權(quán)值 */ArcType ; /* 弧或邊的結(jié)構(gòu)定義 */typedef struct int vexnum, arcnum ; /* 圖的當前頂點數(shù)和弧數(shù) */char vexsMAXVEX ; /* 頂點向量 */int ad

41、jMAXVEXMAXVEX;MGraph ; /* 圖的結(jié)構(gòu)定義 */typedef struct Pathint vertexMAXVEX;int value;int count;GPath;/鄰接鏈表結(jié)構(gòu)體typedef struct ANode /弧的結(jié)點結(jié)構(gòu)類型int adjvex; / 鄰接點在頭結(jié)點數(shù)組中的位置(下標)int info; /該弧的相關(guān)信息,這里用于存放權(quán)值struct ANode *nextarc; /指向下一條弧的指針 ArcNode;typedef struct Vnode /鄰接表頭結(jié)點的類型 char data; /頂點信息ArcNode *firstarc

42、; /指向第一條弧 VNode;typedef struct VNode AdjListMAXVEX; /鄰接表數(shù)組int vexnum,arcnum; /圖中頂點數(shù)n和邊數(shù)e ALGraph; /圖的鄰接表類型MGraph *Init_MGraph()/* 圖的初始化 */ MGraph *G;G=(MGraph *)malloc(sizeof(MGraph) ;G->vexnum=0 ; G->arcnum=0 ; /* 初始化頂點數(shù)、邊數(shù) */return(G) ; ALGraph *Init_ALGraph()/* 圖的初始化 */ ALGraph *G;G=(ALGrap

43、h *)malloc(sizeof(ALGraph) ;G->vexnum=0 ;G->arcnum=0; /* 初始化頂點數(shù) */return(G) ; int LocateVex(MGraph *G, char vp) /* 圖中頂點的定位，若圖中有頂點vp，返回其在頂點數(shù)組的下標值 */ int k ;for (k=0; k<=G->vexnum; k+)if (G->vexsk=vp) return(k) ; return(-1) ; /* 圖中無此頂點 */int LocateVexx(ALGraph *G, char vp) /*圖的頂點定位（圖的頂點

44、定位實際上是確定一個頂點在AdjList數(shù)組中的某個元素的data域內(nèi)容。）*/int k;for(k=0; k<G->vexnum;k+)if(G->AdjListk.data=vp)return(k); /*如果存在此頂點返回頂點數(shù)組下標值 */return(-1); /*如果沒有則返回-1(圖中無此頂點) */void AddVertex(MGraph *G, char vp) /* 往圖的頂點數(shù)組中增加頂點 */ int k, j ;if (G->vexnum>=MAXVEX)printf("圖中頂點數(shù)已達到最多 !n"); elsei

45、f (LocateVex(G, vp)=-1) /圖中無此頂點k=G->vexnum ; G->vexsG->vexnum+=vp ;for (j=0 ; j<G->vexnum ; j+) G->adjjk=INFINITY ;G->adjkj=INFINITY ;/* 是帶權(quán)的有向圖或無向圖 */void AddArc(MGraph *G , ArcType *arc) /* 往圖的鄰接矩陣中添加邊(弧) */ int k=0, j=0;k=LocateVex(G, arc->vex1) ;j=LocateVex(G, arc->vex

46、2) ; G->arcnum+ ;G->adjkj=arc->ArcVal ;G->adjjk=arc->ArcVal ;/* 是無向圖或帶權(quán)的無向圖,需對稱賦值 */void output_graphic(MGraph *G) /* 輸出圖的頂點矩陣和鄰接矩陣 */ int k, j ;printf("圖的頂點如下：n") ; for (k=0; k<G->vexnum; k+)printf("%4c",G->vexsk) ;printf("nn") ;printf("圖的鄰

47、接矩陣如下：n") ; for (k=0; k<G->vexnum; k+)for (j=0; j<G->vexnum; j+)if (G->adjkj=INFINITY) printf("%4s","*") ;else printf("%4d",G->adjkj) ;printf("nn") ;MGraph *create_graph()/* 以鄰接矩陣作為圖的存儲結(jié)構(gòu)建立圖 */ char inchar100, enchar100,fvex,lvex ;int count=0;int weight ; MGraph *G;ArcType *arc ;printf("首先進行圖的初始化!nn") ;G=(MGraph *)malloc(sizeof(MGr