數(shù)據(jù)結(jié)構(gòu)全國(guó)交通咨詢模擬系統(tǒng)實(shí)習(xí)報(bào)告

1、全國(guó)交通咨詢模擬管理系統(tǒng)數(shù)據(jù) 構(gòu)課 設(shè)計(jì) 告學(xué)院：計(jì)算機(jī)學(xué)院姓名：班級(jí)：學(xué)號(hào)：指導(dǎo)老師日期:1. 需求分析出于不同目的的旅客對(duì)交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時(shí)間盡可能短，出門(mén)旅游的游客則期望旅費(fèi)盡可能省，而老年旅客則要求中轉(zhuǎn)次數(shù)最少。編制一個(gè)全國(guó)城市間的交通咨詢程序，為旅客提供兩種或三種最優(yōu)決策的交通咨詢。要求：（1）提供對(duì)城市信息進(jìn)行編輯（如添加或刪除）的功能。（2）城市之間有兩種交通工具：火車(chē)和飛機(jī)。提供對(duì)列車(chē)時(shí)刻表和飛機(jī)航班進(jìn)行編輯（增設(shè)或刪除）的功能。（3）提供兩種最優(yōu)決策：最快到達(dá)或最省錢(qián)到達(dá)。全程只考慮一種交通工具。（4）旅途中耗費(fèi)的總時(shí)間應(yīng)該包括中轉(zhuǎn)站的

2、等候時(shí)間。（5）咨詢以用戶和計(jì)算機(jī)的對(duì)話方式進(jìn)行。2. 設(shè)計(jì)2.1 設(shè)計(jì)思想（1）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)該系統(tǒng)存儲(chǔ)結(jié)構(gòu)運(yùn)用到數(shù)組和結(jié)構(gòu)體。該結(jié)構(gòu)分別存儲(chǔ)火車(chē)列次，航班，出發(fā)點(diǎn)與目的地以及所需要走的路程和所用費(fèi)用。主要用到的數(shù)據(jù)結(jié)構(gòu)有圖中的交通網(wǎng)的各種信息的鄰接矩陣的存儲(chǔ)。最短路徑使用迪杰斯特拉算法編程求算得出最近或最便宜路徑。火車(chē)列次，航班的存儲(chǔ)結(jié)構(gòu)：struct Tvaval II火車(chē)或飛機(jī)的存儲(chǔ)結(jié)構(gòu)IIchar id20;/火車(chē)或飛機(jī)航班的代碼/char start20;/出發(fā)地/char en d20;/目的地/float time;/路途時(shí)間/float price;/價(jià)錢(qián)/；（2 ）算法設(shè)計(jì)在

3、求最短路徑使用到的算法是迪杰斯特拉算法，算法步驟如下：1、 起始點(diǎn)（V0）與其相鄰點(diǎn)的權(quán)值（即當(dāng)前最短路徑）。2、 求出當(dāng)前最短路徑中的最小值即是該起始點(diǎn)（V0）與另一點(diǎn)（Vi）的最短路徑。3、 V0到Vi的距離加上 Vi到Vj的距離小于 V0到Vj則將V0到Vi的距離加上 Vi 到Vj的距離記為V0到Vj當(dāng)前最短路徑，循環(huán)第二、三步。如此得到V0到各點(diǎn) 的最短路徑，進(jìn)而可以得到想要的一條。系統(tǒng)主干功能的實(shí)現(xiàn)是用一個(gè)swich語(yǔ)句來(lái)實(shí)現(xiàn)多功能的選取以及程序的退出；主要有:1:修改地圖，2:編輯火車(chē)時(shí)刻表，3:編輯飛機(jī)航班表，4:選擇出游路線 ,5:退出；繼而通 過(guò)選中其中的數(shù)字來(lái)實(shí)現(xiàn)自己的目的

