大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告材料

1、洛陽(yáng)理工學(xué)院課程設(shè)計(jì)說明書課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)課題校園導(dǎo)游程序?qū)?業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)學(xué)號(hào)姓名完成日期課程設(shè)計(jì)任務(wù)書設(shè)計(jì)題目：校園導(dǎo)游程序設(shè)計(jì)內(nèi)容與要求：?jiǎn)栴}描述用無向網(wǎng)表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景 點(diǎn)，存放景點(diǎn)的編號(hào)、名稱、簡(jiǎn)介等信息，圖中的邊表示景點(diǎn)間的道路， 存放路徑長(zhǎng)度等信息。要求能夠回答有關(guān)景點(diǎn)介紹、游覽路徑等問題。 基本要求(1)查詢各景點(diǎn)的相關(guān)信息；(2)查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑。(3)查詢圖中任意兩個(gè)景點(diǎn)間的所有路徑。(4)增加、刪除、更新有關(guān)景點(diǎn)和道路的信息。指導(dǎo)教師：2016年12月20日課程設(shè)計(jì)評(píng)語(yǔ)成績(jī)：指導(dǎo)教師：年 月 日目錄1、

2、 問題描述 12、 基本要求 13、 測(cè)試數(shù)據(jù) 2四、算法思想 35、 模塊劃分 45.1.1 應(yīng)用函數(shù) 45.1.2 主函數(shù) 55.1.3 查詢景點(diǎn)信息函數(shù) 65.1.4 查詢兩景點(diǎn)之間最短路徑函數(shù) 65.1.5 查詢兩景點(diǎn)之間所有路徑函數(shù) 75.2.6 刪除已有的頂點(diǎn)和路徑 85.2.7 修改已有的頂點(diǎn)和路徑 96、 數(shù)據(jù)結(jié)構(gòu) 107、 測(cè)試 118、 心得 199、 源程序 20問題描述用無向網(wǎng)表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱、簡(jiǎn)介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長(zhǎng)度等信息。要求能夠回答有關(guān)景點(diǎn)介紹、游覽路徑等問題。二、 基本要求（1）

3、 查詢各景點(diǎn)的相關(guān)信息；（2） 查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑。（3） 查詢圖中任意兩個(gè)景點(diǎn)間的所有路徑。（4） 增加、刪除、更新有關(guān)景點(diǎn)和道路的信息。4三、 測(cè)試數(shù)據(jù)菜單函數(shù)：依次輸入：1， 2， 3， 4， 5， 6， 0分別對(duì)應(yīng)景點(diǎn)信息查詢，最短路徑查詢，所有路徑查詢，添加景點(diǎn)及路徑信息，刪除景點(diǎn)及路徑信息，修改景點(diǎn)及路徑信息，退出。查詢景點(diǎn)信息：輸入：1， 2分別對(duì)應(yīng)按編號(hào)查詢，按景點(diǎn)名稱查詢按編號(hào)查詢：輸入編號(hào)：1按景點(diǎn)名稱查詢：輸入名稱：大明橋最短路徑查詢：輸入起始景點(diǎn)和終點(diǎn)景點(diǎn)編號(hào)：1， 7所有路徑查詢：輸入起始景點(diǎn)和終點(diǎn)景點(diǎn)編號(hào)：2， 8添加景點(diǎn)及路徑信息：輸入新景點(diǎn)序號(hào)：9

4、輸入新景點(diǎn)名稱：南門輸入新景點(diǎn)相關(guān)信息：充滿古韻的門，適合拍照輸入到其余各景點(diǎn)的距離：50, 100, 20刪除景點(diǎn)及路徑信息：輸入：1， 2分別對(duì)應(yīng)按編號(hào)查詢，按景點(diǎn)名稱查詢按編號(hào)查詢：輸入需要?jiǎng)h除的景點(diǎn)編號(hào)：8修改景點(diǎn)及路徑信息：輸入：1， 2分別對(duì)應(yīng)修改景點(diǎn)信息，修改道路信息修改景點(diǎn)信息：輸入1， 2分別對(duì)應(yīng)修改景點(diǎn)名稱，修改景點(diǎn)描述修改景點(diǎn)信息：輸入修改序號(hào)：1輸入修改后的名稱：圖書館123四、算法思想先禾J用CreateUDN創(chuàng)建初始無向網(wǎng)，通過 main主函數(shù)調(diào)用顯示，操作功能 的選擇通過Menu函數(shù)輸出，根據(jù)游客需求選擇景點(diǎn)信息查詢、景點(diǎn)之間最短路 徑查詢、景點(diǎn)之間所有路徑查詢、

5、添加景點(diǎn)信息、刪除景點(diǎn)信息或者修改信息。 如果是景點(diǎn)信息查詢，在search中完成，再調(diào)用SearchMenu選擇是按照景點(diǎn)編號(hào)或者景點(diǎn)名稱查詢，游客輸入相應(yīng)內(nèi)容。如果是景點(diǎn)之間最短路徑查詢或是 景點(diǎn)之間所有路徑查詢則游 客輸入起 始景點(diǎn)和結(jié) 束景點(diǎn)；最短路徑 是用ShortestPath實(shí)現(xiàn)，其中運(yùn)用了迪杰斯特拉算法；所有路徑由Searchpathl調(diào)用disppath再調(diào)用path ,在path中通過遞歸算法實(shí)現(xiàn)尋找每一條路并輸出。 如果是添加景點(diǎn)信息調(diào)用 Addnewsight函數(shù)，游客按照提示依次輸入信息內(nèi)容。 如果是刪除景點(diǎn)信息，選擇按照名稱刪除或是按照序號(hào)刪除，再調(diào)用 Delete

