1、數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)報(bào)告班級(jí)：計(jì)嵌141姓名：陳志遠(yuǎn)學(xué)號(hào)：1413052023交通指南系統(tǒng)1. 問(wèn)題描述 假設(shè)以一個(gè)帶權(quán)有向圖表示某一區(qū)域的公交線(xiàn)路圖，圖中頂點(diǎn)代表一些區(qū)域中的重要站點(diǎn)，弧代表已有的公交線(xiàn)路，弧上的權(quán)表示該線(xiàn)路上的票價(jià)（或搭乘所需時(shí)間），試設(shè)計(jì)一個(gè)交通指南系統(tǒng)，指導(dǎo)前來(lái)咨詢(xún)者以最低的票價(jià)或最少的時(shí)間從區(qū)域中的某一站點(diǎn)到達(dá)另一站點(diǎn)。 2. 基本要求 （1）設(shè)計(jì)結(jié)點(diǎn)和圖的存儲(chǔ)結(jié)構(gòu)； （2）設(shè)計(jì)任意兩點(diǎn)最短路徑方法； （3）輸入：圖的相關(guān)信息以建立公交線(xiàn)路網(wǎng)，以及公交線(xiàn)路網(wǎng)咨詢(xún)的任意兩個(gè)站點(diǎn)； （4）輸出：兩個(gè)站點(diǎn)間一條最短的簡(jiǎn)單路徑。 3. 實(shí)現(xiàn)提示 （1） 結(jié)點(diǎn)和圖的存儲(chǔ)結(jié)構(gòu) typ

2、edef struct node int no; float wgt; struct node*next; edgenode; typedef struct char vtx; edgenode*link; vexnode; typedef vexnode Graphn; void Floyd(Graph G，float Ann，int pnn) int i，j，k; for(i=0;in;i+) fot(j=0;jn;j+) Aij=Gij; Pij=-1; for(k=0;kn;k+) for(i=0;in;i+) for(j=0;jn;j+) if(Aik+AkjAij) pij=k;

3、Aij=Aik+Akj; （2）算法提示 采用任意兩點(diǎn)最短路徑的相關(guān)算法。 4.源代碼#include using namespace std;struct ArcCellint adj; /存放弧長(zhǎng) bool *info; /是否用過(guò)該弧;struct _MGraph char vexs20; /存放站點(diǎn)ArcCell arcs2020; /int vexnum;int arcnum;typedef int Path202020; typedef int Distanc2020; class MGraph /沒(méi)用私有成員 public:_MGraph mgraph;/void Destroy

4、Graph(); /析構(gòu)函數(shù)銷(xiāo)毀圖int LocateVex (char u); / 返回頂點(diǎn)在圖中的位置bool CreateDN(); /構(gòu)造有向網(wǎng)void ShortestPath_FLOYD(Path &P,Distanc &D);bool MGraph:CreateDN()/構(gòu)造有向網(wǎng)int i,j ,w;char v1, v2;coutmgraph.vexnummgraph.arcnum ;coutn請(qǐng)輸入各站點(diǎn)名: ;for(i = 0;imgraph.vexsi;for(i = 0;imgraph.vexnum;i+)/初始化鄰接矩陣for(j = 0;jmgraph.vexn

5、um;j+)if(i=j)mgraph.arcsij.adj = 0;elsemgraph.arcsij.adj = 20000; /infinity; = false;for(i = 0;imgraph.arcnum;i+) /構(gòu)造鄰接矩陣coutv1v2w;int m = LocateVex(v1);int n = LocateVex(v2);mgraph.arcsmn.adj = w; / 的權(quán)值return true; void MGraph:DestroyGraph()for(int i = 0 ;imgraph.vexnum;i+)for(in

6、t j = 0;jmgraph.vexnum;j+)if()delete ; = false;mgraph.vexnum = 0;mgraph.arcnum = 0;int MGraph:LocateVex(char u)for(int i = 0 ;i20;i+)if(u = mgraph.vexsi)return i;return -1;void MGraph:ShortestPath_FLOYD(Path &P,Distanc &D)/求每對(duì)頂點(diǎn)間的最短路徑/ 用Floyd算法求有

7、向網(wǎng)G中各對(duì)頂點(diǎn)v和w之間的最短路徑Pvw及其帶權(quán)長(zhǎng)度Dvw/ 若Pvwu為T(mén)RUE，則u是從v到w當(dāng)前求得最短路徑上的頂點(diǎn)。 int u,v,w,i;for(v = 0;vmgraph.vexnum;v+)for(w = 0;wmgraph.vexnum;w+)Dvw = mgraph.arcsvw.adj;/ 頂點(diǎn)v到頂點(diǎn)w的直接距離for(u = 0;umgraph.vexnum;u+)Pvwu = false; /路徑矩陣初值if(Dvw20000) /從v到w有直接路徑Pvwv = Pvww = true;/由v到w的路徑經(jīng)過(guò)v和w兩點(diǎn)for(u = 0;umgraph.vexnum

8、;u+)for(v = 0;vmgraph.vexnum;v+)for(w = 0;wmgraph.vexnum;w+)if(Dvu+DuwDvw)/從v經(jīng)u到w的一條路徑更短Dvw = Dvu+Duw;/ 更新最短距離for(i = 0;imgraph.vexnum;i+) Pvwi = Pvui|Puwi;/從v到w的路徑經(jīng)過(guò)從v到u和從u到w的所有路徑void main()MGraph g;Path p; / 3維數(shù)組Distanc d; / 2維數(shù)組int s,t,k;char v1,v2;float sum=0;coutn*歡迎使用交通指南系統(tǒng)*nendl;g.CreateDN();coutv1v2;s=g.LocateVex (v1);t=g.LocateVex (v2); g.ShortestPath_FLOYD(p,d); if(s!=t) int a=s;coutn由站點(diǎn)g.mgraph.vexss到站點(diǎn)g.mgraph.vexst途中經(jīng)過(guò)站點(diǎn)：;for(k = 0;kg.mgraph.vexnum;k+)if(pstk