4、；然后再引用程序再用一個(gè)switch case語(yǔ)句來(lái)實(shí)現(xiàn)1 23選項(xiàng)中的添加刪除以及退出功能，然后在4中再用if語(yǔ)句來(lái)實(shí)現(xiàn)自己的需求考慮。可以隨時(shí)退出程序。最后再經(jīng)調(diào)用函數(shù)再來(lái)輸出結(jié)果。系統(tǒng)設(shè)計(jì)中包括的函數(shù)模塊:1. 查找模塊int search（char citytable20, char* city, i nt number）在城市數(shù)中查找某個(gè)城市2. 尋找最優(yōu)路線模塊void the_best_path（struct Tvaval* timetable, char* start, char* end, charcity20, i nt times, i nt number, i nt c

5、hoice） /尋找最優(yōu)路線先得到存儲(chǔ)最少花費(fèi)或最短時(shí)間信息的鄰接矩陣，接著得到起始點(diǎn)與相鄰的點(diǎn)的權(quán)值（即當(dāng)前最短路徑）并記錄點(diǎn)，再求出當(dāng)前最短路徑中的最小值即是該起始點(diǎn)（V0）與另一點(diǎn)（Vi）的最短路徑，V0到Vi的距離加上Vi到Vj的距離小于 V0到Vj則將V0到Vi的距離加 上Vi到Vj的距離記為V0到Vj當(dāng)前最短路徑并且記錄前一個(gè)點(diǎn)。然后重復(fù)（4），（5）步得到所有點(diǎn)最短路徑。最后以終點(diǎn)開(kāi)始逐步向前賦值得到所需路徑并輸出該路徑的權(quán)值。3. 主函數(shù)模塊void mai n（）主函數(shù)本設(shè)計(jì)采用的是在界面上通過(guò)輸入相應(yīng)的字符表示的要求來(lái)實(shí)現(xiàn)對(duì)于不同目的不同函數(shù)的調(diào)用，主要用到的數(shù)據(jù)結(jié)構(gòu)有圖中

6、的交通網(wǎng)的各種信息的鄰接矩陣的存儲(chǔ)。通過(guò)顧客輸入不同的字符來(lái)實(shí)現(xiàn)不同的功能，主界面上注釋著這個(gè)程序的系統(tǒng)名稱，組員以及指導(dǎo)老師等基本學(xué)生信息，用星號(hào)來(lái)加以修飾；然后就是用一個(gè)swich語(yǔ)句來(lái)實(shí)現(xiàn)多功能的選取以及 程序的退出；主要有一：1:修改地圖2:編輯火車(chē)時(shí)刻表t3:編輯飛機(jī)航班表t4:選擇出游路線 t5:退出；繼而通過(guò)選中其中的數(shù)字來(lái)實(shí)現(xiàn)自己的目的；然后再引用程序再用一個(gè) switch case語(yǔ)句來(lái)實(shí)現(xiàn)1 2 3選項(xiàng)中的添加刪除以及退出功能，然后在 4中再用if語(yǔ)句來(lái)實(shí) 現(xiàn)自己的需求考慮?？梢噪S時(shí)退出程序。2.2 設(shè)計(jì)表示（1）函數(shù)調(diào)用關(guān)系圖編輯火車(chē)時(shí)刻表編輯飛機(jī)航班表選擇出游路線主函數(shù)

7、修改地圖退出2.3 詳細(xì)設(shè)計(jì)(1 )查找模塊int search(char citytable20, char* city, int nu mber) / 個(gè)城市/在城市數(shù)中查找某int i;for (i = 0; inu mber; i+)if (strcmp(citytablei, city) = 0) return i;return -1;(2)最優(yōu)路徑算法模塊void the_best_path(struct Tvaval* timetable, char* start, char* end, char city20, int times, int number, int choice

8、)/最優(yōu)路線/start表示出發(fā)地，end表示目的地，times表示表示航班或車(chē)次的總次數(shù)，number表示城市的總數(shù)/choice=0表示求最短時(shí)間路線,int i, j, k, st, et;float min, t;char pcity1020;float edge1515, dist15;/15*15choice=1表示求最少花費(fèi)路線/的數(shù)組儲(chǔ)存的是權(quán)值/in t path15, s15;for (i = 0; inu mber; i+)for (j = 0; j nu mber; j+)edgeij = max;for (i = 0; itimes; i+)/dijkstra算法 /

