校園導(dǎo)游系統(tǒng)02550

1、課 程 設(shè) 計(jì) 說 明 書 課程名稱： 數(shù)據(jù)結(jié)構(gòu)與算法 設(shè)計(jì)題目： 校園導(dǎo)游系統(tǒng) 院 系： 計(jì)算機(jī)科學(xué)與信息工程學(xué)院 學(xué)生姓名： 學(xué) 號(hào)： 專業(yè)班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)信息技術(shù)方向11-1 指導(dǎo)教師： 2013年6月21日課 程 設(shè) 計(jì) 任 務(wù) 書設(shè)計(jì)題目校園導(dǎo)游系統(tǒng)學(xué)生姓名孫瑋所在院系計(jì)算機(jī)科學(xué)與信息工程學(xué)院專業(yè)、年級(jí)、班11計(jì)科信息技術(shù)方向設(shè)計(jì)要求： 用無向網(wǎng)表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱、簡介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長度等信息。要求能夠回答有關(guān)景點(diǎn)介紹、游覽路徑等問題學(xué)生應(yīng)完成的工作：孫 瑋 圖的結(jié)構(gòu)以及初始化徐開放 一個(gè)景點(diǎn)到

2、其他所有景點(diǎn)的最短路徑王彩霞 景點(diǎn)的輸出以及查詢梁夢莉 兩個(gè)景點(diǎn)之間的所有路徑何冉冉 兩個(gè)景點(diǎn)之間的最短路徑鄭銀鳳 增加，刪除，修改景點(diǎn)信息參考文獻(xiàn)閱讀：1.數(shù)據(jù)結(jié)構(gòu)(C語言版) 嚴(yán)蔚敏 吳偉民 編著 清華大學(xué)出版社 20112.C程序設(shè)計(jì)（第四版）譚浩強(qiáng) 主編 清華大學(xué)出版工作計(jì)劃： 1、第一周的第一天：小組布置設(shè)計(jì)題目；說明進(jìn)度安排。2、第一周的第二天：小組審題，查閱資料，進(jìn)行設(shè)計(jì)前的必要資料準(zhǔn)備。3、第一周的第三天、第四天、第五天：程序編寫、上機(jī)調(diào)試4、第二周的第一天至第三天： 上機(jī)調(diào)試程序、結(jié)果分析。5、第二周的第四天： 撰寫設(shè)計(jì)報(bào)告。6、第二周的第五天： 設(shè)計(jì)答辯及成績評(píng)定。 任務(wù)下

3、達(dá)日期： 2013年 6月 10 日 任務(wù)完成日期： 2013年 6月 21 日指導(dǎo)教師（簽名）： 學(xué)生（簽名）： 校園導(dǎo)游系統(tǒng)摘 要：隨著社會(huì)經(jīng)濟(jì)的發(fā)展，人們接近自然的機(jī)會(huì)就越多，因此外出旅游現(xiàn)在被越來越多的都市人所看中，所以如何快速方便的找到我們想要的旅游景點(diǎn)的信息和最短路徑，如何簡單的修改相關(guān)的信息，就成了很重要的問題。本設(shè)計(jì)基于圖的結(jié)構(gòu)，用數(shù)組表示法創(chuàng)建一個(gè)無向圖，針對游客的實(shí)際需求，將安陽工學(xué)院的景點(diǎn)編號(hào)、名稱、介紹等信息放入到圖的頂點(diǎn)當(dāng)中，將路徑長度的信息存放在弧當(dāng)中。利用弗洛伊德算法求出兩個(gè)景點(diǎn)之間的最短路徑，利用迪杰斯特拉算法來求從一個(gè)景點(diǎn)到其他剩余的所有景點(diǎn)的最短距離；用相應(yīng)