6、sight 函數(shù)，游客輸入相應(yīng)內(nèi)容進(jìn)行刪除。如果是修改信息，調(diào)用 Changesight , ChangemenuW個(gè)函數(shù)，游客按提示選擇修改景點(diǎn)信息或者道路信 息，再按提示輸入修改后得內(nèi)容。輸出使用調(diào)用的相應(yīng)函數(shù)。信息保存于文件中。五、 模塊劃分5.1 應(yīng)用函數(shù)void CreateUDN(int v,int a);/*void narrate();/*void ShortestPath(int num);/*void output(int sight1,int sight2);/*int Menu();/*void search();/*int SearchMenu();/*void Ha

7、MiTonian(int);/*void Searchpath1(MGraph g);/*void disppath(MGraph g,int i,int j);void path(MGraph g,int i,int j,int k);/* void NextValue(int);void display();/*int Addnewsight(int n);/*int Deletesight();/*void Changesight();/*int Changemenu();/*int Sightmenu();/*造圖函數(shù)*/說明函數(shù)*/最短路徑函數(shù)*/輸出函數(shù)*/主菜單 */查詢景點(diǎn)信息

8、*/查詢子菜單*/圖的遍歷*/查詢兩個(gè)景點(diǎn)間的所有路徑*/確定路徑上第k+1 個(gè)頂點(diǎn)的序號(hào)*/顯示遍歷結(jié)果*/添加新的景點(diǎn)和路徑*/刪除景點(diǎn)和路徑*/修改景點(diǎn)和路徑*/修改路徑或頂點(diǎn)的選擇菜單*/選擇需該景點(diǎn)的菜單*/5.2.1主函數(shù)1 .功能：初始圖通過main主函數(shù)調(diào)用顯示，操作功能的選擇通過 Menu函數(shù)輸出, 顯示為菜單形式提醒用戶進(jìn)行操作，用戶選擇后在 main主函數(shù)中調(diào)用各個(gè)函數(shù) 實(shí)現(xiàn)各種功能。2 .流程圖：開始1T景點(diǎn)信息和操作目錄輸入相應(yīng)序號(hào)55.2.2查詢景點(diǎn)信息函數(shù)1 .功能：在main主函數(shù)中調(diào)用search,打開存儲(chǔ)了信息的文件，在顯示界面顯 示已有的景點(diǎn)名稱和序號(hào)，游

9、客按需求進(jìn)行序號(hào)查詢或者名稱查詢，輸入需要查 詢的序號(hào)或者名稱后會(huì)顯示該景點(diǎn)的名稱及簡(jiǎn)介，而后按任意鍵返回上級(jí)菜單選 擇繼續(xù)查詢或者返回主界面，在查詢景點(diǎn)信息函數(shù)中實(shí)現(xiàn)。2 .流程圖：按編號(hào)查詢按景點(diǎn)查詢沒有找到!5.2.3 查詢兩景點(diǎn)之間最短路徑函數(shù)1 .功能：在main函數(shù)中調(diào)用narrate函數(shù)，打開存儲(chǔ)了信息的文件，游客 輸入起點(diǎn)編號(hào)或者終點(diǎn)編號(hào)，利用迪杰斯特拉算法由ShortestPath最短路徑函 數(shù)選擇一條兩點(diǎn)之間的最短路徑展示給游客，關(guān)閉文件。5.2.4 查詢兩景點(diǎn)之間所有路徑函數(shù)1 .功能：當(dāng)游客輸入完畢后，根據(jù)之前構(gòu)建的無向圖，執(zhí)行過程為進(jìn)層和退 層兩個(gè)階段。首先開始遞歸進(jìn)

10、層，考慮使用基于深度優(yōu)先思想，在搜素過程中， 按照景點(diǎn)編號(hào)大小依次訪問每一個(gè)節(jié)點(diǎn)，若訪問到一個(gè)未被訪問且有路徑相通的 點(diǎn)則將其加入數(shù)組P,直到找到目的地，輸出第一條路徑，然后開始遞歸退層， 按照之前的方式遞歸訪問它的所有未被訪問的相鄰節(jié)點(diǎn)。并通過相應(yīng)的設(shè)置標(biāo)志visited口 的方式使最終能不重復(fù)地走遍所有的簡(jiǎn)單路徑。最后輸出這些路徑即 可。5.2.5 添加新的頂點(diǎn)和路徑1 .功能：在Addnewsight添加新的景點(diǎn)和路徑函數(shù) 中實(shí)現(xiàn)，打開存儲(chǔ)了信 息的文件，輸入需要新添加的景點(diǎn)名稱，基本信息介紹并依次輸入它到原有各景 點(diǎn)的距離，將新信息存儲(chǔ)到文件中并保存。75.2.6刪除已有的頂點(diǎn)和路徑1