9、j = search(city, timetablei.start, number);/尋找出發(fā)地 /k = search(city, timetablei.end, number);/尋找目的地 /if (choice = 0)/最短時(shí)間/t = timetablei.time; if (tedgejk) edgejk = t;else/最少花費(fèi)IIt = timetablei.price; if (tedgejk) edgejk = t;st = search(city, start, nu mber);et = search(city, end, nu mber);for (i = 0;

10、 inu mber; i+)disti = edgesti;si = 0;if (i != st&distimax) pathi = st;else pathi = -1;sst = 1; distst = 0;for (i = 0; inu mber - 1; i+)min = ma x;k = st;for (j = 0; j nu mber; j+)if (!sj & distjmi n)k = j;min = distj;sk = 1;for (j = 0; j nu mber; j+)if (!sj & edgekjmax&distk + edgekj= 0; j-)printf(%

11、s , pcityj);prin tf(n);if (choice = 0)printf(tt 所需總時(shí)間為：5.1f 小時(shí)n, distet); elseprintf(tt 所需的總費(fèi)用為:%7.2f 元n, distet); prin tf(n);(3)主函數(shù)模塊void mai n()int i, j, k, m, n, number = 5, train_number = 6, fly_number = 6;prin tf(tt* n);prin tf(tt*歡迎使用全國(guó)交通查詢系統(tǒng)*n ”);prin tf(tt* n);char city1520 = 最多15個(gè)城市II北京,昆明,

12、曲靖,重慶,武漢；/現(xiàn)有城市, T1,北京,武漢,10, 90 , T2,北京,昆明,8, 70 , T3,昆明,曲靖,3, 30 , T4,昆明,重慶,25, 200 , T5,武漢,重慶,14, 120 , T6,昆明,武漢,8, 80 struct Tvaval flight20 = F1,北京,武漢,3, 500 , F2,北京,昆明, 2.5, 400 F3,昆明,曲靖,1,200 , F4,昆明,重慶,6, 1400 , F5,武漢,重慶,5, 700 , F6,昆明,武漢,3, 450 ;prin tf(tt現(xiàn)有城市); /struct Tvaval train 20 = 輸出現(xiàn)

13、有地圖上的城市,便于后面的輸入和修改/for (j = 0; j nu mber; j+)prin tf(%d.%st, j + 1, cityj); prin tf(nn);loopl:printf(t請(qǐng)選 擇所需 功能：ntt1:修 改地圖ntt2:ntt3:編輯飛機(jī)航班表ntt4:選擇出游路線ntt5:退出”);printf(nt請(qǐng)選擇:);scanf(%d, &i);while (i != 1 & i != 2 & i != 3 & i != 4 & i != 5)prin tf(tt輸入有誤，請(qǐng)重新輸入:);scan f(%d, & i); /避免按錯(cuò)而導(dǎo)致程序錯(cuò)誤/switch (

14、i) /switch語(yǔ)句 /case 1: /第一種情況，修改地圖*/Ioop2:prin tf(t現(xiàn)有城市：ntt);for (j = 0; jnu mber | k1)prin tf(tt輸入有誤，請(qǐng)重新輸入:);scan f(%d, &k); /避免按錯(cuò)而導(dǎo)致程序錯(cuò)誤/if (k = nu mber) nu mber-;編輯火車(chē)時(shí)刻表返回n);elsefor (m = k - 1; mnu mber - 1; m+)strcpy(citym, citym + 1);nu mber-; /elsegoto Ioop2; /城市總數(shù)減少一個(gè)/ifelse goto loop1; / case