4、的函數(shù)來查找景點(diǎn)，并顯示出它的編號(hào)，信息，簡介。并進(jìn)行一定的界面美化，更貼近用戶，相應(yīng)的提示使用戶操作起來更容易。關(guān)鍵詞：最短路徑、查找景點(diǎn)信息、無向圖目 錄1. 設(shè)計(jì)背景41.1程序設(shè)計(jì)內(nèi)容41.2程序設(shè)計(jì)要求42設(shè)計(jì)方案52.1 校園景點(diǎn)圖52.2 程序模塊圖52.3 主函數(shù)設(shè)計(jì)簡要62.4 各函數(shù)模塊的功能63. 方案實(shí)施73.1 程序執(zhí)行流程圖73.2 主函數(shù)設(shè)計(jì)思想74. 結(jié)果測試94.1 主函數(shù)功能模塊測試94.2 主函數(shù)功能測試94.3 各功能所執(zhí)行的操作125. 結(jié)論136. 收獲與致謝147. 參考文獻(xiàn)148. 附件141. 設(shè)計(jì)背景1.1程序設(shè)計(jì)內(nèi)容根據(jù)設(shè)計(jì)要求，利用無向圖

5、將學(xué)校的景點(diǎn)作為圖的頂點(diǎn)，頂點(diǎn)的邊作為景點(diǎn)之間的距離進(jìn)行存儲(chǔ)，根據(jù)游客的需求，查找各個(gè)景點(diǎn)的信息，找出兩個(gè)景點(diǎn)的最短路徑，實(shí)現(xiàn)校園的導(dǎo)游目的。1.2程序設(shè)計(jì)要求用無向網(wǎng)表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱、簡介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長度等信息。要求能夠回答有關(guān)景點(diǎn)介紹、游覽路徑等問題。1、 景點(diǎn)信息和路徑信息保存在文本文件，景點(diǎn)個(gè)數(shù)不少于20個(gè)2、 查詢各景點(diǎn)的相關(guān)信息；3、 查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑。4、 查詢圖中任意兩個(gè)景點(diǎn)間的所有路徑。5、 增加、刪除、更新有關(guān)景點(diǎn)和道路的信息。6、 求多個(gè)景點(diǎn)的最佳（最短）游覽路徑。2設(shè)

6、計(jì)方案2.1 景點(diǎn)抽象圖校園景點(diǎn)抽象圖比較直觀的反應(yīng)的校園景點(diǎn)的總體布局。圖中頂點(diǎn)代表校園景點(diǎn)，頂點(diǎn)之間的邊代表景點(diǎn)之間的路徑，權(quán)值代表景點(diǎn)間的距離，兩個(gè)頂點(diǎn)間沒有邊，表明兩個(gè)景點(diǎn)不能直接到達(dá)。景點(diǎn)抽象圖如圖1所示： 圖1景點(diǎn)抽象圖 2.2 程序模塊圖圖中在初始化階段對無向圖進(jìn)行初始化，通過查找函數(shù)查找各個(gè)景點(diǎn)的信息，以及所有景點(diǎn)之間的最短距離，查找景點(diǎn)的位置和此景點(diǎn)在無向圖中頂點(diǎn)的編號(hào)，最后就能退出程序。程序模塊圖如圖2所示： 2.3 主函數(shù)設(shè)計(jì)簡要 在程序的操作要求以及客戶的需求下，在主函數(shù)設(shè)計(jì)中首先調(diào)用system（“cls”）函數(shù)顯示第一個(gè)界面，此后顯示出一個(gè)可視化的操作界面，可以為游

7、客提供相關(guān)的景點(diǎn)的各種信息，并且提示游客做出最好的選擇，便于其在后面的操作過程當(dāng)中能夠快速方便的找到其需要查找的景點(diǎn)。然后就要用到一個(gè)switch（）的選擇函數(shù)，并用此函數(shù)實(shí)現(xiàn)程序的所有功能：景點(diǎn)信息一覽表，景點(diǎn)信息的查詢，兩個(gè)景點(diǎn)之間的最短距離，兩個(gè)景點(diǎn)之間的所有路徑，增加、刪除、修改景點(diǎn)信息，一個(gè)景點(diǎn)到所有景點(diǎn)的最短路徑，清屏和退出程序。完成相關(guān)的選擇操作后進(jìn)入到選擇的操作界面當(dāng)中，從而實(shí)現(xiàn)所需要的功能。2.4 各函數(shù)模塊的功能 1、調(diào)用無向網(wǎng)的初始化信息實(shí)現(xiàn)景點(diǎn)信息的查詢以及全部輸出 2、用弗洛伊德算法實(shí)現(xiàn)兩個(gè)景點(diǎn)的最短路徑的查詢 3、用迪杰斯特拉算法實(shí)現(xiàn)一個(gè)景點(diǎn)到其余所有景點(diǎn)的最短路徑