11、 .功能：刪除不需要的景點(diǎn)信息，并保存刪除后的文件，方便下一次瀏覽2 .流程圖：9按 景 點(diǎn) 編 號(hào)按景點(diǎn)名稱沒有找到刪除成功結(jié)束5.2.7修改已有的頂點(diǎn)和路徑1 .功能：修改有誤的景點(diǎn)信息，并保存修改后的文件，方便下一次瀏覽2 .流程圖：11修改景點(diǎn)信息修改道路信息輸入景點(diǎn)編號(hào)2 ZZ輸入道路信息相鄰接的景點(diǎn)之間的路程*/定義邊的類型*/景點(diǎn)編號(hào)*/景點(diǎn)名稱*/景點(diǎn)描述*/定義頂點(diǎn)的類型*/typedef structVertexType vex20;ArcCell arcs2020; /* int vexnum,arcnum;MGraph;六、 數(shù)據(jù)結(jié)構(gòu)MGraph義圖的類型，其中包含景點(diǎn)

12、，景點(diǎn)之間的距離，景點(diǎn)數(shù)和邊數(shù) VertexType 是景點(diǎn)的結(jié)構(gòu)體，里面包含了景點(diǎn)編號(hào)，景點(diǎn)名稱，景點(diǎn)描述。ArcCell 是邊的結(jié)構(gòu)體，其中包含了邊的長(zhǎng)度即景點(diǎn)之間的距離。typedef struct ArcCellint adj;/*ArcCell;/*typedef struct VertexTypeint number;/*char sight100;/*char description1000;/*VertexType;/*/*圖中的頂點(diǎn)，即為景點(diǎn)*/圖中的邊，即為景點(diǎn)間的距離*/*頂點(diǎn)數(shù)，邊數(shù)*/*定義圖的類型*/41七、測(cè)試7.1. 測(cè)試數(shù)據(jù)輸入：根據(jù)游客需求選擇景點(diǎn)信息查詢、

13、景點(diǎn)之間最短路徑查詢、景點(diǎn)之間 所有路徑查詢、添加景點(diǎn)信息、刪除景點(diǎn)信息或者修改信息。如果是景點(diǎn)信息查 詢，再選擇是按照景點(diǎn)編號(hào)或者景點(diǎn)名稱查詢，游客輸入相應(yīng)內(nèi)容；如果是景點(diǎn)之間最短路徑查詢或是景點(diǎn)之間所有路徑查詢則游客輸入起始景點(diǎn)和結(jié)束景點(diǎn)； 如果是添加景點(diǎn)信息則按照提示依次輸入信息內(nèi)容；如果是刪除景點(diǎn)信息，選擇按照名稱刪除或是按照序號(hào)刪除，再輸入相應(yīng)內(nèi)容進(jìn)行刪除；如果是修改信息， 按提示選擇修改景點(diǎn)信息或者道路信息，再按提示輸入修改后得內(nèi)容預(yù)期的輸出結(jié)果：運(yùn)行程序直接出現(xiàn)各景點(diǎn)及其編號(hào)，同時(shí)出現(xiàn)操作菜單， 其他結(jié)果依使用者需求而定，請(qǐng)參見程序后的運(yùn)行結(jié)果。1 .菜單函數(shù)特*歡迎使用格口理工

14、學(xué)院開兀校區(qū)校園導(dǎo)游程序*匚n匚房所聿. 息點(diǎn)In.點(diǎn)占；.尋詈京 占宜曾的有有 景兩兩酉已 詢?cè)冊(cè)冺靛?普查查% ， 粕、 1234560請(qǐng)輸入您的選擇:2 .查詢景點(diǎn)信息（按編號(hào)）* *水* *冰*歡迎使用洛陽(yáng)理工學(xué)阮開兀校區(qū)校園導(dǎo)游程序*杭* * 千黎驗(yàn)驗(yàn)院院 大圖教主實(shí)實(shí)裳 ,I，、>/ / !/ !/ !/ 11；. J. 012345678請(qǐng)輸入您要查找的景點(diǎn)編號(hào)：1您要查找景點(diǎn)信息如下：圖書館：環(huán)境優(yōu)雅，充滿書香氣息呈環(huán)形按任意鍵返回.3 .查詢景點(diǎn)信息（按名稱）*宓*京*配*歡迎 使用洛陽(yáng)理工學(xué) 院開元校 區(qū)校園導(dǎo)游程 序*一一z7 012345679§i 請(qǐng)輸

15、入您要查找的景點(diǎn)名稱：大明橋您要查找景點(diǎn)信息如下：大明橋:落于小河上，風(fēng)景優(yōu)美4 .查詢兩景點(diǎn)之間的最短路徑*歡迎使用洛陽(yáng)理工學(xué)院開元校區(qū)校園導(dǎo)湍程序外*¥*景點(diǎn)名稱主R圭DE012345678g1T,¥ss點(diǎn)點(diǎn)早量成點(diǎn)點(diǎn)起終¥x.J、：.-選選從圖書館到璞院餐廳的最短路徑是（最短距離為330nc） 圖書館一 實(shí)驗(yàn)A樓一璞院督廳請(qǐng)按任意鍵繼續(xù)一.5.查詢兩點(diǎn)之間的所有路徑錯(cuò)髓盒I攵學(xué)樓到瓚院餐廳的所有游覽品胭有：學(xué)亶雪院院 致子AH王簽一17 XJr 012345678院明> > > > > 一 一一 亍 ttJT-JT-甲缸 香-&

