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

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》報告題目旅游區(qū)導游圖專業(yè)計算機科學與技術(shù)班級（2）班學生###13旅游區(qū)導游圖題目內(nèi)容問題描述：設(shè)某個旅游區(qū)共有n個旅游景點（n≥10）,每個旅游景點都和相鄰的m個旅游景點（m≥2，m<n）有直接的道路（有對應的距離）相通，請設(shè)計一個簡易的旅游區(qū)導游系統(tǒng)。以(Vi,Vj,d)的形式從鍵盤輸入建立該旅游區(qū)的旅游景點圖，其中：Vi和Vj表示兩個不同的旅游景點，d表示這兩個景點之間的道路距離；該旅游景點圖采用鄰接矩陣存儲結(jié)構(gòu)(數(shù)組)。實現(xiàn)要求：⑴旅游景點圖的輸出：分別以鄰接矩陣、鄰接鏈表的方式輸出該旅游景點圖。⑵相鄰景點查詢：假設(shè)對于每個景點，設(shè)置有簡易的信息查詢，要求能給出與該景點相鄰的所有景點(有直接的道路相通)及對應的距離。⑶景點路線查詢：假設(shè)對于每個景點，設(shè)置有景點路線查詢，要求能給出從該景點出發(fā)到任一其它景點的最短簡單路徑及距離。⑷景點路線綜合查詢：對于該旅游區(qū)的任意兩個景點，找出它們之間的最短簡單路徑及距離。⑸最佳旅游路線確定：假設(shè)該旅游區(qū)的入口也是出口，請確定一條最佳的旅游線路，該線路必須經(jīng)過所有的旅游景點（有些景點可以重復經(jīng)過）且走的路最短。⑹設(shè)計一個菜單，上述操作要求都作為菜單中的主要菜單項。本人完成的工作完成的工作：首先是用鄰接矩陣的存儲形式建立無向帶權(quán)圖，然后將鄰接矩陣轉(zhuǎn)換為鄰接鏈表，最后用狄克斯特拉函數(shù)求出后面的三道有關(guān)最短路徑的小題，設(shè)計主函數(shù)。所采用的數(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)體typedefstruct{ charvex1,vex2;/*弧或邊所依附的兩個頂點*/intArcVal;/*弧或邊的權(quán)值*/}ArcType;/*弧或邊的結(jié)構(gòu)定義*/typedefstruct{ intvexnum,arcnum;/*圖的當前頂點數(shù)和弧數(shù)*/ charvexs[MAXVEX];/*頂點向量*/ intadj[MAXVEX][MAXVEX];}MGraph;/*圖的結(jié)構(gòu)定義*///鄰接鏈表結(jié)構(gòu)體typedefstructANode//弧的結(jié)點結(jié)構(gòu)類型{intadjvex;//該弧的終點位置intinfo;//該弧的相關(guān)信息,這里用于存放權(quán)值structANode*nextarc;//指向下一條弧的指針}ArcNode;typedefstructVnode//鄰接表頭結(jié)點的類型{ chardata;//頂點信息ArcNode*firstarc;//指向第一條弧}VNode;typedefstruct{VNodeAdjList[MAXVEX];intvexnum,arcnum;//圖中頂點數(shù)n和邊數(shù)e}ALGraph;//圖的鄰接表類型所設(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(ALGraph)); G->vexnum=0; G->arcnum=0;/*初始化頂點數(shù)*/ return(G);}圖中頂點定位的函數(shù)，判斷頂點是否重復輸入了intLocateVex(MGraph*G,charvp)/*圖中頂點的定位，若圖中有頂點vp，返回其在頂點數(shù)組的下標值*/{ intk; for(k=0;k<=G->vexnum;k++) if(G->vexs[k]==vp)return(k);開始k=0開始k=0返回-1k<=頂點總數(shù)？G->vexs[k]==vp？返回k結(jié)束k++}NNYY往圖中增加頂點的函數(shù)voidAddVertex(MGraph*G,charvp)/*往圖的頂點數(shù)組中增加頂點*/{ intk,j; if(G->vexnum>=MAXVEX) printf("圖中頂點數(shù)已達到最多!\n"); else { if(LocateVex(G,vp)==-1) { k=G->vexnum;G->vexs[G->vexnum++]=vp; for(j=0;j<G->vexnum;j++) { G->adj[j][k]=INFINITY; G->adj[k][j]=INFINITY; /*是帶權(quán)的有向圖或無向圖*/開始把這個點跟其他所有點建立關(guān)系，為開始把這個點跟其他所有點建立關(guān)系，為INFINITY，表示不存在連通關(guān)系新增加一個頂點給k賦值=頂點總數(shù)調(diào)用函數(shù)LocateVex，判斷頂點是否有重復判斷頂點數(shù)目是否已經(jīng)超過最大值結(jié)束 } }}NYNY往圖的鄰接矩陣中添加邊(弧)voidAddArc(MGraph*G,ArcType*arc)/*往圖的鄰接矩陣中添加邊(弧)*/{ intk=0,j=0; k=LocateVex(G,arc->vex1); j=LocateVex(G,arc->vex2); if(k==-1||j==-1) printf("邊或弧的頂點不存在，錯誤!\n"); else { G->arcnum++; G->adj[k][j]=arc->ArcVal; G->adj[j][k]=arc->ArcVal; /*是無向圖或帶權(quán)的無向圖,需對稱賦值*/開始給兩個頂點之間加上權(quán)值開始給兩個頂點之間加上權(quán)值邊數(shù)加一判斷弧所依托的兩個頂點是否存在結(jié)束 }輸出圖的頂點矩陣和鄰接矩陣voidoutput_graphic(MGraph*G)/*輸出圖的頂點矩陣和鄰接矩陣*/{ intk,j;printf("圖的頂點如下：\n");for(k=0;k<G->vexnum;k++)printf("%4c",G->vexs[k]);printf("\n\n");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++printf("%4s","**");elseprintf("%4d",G->adj[k][j]);printf("\n\n");} }YNYNY以鄰接矩陣作為圖的存儲結(jié)構(gòu)建立圖MGraph*create_graph()/*以鄰接矩陣作為圖的存儲結(jié)構(gòu)建立圖*/{ charinchar[100],enchar[100],fvex,lvex;intcount=0;intweight;MGraph*G;ArcType*arc;printf("首先進行圖的初始化!!\n\n");G=(MGraph*)malloc(sizeof(MGraph));G=Init_MGraph();arc=(ArcType*)malloc(sizeof(ArcType)); printf("\n請以(頂點,頂點,權(quán)值)的形式輸入圖的邊(或弧)，第一個頂點是?表示結(jié)束：\n"); while(1) { scanf("%s",inchar);fvex=inchar[0];/*輸入第一個頂點，?結(jié)束*/ if(fvex=='?')break; else { AddVertex(G,fvex); scanf("%s",enchar);lvex=enchar[0];AddVertex(G,lvex); scanf("%d",&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){ inti,j,n=g->vexnum;//n為頂點數(shù) ArcNode*p; G=(ALGraph*)malloc(sizeof(ALGraph)); G->arcnum=g->arcnum; G->vexnum=g->vexnum; for(i=0;i<G->vexnum;i++) G->AdjList[i].firstarc=NULL; for(i=0;i<n;i++)//檢查鄰接矩陣中每個元素 { for(j=n-1;j>=0;j--) if(g->adj[i][j]!=INFINITY)//鄰接矩陣的當前元素不為 { p=(ArcNode*)malloc(sizeof(ArcNode));//創(chuàng)建一個結(jié)點*p G->AdjList[j].data=g->vexs[j]; p->adjvex=g->vexs[j]; p->info=g->adj[i][j]; p->nextarc=G->AdjList[i].firstarc;//將*p鏈到鏈表后G->AdjList[i].firstarc=p; } } returnG;}j--j--給鄰接點賦上鄰接矩陣對應的頂點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?鄰接鏈表的輸出voidoutput_graphic_c(MGraph*g,ALGraph*G){ inti; ArcNode*p; for(i=0;i<g->vexnum;i++) { printf("%c",G->AdjList[i].data); p=G->AdjList[i].firstarc; while(p!=NULL) { printf("%s","->"); printf("(%c,%d)",p->adjvex,p->info); p=p->nextarc; } printf("\n\n"); }}相鄰景點查詢并輸出voidoutput_Find_ALGraph(ALGraph*G){/*相鄰景點查詢并輸出*/ intj; ArcNode*p; printf("請輸入你要查詢的景點(下標值):\n"); scanf("%d",&j); p=G->AdjList[j].firstarc; while(p) { printf("景點%c到景點%c的距離是%d(該兩個景點之間有直接的道路相通)\n",G->AdjList[j].data,p->adjvex,p->info); p=p->nextarc;開始結(jié)束開始結(jié)束輸出兩個頂點之間的距離把該景點在數(shù)組中的鄰接邊的頭指針賦值給p輸入景點對應的下標值判斷鄰接邊單鏈表的結(jié)點指針是否為空p指向下一個結(jié)點指針 printf("\n\n");}景點路線查詢：假設(shè)對于每個景點，設(shè)置有景點路線查詢，要求能給出從該景點出發(fā)到任一其它景點的最短簡單路徑及距離。voidDijkstra_One(ALGraph*G,MGraph*g,intv0,intdistance[],intpre[]){//帶權(quán)圖G從頂點v0到其他定點的最短距離distance和最短路徑前驅(qū)結(jié)點的下標pre intw; intS[30],i,j,k,p,min; printf("你所要開始查詢的景點是:%c\n",G->AdjList[v0].data); for(i=0;i<g->vexnum;i++) { distance[i]=g->adj[v0][i]; S[i]=0; if(distance[i]<INFINITY) pre[i]=v0; else pre[i]=-1; } S[v0]=1;//頂點v0已加入到集合S中 for(i=0;i<g->vexnum;i++) { min=INFINITY; for(j=0;j<g->vexnum;j++) { if(!S[j]&&distance[j]<min) { min=distance[j]; k=j; } } S[k]=1;///將找到的頂點加入到集合S中 for(w=0;w<g->vexnum;w++)///修改集合T中頂點的距離值 if(!S[w]&&distance[w]>distance[k]+g->adj[k][w]) { distance[w]=distance[k]+g->adj[k][w]; pre[w]=k; } } printf("查詢結(jié)果:\n"); for(j=0;j<g->vexnum;j++)//輸出結(jié)果 if(pre[j]!=-1) { printf("從景點%c到景點%c",G->AdjList[v0].data,g->vexs[j]); p=pre[j]; printf("的最短距離是:%d",distance[j]); printf("途中經(jīng)過的景點有:"); while(p!=-1) { printf("%c",g->vexs[p]); p=pre[p]; } printf("\n"); } elseif(j!=v0) printf("\n%c到%c:nopath",g->vexs[j],g->vexs[v0]);開始用循環(huán)結(jié)構(gòu)實現(xiàn)各數(shù)組的初始化開始用循環(huán)結(jié)構(gòu)實現(xiàn)各數(shù)組的初始化輸入要查詢景點的下標值定義最短路徑的終點集數(shù)組S置S={v0}求出當前最小的dist[j]值w=0將第j個頂點放入S中結(jié)束結(jié)束從v0到w的最短路徑中，w的前一個頂點是k判斷w是否小于頂點總數(shù)從V0出發(fā)中間只經(jīng)過集合S中的頂點而到達Vw的所有路徑中長度最小的路徑長度distance[w]是否大于distance[w]+邊adj[k][w]的值從V0出發(fā)到w的最短距離distance[w]=從V0出發(fā)到w的最短距離distance[k]+邊adj[k][w]的權(quán)值w++查詢結(jié)果輸出NY景點路線綜合查詢：對于該旅游區(qū)的任意兩個景點，找出它們之間的最短簡單路徑及距離。voidDijkstra_Two(ALGraph*G,MGraph*g,intv0,intdistance[],intpre[]){ //帶權(quán)圖G從頂點v0到其他定點的最短距離distance和最短路徑前驅(qū)結(jié)點的下標pre intw; intS[30],i,j,k,p,min,d; printf("你所要開始查詢的開始景點是:%c\n\n",G->AdjList[v0].data); for(i=0;i<g->vexnum;i++) { distance[i]=g->adj[v0][i]; S[i]=0; if(distance[i]<INFINITY) pre[i]=v0; else pre[i]=-1; } S[v0]=1;//頂點v0已加入到集合S中 for(i=0;i<g->vexnum;i++) { min=INFINITY; for(j=0;j<g->vexnum;j++) { if(!S[j]&&distance[j]<min) { min=distance[j]; k=j; } } S[k]=1;///將找到的頂點加入到集合S中 for(w=0;w<g->vexnum;w++)///修改集合T中頂點的距離值 if(!S[w]&&distance[w]>distance[k]+g->adj[k][w]) { distance[w]=distance[k]+g->adj[k][w]; pre[w]=k; } } printf("輸入你要查詢的另外一個景點(下標值):"); scanf("%d",&d); printf("你要查詢的另外一個景點是:%c\n",g->vexs[d]); printf("\n查詢結(jié)果:\n");//輸出結(jié)果 if(pre[d]!=-1) { printf("從景點%c到景點%c",G->AdjList[v0].data,g->vexs[d]); p=pre[d]; printf("的最短距離是:%d",distance[d]); printf("途中經(jīng)過的景點有:"); while(p!=-1) { printf("%c",g->vexs[p]); p=pre[p]; }開始用循環(huán)結(jié)構(gòu)實現(xiàn)各數(shù)組的初始化開始用循環(huán)結(jié)構(gòu)實現(xiàn)各數(shù)組的初始化輸入要查詢景點的下標值定義最短路徑的終點集數(shù)組S置S={v0} }}求出當前最小的dist[j]值求出當前最小的dist[j]值w=0將第j個頂點放入S中結(jié)束從v0到w的最短路徑中，w的前一個頂點是k判斷w是否小于頂點總數(shù)從V0出發(fā)中間只經(jīng)過集合S中的頂點而到達Vw的所有路徑中長度最小的路徑長度distance[w]是否大于distance[w]+邊adj[k][w]的值從V0出發(fā)到w的最短距離distance[w]=從V0出發(fā)到w的最短距離distance[k]+邊adj[k][w]的權(quán)值w++輸入要查詢另外一景點的下標值查詢結(jié)果輸出最佳旅游路線確定：假設(shè)該旅游區(qū)的入口也是出口，請確定一條最佳的旅游線路，該線路必須經(jīng)過所有的旅游景點（有些景點可以重復經(jīng)過）且走的路最短。voiddfs_path(ALGraph*g,intsrc,intcur,intvis[],GPath*cur_path,GPath*min_path){ if(vis[src]) { 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ū)域復制sizeof(GPath)個字節(jié)到min_path所指內(nèi)存區(qū)域*/ return; } } return; } ArcNode*node=g->AdjList[cur].firstarc; for(;node!=NULL;node=node->nextarc)/*起始條件為node=g->AdjList[cur].firstarc*/ { charadj=node->adjvex; intindex=LocateVex(g,adj); if(vis[index]==0) { cur_path->vertex[cur_path->count++]=index; cur_path->value+=node->info; vis[index]=1; dfs_path(g,src,index,vis,cur_path,min_path); cur_path->count--; cur_path->value-=node->info;結(jié)束判斷vp是否存在結(jié)束判斷vp是否存在弧頭頂點數(shù)據(jù)元素=LocateVexx(g,adj)最小生成樹權(quán)值加遞歸開始把頂點的值vp復制給adj把鄰接表數(shù)組的頭指針賦值給node用循環(huán)結(jié)構(gòu)復制cur_pat的內(nèi)存到min_path判斷鄰接表指針是否為空node指向下一個結(jié)點 } }}YNNYvoidbest_path(ALGraph*g,intsrc){ intvis[MAXVEX]; memset(vis,0,sizeof(vis)); GPathcur_path,min_path; 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=INFINITY; dfs_path(g,src,src,vis,&cur_path,&min_path); if(min_path.value!=INFINITY) { inti=0; printf("\n最佳旅游路線景點下標值是:\n"); for(i=0;i<min_path.count;i++) { printf("%d->",min_path.vertex[i]); } printf("\n"); printf("\n最佳旅游路線景點是:\n"); for(i=0;i<min_path.count;i++) { printf("%c->",g->AdjList[min_path.vertex[i]].data); } printf("\n"); }else { printf("建立的圖中沒有最佳路徑\n"); }}主函數(shù)voidmain(){ intn,opse,v0,i; intdistance[MAXVEX],pre[2*MAXVEX],path[MAXVEX]; ALGraph*G; MGraph*M; do {printf("\n\n請選擇對圖的操作要求:\n\n"); for(n=0;n<=30;n++) printf("*"); printf("\n*"); printf("1----建立圖的鄰接矩陣"); printf("2----圖的鄰接矩陣的輸出"); printf("*\n"); printf("\n*"); printf("3----圖的鄰接鏈表的輸出"); printf("4----相鄰景點查詢"); printf("*\n"); printf("\n*"); printf("5----從某點出發(fā)到另外所有點最短簡單路徑及距離"); printf("*\n"); printf("\n*"); printf("6----兩個景點之間的最短距離(下標值)"); printf("*\n"); printf("\n*"); printf("7----最佳路徑"); printf("8----退出"); printf("*\n"); for(n=0;n<=30;n++) printf("*"); printf("\n\n"); do {scanf("%d",&opse); }while(opse<1||opse>8); switch(opse) { case1: {M=(MGraph*)malloc(sizeof(MGraph)); M=create_graph(); printf("\n\n"); break; } case2: {printf("\n您所建立的圖是：\n"); output_graphic(M); break; } case3: {printf("圖G的鄰接矩陣轉(zhuǎn)換成鄰接表:\n"); G=MGraphToALGraph(M,G);output_graphic_c(M,G); break; } case4: { printf("\n相鄰景點是：\n"); output_Find_ALGraph(G); break; } case5: { printf("\n最短簡單路徑及距離是：\n"); scanf("%d",&v0); Dijkstra_One(G,M,v0,distance,pre); break; } case6: { printf("兩個景點之間的最短距離(下標值):"); scanf("%d",&v0); Dijkstra_Two(G,M,v0,distance,pre); break; } case7: { printf("最佳路徑(下標值):"); Dijkstra(M,0,distance,path); printf("從結(jié)點%c到其他各結(jié)點的最短距離為:\n",M->vexs[0]); for(i=1;i<M->vexnum;i++) printf("到結(jié)點%c的最短距離為%d:\n",M->vexs[i],distance[i]); printf("從結(jié)點%c到其他各結(jié)點最短路徑的前一結(jié)點為:\n",M->vexs[0]); for(i=1;i<M->vexnum;i++) if(path[i]!=-1) printf("到結(jié)點%c的前一結(jié)點為%c:\n",M->vexs[i],M->vexs[path[i]]); 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é)束結(jié)束調(diào)用output_Find_ALGraph()輸出相鄰景點breakbreak調(diào)用dijkshort_Two（）函數(shù)，查找兩個景點間的最短距離調(diào)用dijkshort_One（）函數(shù)，查找最短簡單路徑和距離breakbreak調(diào)用Dijkstra（）函數(shù)，查找最佳路徑每個題目都必須有運行時的輸入數(shù)據(jù)（隨機產(chǎn)生的數(shù)據(jù)要求輸出顯示），運行的輸出結(jié)果。建立鄰接矩陣：鄰接矩陣輸出：鄰接鏈表輸出：相鄰景點查詢：從某點出發(fā)到另外所有點最短簡單路徑及距離：兩個景點之間的最短距離：最佳路徑：每個函數(shù)中應給出盡可能詳細的中文注釋。（源程序-全）#include"stdio.h"#include"malloc.h"#include"string.h"#defineINFINITY32767/*最大值∞*//*根據(jù)圖的權(quán)值類型，分別定義為最大整數(shù)或?qū)崝?shù)*/#defineMAXVEX30/*最大頂點數(shù)目*///鄰接矩陣結(jié)構(gòu)體typedefstruct{ charvex1,vex2;/*弧或邊所依附的兩個頂點*/intArcVal;/*弧或邊的權(quán)值*/}ArcType;/*弧或邊的結(jié)構(gòu)定義*/typedefstruct{ intvexnum,arcnum;/*圖的當前頂點數(shù)和弧數(shù)*/ charvexs[MAXVEX];/*頂點向量*/ intadj[MAXVEX][MAXVEX];}MGraph;/*圖的結(jié)構(gòu)定義*/typedefstructPath{ intvertex[MAXVEX]; intvalue; intcount;}GPath;//鄰接鏈表結(jié)構(gòu)體typedefstructANode{//弧的結(jié)點結(jié)構(gòu)類型 intadjvex;//鄰接點在頭結(jié)點數(shù)組中的位置(下標) intinfo;//該弧的相關(guān)信息,這里用于存放權(quán)值 structANode*nextarc;//指向下一條弧的指針}ArcNode;typedefstructVnode//鄰接表頭結(jié)點的類型{ chardata;//頂點信息 ArcNode*firstarc;//指向第一條弧}VNode;typedefstruct{ VNodeAdjList[MAXVEX];//鄰接表數(shù)組 intvexnum,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=(ALGraph*)malloc(sizeof(ALGraph)); G->vexnum=0; G->arcnum=0;/*初始化頂點數(shù)*/ return(G);}intLocateVex(MGraph*G,charvp)/*圖中頂點的定位，若圖中有頂點vp，返回其在頂點數(shù)組的下標值*/{ intk; for(k=0;k<=G->vexnum;k++) if(G->vexs[k]==vp)return(k); return(-1);/*圖中無此頂點*/}intLocateVexx(ALGraph*G,charvp)/*圖的頂點定位（圖的頂點定位實際上是確定一個頂點在AdjList數(shù)組中的某個元素的data域內(nèi)容。）*/{ intk; for(k=0;k<G->vexnum;k++) if(G->AdjList[k].data==vp) return(k);/*如果存在此頂點返回頂點數(shù)組下標值*/ return(-1);/*如果沒有則返回-1(圖中無此頂點)*/}voidAddVertex(MGraph*G,charvp)/*往圖的頂點數(shù)組中增加頂點*/{ intk,j; if(G->vexnum>=MAXVEX) printf("圖中頂點數(shù)已達到最多!\n"); else { if(LocateVex(G,vp)==-1)// 圖中無此頂點 { k=G->vexnum;G->vexs[G->vexnum++]=vp; for(j=0;j<G->vexnum;j++) { G->adj[j][k]=INFINITY; G->adj[k][j]=INFINITY; /*是帶權(quán)的有向圖或無向圖*/ } } }}voidAddArc(MGraph*G,ArcType*arc)/*往圖的鄰接矩陣中添加邊(弧)*/{ intk=0,j=0; k=LocateVex(G,arc->vex1); j=LocateVex(G,arc->vex2); { G->arcnum++; G->adj[k][j]=arc->ArcVal; G->adj[j][k]=arc->ArcVal; /*是無向圖或帶權(quán)的無向圖,需對稱賦值*/ } }voidoutput_graphic(MGraph*G)/*輸出圖的頂點矩陣和鄰接矩陣*/{ intk,j; printf("圖的頂點如下：\n"); for(k=0;k<G->vexnum;k++) printf("%4c",G->vexs[k]); printf("\n\n"); printf("圖的鄰接矩陣如下：\n"); for(k=0;k<G->vexnum;k++) { for(j=0;j<G->vexnum;j++) if(G->adj[k][j]==INFINITY) printf("%4s","**"); else printf("%4d",G->adj[k][j]); printf("\n\n"); } }MGraph*create_graph()/*以鄰接矩陣作為圖的存儲結(jié)構(gòu)建立圖*/{ charinchar[100],enchar[100],fvex,lvex; intcount=0; intweight; MGraph*G; ArcType*arc; printf("首先進行圖的初始化!!\n\n"); G=(MGraph*)malloc(sizeof(MGraph)); G=Init_MGraph(); arc=(ArcType*)malloc(sizeof(ArcType)); printf("\n請以(頂點,頂點,權(quán)值)的形式輸入圖的邊(或弧)，第一個頂點是?表示結(jié)束：\n"); while(1) { scanf("%s",inchar);fvex=inchar[0];/*輸入第一個頂點，?結(jié)束*/ if(fvex=='?')break; else { AddVertex(G,fvex); scanf("%s",enchar);lvex=enchar[0];AddVertex(G,lvex);/*輸入第二個頂點和權(quán)值*/ scanf("%d",&weight); 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){ inti,j,n=g->vexnum;//n為鄰接矩陣頂點總數(shù) ArcNode*p; G=(ALGraph*)malloc(sizeof(ALGraph)); G->arcnum=g->arcnum; G->vexnum=g->vexnum; for(i=0;i<G->vexnum;i++) G->AdjList[i].firstarc=NULL; for(i=0;i<n;i++)//檢查鄰接矩陣中每個元素 { for(j=n-1;j>=0;j--) if(g->adj[i][j]!=INFINITY)//鄰接矩陣的當前元素不為 { p=(ArcNode*)malloc(sizeof(ArcNode));//創(chuàng)建一個結(jié)點*p G->AdjList[j].data=g->vexs[j];//頂點數(shù)據(jù)元素賦值 p->adjvex=g->vexs[j];//給鄰接點數(shù)組中的每一個頭結(jié)點賦值 p->info=g->adj[i][j]; //給鄰接鏈表賦上權(quán)值 p->nextarc=G->AdjList[i].firstarc;//將*p鏈到鏈表后 G->AdjList[i].firstarc=p;//將i轉(zhuǎn)變?yōu)猷徑颖頂?shù)組的頭結(jié)點 } } returnG;}voidoutput_graphic_c(MGraph*g,ALGraph*G){ inti; ArcNode*p;//ArcNode弧的結(jié)點結(jié)構(gòu)類型 for(i=0;i<g->vexnum;i++) { printf("%c",G->AdjList[i].data);//輸出鄰接表數(shù)組的頭結(jié)點元素 p=G->AdjList[i].firstarc;//鄰接表的頭指針 while(p!=NULL) { printf("%s","->");//整個一條單鏈表輸出 printf("(%c,%d)",p->adjvex,p->info); p=p->nextarc; } printf("\n\n"); }}voidoutput_Find_ALGraph(ALGraph*G,charvp){/*相鄰景點查詢并輸出*/ intj; ArcNode*p; //printf("請輸入你要查詢的景點:\n"); //scanf("%d",&j);//scanf("%c",&ch);j=LocateVexx(G,vp); p=G->AdjList[j].firstarc;//鄰接表的頭指針 while(p) { printf("景點%c到景點%c的距離是%d(該兩個景點之間有直接的道路相通)\n",G->AdjList[j].data,p->adjvex,p->info); p=p->nextarc;//指向下一個結(jié)點指針 } printf("\n\n");}voidDijkstra_One(ALGraph*G,MGraph*g,charv0,intdistance[],intpre[]){//S[]為已求得最短路徑的終點集 //帶權(quán)圖G從頂點v0到其他定點的最短距離distance和最短路徑前驅(qū)結(jié)點的下標pre //數(shù)組pre[n]保存從Vs到其它頂點的最短路徑。若pre[i]=k，表示從Vs到Vi的最短路徑中，Vi的前一個頂點是Vk， intw,m; intS[30],i,j,k,p,min; m=LocateVexx(G,v0); //printf("你所要開始查詢的景點是:%c\n",G->AdjList[m].data); for(i=0;i<g->vexnum;i++)/*各數(shù)組的初始化*/ { distance[i]=g->adj[m][i]; S[i]=0; if(distance[i]<INFINITY) pre[i]=m; else pre[i]=-1; } S[m]=1;//頂點v0已加入到集合S中設(shè)置s={v0} for(i=0;i<g->vexnum;i++)//找不在S中的頂點vk { min=INFINITY; for(j=0;j<g->vexnum;j++) { if(!S[j]&&distance[j]<min) { min=distance[j]; k=j; /*求出當前最小的distance[j]值*/ } } S[k]=1;//將找到的頂點j加入到集合S中 for(w=0;w<g->vexnum;w++)//修改集合s中頂點的距離值 if(!S[w]&&distance[w]>distance[k]+g->adj[k][w]) { distance[w]=distance[k]+g->adj[k][w]; pre[w]=k;//修改distance和pre數(shù)組的值 } } printf("查詢結(jié)果:\n");//找到最短路徑 for(j=0;j<g->vexnum;j++)//輸出結(jié)果 if(pre[j]!=-1) { printf("從景點%c到景點%c",G->AdjList[m].data,g->vexs[j]); p=pre[j]; printf("的最短距離是:%d",distance[j]); printf("途中經(jīng)過的景點有:"); while(p!=-1) { printf("%c",g->vexs[p]); p=pre[p]; } printf("\n"); } elseif(j!=m) printf("\n%c到%c:nopath",g->vexs[j],g->vexs[m]);}voidDijkstra_Two(ALGraph*G,MGraph*g,charv0,chard,intdistance[],intpre[]){ //帶權(quán)圖G從頂點v0到其他定點的最短距離distance和最短路徑前驅(qū)結(jié)點的下標pre intw,m,n; intS[30],i,j,k,p,min; //chard; m=LocateVexx(G,v0); //printf("你所要開始查詢的開始景點是:%c\n\n",G->AdjList[v0].data); for(i=0;i<g->vexnum;i++)/*各數(shù)組的初始化*/ { distance[i]=g->adj[m][i]; S[i]=0; if(distance[i]<INFINITY) pre[i]=m; else pre[i]=-1; } S[m]=1;//頂點v0已加入到集合S中設(shè)置s={v0} for(i=0;i<g->vexnum;i++)//找不在S中的頂點vk { min=INFINITY; for(j=0;j<g->vexnum;j++) { if(!S[j]&&distance[j]<min) { min=distance[j]; k=j; } }/*求出當前最小的distance[j]值*/ S[k]=1;//將找到的頂點加入到集合S中 for(w=0;w<g->vexnum;w++)//修改集合s中頂點的距離值 if(!S[w]&&distance[w]>distance[k]+g->adj[k][w]) { distance[w]=distance[k]+g->adj[k][w]; pre[w]=k; }//修改distance和pre數(shù)組的值 } //printf("輸入你要查詢的另外一個景點(下標值):"); //scanf("%c",&d); n=LocateVexx(G,d); //printf("你要查詢的另外一個景點是:%c\n",g->vexs[n]); printf("\n查詢結(jié)果:\n");//輸出結(jié)果 if(pre[n]!=-1) { printf("從景點%c到景點%c",G->AdjList[m].data,g->vexs[n]); p=pre[n]; printf("的最短距離是:%d",distance[n]); printf("途中經(jīng)過的景點有:"); while(p!=-1) { printf("%c",g->vexs[p]); p=pre[p]; } printf("\n"); }}voiddfs_path(ALGraph*g,intsrc,intcur,intvis[],GPath*cur_path,GPath*min_path){ if(vis[src]) { 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ū)域復制sizeof(GPath)個字節(jié)到min_path所指內(nèi)存區(qū)域*/ return; } } return; } ArcNode*node=g->AdjList[cur].firstarc; for(;node!=NULL;node=node->nextarc)/*起始條件為node=g->AdjList[cur].firstarc*/ { charadj=node->adjvex; intindex=LocateVexx(g,adj); if(vis[index]==0) { cur_path->vertex[cur_path->count++]=index; cur_path->value+=node->info; vis[index]=1; dfs_path(g,src,index,vis,cur_path,min_path); cur_path->count--; cur_path->value-=node->info; vis[index]=0; } }}voidbest_path(ALGraph*g,intsrc){ intvis[MAXVEX]; memset(vis,0,sizeof(vis)); GPathcur_path,min_path; 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=INFINITY; dfs_path(g,src,src,vis,&cur_path,&min_path); if(min_path.value!=INFINITY) { inti=0; printf("\n最佳旅游路線景點下標值是:\n"); for(i=0;i<min_path.count;i++) { printf("%d->",min_path.vertex[i]); } printf("\n"); printf("\n最佳旅游路線景點是:\n"); for(i=0;i<min_path.count;i++) { printf("%c->",g->AdjList[min_path.vertex[i]].data); } printf("\n"); }else { printf("建立的圖中沒有最佳路徑\n"); }}voidmain(){intm; intn,opse; charvp,v0,d,src; intdistance[MAXVEX],pre[2*MAXVEX]; ALGraph*G; MGraph*M; do {printf("\n\n請選擇對圖的操作要求:\n\n"); for(n=0;n<=5;n++) printf("*"); printf("\n*"); printf("1----建立圖的鄰接矩陣"); printf("2----圖的鄰接矩陣的輸出"); printf("*\n"); printf("\n*"); printf("3----圖的鄰接鏈表的輸出"); printf("4----相鄰景點查詢(下標值)"); printf("*\n"); printf("\n*"); printf("5----從某點出發(fā)到另外所有點最短簡單路徑及距離(下標值)"); printf("*\n"); printf("\n*"); printf("6----兩個景點之間的最短距離(下標值)"); printf("*\n"); printf("\n*"); printf("7----最佳路徑"); printf("8----退出"); printf("*\n"); for(n=0;n<=5;n++) printf("*"); printf("\n\n"); do {scanf("%d",&opse); }while(opse<1||opse>8); switch(opse) { case1: {M=(MGraph*)malloc(sizeof(MGraph)); M=create_graph(); printf("\n\n"); break; } case2: {printf("\n您所建立的圖是：\n"); output_graphic(M); break; } case3: {printf("圖G的鄰接矩陣轉(zhuǎn)換成鄰接表:\n"); G=MGraphToALGraph(M,G);output_graphic_c(M,G); break; } case4: { printf("\n請輸入你要查詢的景點：\n"); scanf("%c",&vp); output_Find_ALGraph(G,vp); break; } case5: { printf("\n輸入一個頂點是：\n"); scanf("%c",&v0); Dijkstra_One(G,M,v0,distance,pre); break; } case6: { printf("你所要開始查詢的開始景點是:\n\n"); scanf("%c",&v0); printf("你要查詢的另外一個景點是:\n"); scanf("%c",&d); Dijkstra_Two(G,M,v0,d,distance,pre); break; } case7: { printf("輸入你要查詢的開始景點:"); scanf("%c",&v0);m=LocateVexx(G,v0); best_path(G,m); break; } } }while(opse!=8);}問題與總結(jié)問題：1、第一次答辯的時候，老師要求景點名稱在后面也要輸入字符型，回來后，想了一下，用了一個簡單的辦法，即調(diào)用LocateVexx函數(shù)返回我輸入景點所對應的下標值。這樣就避免了只能輸入下標值帶來的不便了；2、沒有完全符合最后一題的意思完成該題，最后一小題題目要求是可以重復經(jīng)過某些點，但是我的程序是每個點只經(jīng)過一次的最短回路（即所建的圖需是哈密頓圖才有回路，否則會輸出沒有最短路徑）；為了解決這個問題，我在網(wǎng)上也看了很多的資料，比如：TSP問題（旅行商問題/貨郎擔問題）、蟻群算法、、模擬退火算法、KM算法、中國郵遞員算法等，其中發(fā)現(xiàn)經(jīng)典的旅行商問題（貨郎擔問題）并不符合題目最后一題的要求，下面是在網(wǎng)上截圖的資料：為了解決這個難題，雖然在網(wǎng)上找了很多的資料，努力了三天，但是還是沒有能力解決這個問題?？偨Y(jié)：將鄰接矩陣轉(zhuǎn)換為鄰接鏈表走了很多彎路、花了很長的時間；還有就是引用一些書上的函數(shù)時，要正確用函數(shù)對結(jié)構(gòu)體成員調(diào)用，不能照搬過來，得看一下結(jié)構(gòu)上的區(qū)別。