8、的輸出 4、用system（“cls”）函數(shù)實(shí)現(xiàn)清屏功能 5、用exit（）函數(shù)實(shí)現(xiàn)退出程序的功能。 3. 方案實(shí)施3.1 程序執(zhí)行流程圖流程圖是算法設(shè)計(jì)中不可缺少的一部分，通過流程圖，可以更加清晰的理解程序算法的過程，清楚算法的進(jìn)程，使算法一目了然。流程圖如圖3-1： 圖3 程序流程圖3.2 主函數(shù)設(shè)計(jì)思想while(1) /無限循環(huán)完成程序的循環(huán)執(zhí)行switch(choise)case 0: printall(G);break; /0.所有景點(diǎn)信息一覽表 case 1: searchinfo(G); break; /1.景點(diǎn)信息查詢 case 2: shortpath(G);break;

9、/2.查詢兩個(gè)頂點(diǎn)間的最短路徑 case 3: oubleall(G);break; /3.查詢兩個(gè)景點(diǎn)間所有的路徑 case 4: changevex(G);break; /4.增加,刪除,更新有關(guān)景點(diǎn)的信息 case 5: shortallpath(G);break; /5.一個(gè)景點(diǎn)到其他所有景點(diǎn)的 /最短路徑（迪杰斯特拉） case 6: system("cls");break; /清屏 case 7: exit(0); /退出程序 default: break; 用一個(gè)無限循環(huán)實(shí)現(xiàn)程序的循環(huán)執(zhí)行，但是死循環(huán)是無法自動(dòng)退出的，因此增加7號(hào)功能，調(diào)用exit（）函數(shù)實(shí)現(xiàn)

10、退出程序的操作。主函數(shù)采用模塊化設(shè)計(jì)，將函數(shù)的功能放在函數(shù)中實(shí)現(xiàn)，簡化主函數(shù)。相應(yīng)的函數(shù)模塊實(shí)現(xiàn)對應(yīng)的功能1、0號(hào)（景點(diǎn)信息一覽表）1號(hào)功能（查詢景點(diǎn)信息）調(diào)用無向網(wǎng)的初始化信息實(shí)現(xiàn)景點(diǎn)信息的查詢以及全部輸出 2、2號(hào)功能（查詢兩個(gè)景點(diǎn)的最短路徑）應(yīng)用弗洛伊德算法實(shí)現(xiàn)兩個(gè)景點(diǎn)的最短路徑的查詢3、3號(hào)功能（查詢兩個(gè)景點(diǎn)之間的所有路徑）應(yīng)用圖的遍歷查詢兩個(gè)景點(diǎn)間所有的路徑4、4號(hào)功能（增加，刪除，更新有關(guān)景點(diǎn)信息）更改無向網(wǎng)的初始化實(shí)現(xiàn)更改景點(diǎn)信息 5、5號(hào)功能（一個(gè)景點(diǎn)到其他景點(diǎn)的最短路徑）實(shí)現(xiàn)一個(gè)景點(diǎn)到其他所有景點(diǎn)的最短路徑（迪杰斯特拉）6、6號(hào)功能（清屏）調(diào)用system（“cls”）函數(shù)實(shí)

11、現(xiàn)清屏功能，7、7號(hào)功能（退出程序）調(diào)用exit（）函數(shù)實(shí)現(xiàn)退出程序的功能。 4. 結(jié)果測試4.1 主函數(shù)功能模塊測試 主函數(shù)的執(zhí)行界面，測試結(jié)果如圖4所示圖4 主函數(shù)界面的運(yùn)行結(jié)果4.2主函數(shù)功能測試1、在請選擇查詢的項(xiàng)目后輸入0，按enter鍵，即完成0號(hào)功能測試，0號(hào)功能測試結(jié)果如圖5所示圖5 0號(hào)功能運(yùn)行結(jié)果 2、在請選擇查詢的項(xiàng)目后面輸入1，按enter鍵，即完成1號(hào)功能測試， 1號(hào)功能測試結(jié)果如圖6所示圖6 1號(hào)功能運(yùn)行結(jié)果 3、在選擇項(xiàng)目后輸入2，完成2號(hào)功能，2號(hào)功能的運(yùn)行結(jié)果如圖7所示 圖7 2號(hào)功能的運(yùn)行結(jié)果 4、在請選擇查詢的項(xiàng)目后輸入3，按enter鍵，即完成3號(hào)功能的