16、#171;-.嘲答卷兀 璞子子 Ig-s-k*堂坊護(hù)Bf眇,眇B(yǎng)f餐樓嘴樓嘍樓褸 a孟SS孟孟子 ,TPIP 二工JP-M二£三 IFJSSB1234566.添加新的景點(diǎn)及其路徑添加過程4 C:UsersG ¥ XDesktQpnpLexe*東*歡迎使用落陽(yáng)理院開兀校區(qū)校園導(dǎo)三方程序*木*水水水IZH明小學(xué)靠驗(yàn)驗(yàn)院院大圖教rH頭實(shí)實(shí)最012345678ABC行褸褸褸一JTJf展輸入新景點(diǎn)的序號(hào)'so1曾呼入新景點(diǎn)的名稱 童年入新景點(diǎn)的木 龍曙古矗的門，:“請(qǐng)輸入此景點(diǎn)到第。個(gè)景點(diǎn)的距離（單位=Q （同一景點(diǎn)或不可到達(dá)用2QQ00表示,極大值）, 50添加后*歡迎使用

17、洛B日理工學(xué)院開兀校區(qū)校園導(dǎo)游程序杼杼*景點(diǎn)名稱口口口口 事于嘉驗(yàn)驗(yàn)院國(guó) 畜教PH頭實(shí)實(shí) 0123456789 /k fk zk fk rv/k/k zk 8US短日或 息點(diǎn)點(diǎn) 每位篁量壹區(qū) 點(diǎn)豆量0?的有有 景BW新已已 詢?cè)冊(cè)兗?查查查添、工X% 、 1224560請(qǐng)輸入您的選擇:7 .刪除景點(diǎn) 刪除過程*冰*本歡迎使用1：3陽(yáng)理工學(xué)院開元校區(qū)校園導(dǎo)游程序*林*歡迎使用洛陽(yáng)理工學(xué)院開元校區(qū)校園導(dǎo)游程序* * *(mtABC噓驗(yàn)償 嗇教主實(shí)實(shí)鬟Ylzulz-XJk)/ 012345678請(qǐng)輸入您要?jiǎng)h除景點(diǎn)的編號(hào)：8刪除成功！按任意鍵返回.一刪除后1路 日或 息點(diǎn)點(diǎn)點(diǎn) 141點(diǎn)星壹蒿 點(diǎn)豆量早

18、的春 景兩兩新已已 詢?cè)冊(cè)兗?查杳香_添® 、，、 12 3 4 5 6 0請(qǐng)輸入您的選擇:8 .修改景點(diǎn)信息*歡迎使用 洛 陽(yáng)理工學(xué)院開兀校區(qū)校園導(dǎo)游程序*海強(qiáng)人修改后的景點(diǎn)名機(jī) 圖書館123驗(yàn)驗(yàn)悍 大圖教子其實(shí)實(shí)璞南 0 12345679/fx fl-yx-(-/1請(qǐng)輸入您的選擇：1修改成功!修改后*/：.：.：.：*：*歡迎使用洛陽(yáng)理工學(xué)院開元校區(qū)校園導(dǎo)游程序*：*籥臉驗(yàn)博 而圖教主頭實(shí)mSMSI/ XJr Y/ 012345679nnnn34-n-息用點(diǎn)點(diǎn)點(diǎn) 省堂置量早 占宜£早的WP =克兩翳已已 詢?cè)冊(cè)兗?查查查12 3 4 5 6 0請(qǐng)輸入您的選擇:9 .文件

19、內(nèi)容 n T . r 文件的編4(E)梢式(0)查看的幫助(H)落于小河上，風(fēng)景優(yōu)美 暴期鬻嚶行書香氣息，呈環(huán)形課和自習(xí)的地方，臨近圖書館 子衿餐五一餐廳，薪裝修過的餐廳，臨近實(shí)驗(yàn)樓，是男女比例最適中的餐廳 t實(shí)燧樓 老師辦公室 實(shí)驗(yàn)B樓計(jì)算機(jī)機(jī)房矗矗樓聶二祟儒男生宿舍，食物種類比較多 另三第寓女生宿舍樓，比較便宜-I count -記事本文件舊編瑁(E) 格式Q)查看凹幫助(H)9八、 心得通過對(duì)這次對(duì)校園導(dǎo)游系統(tǒng)程序編寫，我切實(shí)體會(huì)到了如何編寫一個(gè)較大的程序。 這是我自己相對(duì)獨(dú)立做的最大的一個(gè)程序，過程中遇到了各種各樣的問題。但同時(shí)鞏固了課堂上所學(xué)的知識(shí)，也學(xué)到了很多新的東西，也收獲了很多

