數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三圖的應(yīng)用_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三圖的應(yīng)用_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三圖的應(yīng)用_第3頁(yè)
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三圖的應(yīng)用_第4頁(yè)
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三圖的應(yīng)用_第5頁(yè)
已閱讀5頁(yè),還剩13頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三 圖的應(yīng)用(代碼&測(cè)試界面)/Traffic_Inquiry.h#include <stdio.h>#include <stdlib.h>#define FINITY 999 /用999代表無窮大 #define M 20 /城市最大個(gè)數(shù) typedef struct /鄰接矩陣類型定義 char name8;CityNode; /城市信息結(jié)點(diǎn)的結(jié)構(gòu)體(頂點(diǎn)值類型)typedef int distype; /權(quán)值類型-距離 typedef int costype; /權(quán)值類型-費(fèi)用 typedef struct CityNode citysM; /

2、頂點(diǎn)信息域 distype disMM; /領(lǐng)接矩陣-距離costype cosMM; /鄰接矩陣-費(fèi)用int n, e; /圖中頂點(diǎn)總數(shù)與邊數(shù) Mgraph; /建立圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu) void CreateGraph(Mgraph *g)int i, j, k; double d, c;printf("請(qǐng)輸入城市數(shù)與路徑數(shù):");scanf("%d %d",&g->n, &g->e); for(i=0; i<g->n; i+) /讀入圖的頂點(diǎn)數(shù) printf("請(qǐng)輸入第%d個(gè)城市名稱:",

3、i); scanf("%s",g->); for(i=0; i<g->n; i+) /初始化鄰接矩陣 for(j=0; j<g->n; j+) if(i=j) g->disij=0;g->cosij=0;else g->disij=FINITY;g->cosij=FINITY; printf("n城市名稱錄入完畢,錄入結(jié)果:nt"); for(i=0; i<g->n; i+) printf("%d->%st",i,g->citysi.n

4、ame); printf("n錄入路徑的權(quán)值信息,示例:0 1 34 40"); printf("代表%s到%s的距離為34千米,費(fèi)用為40元n",g->,g->);for(k=0; k<g->e; k+) /讀入網(wǎng)絡(luò)中的邊scanf("%d %d %lf %lf",&i, &j, &d, &c);g->disij=g->disji=d;g->cosij=g->cosji=c; /Dijkstra算法求解單源最短