12、測試，3號(hào)功能測試結(jié)果如圖8所示圖8 3號(hào)功能運(yùn)行結(jié)果 5、在選擇查詢的項(xiàng)目后輸入4，即完成4號(hào)功能的測試，4號(hào)功能的運(yùn)行結(jié)果如圖9所示圖9 4號(hào)功能的運(yùn)行結(jié)果6、在選擇的項(xiàng)目后輸入5，即完成5號(hào)功能的測試，5號(hào)功能的測試結(jié)果如圖10所示 圖10 5號(hào)功能的運(yùn)行結(jié)果4.3 各功能所執(zhí)行的操作 共有8個(gè)功能，各個(gè)功能所執(zhí)行的操作如下所示 0號(hào)功能：景點(diǎn)信息一覽表 1號(hào)功能：查詢景點(diǎn)信息 2號(hào)功能：查詢兩個(gè)景點(diǎn)的最短路徑 3號(hào)功能：查詢兩個(gè)景點(diǎn)之間的所有路徑 4號(hào)功能：增加，刪除，更新有關(guān)景點(diǎn)信息 5號(hào)功能：一個(gè)景點(diǎn)到其他景點(diǎn)的最短路徑 6號(hào)功能：清屏 7號(hào)功能：退出程序5. 結(jié)論 經(jīng)過這次課程設(shè)

13、計(jì)，我對程序中算法的概念理解的更加透徹。算法是程序中必不可少的部分，它是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。如果一個(gè)算法有缺陷，或不適合于某個(gè)問題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問題。不同的算法可能用不同的時(shí)間、空間或效率來完成同樣的任務(wù)。同時(shí)，在選擇算法時(shí)必須考慮算法的時(shí)間復(fù)雜度和空間復(fù)雜度，這樣才能讓程序正常，高效的運(yùn)行。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計(jì)算機(jī)的硬(特別是編碼理論、存儲(chǔ)裝置和存取方法)的研究范圍,而且和計(jì)算機(jī)軟

14、件的研究有著更密切的關(guān)系,無論是編譯程序還是操作系統(tǒng),都涉及到數(shù)據(jù)元素在存儲(chǔ)器中的分配問題.在研究信息檢索時(shí)也必須考慮如何組織數(shù)據(jù),以便查找和存取數(shù)據(jù)元素更為方面。因此,可以認(rèn)為數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程.在計(jì)算機(jī)科學(xué)中,數(shù)據(jù)結(jié)構(gòu)不僅是一般程序設(shè)計(jì)(特別是非數(shù)值計(jì)算的程序設(shè)計(jì))的基礎(chǔ),而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。6. 收獲與致謝首先，在本次作業(yè)中，通過運(yùn)行程序，我對無向圖的運(yùn)用有了更深的理解，對它的方法又加以掌握，為以后的學(xué)習(xí)增加了基礎(chǔ)。小組內(nèi)成員的分工不同，負(fù)責(zé)的模塊不同，但大家能夠齊心協(xié)力，共同努力。感謝成員的不懈努力，正有了成員的配合 ，才順利完成做業(yè)。還要感謝孫高飛老師的教導(dǎo)，正因?yàn)橛兴膸椭?，有他知識(shí)的教育，我們才能夠運(yùn)用無向圖將學(xué)校景點(diǎn)化，順利完成作業(yè)。7. 參考文獻(xiàn)1.譚浩強(qiáng). C程序設(shè)計(jì)（第四版)J. 清華大學(xué)出版, 20102.嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu) (C語言版)J.清華大學(xué)出版社, 20118. 附件指導(dǎo)教師評(píng)語：1、課程設(shè)計(jì)報(bào)告：a、內(nèi)容： 不完整 完整 詳細(xì) b、方案設(shè)計(jì)： 較差 合理 非常合理c、實(shí)現(xiàn)： 未