15、 1，修改地圖/case 2: /修改火車(chē)時(shí)間表Ioop3:prin tf(nttprin tf(tt/輸出各火車(chē)時(shí)刻表/回到主菜單/現(xiàn)有火車(chē)時(shí)刻表：n);車(chē)次起點(diǎn)站終點(diǎn)站路途時(shí)間(h)for (j = 0; jtra in_nu mber; j+)prin tf(tt%d:%st%st%st%5.1ftt%5.2ftn.票價(jià)(元)n);j + 1,查看修改后的地圖，便于判斷或是再次修改 train j.id, train j.start, train j.e nd, train j.time, train j.price);prin tf(nn);printf(t功能：1.添加 t2.刪除t

16、3.返回 n);prin tf(t請(qǐng)選擇：);scan f(%d, &j);while (j != 1 & j != 2 & j != 3)prin tf(tt輸入有誤，請(qǐng)重新輸入：”)；scan f(%d, &j); /避免按錯(cuò)而導(dǎo)致程序錯(cuò)誤/ prin tf(n);if (j = 1) prin tf(現(xiàn)有城市：n);for (k = 0; ktra in_nu mber | k1)prin tf(tt輸入有誤，請(qǐng)重新輸入:);scan f(%d, &k); /避免按錯(cuò)而導(dǎo)致程序錯(cuò)誤/if (k = train_number) train_number-; /火車(chē)車(chē)次減一 /elsefor

17、 (m = k - 1; mtra in_nu mber - 1; m+)trai nm = trai nm + 1;train _nu mber-;goto Ioop3; / 回到Ioop3，查看修改后的列車(chē)信息/else goto loop1; /回到主菜單 /case 2 ,修改火車(chē)時(shí)刻表/case 3:/修改飛機(jī)航班表，和列車(chē)相似/Ioop4:prin tf(tt現(xiàn)有飛機(jī)航班表：n);printf(tt班次t起點(diǎn)t終點(diǎn)t路途時(shí)間t票價(jià)n);for (j = 0; jfly_ nu mber; j+)prin tf(tt%d:%st%st%st%5.1ftt%5.2ft n,j +1,f

18、lightj.id, flightj.start, flightj.e nd,flightj.time, flightj.price);prin tf(nn);printf(tt功能：1.添加 t2.刪除 t3.返回 n);prin tf(tt請(qǐng)選擇：”)；scan f(%d, &j);while (j != 1 & j != 2 & j != 3)prin tf(tt輸入有誤，請(qǐng)重新輸入：”)；scan f(%d, &j); /避免按錯(cuò)而導(dǎo)致程序錯(cuò)誤/prin tf(n);if (j = 1)prin tf(現(xiàn)有城市：n);for (k = 0; kfly_number | k1)prin

19、tf(tt輸入有誤，請(qǐng)重新輸入：”)；scan f(%d, &k); /避免按錯(cuò)而導(dǎo)致程序錯(cuò)誤/if (k = fly_nu mber) fly_nu mber-;elsefor (m = k - 1; mfly_ nu mber - 1; m+)flightm = flightm + 1;fly_nu mber-;/elsegoto loop4;/else ifelse goto loop1;/case 3,修改飛機(jī)航班表/case 4:printf(tt請(qǐng)選擇交通工具(1.火車(chē)2.飛機(jī)):);scan f(%d, &j);while (j != 1 & j != 2)prin tf(tt輸

20、入有誤，請(qǐng)重新輸入：”)；scan f(%d, &j); /避免按錯(cuò)而導(dǎo)致程序錯(cuò)誤/printf(tt請(qǐng)選擇決策方案(1.最短時(shí)間2.最少花費(fèi)):);scan f(%d, &k);while (k != 1 & k != 2)prin tf(tt輸入有誤，請(qǐng)重新輸入：”)；scan f(%d, &k); /避免按錯(cuò)而導(dǎo)致程序錯(cuò)誤/prin tf(t 現(xiàn)有城市：n);for (i = 0; inumber | mnumber | nenTsDebugCppL, ese藕憎仙證回.8 -2.婁點(diǎn)西 市數(shù)別起亠 戰(zhàn)杲八叭年 至輸軍訃 現(xiàn)請(qǐng)久上一r?路連對(duì)I永s .e3 -EJ25.B14 .0S.Q3.0淸矍牡電-叟伺添加新的火車(chē)班次刪除火車(chē)車(chē)次(3)飛機(jī)時(shí)刻表中的編輯與刪除八C:Duuumems wd 5ettihsAJinistctcrMY DocucrrtsPelmijC