【文章內(nèi)容簡(jiǎn)介】 intime[0],(*(*(arcs+qadjvex)+radjvex)).stata[rroute].begintime[1],[qadjvex].cityname,[radjvex].cityname)。 else printf(乘坐No.%d飛機(jī)航班在%d:%d從%s到%s\n,(*(*(arcs+qadjvex)+radjvex)).stata[rroute].number,(*(*(arcs+qadjvex)+radjvex)).stata[rroute].begintime[0],(*(*(arcs+qadjvex)+radjvex)).stata[rroute].begintime[1],[qadjvex].cityname,[radjvex].cityname)。 q=r。 r=rnext。 } printf(最少旅行費(fèi)用是%f元\n\n,m)。 for(v=0。v。v++) {q=p[v].next。 while(q!=NULL) {s=q。 q=qnext。 free(s)。 } p[v].next=NULL。 } free(p)。 return。 } else if(v!=1) {*(final+v)=True。 for(w=0。w。w++) if(*(final+w)==Falseamp。amp。(*(*(arcs+v)+w)).last1) {MinExpenditure(*(*(arcs+v)+w),amp。expenditure,amp。route)。 if(*(M+w)m+expenditure) {*(M+w)=m+expenditure。 q=p[w].next。 while(q!=NULL) {s=q。 q=qnext。 free(s)。 } q=amp。p[w]。 s=p[v].next。 while(s!=NULL) {r=(Node *)malloc(sizeof(Node))。 radjvex=sadjvex。 rroute=sroute。 qnext=r。 q=r。 s=snext。 } r=(Node *)malloc(sizeof(Node))。 radjvex=w。 rroute=route。 rnext=NULL。 qnext=r。 }}}} for(v=0。v。v++) {q=p[v].next。 while(q!=NULL) {s=q。 q=qnext。 free(s)。 } p[v].next=NULL。 } free(p)。 if(k==1) printf(\n不存在列車(chē)車(chē)次從%s到%s\n\n,[v0].cityname,[v1].cityname)。 else printf(\n不存在飛機(jī)航班從%s到%s\n\n,[v0].cityname,[v1].cityname)。} 測(cè)試與分析考慮到道路網(wǎng)多是稀疏網(wǎng)，故采用了鄰接表作存儲(chǔ)結(jié)構(gòu)，其空間復(fù)雜度位O(e)，此時(shí)的時(shí)間復(fù)雜度也為O（e）。構(gòu)建鄰接表的時(shí)間復(fù)雜度位O(n+e)，輸出路徑的時(shí)間復(fù)雜度為O（n2）。由此，本交通資詢(xún)系統(tǒng)的時(shí)間復(fù)雜度位O（n2）。本程序在求最短路徑時(shí)使用了迪杰斯特拉算法，主要考慮在本程序的初級(jí)階段，并不需要大量的查詢(xún)，更多會(huì)是圖信息的添加和修改，重在算法的理解和掌握，因此采用了算法復(fù)雜度相對(duì)較低的迪杰斯特拉算法。當(dāng)然，從性能上來(lái)說(shuō)，當(dāng)交通圖基本穩(wěn)定，而且城市信息基本完善的時(shí)候，使用佛洛伊德把所有的最短路徑信息存儲(chǔ)起來(lái)可能會(huì)更方便一點(diǎn)，后續(xù)的查詢(xún)的時(shí)間復(fù)雜度也會(huì)相對(duì)降低。由此可見(jiàn)，在選用算法時(shí)，不能單純地只考慮算法的時(shí)間復(fù)雜度，有時(shí)還必須綜合考慮各種因素。表11 航班時(shí)刻表 機(jī) 號(hào) 出 發(fā) 地 到 達(dá) 地出發(fā)時(shí)間到達(dá)時(shí)間費(fèi) 用 6320北京上海上海北京16：2018：00 17：2519：05680元2104北京烏魯木齊烏魯木齊 北京8：0010：459：5511：401150元201北京西安 西安 北京15：2512：3517：0014：15930元2323西安廣州 廣州 西安7：1510：159：3511：351320元173拉薩昆明 昆明拉薩10：2012：3511：4514：00830元3304拉薩武漢 武漢拉薩14：1516：2515：4517：55890元82烏魯木齊昆明 昆明烏魯木齊 9：3013：0512：1515：501480元4723武漢廣州廣州武漢 7：0511：258：4513 ：05810元表12 列車(chē)時(shí)刻表車(chē) 次出 發(fā) 地 到 達(dá) 地出發(fā)時(shí)間到達(dá)時(shí)間車(chē) 費(fèi)27北京鄭州西安鄭州鄭州西安鄭州北京13：1521：2405：4113：4221：1205：1313：3021：3978元82元82元78元41北京鄭州上海鄭州鄭州上海鄭州北京7：1115：2000：3509：4015：0800：1309：2817：3790元100元100元90元59上海廣州廣州上海08：2003：3903：1622：53182元134蘭州北京北京蘭州03：5219：2418：5610：28162元323廣州昆明昆明廣州06：1816：3116：1402：27102元873武漢昆明昆明武漢07：1321：4221：1711：46134元116武漢長(zhǎng)沙長(zhǎng)沙武漢9：3618：5418：3203：4898元373長(zhǎng)沙廣州廣州長(zhǎng)沙13：1500：3500：1511：35116元747蘭州武漢武漢蘭州17：4115：1314：4712：19210元371蘭州烏魯木齊烏魯木齊 蘭州11：4200：3523：5411：23114元218武漢西安西安武漢18：5001：3411：5118：35178元第四章 全國(guó)交通咨詢(xún)系統(tǒng)的運(yùn)行 程序主界面全國(guó)交通資詢(xún)系統(tǒng)運(yùn)行主界面，該主界面包括管理員管理、用戶(hù)資訊、顯示交通系統(tǒng)、退出系統(tǒng)四個(gè)選項(xiàng)?？梢赃x擇不同的選項(xiàng)進(jìn)入不同的操作界面。： 全國(guó)交通資詢(xún)主菜單界面 管理員登錄主界面管理員登陸全國(guó)交通資詢(xún)界面，可以進(jìn)行五項(xiàng)基本操作，初始化交通系統(tǒng)、城市編輯、飛機(jī)航班編輯、列車(chē)車(chē)次編輯、返回上一級(jí)菜單。： 管理員登錄界面對(duì)全國(guó)交通資詢(xún)系統(tǒng)進(jìn)行初始化，可選擇兩種初始化方式，鍵盤(pán)和文檔兩種方式。： 全國(guó)交通資詢(xún)系統(tǒng)初始化界面選擇城市編輯，可以進(jìn)行兩項(xiàng)基本操作，增加城市和刪除城市。： 城市編輯界面選擇飛機(jī)航班編輯，可以進(jìn)行兩項(xiàng)基本操作，新增航班和刪除航班。： 飛機(jī)航班編輯界面選擇列車(chē)車(chē)次編輯，可以進(jìn)行兩項(xiàng)基本操作，新增車(chē)次和刪除車(chē)次。： 列車(chē)車(chē)次編輯界面 用戶(hù)界面登錄界面全國(guó)交通資詢(xún)用戶(hù)登錄主界面，可以進(jìn)行四項(xiàng)基本操作，最少旅行費(fèi)用查詢(xún)、最少旅行時(shí)間查詢(xún)、最少旅行中轉(zhuǎn)次數(shù)查詢(xún)和返回上一級(jí)菜單。： 用戶(hù)主界面用戶(hù)查詢(xún)最少旅行費(fèi)用查詢(xún)界面，進(jìn)行最少旅行費(fèi)用查詢(xún)。： 最少旅行費(fèi)用查詢(xún)用戶(hù)查詢(xún)最少旅行時(shí)間查詢(xún)界面，進(jìn)行最少旅行費(fèi)用查詢(xún)。： 最少旅行時(shí)間查詢(xún)用戶(hù)查詢(xún)最少旅行中轉(zhuǎn)次數(shù)查詢(xún)，進(jìn)行最少旅行費(fèi)用查詢(xún)。： 最少旅行中轉(zhuǎn)次數(shù)查詢(xún) 顯示交通系統(tǒng)界面全國(guó)交通資詢(xún)系統(tǒng)交通系統(tǒng)界面，可以進(jìn)行四項(xiàng)基本操作，顯示城市、顯示飛機(jī)航班、顯示列車(chē)車(chē)次和返回上一級(jí)菜單。： 全國(guó)交通資詢(xún)系統(tǒng)交通系統(tǒng)界面全國(guó)交通資詢(xún)系統(tǒng)顯示城市界面，進(jìn)行城市信息查詢(xún)。： 全國(guó)交通資詢(xún)系統(tǒng)交通系統(tǒng)界面全國(guó)交通資詢(xún)系統(tǒng)顯示飛機(jī)航班界面，進(jìn)行飛機(jī)航班查詢(xún)。： 全國(guó)交通資詢(xún)系統(tǒng)顯示飛機(jī)航班界面全國(guó)交通資詢(xún)系統(tǒng)顯示列車(chē)車(chē)次界面，進(jìn)行列車(chē)車(chē)次查詢(xún)。： 全國(guó)交通資詢(xún)系統(tǒng)顯示列車(chē)車(chē)次界面結(jié)束語(yǔ)遇到的問(wèn)題：主要遇到了怎樣儲(chǔ)存和讀取哈夫曼樹(shù)的問(wèn)題，知道了應(yīng)該靈活解決問(wèn)題，如在建哈夫曼樹(shù)時(shí)要由葉子結(jié)點(diǎn)向根結(jié)點(diǎn)的次序，而在讀取時(shí)應(yīng)由根結(jié)點(diǎn)向葉子結(jié)點(diǎn)的次序。文件流問(wèn)題：無(wú)法讀指定的文件。解決，先判斷文件能否打開(kāi)，若能打開(kāi)，則繼續(xù)操作，還要判斷是否是全文結(jié)束。總結(jié)：這次實(shí)驗(yàn)難度很高，有許多復(fù)雜的函數(shù)和文件流問(wèn)題。遇到了許多問(wèn)題，在哈夫曼樹(shù)的建立存儲(chǔ)和讀取方面可以參照書(shū)獨(dú)立完成，但文件流方面難度較高，涉及到許多特定語(yǔ)句和形式，如if(!())，ofstream coding()。等，由于以前不經(jīng)常使用，接觸不多，所以使用比較困難，通過(guò)向他人請(qǐng)教和參考以有的例子得以解決。通過(guò)此次實(shí)驗(yàn)更加鞏固了樹(shù)、二叉樹(shù)的用法，深入理解了樹(shù)和二叉樹(shù)在計(jì)算機(jī)中的存儲(chǔ)和讀取方式，也增強(qiáng)了自學(xué)能力，并且對(duì)文件流方面的知識(shí)有更深一步的運(yùn)用和了解，雖然還不能靈活的應(yīng)用，但已經(jīng)起到了拋磚引玉的作用。同時(shí)也更加意識(shí)到，每一次編程都是對(duì)自己學(xué)習(xí)能力和耐力的挑戰(zhàn)，督促我去了解更有用的東西，得到進(jìn)一步的提高。 參考文獻(xiàn)[1] Server2000數(shù)據(jù)庫(kù)應(yīng)用開(kāi)發(fā)[M].北京:電子工業(yè)出版社,2001,06[2] 王黎,[M].北京:清華大學(xué)出版社,2002,01[3] [M].北京:清華大學(xué)出版社,2003,02[4] Windows程序設(shè)計(jì)[M].北京:清華大學(xué)出版社,2004,06[5] [M].北京:北京希望電子出版社,2002,05[6] 嚴(yán)蔚敏,(C語(yǔ)言版)[M].北京:清華大學(xué)出版社,1997,09[7] C++ [M].北京:人民郵電出版社,2005,08[8] 朱晴婷,黃海鷹,++程序設(shè)計(jì)[M].北京:清華大學(xué)出版社,1998,09[9] 嚴(yán)蔚敏,[M].北京:清華大學(xué)出版社,2002,06[10] [M].北京:清華大學(xué)出版社,2002,04[11] [M].北京:清華大學(xué)出版社,2002,03附錄 主要代碼：int main() {ALGraph G。 int i。 printf( ┏━━━━━━━━━━━━━━━━━┓\n)。printf( ┃ 歡迎使用交通咨詢(xún)管理系統(tǒng) ┃\n)。printf( ┃ ┃\n)。printf( ┃ 主菜單 ┃\n)。printf( ┃ ┃\n)。printf( ┃ 制作者：余森 ┃\n)。printf( ┃ ┃\n)。printf( ┃ （請(qǐng)按提示操作） ┃\n)。printf( ┃ ┃\n)。printf( ┣━━━━━━━━━━━━━━━━━┫\n)。printf( ┃ ┃\n)。printf( ┃ 1 管理員管理 ┃\n)。pr