20、。拿到題目，第一步就是構(gòu)思，分析，創(chuàng)建。題目要求用無向網(wǎng)完成，所以我考慮的是用鄰接矩陣存儲(chǔ)這個(gè)無向網(wǎng)，參考了書上的無向網(wǎng)的鄰接矩陣存儲(chǔ)程序?qū)懥薈reatUDN。查詢兩個(gè)景點(diǎn)之間的最短路徑剛開始我參考的是書上的迪杰斯特拉算法，后來發(fā)現(xiàn)書上定義的頂點(diǎn)的結(jié)構(gòu)體數(shù)組內(nèi)容太簡(jiǎn)單，程序考慮的情況也很簡(jiǎn)單，無法滿足我題目的需求，于是我又把迪杰斯特拉算法研讀了一遍，自己做了改進(jìn)。查找所有路徑的Searchpath1 函數(shù)剛開始一直沒有寫出來，我和同學(xué)先在紙上畫出頂點(diǎn)，參考深度優(yōu)先遍歷把整個(gè)路徑走了一遍，但是編程沒有什么思路，上網(wǎng)查找了關(guān)于這個(gè)算法的資料，看到有人說可以考慮用遞歸實(shí)現(xiàn)，就試著用遞歸實(shí)現(xiàn)， 同時(shí)參

21、照迪杰斯特拉算法用一個(gè)數(shù)組收集訪問過的頂點(diǎn)，還設(shè)置了一個(gè)標(biāo)志量標(biāo)記頂點(diǎn)是否被訪問。文件在上學(xué)期的課設(shè)中我寫過，當(dāng)時(shí)學(xué)習(xí)了一些關(guān)于文件的知識(shí)，所以運(yùn)用并沒有遇到太多問題，利用文件保存數(shù)據(jù)，需要 fopen 打開文件進(jìn)行讀寫，還要fclose函數(shù)進(jìn)行關(guān)閉操作，可能還會(huì)用到 fread讀取文件。后來知道a+可以繼 續(xù)錄入，于是我通過加入一個(gè) a+形式的語(yǔ)句，實(shí)現(xiàn)了可不定時(shí)地增加景點(diǎn)數(shù)據(jù) 的功能所有框架寫查找、刪除、修改和添加函數(shù)本身并不太難，寫好以后用main函數(shù)調(diào)用可以了。寫出框架后，剛開始運(yùn)行也是沒什么問題的，但是多做幾步就遇到了問題。在添加的時(shí)候，剛開始沒有考慮序號(hào)，程序自動(dòng)生成的序號(hào)和我想。

22、要的并不是一種， 于是我在添加景點(diǎn)里面讓游客自己輸入序號(hào)。后來又發(fā)現(xiàn)刪除沒有考慮找不到需要?jiǎng)h除的目標(biāo)的可能性，用一個(gè)判斷符a 來判斷是否刪除成功。接下來整個(gè)運(yùn)行都沒有錯(cuò)但是如果刪除兩個(gè)景點(diǎn)就會(huì)出現(xiàn)問題了，試了很久發(fā)現(xiàn)是循環(huán)條件有問題，雖然固定了景點(diǎn)編號(hào) number,但是循環(huán)的numffi number不能對(duì)應(yīng)，于是去詢問老師，老師說可以把整個(gè)鄰接矩陣重新修改或者設(shè)置特殊符號(hào)控制輸出，我選擇了相對(duì)簡(jiǎn)便的修改方法。這個(gè)程序很長(zhǎng)，編寫花了很多時(shí)間，在程序編寫過程中，我不斷遇到困難，調(diào)試時(shí)更是出現(xiàn)了很多問題，一個(gè)個(gè)的修改，有的花了很長(zhǎng)的時(shí)間。但我的努力和辛苦沒有白費(fèi)，在老師的指導(dǎo)，同學(xué)的幫助，和自己

23、的努力下我終于完成了這個(gè)程序。 很感謝老師最后的點(diǎn)睛之筆，在我和同學(xué)冥思苦想很長(zhǎng)時(shí)間都沒有解決方案的時(shí)候是老師幫助我們解決了問題。同時(shí)也反映出我思考問題的不全面和經(jīng)驗(yàn)的欠缺。在程序編寫和解決問題時(shí)，每一個(gè)細(xì)節(jié)都很重要，既要避免功能的重復(fù)也要避免功能疏漏的地方。理論和實(shí)踐相結(jié)合是學(xué)好數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵，這次的課設(shè)既培養(yǎng)了我們的自學(xué)能力，也提高了我們的學(xué)習(xí)興趣。九、 源程序#include <string.h>#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define Max 20000

24、typedef struct ArcCell相鄰接的景點(diǎn)之間的路程*/定義邊的類型*/int adj;/*ArcCell;/*typedef structVertexType vex20;/*ArcCell arcs2020;/*int vexnum,arcnum;/*MGraph;/*FILE *fp,*count ;/*用于指向file 類型 */MGraph G;/*char nameofschool100;/*int NUM=9;int P2020;/*int p20;/*int visited20;/*/int a=0;/*路徑的條數(shù)*/long int D20;/*圖中的頂點(diǎn)，即為

25、景點(diǎn)*/圖中的邊，即為景點(diǎn)間的距離*/頂點(diǎn)數(shù)，邊數(shù)*/定義圖的類型*/變量類型聲明，聲明fp 是 FILE 型指針，把圖定義為全局變量*/學(xué)校名稱*/用來存放圖中的邊*/全局?jǐn)?shù)組，用來存放路徑上的各頂點(diǎn)*/全局?jǐn)?shù)組，用來記錄各頂點(diǎn)被訪問的情況全局變量，用來記錄每對(duì)頂點(diǎn)之間的所有輔助變量存儲(chǔ)最短路徑長(zhǎng)度*/void CreateUDN(int v,int a);/*void narrate();/*造圖函數(shù)*/說明函數(shù)*/typedef struct VertexType int number;/*景點(diǎn)編號(hào)*/char sight100;/*景點(diǎn)名稱*/char description1000;

