數(shù)據(jù)結(jié)構(gòu)課程設(shè)計——校園導(dǎo)游咨詢系統(tǒng)(編輯修改稿)
2025-07-12 01:44 本頁面
【文章內(nèi)容簡介】 { int col。 if(v10||v1||v20||v2) { printf(參數(shù) v1 或 v2 越界出錯！ \n)。 exit(1)。 } for(col=v2+1。col。col++) if([v1][col]0amp。amp。[v1][col]MaxWeight) return col。 return 1。 } (3)/* 圖的創(chuàng)建函數(shù)所放的頭文件 */ typedef struct { int row。/*行下標(biāo) */ int col。/*列下標(biāo) */ int weight。/*權(quán)值 */ }RowColWeight。/*邊信息結(jié)構(gòu)體定義 */ void CreatGraph(AdjMGraph *G,DataType V[],int n,RowColWeight E[],int e) /*在圖 G 中插入 n 個結(jié)點(diǎn)信息 V 和 e 條邊信息 E*/ { int i,k。 Initiate(G,n)。/*結(jié)點(diǎn)順序表初始化 */ for(i=0。in。i++) InsertVertex(G,V[i])。/*結(jié)點(diǎn)插入 */ for(k=0。ke。k++) InsertEdge(G,E[k].row,E[k].col,E[k].weight)。/*邊插入 */ } (4)/* 狄克斯特拉函數(shù)設(shè)計所放的頭文件 */ void Dijkstra(AdjMGraph G,int v0,int distance[],int path[]) /*帶權(quán)圖 G從下標(biāo) v0 結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短距離 distance*/ /*和最短路徑下標(biāo) path*/ { int n=。 int *s=(int *)malloc(sizeof(int)*n)。 int minDis,i,j,u。 /*初始化 */ for(i=0。in。i++) { distance[i]=[v0][i]。 s[i]=0。 if(i!=v0amp。amp。distance[i]MaxWeight) path[i]=v0。 else path[i]=1。 } s[v0]=1。/*標(biāo)記結(jié)點(diǎn) v0 已從集合 T加入到集合 S中 */ /*在當(dāng)前還未到最短路徑的結(jié)點(diǎn)集中選取具有最短距離的結(jié)點(diǎn) u*/ for(i=1。in。i++) { minDis=MaxWeight。 for(j=0。jn。j++) if(s[j]==0amp。amp。distance[j]minDis) { u=j。 minDis=distance[j]。 } /*當(dāng)已不再存在最短路徑時算法結(jié)束；此語句對非連通圖是必須的 */ if(minDis==MaxWeight)return。 s[u]=1。/*標(biāo)記結(jié)點(diǎn) u 已從集合 T加入到集合 S中 */ /*修改從 v0 到其他結(jié)點(diǎn)的最短距離和最短路徑 */ for(j=0。jn。j++) if(s[j]==0amp。amp。[u][j]MaxWeightamp。amp。distance[u]+[u][j]distance[j]) { /*結(jié)點(diǎn) v0 經(jīng)結(jié)點(diǎn) u到其他結(jié)點(diǎn)的最短距離和最短路徑 */ distance[j]=distance[u]+[u][j]。 path[j]=u。 } } } (5)/* 文件 */ include include include typedef char DataType。 define MaxSize 100 define MaxVertices 10 define MaxWeight 10000 include include include void SgPrint(AdjMGraph g,int n,int distance[],int path[],int j) { /*輸出源點(diǎn)到其他各結(jié)點(diǎn)的最短距離和最短路徑 */ int i。 /*從源結(jié)點(diǎn)到其他各結(jié)點(diǎn)的最短路徑及其距離分別為： */ printf( 從該結(jié)點(diǎn) %c 到 其 他 各 結(jié) 點(diǎn) 的 最 短 路 徑 及 其 距 離 分 別 為 ：\n,[j])。 printf(\n)。//輸出換行符 for(i=0。in。i++) { /*從源結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的最短路徑為 */ printf( 從 結(jié) 點(diǎn) %c 到 結(jié) 點(diǎn) %c 的 最 短 路 徑為 :,[j],[i])。 printf(()。//輸出左括號 if(path[i]!=1)//源點(diǎn)到其他結(jié)點(diǎn)的最短路徑的前一結(jié)點(diǎn)判斷 { if(path[path[i]]!=1)//該前一結(jié)點(diǎn)的前一結(jié)點(diǎn)進(jìn)行判斷 { if(path[path[path[i]]]!=1)//該前一結(jié)點(diǎn)的前一結(jié)點(diǎn)的前一結(jié)點(diǎn)進(jìn)行判斷 { printf(%c,[path[path[path[i]]]])。//輸出相應(yīng)存在的前一結(jié)點(diǎn)
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1