【正文】 交通圖咨詢查詢系統(tǒng)數(shù)據(jù)結(jié)構(gòu)培訓(xùn)資料作者：日期：信息科學(xué)與工程學(xué)院《結(jié)構(gòu)數(shù)據(jù)》課 程 設(shè) 計(jì) 報(bào) 告課程設(shè)計(jì)名稱： 交通咨詢系統(tǒng) 專 業(yè) 班 級(jí) ： 計(jì)算機(jī)xxx 學(xué) 生 姓 名 ： xxx 學(xué) 號(hào) ： 2015xxxx 指 導(dǎo) 教 師 ： xx 課程設(shè)計(jì)時(shí)間： — 計(jì)算機(jī)應(yīng)用技術(shù) 專業(yè)課程設(shè)計(jì)任務(wù)書學(xué)生姓名Xxx專業(yè)班級(jí)學(xué)號(hào)題 目交通咨詢系統(tǒng)課題性質(zhì)A課題來源D指導(dǎo)教師白浩同組姓名無主要內(nèi)容1. 建立交通網(wǎng)絡(luò)圖的存儲(chǔ)結(jié)構(gòu)。2. 某個(gè)城市到達(dá)其余各城市的最短路徑。3. 實(shí)現(xiàn)兩個(gè)城市之間最短路徑的問題。4. 主要目的是給用戶提供路徑咨詢?nèi)蝿?wù)要求5. 根據(jù)需求分析給出概要設(shè)計(jì)，本系統(tǒng)包括以下功能模塊：添加信息、查詢信息、刪除信息、修改信息、退出和保存信息；6. 結(jié)合課題利用數(shù)據(jù)結(jié)構(gòu)相關(guān)知識(shí)，利用C語言實(shí)現(xiàn)該系統(tǒng)的所有上述功能，要求界面友善，程序運(yùn)行正常；7. 提交課程設(shè)計(jì)報(bào)告1份（具體寫作要求參考樣例），可運(yùn)行的系統(tǒng)和源代碼電子版一套。參考文獻(xiàn)嚴(yán)蔚敏.《數(shù)據(jù)結(jié)構(gòu)（C語言版）》.北京：清華大學(xué)出版社譚浩強(qiáng).《C語言程序設(shè)計(jì)》.（第三版）北京：清華大學(xué)出版社審查意見指導(dǎo)教師簽字：xx教研室主任簽字：xx 2016 年 06 月 27 日 說明：本表由指導(dǎo)教師填寫，由教研室主任審核后下達(dá)給選題學(xué)生，裝訂在設(shè)計(jì)（論文）首頁填 表 說 明1．“課題性質(zhì)”一欄：A．工程設(shè)計(jì)；B．工程技術(shù)研究；C．軟件工程（如CAI課題等）；D．文獻(xiàn)型綜述；E．其它。2．“課題來源”一欄：A．自然科學(xué)基金與部、省、市級(jí)以上科研課題；B．企、事業(yè)單位委托課題；C．校、院（系、部）級(jí)基金課題；D．自擬課題。目錄1 需求分析 1 添加交通圖信息 1 查詢單源最短路徑 1 查詢多源最短路徑 1 更新交通圖信息 2 讀取、保存信息 22 概要設(shè)計(jì) 3 數(shù)據(jù)類型的定義 3 功能模塊結(jié)構(gòu)圖 43 運(yùn)行環(huán)境 64 開發(fā)工具和編程語言 65 詳細(xì)設(shè)計(jì) 7 圖結(jié)構(gòu)的基本操作 7 8 8 8 8 迪杰斯特拉算法的實(shí)現(xiàn) 8 迪杰斯特拉算法函數(shù) 8 提取迪杰斯特拉函數(shù)信息 8 求多源最短路徑 86 程序編碼 97 運(yùn)行結(jié)果 418 心得體會(huì) 469參考文獻(xiàn) 471 需求分析本系統(tǒng)中的數(shù)據(jù)來源于標(biāo)準(zhǔn)輸入設(shè)備（如鍵盤）和文件，可以實(shí)現(xiàn)對(duì)交通圖城市、城市到其余城市的距離的操作，根據(jù)需要可查詢某兩個(gè)城市之間的最短距離、城市到各城市的最短距離，各個(gè)城市到各個(gè)城市的最短距離，以及路徑。本系統(tǒng)要實(shí)現(xiàn)的功能有：添加城市和城市間距離，刪除城市及城市間距離，修改城市間距離，查詢城市間的最短路徑，查詢某個(gè)城市到某個(gè)城市的最短路徑。具體如下： 添加交通圖信息能錄入新數(shù)據(jù)（城市和路徑）。當(dāng)錄入了重復(fù)的城市和路徑時(shí)，則提示數(shù)據(jù)錄入重復(fù)并取消錄入；當(dāng)交通圖中超過15個(gè)城市時(shí)，存儲(chǔ)空間已滿，不能再錄入新數(shù)據(jù)；錄入的新數(shù)據(jù)能按遞增的順序自動(dòng)進(jìn)行條目編號(hào)。 查詢單源最短路徑能夠?qū)崿F(xiàn)輸入起點(diǎn)城市名后，查詢出其到各個(gè)城市的最短路徑，輸出該城市到的其他所有的城市的最短路徑。 查詢多源最短路徑 輸入起點(diǎn)城市名和終點(diǎn)城市名，查詢出兩個(gè)城市的最短路徑，并輸出該最短路徑。 更新交通圖信息根據(jù)給定的城市名能夠修改該城市的名字?；蛘咻斎雰蓚€(gè)城市，修改一條路徑的距離。 刪除交通圖信息 根據(jù)輸入的城市名 ，刪除與該城市有關(guān)的所有路徑。輸入兩個(gè)城市可以刪除一條路徑。 讀取、保存信息能夠?qū)崿F(xiàn)退出系統(tǒng)時(shí)把交通圖中的信息保存在一個(gè)文件中，在程序瑕疵運(yùn)行時(shí)能夠讀取出來。2 概要設(shè)計(jì) 數(shù)據(jù)類型的定義1. 定義交通圖城市的元素類型 typedef struct _city{ char name[10]。城市名 struct _path * firstpath；//第一個(gè)路徑 }AdjList[15],CityNode。2. 定義交通圖的路徑元素類型 typedef struct _path{ int adjcity//鄰接點(diǎn)域 int distance；//距離 struct _path *nextpath；//下一個(gè)路徑 }PathNode,*PathPtr。3. 定義交通圖類型 typedef struct { int cities。 int paths。 AdjList list；}Graph 。4. 全局變量PList head。typedef int PathMatrix。typedef int ShortPathTable。PathMatrix P[MAX_CITIES][MAX_CITIES]。ShortPathTable D[MAX_CITIES]。 功能模塊結(jié)構(gòu)圖根據(jù)需求分析，為了滿足用戶的功能需求，按照軟件開發(fā)方法學(xué)中的模塊劃分原則，我將本系統(tǒng)主要?jiǎng)澐譃槿缦履K：操作交通圖信息，和查詢交通圖路徑兩大模塊。各模塊之間的關(guān)系如圖1所示。 圖 1模塊結(jié)構(gòu)圖為了實(shí)現(xiàn)上述功能模塊，分別在順序表和單鏈表物理結(jié)構(gòu)上定義了多個(gè)函數(shù)，本系統(tǒng)定義的函數(shù)和功能如下：1. 數(shù)據(jù)結(jié)構(gòu)部分部分 void initalize_graph(Graph *G)功能為：圖初始化，即生成一個(gè)空?qǐng)D。int CreatAdjList(Graph *G)//初始化交通圖功能為：圖的創(chuàng)建，用圖存儲(chǔ)數(shù)據(jù)。void ADD_CITY(Graph *G)功能為：往圖G中插入一個(gè)城市結(jié)點(diǎn)。void ADD_PATH(Graph *G,int ori,int add,PathNode *p)功能為：往圖G中插入一個(gè)路徑結(jié)點(diǎn)。void DELETE_CITY(Graph *G,int city)功能為：刪除圖G中的指定的城市及其相關(guān)的路徑。void DELETE_PATH(Graph *G,int left,int right)功能為：刪除圖G中一條指定的路徑。void UPDATE_PATH(Graph *G,int left,int right)功能為：更新圖G中的一個(gè)路徑信息 。Status SqListSearchByName(SqList *L,char *name) 。功能為：通過姓名查找順序表中,返回值為其在通訊錄中的位置 。void UPDATE_CITY(Graph *G,int city,char *name)功能為：更新圖G中的一個(gè)城市信息 。Status SqListSearchByName(SqList *L,char *phone) 。功能為：通過電話號(hào)碼查找順序表中,返回值為其在通訊錄中的位置。 void MODE_CLIENT(Graph *G)功能為：客戶端界面函數(shù)。 void MODE_ADMIN(Graph *G)功能為：管理員端界面函數(shù)。 int ReadAdjList(Graph *G)功能為：從文件中讀取交通圖。 int WriteAdjList(Graph *G) 功能為：在文件中存儲(chǔ)交通圖。 void menu(int i)功能為：各種的端界面打印。void ShortestPath(Graph *G,int v0)功能為：迪杰斯特拉算法，求出對(duì)V0單源最短路徑。void Print(Graph *G,int v0)功能為：根據(jù)迪杰斯特拉算法，打印出V0單源最短路徑。void Print2(Graph *G,int v1,int v2)功能為：根據(jù)迪杰斯特拉算法，打印出V1和V2的最短路徑。void FindPath(Graph *G,int v)功能為：打印出V1到V2的經(jīng)過路徑。int dis(Graph *G,int left,int right)功能為：返回指定路徑的距離。3 運(yùn)行環(huán)境1. 硬件環(huán)境:PC機(jī)內(nèi)存 4G；硬盤500G2. 軟件環(huán)境：操作系統(tǒng)：windows104 開發(fā)工具和編程語言開發(fā)環(huán)境：CodeBlocks 、Dev C++編程語言：C語言5 詳細(xì)設(shè)計(jì)在概要設(shè)計(jì)的基礎(chǔ)上，對(duì)每個(gè)模塊進(jìn)行內(nèi)部邏輯處理部分詳細(xì)設(shè)計(jì)。下面分別列出各個(gè)模塊具體實(shí)現(xiàn)流程圖： 圖結(jié)構(gòu)的基本操作 觀察了數(shù)據(jù)對(duì)象后，我選擇用一個(gè)鄰接表用來存儲(chǔ)圖2信息，則數(shù)據(jù)結(jié)構(gòu)的基本操作也就確定了，分別為圖的添加、刪除、更新。 圖 2 模擬交通圖 和圖的基本操作相同，只是該城市每增加一個(gè)城市結(jié)點(diǎn)要在弧的鄰接點(diǎn)對(duì)應(yīng)的城市上也增加一條弧。 和圖的基本操作相同。 和圖的基本操作相同，只是該城市每刪除一個(gè)城市結(jié)點(diǎn)要在弧的鄰接點(diǎn)對(duì)應(yīng)的城市上也刪除那條弧。 在主函數(shù)的開始部分添加Read函數(shù)，在管理員修改模式添加Write函數(shù)。實(shí)現(xiàn)對(duì)圖結(jié)構(gòu)的讀取保存。 迪杰斯特拉算法的實(shí)現(xiàn) 把算法實(shí)現(xiàn)得到不僅僅是一系列數(shù)組，而是將這些數(shù)組的信息提煉成有用的信息輸出出來，將抽象的數(shù)據(jù)轉(zhuǎn)換為具象的信息。 迪杰斯特拉算法函數(shù) 定義了若干個(gè)全局輔助變量，如路徑矩陣P[][]和距離數(shù)組D[]，final用來標(biāo)記是否找到了點(diǎn)的最短路徑在函數(shù)的初始階段進(jìn)行對(duì)個(gè)輔助變量的初始化，第一趟把V0相鄰的路徑距離保存下來。選擇一個(gè)最小的用final記錄下來，記錄下最終的D和P值。再遍歷其他結(jié)點(diǎn)，如果出現(xiàn)新的路徑，且路徑小于最大值INFINITY，則保存路徑和距離以便下次比較。循環(huán)n1次得到V0到各結(jié)點(diǎn)的最短距離和路徑。 提取迪杰斯特拉函數(shù)信息 根據(jù)P函數(shù)與D函數(shù)，可以將V0到每個(gè)終點(diǎn)的經(jīng)過結(jié)點(diǎn)和最終路徑求出，利用Print函數(shù)打印出V0和V，再調(diào)用FindPath函數(shù)，打印經(jīng)過的結(jié)點(diǎn)。最后打印出距離，便可在屏幕上打印出單源最短路徑。 求多源最短路徑 對(duì)每個(gè)結(jié)點(diǎn)循環(huán)調(diào)用便可打印出每個(gè)結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短路徑，通過改變Print函數(shù)的形參，便可以求出兩點(diǎn)間的最短路徑。 6 程序編碼根據(jù)詳細(xì)設(shè)計(jì)轉(zhuǎn)化為如下代碼，下面列出部分代碼：includeinclu