26、/*景點(diǎn)描述*/VertexType;/*定義頂點(diǎn)的類型*/void ShortestPath(int num);/*void output(int sight1,int sight2);/*int Menu();/*void search();/*int SearchMenu();/*void HaMiTonian(int);/*void Searchpath1(MGraph g);/*void disppath(MGraph g,int i,int j);void path(MGraph g,int i,int j,int k); /* void NextValue(int); void

27、display();int Addnewsight(int n); int Deletesight();void Changesight(); int Changemenu(); int Sightmenu();void main() int v0,v1; int ck;CreateUDN(NUM,11); do ck=Menu(); switch(ck) case 1: search(); break; case 2: system("cls"); narrate(); printf("nnttt scanf("%d",&v0); p

28、rintf("ttt scanf("%d",&v1); ShortestPath(v0); output(v0,v1); printf("nntttt getchar(); getchar();break;/*/*/*/*/*/*/*最短路徑函數(shù)*/輸出函數(shù)*/主菜單 */查詢景點(diǎn)信息*/查詢子菜單*/圖的遍歷*/查詢兩個(gè)景點(diǎn)間的所有路徑*/確定路徑上第k+1 個(gè)頂點(diǎn)的序號(hào)*/顯示遍歷結(jié)果*/添加新的景點(diǎn)和路徑*/刪除景點(diǎn)和路徑*/修改景點(diǎn)和路徑*/修改路徑或頂點(diǎn)的選擇菜單*/選擇需該景點(diǎn)的菜單*/主函數(shù) */請(qǐng)選擇起點(diǎn)景點(diǎn)（。%。： "

29、;,NUM-1）;請(qǐng)選擇終點(diǎn)景點(diǎn)（0%d）: ",NUM-1）;/*計(jì)算兩個(gè)景點(diǎn)之間的最短路徑*/*輸出結(jié)果*/請(qǐng)按任意鍵繼續(xù).n"）;system("cls");narrate();Searchpath1(G);printf("nntttt請(qǐng)按任意鍵繼續(xù).n");getchar();getchar();break;case 3:system("cls");narrate();NUM=Addnewsight(NUM);system("cls");narrate();break;case 4:NU