5、路徑 typedef enumFALSE,TRUE boolean; /FALSE為0,TRUE為1 void dijkstra(Mgraph g, int v0,const int q) /函數(shù)參數(shù):圖的領(lǐng)接矩陣g;源點(diǎn)v0;int dM;/權(quán)值(距離或費(fèi)用)向量類型int pM;/路徑類型boolean finalM; /表示當(dāng)前元素是否已經(jīng)求出最短路徑int i,k,v,min;/第一步,初始化集合s與距離向量dfor (v=0; v<g.n; v+)finalv=FALSE;if(q) dv=g.disv0v;else dv=g.cosv0v;if (dv<FINITY &

6、amp;& dv!=0)pv=v0; else pv=-1; /v無前驅(qū)finalv0=TRUE; dv0=0; /初始時(shí)s中只有v0一個(gè)結(jié)點(diǎn)/第二步,依次找出n-1個(gè)結(jié)點(diǎn)加入s中for(i=1; i<g.n; i+)min=FINITY;for(k=0;k<g.n;+k) /找最小邊入結(jié)點(diǎn) if(!finalk&&dk<min) /!finalk表示k還在V-S中 v=k;min=dk;if(min<FINITY)if(q) printf(" %s 到 %s 的最短距離為:%d千米n",,g.ci

7、,min);else printf(" %s 到 %s 的最小費(fèi)用為:%d元n",,,min);else if(min=FINITY) return;finalv=TRUE; /v加入S/第三步,修改V-S中各節(jié)點(diǎn)的距離for(k=0;k<g.n;+k)if(!finalk&&(min+g.disvk<dk)dk=min+g.disvk;pk=v; void floyd(Mgraph g,int q) /Floyd方法求所有頂點(diǎn)對(duì)間的最短路徑(q用于判斷參與算法的是距離還是費(fèi)

8、用) int eMM; /權(quán)值(距離或費(fèi)用)向量類型 int pMM; /路徑類型 int i, j, k; if(q) memcpy(e,g.dis,M*M*sizeof(int); else memcpy(e,g.cos,M*M*sizeof(int); for(i=0;i<g.n;i+) /初始化 for(j=0;j<g.n;j+)if(i!=j && eij<FINITY) pij=i; else pij=-1; for(k=0;k<g.n;k+) /遞推求解每一對(duì)頂點(diǎn)間的最短距離for(i=0;i<g.n;i+)for(j=0;j<

9、g.n;j+) if(eij>(eik+ekj) eij=eik+ekj; pij=k; printf("n");for(i=0;i<g.n;i+) for(j=0;j<g.n;j+) if(i!=j&&eij!=0&&eij<FINITY) if(q) printf(" %s 到 %s 的最短距離為:%dkm。n",,,eij);else printf(" %s 到 %s 的最小費(fèi)用為:%d元。n",

10、,,eij);printf("n");void refer(Mgraph g, int *v0)for(int i=0; i<g.n; i+)printf("%d->%st",i,);printf("n請(qǐng)輸入查詢城市序號(hào):");scanf("%d",v0);if(!(*v0<g.n)printf("你的輸入有誤!n");refer(g,v0);int menu () int set;printf("t n"

11、); printf("t 操作目錄 n"); printf("t n"); printf("t 歡 1.查詢某地到它市最短路徑 n"); printf("t 迎 n"); printf("t 使 2.查詢某地到它市最小費(fèi)用 n"); printf("t 用 n"); printf("t 交 3.顯示各大城市間最短路徑 n");printf("t 通 n"); printf("t 查 4.顯示各大城市間最小費(fèi)用 n")

12、;printf("t 詢 n"); printf("t 系 5.進(jìn)入管理員模式修改數(shù)據(jù) n");printf("t 統(tǒng) n"); printf("t 6.退出交通查詢及管理系統(tǒng) n"); printf("t n"); printf("t n"); printf("n請(qǐng)根據(jù)你的需求選擇操作:"); scanf("%d",&set);printf("n");return set; /main.c#include

13、<stdio.h>#include <stdlib.h>#include <string.h>#include "Traffic_Inquiry.h"int main() int v0;int set=1;Mgraph g; /默認(rèn)交通圖 g.n=8; g.e=11;for(int i=0; i<g.n; i+) /初始化鄰接矩陣 for(int j=0; j<g.n; j+) if(i=j) g.disij=0;g.cosij=0;else g.disij=FINITY;g.cosij=FINITY; strcpy(g.ci

14、,"太原"); strcpy(,"成都");strcpy(,"上海"); strcpy(,"北京");strcpy(,"深圳"); strcpy(,"重慶");strcpy(,"杭州"); strcpy(,"廈門");g.cos01=g.c

15、os10=99; g.dis01=g.dis10=19;g.cos03=g.cos30=12; g.dis03=g.dis30=51;g.cos12=g.cos21=54; g.dis12=g.dis21=14; g.cos17=g.cos71=123; g.dis17=g.dis71=13;g.cos24=g.cos42=201; g.dis24=g.dis42=61;g.cos27=g.cos72=15; g.dis27=g.dis72=25;g.cos36=g.cos63=77; g.dis36=g.dis63=77;g.cos35=g.cos53=45; g.dis35=g.dis53

16、=15;g.cos45=g.cos54=14; g.dis45=g.dis54=17;g.cos76=g.cos67=25; g.dis76=g.dis67=87;g.cos75=g.cos57=66; g.dis75=g.dis57=12;while(set)switch(menu()case 1:refer(g,&v0);dijkstra(g,v0,1);break;case 2:refer(g,&v0);dijkstra(g,v0,0);break;case 3:floyd(g,1);break; /距離 case 4:floyd(g,0);break; /費(fèi)用 case 5:CreateGraph(&g);break;case 6:set=0;printf("tttt歡迎下次使用!n");break;de

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論