附錄資料：不需要的可以自行刪除鍋爐基礎(chǔ)施工措施(內(nèi)容)項目工程概況及工程量2.1工程概況xx集團塔山2×600MW機組坑口電廠鍋爐房基礎(chǔ)縱向為K1、K2、K3、K4、K5、K6六個基礎(chǔ)軸線，基礎(chǔ)底標高為-5.5m，±0.000相當于絕對標高（黃海高程）1074.8m。基礎(chǔ)設(shè)計為鋼筋混凝土獨立基礎(chǔ),承臺之間設(shè)連梁及剪力墻.其中CT-1基礎(chǔ)2個，CT-2基礎(chǔ)3個，CT-3基礎(chǔ)2個，CT-4基礎(chǔ)8個，CT-4a基礎(chǔ)7個，CT-5基礎(chǔ)2個，CT-5a基礎(chǔ)2個，CT-5b基礎(chǔ)2個，CT-6基礎(chǔ)2個，CT-7基礎(chǔ)4個，CT-8基礎(chǔ)2個，CT-8a基礎(chǔ)1個，CT-9基礎(chǔ)2個，CT-10基礎(chǔ)2個?；A(chǔ)承臺上短柱最大斷面2.2×2.2M,短柱頂標高為-0.6M.混凝土強度等級:基礎(chǔ)、拉梁為C35（CT-6、8、8a為C40），短柱、剪力墻為C40。鍋爐基礎(chǔ)澆注時先澆注至—1.70m標高，待地腳螺栓和固定支架安裝完畢后再澆至—0.60m標高。2.2主要工程量鋼筋：Φ32101.4TΦ2866.2TΦ2526.2TΦ161.4TΦ148.9TΦ126.9Tφ1447Tφ1211.7Tφ1012.1Tφ85Tφ1648.3T砼：C401252m3C351372m33.作業(yè)準備工作及條件3.1作業(yè)人力計劃木工60人鋼筋工30人砼工15人架子工40人測量工2人機械工2人電工1人電焊工3人技術(shù)員1人質(zhì)檢員1人施工員2人3.2材料準備100×100方木10m３50×100方木8m鋼管60T十字扣件12000個腳手板800塊鉛絲22#1250kg鋼模板2200m2鉛絲12#3.3機具準備反鏟1輛自卸汽車5輛機動翻斗車2輛手推翻斗車10輛臺鉆1臺對焊機1臺磨光機2臺振搗器6臺砂輪切割機1臺鋼筋運輸拖板車1輛泵車2臺罐車3輛4.作業(yè)程序及作業(yè)方法4.1施工順序測量放線→土方開挖→墊層施工→人工破樁→放線→基礎(chǔ)承臺鋼筋綁扎→基礎(chǔ)承臺模板安裝→基礎(chǔ)承臺混凝土澆筑→短柱鋼筋綁扎→短柱模板安裝→短柱混凝土澆筑4.2主要施工方法4.2.1土方開挖本基坑采用反鏟作業(yè)，自卸汽車運土。放坡坡度為1:0.75，基底作業(yè)面寬度為1m，詳見附圖1。根據(jù)設(shè)計挖方圖，鍋爐間機械挖方控制深度為-5.6m，機械挖方控制深基底暫留土層為300厚人工挖土。坡道位置詳見附圖，坡道寬為7.0m。護欄距邊坡頂緣1.5m處，高度1050mm,立桿間距2000mm，中間加設(shè)一道橫桿，并刷紅白相間油漆條紋?；油谕僚蓪Ｈ诵奁?，要求上（下）口拉線修直，邊坡順直平滑。挖方土料運于指定堆土（或用土）場地，要求隨時集中并整形。為防止風吹土揚，應拍實或淋濕土堆表面。隨時抄平，控制挖方深度。及時放出底線，以免超挖或少挖。修坡時要借助靠尺掛線，做到坡面一致，邊線順直。4.2.2墊層施工土方開挖機械至-5.3m后將余下的0.3m人工挖除至-5.6m，基槽經(jīng)設(shè)計人員、監(jiān)理驗收合格后用50×100方木支設(shè)模板，墊層砼表面抹平后用木抹子或棕刷拉毛。表面平整度的誤差不超過10mm。4.2.3樁頭施工墊層施工完畢后進行破樁頭，嚴格控制樁頭標高，保證伸入承臺100mm。剔除時應注意保護好樁插入承臺內(nèi)的鋼筋，剔除方法為風鎬或鑿子在樁側(cè)面剔槽，將箍筋割除，主筋彎出，混凝土鑿除，然后用機械運走。4.2.4架子工程腳手架搭設(shè)地基應平整夯實，并加設(shè)50木板、掃地桿，滿鋪腳手板，并用12#鉛絲栓牢，不得有探頭板，頂部加設(shè)雙層防護欄桿。承臺施工搭設(shè)雙排操作架，腳手架立桿離基礎(chǔ)邊300mm左右，立桿縱向間距1.5m，水平間距1.5m，步距1.8m，小橫桿間距1.2m。外側(cè)加設(shè)剪刀撐和斜拉撐。剪刀撐不得大于45度。在承臺內(nèi)的立桿下加Φ32鋼筋支撐，頂部焊L=100mm鋼筋頭，高出混凝土面100mm。搭設(shè)方法見附圖2。4.2.5鋼筋工程鋼筋采用集中配制，現(xiàn)場綁扎，鋼筋接頭采用閃光對焊。綁扎鋼筋前先在墊層上彈出基礎(chǔ)軸線、柱邊線軸線、板墻及四角并用紅油漆標明。在基礎(chǔ)邊線內(nèi)畫出底板鋼筋的位置，擺放并綁扎底板鋼筋。柱鋼筋、板墻和底板鋼筋綁扎在一起，在基礎(chǔ)頂部柱鋼筋用鋼管扣件框住并找準位置綁扎在鋼管框上，鋼管框和模板加固鋼管連在一起，形成一個整體。鋼筋綁扎時先綁扎底板受力主筋，然后安裝模板支架（見模板工程），最后綁扎上部附加鋼筋。鋼筋保護層用1：2水泥砂漿制作，基礎(chǔ)底保護層100mm，側(cè)面及頂面為35mm，柱和拉梁保護層為35mm，剪力墻保護層為25mm。在墊塊上設(shè)置22#鉛絲綁扎在柱主筋上，呈梅花形綁扎@1000mm。4.2.6模板工程基礎(chǔ)及柱采用竹膠模板，模板加固基礎(chǔ)用鋼管圍檁和M12對拉螺栓桿加固@750×600.詳見附圖3。上層臺階懸空模板用Φ20鋼筋支架架設(shè)，間距1.5m設(shè)置一道。在基礎(chǔ)四周打入鋼管地錨用鋼管斜撐加固，使整個基礎(chǔ)成為一個整體。模板支設(shè)必須涂刷隔離劑，拆模要按照先支后拆，先支后拆的順序進行，由高到低自上而下拆，拆除時嚴禁猛撬、猛砸，破壞砼棱角和表面。4.2.7砼工程4.2.7.1混凝土由攪拌站集中供應,罐車運送,泵車布料,混凝土攪拌時嚴格按試驗室配合比進行試配,計量器具必須經(jīng)過驗定,計量要準確.混凝土澆灌采用全面分層法,拉梁及板墻采用斜面分層法.混凝土澆注一次成型,施工縫留在承臺與短柱交接處.暫留K5軸CT-4a不施工,以便泵車進入基坑內(nèi)澆注混凝土,待其他承臺施工完畢后最后施工此承臺.混凝土振搗采