30、M=Deletesight();break;case 5:Changesight();break;while(ck!=0);int Menu()/*主菜單 */int c;int flag;doflag=1;system("cls");narrate();printf("nttt n")；printf("ttt11 n")；printf("tttI 1、查詢景點(diǎn)信息1 n")；printf("tttI 2、查詢兩景點(diǎn)間最短路徑1 n")；printf("tttI 3、查詢兩景點(diǎn)間所有路

31、線1 n")；printf("tttI 4、添加新的景點(diǎn)和路徑1 n")；printf("tttI 5、刪除已有景點(diǎn)和路徑1 n")；printf("tttI 6、修改已有景點(diǎn)或路徑1 n")；printf("tttI 0、退出1 n")；printf("ttt11 n")；printf("ttt11n");printf("tttt請(qǐng)輸入您的選擇：");scanf("%d",&c);if(c=1|c=2|c=3|c=4

32、|c=5|c=6|c=0)flag=0;while(flag);return c;int SearchMenu()/*int c;int flag;doflag=1;system("cls");查詢子菜單函數(shù)*/printf("nttti n");printf("ttt11 n");printf("ttt11、按照景點(diǎn)編號(hào)查詢I n");printf("ttt12、按照景點(diǎn)名稱查詢I n");printf("ttt0、返回n");printf("ttt11 n&qu

33、ot;);printf("ttt11n");narrate();printf("tttt請(qǐng)輸入您的選擇：");scanf("%d",&c);if(c=1|c=2|c=0)flag=0;while(flag);return c;void search()/*int num;int i; int c; char name20;fp=fopen("guide.txt","r+");/*count=fopen("count.txt","r+");/*do

34、system("cls"); c=SearchMenu();查詢景點(diǎn)信息函數(shù)*/讀打開原文件book.txt*/ 讀寫count文件*/switch (c)case 1:system("cls");narrate();printf("nntt請(qǐng)輸入您要查找的景點(diǎn)編號(hào)：");scanf("%d",&num);for(i=0;i<NUM;i+)if(num=G.vexi.number)printf("nnttt您要查找景點(diǎn)信息如下:");printf("nnttt%s: %-

35、25snn",G.vexi.sight,G.vexi.description);printf("nttt按任意鍵返回.");getchar();getchar();break;if(i=NUM)printf("nnttt沒有找到！");printf("nnttt按任意鍵返回.");getchar();getchar();break;case 2:system("cls");narrate();printf("nntt請(qǐng)輸入您要查找的景點(diǎn)名稱：");scanf("%s"

36、;,name);for(i=0;i<NUM;i+)if(!strcmp(name,G.vexi.sight)printf("nnttt您要查找景點(diǎn)信息如下:");printf("nnttt%s:%-25snn",G.vexi.sight,G.vexi.description);printf("nttt按任意鍵返回.");getchar();getchar();break;if(i=NUM)printf("nnttt沒有找到！");printf("nnttt按任意鍵返回.");getchar

37、();getchar();break;while(c!=0);fwrite(&G,sizeof(MGraph),1,fp); /*保存到文件中*/fclose(fp);fprintf(count,"%d",NUM);fclose(count);void CreateUDN(int v,int a)/*int i,j;if(fp=fopen("guide.txt","a+")=NULL) /ticket 文件保存記錄的詳細(xì)信息printf(" 文件未找到n");if(count=fopen("cou

38、nt.txt","w+ ")=NULL) /countfprintf(count,"0");創(chuàng)建初始圖函數(shù)*/調(diào)用了 fopen, 要用 fclose 關(guān)閉文件保存記錄的條數(shù)elsefscanf(count,"%d",&NUM);strcpy(nameofschool," 洛陽(yáng)理工學(xué)院開元校區(qū)");G.vexnum=v;/*數(shù) */G.arcnum=a;for(i=0;i<20;+i) G.vexi.number=i; /*/初始化結(jié)構(gòu)中的景點(diǎn)數(shù)和邊初始化每一個(gè)景點(diǎn)的編號(hào)/* 初始化每一個(gè)景

39、點(diǎn)名及其景點(diǎn)描述*/strcpy（G.vex0.sight," 大明橋 "）;strcpy（G.vex0.description," 落于小河上，風(fēng)景優(yōu)美"）;strcpy(G.vex1.sight," strcpy(G.vex1.description," strcpy(G.vex2.sight," strcpy(G.vex2.description," strcpy(G.vex3.sight," strcpy(G.vex3.description," ");strcpy(G.vex

40、4.sight," strcpy(G.vex4.description," strcpy(G.vex5.sight," strcpy(G.vex5.description," strcpy(G.vex6.sight," strcpy(G.vex6.description," strcpy(G.vex7.sight," strcpy(G.vex7.description," strcpy(G.vex8.sight,"strcpy(G.vex8.description," /* 這里把所有的邊假定為

41、圖書館");環(huán)境優(yōu)雅，充滿書香氣息，呈環(huán)形");教學(xué)樓");上課和自習(xí)的地方, 臨近圖書館");子衿餐廳");一餐廳，新裝修過的餐廳，臨近實(shí)驗(yàn)樓，實(shí)驗(yàn)A樓)老師辦公室");實(shí)驗(yàn) B 樓 ");計(jì)算機(jī)機(jī)房");實(shí)驗(yàn)C樓)電氣實(shí)驗(yàn)樓");璞院餐廳");第二餐廳，臨近男生宿舍，食物種類比較多琇院餐廳");20000，含義是這兩個(gè)景點(diǎn)之間是不可到達(dá)是男女比例最適");第三餐廳，臨近女生宿舍樓，比較便宜");, 極大值 */for(i=0;i<20;+i)for(j=0

42、;j<20;+j)G.arcsij.adj=Max;/*下邊是可直接到達(dá)的景點(diǎn)間的距離，由于兩個(gè)景點(diǎn)間距離是互相的，所以要對(duì)圖中對(duì)稱的邊同時(shí)賦值。*/G.arcs01.adj=G.arcs10.adj=50;G.arcs13.adj=G.arcs31.adj=70;G.arcs06.adj=G.arcs60.adj=250;G.arcs14.adj=G.arcs41.adj=80;G.arcs24.adj=G.arcs42.adj=100;G.arcs35.adj=G.arcs53.adj=90;G.arcs52.adj=G.arcs25.adj=100;G.arcs46.adj=G.a

43、rcs64.adj=75;G.arcs47.adj=G.arcs74.adj=300;G.arcs27.adj=G.arcs72.adj=400;G.arcs78.adj=G.arcs87.adj=40;fwrite(&G,sizeof(MGraph),1,fp); /保存到文件中fclose(fp); /關(guān)閉文件, 但不是屏幕fprintf(count,"%d",NUM);fclose(count);void narrate() /* 說明函數(shù)*/ int i;printf("nt*歡 迎 使 用 %s 校 園 導(dǎo) 游 程 序*n",nameo

44、fschool);printf("tn"); printf("tttt景點(diǎn)名稱ttttttn");printf("tttn");for(i=0;i<NUM;i+)if(G.vexi.number!=-1) printf("tttt%c(%2d)%-10s%cn",3,G.vexi.number,G.vexi.sight,3);/* 輸出景點(diǎn)列表*/ printf("tttn");void ShortestPath(int num) /*點(diǎn)的編號(hào)*/int v,w,i,t;/* iint f

45、inal20;/*int min;fp=fopen("guide.txt","r+"); /count=fopen("count.txt","r+"); /迪杰斯特拉算法最短路徑函數(shù)num 為入口、w和v為計(jì)數(shù)輔助變量*/輔助數(shù)組*/讀打開原文件book.txt讀寫 count 文件for(v=0;v<NUM;v+)finalv=0; /*Dv=G.arcsnumv.adj;/*for(w=0;w<NUM;w+) /*假設(shè)從頂點(diǎn)num到頂點(diǎn)v沒有最短路徑*/將與之相關(guān)的權(quán)值放入D中存放*/設(shè)置為空路徑*

46、/Pvw=0;if(Dv<20000) /* 存在路徑*/Pvnum=1; /* 存在標(biāo)志置為1 */Pvv=1; /* 自身到自身*/Dnum=0;finalnum=1; /*初始化num頂點(diǎn)屬于S集合*/* 開始主循環(huán)，每一次求得num到某個(gè)頂點(diǎn)的最短路徑，并將其加入到S集合*/for(i=0;i<NUM;+i) /*其余 G.vexnum-1 個(gè)頂點(diǎn) */min=Max; /*當(dāng)前所知離頂點(diǎn) num的最近距離*/for(w=0;w<NUM;+w) if(!finalw) /* w if(Dw<min) /* w v=w;min=Dw;finalv=1; /*頂點(diǎn)在

47、 v-s 中 */頂點(diǎn)離num頂點(diǎn)更近*/離num頂點(diǎn)更近的v加入到s集合*/for(w=0;w<NUM;+w) /* 更新當(dāng)前最短路徑極其距離*/保存到文件中不在 s 集合， 并且比以前所找到if(!finalw&&(min+G.arcsvw.adj)<Dw)/*/Dw=min+G.arcsvw.adj;for(t=0;t<NUM;t+)Pwt=Pvt;Pww=1;fwrite(&G,sizeof(MGraph),1,fp); / fclose(fp);fprintf(count,"%d",NUM); fclose(count);

48、void output(int sight1,int sight2) /*輸出函數(shù)*/int a,b,c,d,q=0;a=sight2; /* 將景點(diǎn)二賦值給a */if(a!=sight1) /*如果景點(diǎn)二不和景點(diǎn)一輸入重合，則進(jìn)行. */printf("nt從 %s 到 %s 的 最 短 路 徑 是",G.vexsight1.sight,G.vexsight2.sight);/*輸出提示信息*/printf("t(最短距離為%dm.)nnt",Da); /*輸出 sight1 到 sight2 的最短路徑長(zhǎng)度，存放在D 數(shù)組中 */printf(&q

49、uot;t%s",G.vexsight1.sight); /*輸出景點(diǎn)一的名稱*/d=sight1; /*將景點(diǎn)一的編號(hào)賦值給d */for(c=0;c<NUM;+c) gate:; /*標(biāo)號(hào)，可以作為goto 語(yǔ)句跳轉(zhuǎn)的位置*/Pasight1=0;for(b=0;b<NUM;b+) if(G.arcsdb.adj<20000&&Pab) /*如果景點(diǎn)一和它的一個(gè)臨界點(diǎn)之間存在路徑且最短路徑*/printf("->%s",G.vexb.sight); /*輸出此節(jié)點(diǎn)的名稱*/q=q+1;/*計(jì)數(shù)變量加一，滿8 控制輸出時(shí)的

50、換行*/Pab=0; d=b; /*將 b 作為出發(fā)點(diǎn)進(jìn)行下一次循環(huán)輸出，如此反復(fù)*/if(q%8=0) printf("n"); goto gate; /*從當(dāng)前位置出發(fā)*/ void Searchpath1(MGraph g)/* 查詢兩個(gè)景點(diǎn)間的所有路徑*/int l=0;int k=0;int i,j;fp=fopen("guide.txt","r+");/讀打開原文件book.txtcount=fopen("count.txt","r+");/讀寫 count 文件printf(&qu

51、ot;選擇出發(fā)景點(diǎn)：");scanf("%d",&i); printf("選擇目地景點(diǎn)：");scanf("%d",&j); for(;k<g.vexnum;k+)/*g.vexnumber 表示網(wǎng)中的頂點(diǎn)個(gè)數(shù)*/if(i=g.vexk.number) i=k;/* 在網(wǎng)中找到其編號(hào)與輸入的出發(fā)景點(diǎn)的編號(hào)相同的頂點(diǎn)*/for(;l<g.vexnum;l+) if(j=g.vexl.number) j=l;/* 在網(wǎng)中找到其編號(hào)與輸入的目地景點(diǎn)的編號(hào)相同的頂點(diǎn)*/ printf("n 從

52、%s 到 %s 的 所 有 游 覽 路 徑 有 :nn",g.vexi.sight,g.vexj.sight);/*輸出出發(fā)景點(diǎn)和目地景點(diǎn)的名稱*/disppath(g,i,j);/* 調(diào)用 disppath 函數(shù) , 用來輸出兩個(gè)景點(diǎn)間的所有路徑*/fwrite(&G,sizeof(MGraph),1,fp); /保存到文件中fclose(fp); fprintf(count,"%d",NUM); fclose(count); void disppath(MGraph g,int i,int j)int k;p0=i;/ 把i賦2P0 , P是一條道路上

53、的所有景點(diǎn)的數(shù)組for(k=0;k<g.vexnum;k+)visitedi=0;/* 初始化各頂點(diǎn)的訪問標(biāo)志位，即都為未訪問過的*/a=0;/* 初始化路徑的條數(shù)*/path(g,i,j,0);/* 通過調(diào)用path 函數(shù)，找到從vi 到 vj 的所有路徑并輸出*/ void path(MGraph g,int i,int j,int k)/* 確定路徑上第k+1 個(gè)頂點(diǎn)的序號(hào)*/int s;if(pk=j)/* 找到一條路徑*/a+;/* 路徑的條數(shù)值加1*/printf("第 條:t",a);for(s=0;s<=k-1;s+) /* 輸出一條路徑,s 是頂點(diǎn)