數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-校園導(dǎo)游咨詢(xún)

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--校園導(dǎo)游咨詢(xún)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--校園導(dǎo)游咨詢(xún)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--校園導(dǎo)游咨詢(xún)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--校園導(dǎo)游咨詢(xún)編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:瓊州學(xué)院電子信息工程學(xué)院課程設(shè)計(jì)報(bào)告課程名稱(chēng)：《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)設(shè)計(jì)題目：校園導(dǎo)游咨詢(xún)專(zhuān)業(yè)：軟件工程班級(jí)：2010軟件工程學(xué)生姓名：學(xué)號(hào)：起止日期：指導(dǎo)教師：指導(dǎo)教師評(píng)語(yǔ)：最終成績(jī)：指導(dǎo)教師簽名：年月日成績(jī)?cè)u(píng)定項(xiàng)目權(quán)重成績(jī)1、設(shè)計(jì)過(guò)程中的學(xué)習(xí)態(tài)度0.22、課程設(shè)計(jì)的質(zhì)量及答辯0.53、設(shè)計(jì)報(bào)告書(shū)規(guī)范程度0.34、總成績(jī)注意事項(xiàng)一、設(shè)計(jì)目的《數(shù)據(jù)結(jié)構(gòu)》是一門(mén)實(shí)踐性較強(qiáng)的軟件基礎(chǔ)課，為了學(xué)好這門(mén)課程，必須在掌握理論知識(shí)的同時(shí)，加強(qiáng)上機(jī)實(shí)踐。本課程設(shè)計(jì)的目的就是要達(dá)到理論與實(shí)際應(yīng)用相結(jié)合，使同學(xué)們能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問(wèn)題在計(jì)算機(jī)內(nèi)部表示出來(lái)，并培養(yǎng)基本的、良好的程序設(shè)計(jì)技能。二、設(shè)計(jì)要求1．通過(guò)這次課程設(shè)計(jì)，要求在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深課程基本內(nèi)容的理解。同時(shí)，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。2．學(xué)生必須仔細(xì)研讀《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)要求，以學(xué)生自學(xué)為主、指導(dǎo)教師指導(dǎo)為輔，獨(dú)立完成課程設(shè)計(jì)的任務(wù)，有問(wèn)題及時(shí)主動(dòng)與指導(dǎo)教師溝通。3．本次課程設(shè)計(jì)按照教學(xué)要求需要在本學(xué)期15周前完成，學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課程設(shè)計(jì)的時(shí)間計(jì)劃，并在課程設(shè)計(jì)過(guò)程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)向指導(dǎo)教師匯報(bào)。4．編程語(yǔ)言：C語(yǔ)言。三、課程設(shè)計(jì)說(shuō)明書(shū)的格式要求設(shè)計(jì)文檔的撰寫(xiě)必須提前進(jìn)行，以保證使文檔與程序同步提交。1．設(shè)計(jì)題目2．運(yùn)行環(huán)境（軟、硬件環(huán)境）3．算法的需求分析4．算法概要設(shè)計(jì)5．算法詳細(xì)設(shè)計(jì)6．算法的測(cè)試7．運(yùn)行結(jié)果分析8．收獲及體會(huì)四、問(wèn)題分析、設(shè)計(jì)和測(cè)試過(guò)程要規(guī)范化1．需求分析：將題目中要求的功能進(jìn)行敘述分析。2．概要設(shè)計(jì)：算法的設(shè)計(jì)說(shuō)明，描述解決此問(wèn)題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的，按照指定的設(shè)計(jì)），描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語(yǔ)句的時(shí)間復(fù)雜度。3．詳細(xì)設(shè)計(jì)：即各個(gè)算法的具體實(shí)現(xiàn)步驟，每個(gè)題目要有相應(yīng)的源程序，其中每個(gè)功能模塊采用不同的函數(shù)實(shí)現(xiàn)。源程序要規(guī)范編寫(xiě)：結(jié)構(gòu)要清晰，注釋要清楚。重點(diǎn)函數(shù)的重點(diǎn)變量和重點(diǎn)功能部分要加上清楚的程序注釋。4．調(diào)試和測(cè)試：給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來(lái)。在調(diào)試過(guò)程中遇到的問(wèn)題和解決方法也要記錄下來(lái)。程序要能夠正常運(yùn)行，還要有基本的容錯(cuò)功能。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。5．改進(jìn)措施：

對(duì)有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。五、對(duì)指導(dǎo)教師的要求指導(dǎo)教師要關(guān)心學(xué)生的課程設(shè)計(jì)進(jìn)展，認(rèn)真答疑。對(duì)課程設(shè)計(jì)報(bào)告的撰寫(xiě)要給予充分的指導(dǎo)，報(bào)告中切忌出現(xiàn)大篇源代碼，應(yīng)嚴(yán)格要求學(xué)生將主要篇幅放在“原理實(shí)現(xiàn)”上，即如何用框圖表達(dá)設(shè)計(jì)和實(shí)施思想。課程設(shè)計(jì)報(bào)告要用紅筆批閱，最終成績(jī)以?xún)?yōu)、良、中、及格與不及格分等計(jì)算。目錄摘要 11設(shè)計(jì)內(nèi)容和要求 -2-1.1設(shè)計(jì)內(nèi)容 -2-1.1設(shè)計(jì)要求 -2-2概要設(shè)計(jì) 22.1程序的模塊圖 22.2主函數(shù)的概要設(shè)計(jì) 32.3查找介紹函數(shù)的概要設(shè)計(jì) 32.4查找最短路徑函數(shù)的概要設(shè)計(jì) 32.5景點(diǎn)分布圖的概要設(shè)計(jì) 32.6退出函數(shù)的概要設(shè)計(jì) 33詳細(xì)設(shè)計(jì) 53.1程序的流程圖 53.2主函數(shù)的詳細(xì)設(shè)計(jì) 63.3查找介紹函數(shù)的詳細(xì)設(shè)計(jì) 63.4查找最短路徑函數(shù)的詳細(xì)設(shè)計(jì) 73.5景點(diǎn)分布圖的詳細(xì)設(shè)計(jì) 83.6退出函數(shù)的詳細(xì)設(shè)計(jì) 93.7數(shù)據(jù)結(jié)構(gòu)的詳細(xì)設(shè)計(jì) 94軟件測(cè)試 104.1菜單的測(cè)試 104.2查找景點(diǎn)簡(jiǎn)介的測(cè)試 114.3查找兩個(gè)景點(diǎn)之間的最短距離的測(cè)試 124.4查看景點(diǎn)分布圖的測(cè)試 134.5退出的測(cè)試 145軟件使用說(shuō)明 156參考文獻(xiàn) 167附錄 177.1系統(tǒng)完整代碼 17摘要現(xiàn)代快節(jié)奏的生活使得都市人越來(lái)越渴望親近自然，因此外出旅游現(xiàn)在被越來(lái)越多的都市人所看中，所以如何快速方便的找到我們想要的旅游景點(diǎn)的信息和最短路徑就成了一個(gè)很重要的問(wèn)題。本設(shè)計(jì)基于圖的結(jié)構(gòu)，創(chuàng)建一個(gè)無(wú)向圖，針對(duì)游客的實(shí)際需求，將瓊州學(xué)院的景點(diǎn)編號(hào)、名稱(chēng)、介紹等信息放入到圖的頂點(diǎn)當(dāng)中并保存在景點(diǎn)文本文件當(dāng)中，將兩個(gè)景點(diǎn)的編號(hào)和它們之間的距離當(dāng)作權(quán)值也保存到權(quán)值文本文件當(dāng)中，利用迪杰斯特拉算法來(lái)求從一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)的最短距離，利用Search();函數(shù)來(lái)查找景點(diǎn)，并顯示出它的信息，從而解決了要查找景點(diǎn)信息和景點(diǎn)之間的最短路徑的問(wèn)題，最后按照顯示屏上的提示進(jìn)行相關(guān)的操作。關(guān)鍵詞：分布圖、查找信息、最短距離、校園導(dǎo)游咨詢(xún)1設(shè)計(jì)內(nèi)容和要求1.1設(shè)計(jì)內(nèi)容 依據(jù)課程設(shè)計(jì)的要求，利用一個(gè)無(wú)向圖的結(jié)構(gòu)，將景點(diǎn)當(dāng)作圖的頂點(diǎn)，將景點(diǎn)之間的距離當(dāng)作權(quán)值來(lái)儲(chǔ)存，然后根據(jù)游客自己的需求，按照顯示屏上的提示來(lái)進(jìn)行查找景點(diǎn)介紹，查找兩個(gè)景點(diǎn)之間的最短距離，退出程序等基本操作。1.1設(shè)計(jì)要求本軟件為校園導(dǎo)游咨詢(xún)系統(tǒng)，根據(jù)游客的實(shí)際需求而設(shè)計(jì)，首先創(chuàng)建一個(gè)無(wú)向圖，然后從文件當(dāng)中讀取所有景點(diǎn)的編號(hào)、名稱(chēng)、介紹和兩點(diǎn)之間的權(quán)值，并將它們寫(xiě)入到無(wú)向圖當(dāng)中。功能主要包括查找已知景點(diǎn)的信息，查找從一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)的最短路徑，退出等基本操作。軟件的界面要求使用VC++6.0的運(yùn)行環(huán)境。軟件的數(shù)據(jù)庫(kù)包括校園景點(diǎn)的編號(hào)、名稱(chēng)、介紹和兩個(gè)景點(diǎn)之間的距離（權(quán)值），首先要定義頂點(diǎn)的數(shù)據(jù)類(lèi)型結(jié)構(gòu)體，里面包括景點(diǎn)的編號(hào)、名稱(chēng)、介紹，然后定義一個(gè)鄰接矩陣結(jié)構(gòu)體來(lái)儲(chǔ)存邊的信息，最后定義一個(gè)無(wú)向圖類(lèi)型的結(jié)構(gòu)體來(lái)儲(chǔ)存頂點(diǎn)的信息，邊的信息，頂點(diǎn)的個(gè)數(shù)，邊的條數(shù)。最后游客按照顯示屏上的提示來(lái)進(jìn)行相關(guān)的操作。2概要設(shè)計(jì)2.1程序的模塊圖本軟件的算法依據(jù)無(wú)向圖的操作通過(guò)查找函數(shù)查找景點(diǎn)的信息，通過(guò)費(fèi)洛伊德函數(shù)來(lái)查找最短距離，開(kāi)始時(shí)首先從文件當(dāng)中讀取景點(diǎn)的編號(hào)、名稱(chēng)、介紹和兩個(gè)景點(diǎn)之間的距離即權(quán)值，然后將其加入到圖當(dāng)中，再調(diào)用查找函數(shù)查找景點(diǎn)的信息，調(diào)用費(fèi)洛伊德函數(shù)來(lái)查找最短距離，調(diào)用退出函數(shù)實(shí)現(xiàn)退出功能，其模塊圖如圖2.5所示：開(kāi)始開(kāi)始加入圖加入圖分布圖退出最短距離查找信息分布圖退出最短距離查找信息屏幕顯示屏幕顯示屏幕顯示屏幕顯示屏幕顯示屏幕顯示圖2.5模塊圖2.2主函數(shù)的概要設(shè)計(jì) 基于程序的操作要求，對(duì)于主函數(shù)的設(shè)計(jì)首先是顯示一個(gè)可視化的操作界面提醒游客進(jìn)行相關(guān)的操作和提示游客其可供選擇的景點(diǎn)的名稱(chēng)，便于其在后面的操作過(guò)程當(dāng)中能夠快速方便的找到其需要查找的景點(diǎn)的名稱(chēng)。而后就是一個(gè)switch（）；的選擇函數(shù)，提供查找景點(diǎn)信息，查找兩個(gè)景點(diǎn)之間的最短距離和退出的相關(guān)的選擇操作而后進(jìn)入到每一個(gè)操作界面當(dāng)中，從而實(shí)現(xiàn)所需要的功能。2.3查找介紹函數(shù)的概要設(shè)計(jì) 當(dāng)游客選擇了要查找景點(diǎn)的信息的介紹這一項(xiàng)功能的時(shí)候，就會(huì)進(jìn)入到查找的界面，對(duì)于查找景點(diǎn)信息就是利用Search();函數(shù)，當(dāng)游客輸入景點(diǎn)的名稱(chēng)的時(shí)候看其是否與文件當(dāng)中的數(shù)據(jù)相匹配，如果有則輸出它的介紹，如果沒(méi)有則輸出錯(cuò)誤的提示提醒游客進(jìn)行相關(guān)的操作來(lái)進(jìn)入到正確的操作過(guò)程當(dāng)中。2.4查找最短路徑函數(shù)的概要設(shè)計(jì) 對(duì)于查找最短路徑的這一項(xiàng)功能，可以利用迪杰斯特拉算法，但我是用的費(fèi)洛伊德算法，相對(duì)來(lái)說(shuō)步驟跟簡(jiǎn)單一點(diǎn)。后面有詳細(xì)介紹。2.5景點(diǎn)分布圖的概要設(shè)計(jì)先手稿繪制所有景點(diǎn)的分布，利用printf（）；函數(shù)打印分布圖的框架構(gòu)造。各景點(diǎn)之間用線條鏈接，通過(guò)分布圖能全面的對(duì)校園各景點(diǎn)有個(gè)方位感。2.6退出函數(shù)的概要設(shè)計(jì) 關(guān)于退出函數(shù)，則是當(dāng)游客執(zhí)行完了他想要進(jìn)行的操作過(guò)后選擇退出的功能的時(shí)候就調(diào)用退出函數(shù)exit(0);跳入到退出界面實(shí)現(xiàn)退出的功能。3詳細(xì)設(shè)計(jì)3.1程序的流程圖 當(dāng)我們想要更加實(shí)際的了解一個(gè)程序的算法過(guò)程的時(shí)候，我們就要依據(jù)程序的流程圖來(lái)給我們一個(gè)比較實(shí)際的過(guò)程，從流程圖當(dāng)中能夠更加清楚整個(gè)程序?qū)崿F(xiàn)的過(guò)程是怎樣的。其流程圖如圖3.1所示：startstart創(chuàng)建無(wú)向圖寫(xiě)入無(wú)向圖中Case3Case2Case1查找信息最短路徑TTFFCase4分布圖TendF圖3.1流程圖3.2主函數(shù)的詳細(xì)設(shè)計(jì) 主函數(shù)是一個(gè)程序的主體，當(dāng)我們要進(jìn)行我們所需要的操作的時(shí)候我們就要根據(jù)主函數(shù)中的顯示信息和它給我們的相關(guān)的提示信息來(lái)進(jìn)行所需要的操作，因此在這次的程序?qū)崿F(xiàn)的過(guò)程當(dāng)中，調(diào)用 Browser();提示游客根據(jù)switch();的選擇語(yǔ)句，選擇來(lái)進(jìn)入到相關(guān)的操作界面實(shí)現(xiàn)程序的基本功能。，3.3查找介紹函數(shù)的詳細(xì)設(shè)計(jì) 當(dāng)游客選擇了要查找景點(diǎn)的信息的介紹這一項(xiàng)功能的時(shí)候，程序就會(huì)調(diào)用Search();函數(shù)進(jìn)入到查找景點(diǎn)的介紹的界面，當(dāng)游客輸入了需要查找的景點(diǎn)的編號(hào)的時(shí)候，程序通過(guò)結(jié)構(gòu)體，自動(dòng)匹配相應(yīng)的信息，查找是否有這個(gè)景點(diǎn)。voidSearch(MGraph*G){ intk,flag=1; while(flag){ printf("請(qǐng)輸入要查詢(xún)的景點(diǎn)編號(hào):"); scanf("%d",&k); if(k<=0||k>G->vexnum){ printf("景點(diǎn)編號(hào)不存在!請(qǐng)重新輸入景點(diǎn)編號(hào):"); scanf("%d",&k); } if(k>0&&k<=G->vexnum)flag=0; } printf("\n┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃編號(hào)┃景點(diǎn)名稱(chēng)┃簡(jiǎn)介┃\n"); printf("┃%-4d┃%-16s┃%-62s┃\n",G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction); printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");}，找到將它的編號(hào)返回，并輸出它的介紹，沒(méi)有找到這輸出錯(cuò)誤提示，提醒游客進(jìn)行相關(guān)的操作進(jìn)入正確的操作過(guò)程當(dāng)中。3.4查找最短路徑函數(shù)的詳細(xì)設(shè)計(jì) 當(dāng)游客選擇了要查找兩個(gè)景點(diǎn)之間的最短距離這一項(xiàng)功能的時(shí)候，函數(shù)進(jìn)入到查找兩個(gè)景點(diǎn)之間的最短距離的操作界面當(dāng)中，當(dāng)游客輸入了兩個(gè)景點(diǎn)的名稱(chēng)過(guò)后，程序會(huì)判斷是否有這兩個(gè)景點(diǎn)，如果有則返回他們各自的編號(hào)，并調(diào)用Floyd();函數(shù)進(jìn)入到查找最短路徑問(wèn)題的程序當(dāng)中。voidFloyd(MGraph*G){ intv,u,i,w,k,j,flag=1,p[14][14][14],D[14][14]; for(v=1;v<=G->vexnum;v++) for(w=1;w<=G->vexnum;w++) { D[v][w]=G->arcs[v][w].adj; for(u=1;u<=G->vexnum;u++) p[v][w][u]=0; if(D[v][w]<INFINITY) { p[v][w][v]=1;p[v][w][w]=1; } } for(u=1;u<=G->vexnum;u++) for(v=1;v<=G->vexnum;v++) for(w=1;w<=G->vexnum;w++) if(D[v][u]+D[u][w]<D[v][w]) { D[v][w]=D[v][u]+D[u][w]; for(i=1;i<=G->vexnum;i++) p[v][w][i]=p[v][u][i]||p[u][w][i]; } while(flag) { printf("請(qǐng)輸入出發(fā)點(diǎn)和目的地的編號(hào):"); scanf("%d%d",&k,&j); if(k<=0||k>G->vexnum||j<=0||j>G->vexnum) { printf("景點(diǎn)編號(hào)不存在!請(qǐng)重新輸入出發(fā)點(diǎn)和目的地的編號(hào):"); scanf("%d%d",&k,&j); } if(k==j) { printf("出發(fā)點(diǎn)和目的地一樣!請(qǐng)重新輸入出發(fā)點(diǎn)和目的地的編號(hào):"); scanf("%d%d",&k,&j); } if(k>0&&k<=G->vexnum&&j>0&&j<=G->vexnum) flag=0; } printf("\n最短游覽路線：%s",G->vexs[k].name); if(k>j){ for(u=G->vexnum;u>0;u--) if(p[k][j][u]&&k!=u&&j!=u) printf("-->%s",G->vexs[u].name);} if(k<j){ for(u=1;u<=G->vexnum;u++) if(p[k][j][u]&&k!=u&&j!=u) printf("-->%s",G->vexs[u].name);} printf("-->%s",G->vexs[j].name); printf("總路線長(zhǎng)%dm\n",D[k][j]);} 已知有n個(gè)頂點(diǎn)的有向圖,佛洛伊德算法可以求解出每一對(duì)頂點(diǎn)之間的最短路徑。假設(shè)使用鄰接矩陣d(i,j)來(lái)對(duì)圖進(jìn)行存儲(chǔ),d(i,j)表示υi到υj之間的距離,但是該距離不一定是最短距離。佛洛伊德算法的基本思想是:為求頂點(diǎn)υi→υj之間的最短距離,需要進(jìn)行n次試探。首先將υ0加入路徑,考慮路徑υi→υ0→υj是否存在,如果存在,則比較υi→υj和υi→υ0→υj的路徑長(zhǎng)度,取長(zhǎng)度短的路徑作為υi→υj的路徑,記作(υi,υj)。接著在路徑上再增加一個(gè)頂點(diǎn)υ1,比較υi→υ1→υj和(υi,υj)的路徑長(zhǎng)度,取長(zhǎng)度短的路徑作為(υi,υj)。不斷將頂點(diǎn)υ2,υ3,.,υn-1加入進(jìn)行試探,最后得到的(υi,υj)必定為υi→υj的最短路徑。若使用數(shù)組dk(i,j)表示加入頂點(diǎn)k后,最短路徑長(zhǎng)度的變化情況,使用數(shù)組pk(i,j)表示加入頂點(diǎn)k后,最短路徑上頂點(diǎn)的變化情況,這樣就求得了最短路徑和最短路徑長(zhǎng)度。3.5景點(diǎn)分布圖的詳細(xì)設(shè)計(jì) 這里不詳細(xì)介紹，具體代碼，查看附錄browse_view_distribute()函數(shù)。3.6退出函數(shù)的詳細(xì)設(shè)計(jì) 對(duì)于退出函數(shù)，當(dāng)游客選擇了退出這一個(gè)操作的時(shí)候，程序就會(huì)調(diào)用exit(0);函數(shù)實(shí)現(xiàn)退出主函數(shù)的功能。最后會(huì)提示游客，歡迎下次繼續(xù)使用！3.7數(shù)據(jù)結(jié)構(gòu)的詳細(xì)設(shè)計(jì) 本軟件的數(shù)據(jù)結(jié)構(gòu)包括3個(gè)部分：鄰接矩陣typedefintAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];定義一個(gè)鄰接矩陣，用鄰接矩陣來(lái)定義和儲(chǔ)存邊的相關(guān)信息。2.頂點(diǎn)的結(jié)構(gòu)體typedefstructVertex//定義圖中頂點(diǎn)的數(shù)據(jù)類(lèi)型{ intnum;//景點(diǎn)編號(hào) charname[30];//景點(diǎn)名稱(chēng) charintroduction[200];//景點(diǎn)介紹}Vertex;定義一個(gè)頂點(diǎn)的結(jié)構(gòu)體，用來(lái)儲(chǔ)存景點(diǎn)的編號(hào)、景點(diǎn)得名稱(chēng)和景點(diǎn)的介紹等關(guān)于景點(diǎn)的信息。3.無(wú)向圖的結(jié)構(gòu)體typedefstruct//定義圖的數(shù)據(jù)類(lèi)型{ Vertexvexs[MAX_VERTEX_NUM];//頂點(diǎn)的結(jié)構(gòu)體 AdjMatrixarcs;//邊的鄰接矩陣 intvexnum,arcnum;//頂點(diǎn)的個(gè)數(shù)，邊的個(gè)數(shù)}MGraph;定義一個(gè)圖的結(jié)構(gòu)體，用來(lái)儲(chǔ)存頂點(diǎn)的信息、邊的信息、頂點(diǎn)的個(gè)數(shù)和邊的個(gè)數(shù)等相關(guān)的信息便于我們以后在用的時(shí)候能夠方便快捷的調(diào)用。定義好這些結(jié)構(gòu)體后，當(dāng)我們以后需要調(diào)用的時(shí)候，我們就能夠方便快捷的調(diào)用這些結(jié)構(gòu)體，從而使得我們?cè)谶\(yùn)行程序的時(shí)候能夠更加的快速能夠提高我們的程序的運(yùn)行效率，大大的節(jié)省了我們的時(shí)間還使得程序變得更加的簡(jiǎn)單。4軟件測(cè)試4.1菜單的測(cè)試 對(duì)于菜單函數(shù)的測(cè)試，首先菜單是一個(gè)可示化的界面，它能夠提示游客依據(jù)顯示屏上出現(xiàn)的提示來(lái)進(jìn)行相關(guān)的操作，查看所有的景點(diǎn)從而方便游客進(jìn)行相關(guān)的操作，因而我們?cè)谶\(yùn)行程序的時(shí)候首先就會(huì)進(jìn)入到菜單函數(shù)當(dāng)中，經(jīng)過(guò)測(cè)試其能夠?qū)崿F(xiàn)我們所要實(shí)現(xiàn)得基本功能，其效果圖如圖4.1所示：圖4.1菜單4.2查找景點(diǎn)簡(jiǎn)介的測(cè)試 對(duì)于查找景點(diǎn)的介紹的測(cè)試，首先依據(jù)顯示屏上的提示首先輸入要進(jìn)行的操作輸入3進(jìn)入查找景點(diǎn)信息的操作界面，然后輸入需要查找的景點(diǎn)的名稱(chēng)即可顯示出景點(diǎn)的介紹信息，經(jīng)過(guò)測(cè)試可以得出其沒(méi)有什么錯(cuò)誤，程序能夠按照我的要求實(shí)現(xiàn)它的功能，其效果圖如圖4.2所示：圖4.2查找景點(diǎn)信息4.3查找兩個(gè)景點(diǎn)之間的最短距離的測(cè)試 同查找景點(diǎn)的信息一樣，對(duì)于查找景點(diǎn)之間的最短距離的測(cè)試，我們就要依據(jù)提示輸入2進(jìn)入到查詢(xún)最短路徑的界面，依次輸入所需要查找的兩個(gè)景點(diǎn)就會(huì)顯示出怎樣到達(dá)這兩個(gè)景點(diǎn)并顯示出它們之間的最短路徑，經(jīng)過(guò)測(cè)試可見(jiàn)程序能夠按照我的要求來(lái)實(shí)現(xiàn)其所需要的功能，其效果圖如圖4.3所示：圖4.3查找兩個(gè)景點(diǎn)之間的最短距離4.4查看景點(diǎn)分布圖的測(cè)試對(duì)于查看景點(diǎn)分布圖的測(cè)試，我需要依據(jù)顯示屏上的提示，需要輸入1進(jìn)入到分布圖的界面，系統(tǒng)就會(huì)直接調(diào)用browse_view_distribute();函數(shù)，在屏幕上打印出景點(diǎn)的分布圖。圖4.4景點(diǎn)分布圖界面4.5退出的測(cè)試 原理同上，對(duì)于退出函數(shù)的測(cè)試，我需要依據(jù)顯示屏上的提示，需要輸入4進(jìn)入到退出的界面，系統(tǒng)就會(huì)直接調(diào)用退出的函數(shù)，顯示出“歡迎下次繼續(xù)使用！”的話，退出了系統(tǒng)，其效果圖如圖4.4所示：圖4.5退出界面5軟件使用說(shuō)明 對(duì)于軟件的使用，對(duì)于第一次使用軟件的游客來(lái)說(shuō)，要讓他們?cè)诘谝淮斡玫臅r(shí)候就能夠快速輕松的掌握軟件的用法，因此在程序一開(kāi)始運(yùn)行的時(shí)候，我們要進(jìn)行如下的操作：（1）首先我會(huì)給游客提供一個(gè)可視化的菜單操作界面，在顯示屏上提示用戶其可以進(jìn)行的操作和他能夠查詢(xún)的景點(diǎn)的編號(hào)、名稱(chēng)。（2）用戶輸入了“1”后，屏幕上會(huì)顯示出所有景點(diǎn)的位置關(guān)系平面圖。能夠大致了解景點(diǎn)的分布。（3）當(dāng)用戶輸入了“2”后，進(jìn)入到查詢(xún)?nèi)我鈨删包c(diǎn)間最短路徑的界面，然后提示用戶依次輸入兩個(gè)景點(diǎn)的編號(hào)，程序就會(huì)將這兩個(gè)景點(diǎn)的最短路徑給我們表示出來(lái)并顯示出最短路徑是多少。（4）用戶輸入了“3”后，進(jìn)入到查詢(xún)景點(diǎn)信息的界面，然后提示用戶輸入景點(diǎn)的編號(hào)（一次限一個(gè)），程序就會(huì)顯示出這個(gè)景點(diǎn)的詳細(xì)介紹。（5）當(dāng)用戶輸入了“4”后，進(jìn)入到退出界面，這時(shí)系統(tǒng)就會(huì)顯示“歡迎下次繼續(xù)使用!”的提示語(yǔ)，最后按下任意鍵退出系統(tǒng)。6參考文獻(xiàn)數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)嚴(yán)蔚敏吳偉民編著清華大學(xué)出版社2002C程序設(shè)計(jì)經(jīng)典教程，[美]Deitel,H.M.，[美]Deitel,P.J.著，清華大學(xué)出版社2006Windows程序設(shè)計(jì)，[美]CharlesPetzold著，北京大學(xué)出版社2004DataStructures：APseudecode（ApproachwithC）[美]RichardF.Gilberg，[美]BehrouzA.Forouzan著7附錄7.1系統(tǒng)完整代碼#defineINFINITY10000/*無(wú)窮大*/#defineMAX_VERTEX_NUM40#defineMAX40#include<stdlib.h>#include<stdio.h>#include<conio.h>#include<string.h>#include"Exit.h"typedefstructArCell{ intadj;//路徑長(zhǎng)度}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct//圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱(chēng)、簡(jiǎn)介等信息，{ charname[30]; intnum; charintroduction[200];//簡(jiǎn)介}infotype;typedefstruct{ infotypevexs[MAX_VERTEX_NUM];//景點(diǎn) AdjMatrixarcs;//路徑數(shù)組 intvexnum,arcnum;//景點(diǎn)數(shù)，路徑長(zhǎng)度記錄}MGraph;MGraphb;//全局變量voidcmd(void);//在主函數(shù)中用來(lái)調(diào)用其他應(yīng)用子函數(shù)的函數(shù)聲明MGraphInitGraph(void);//用來(lái)構(gòu)造學(xué)校地圖的子函數(shù)返回MGraph類(lèi)型voidMenu(void);//菜單函數(shù)；voidBrowser(MGraph*G);//調(diào)用MGraph類(lèi)型的地址，進(jìn)行voidShortestPath_DIJ(MGraph*G);//迪杰斯特拉算法求最短路徑的子函數(shù)voidFloyd(MGraph*G);//佛洛伊德算法voidSearch(MGraph*G);//尋找要查詢(xún)的景點(diǎn)，并輸出該景點(diǎn)的信息voidbrowse_view_distribute();//查看景點(diǎn)分布圖voidtou(MGraph*G);//景點(diǎn)列表voidpanduan();//voidExit();//退出intLocateVex(MGraph*G,char*v);//定點(diǎn)位置MGraph*CreatUDN(MGraph*G);////初始化圖形，接受用戶輸入voidprint(MGraph*G);//打印輸出子函數(shù)/******************************************************/voidmain(void){ system("color1f");//設(shè)置調(diào)試窗口背景和字體顏色 system("modecon:cols=140lines=130");//設(shè)置調(diào)試窗口的大小 cmd();//用該函數(shù)來(lái)調(diào)用其他需要用到的函數(shù)}/******************************************************/voidcmd(void)//用來(lái)調(diào)用其他需要用到的函數(shù)的子函數(shù){ inti; b=InitGraph();//構(gòu)造校園地圖 Browser(&b);//Menu();//調(diào)用菜單函數(shù) scanf("%d",&i); while(i!=4) { switch(i) { case1:system("cls");/*ShortestPath_DIJ(&b);*/browse_view_distribute();Browser(&b);break; case2:system("cls");tou(&b);Floyd(&b);Browser(&b);break; case3:system("cls");tou(&b);Search(&b);Browser(&b);break; case4:exit(0);break; default:break; } scanf("%d",&i); } printf("歡迎下次繼續(xù)使用!\n\n");}//*******************************************************************MGraphInitGraph(void)//構(gòu)造校園地圖{ MGraphG; inti,j; G.vexnum=13;//景點(diǎn)數(shù)量 G.arcnum=21;//路徑數(shù)量 for(i=1;i<=G.vexnum;i++) G.vexs[i].num=i;//對(duì)景點(diǎn)進(jìn)行對(duì)應(yīng)編號(hào)/*對(duì)對(duì)應(yīng)的景點(diǎn)編號(hào)進(jìn)行命名，輸入簡(jiǎn)介*/ strcpy(G.vexs[3].name,"行政辦公樓");strcpy(G.vexs[3].introduction,"學(xué)校的行政機(jī)構(gòu)。"); strcpy(G.vexs[6].name,"圖書(shū)館"); strcpy(G.vexs[6].introduction,"體積龐大，是學(xué)校的標(biāo)志性建筑，目前還在建設(shè)中。"); strcpy(G.vexs[2].name,"果園"); strcpy(G.vexs[2].introduction,"枝葉茂盛，各種新鮮水果。");strcpy(G.vexs[1].name,"校門(mén)"); strcpy(G.vexs[1].introduction,"學(xué)校的形象，氣勢(shì)宏偉。"); strcpy(G.vexs[4].name,"體育運(yùn)動(dòng)區(qū)"); strcpy(G.vexs[4].introduction,"包括有排球場(chǎng)、籃球場(chǎng)、網(wǎng)球場(chǎng)等。"); strcpy(G.vexs[5].name,"教學(xué)區(qū)"); strcpy(G.vexs[5].introduction,"包括左教學(xué)樓、小湖、右教學(xué)樓、實(shí)驗(yàn)樓和醫(yī)務(wù)室等。"); strcpy(G.vexs[10].name,"男生宿舍"); strcpy(G.vexs[10].introduction,"分1、2、7、8棟，供男同學(xué)居住，女生勿進(jìn)。"); strcpy(G.vexs[7].name,"琴房"); strcpy(G.vexs[7].introduction,"音樂(lè)學(xué)院學(xué)生練琴的地方。"); strcpy(G.vexs[8].name,"足球場(chǎng)"); strcpy(G.vexs[8].introduction,"踢球，跑步，運(yùn)動(dòng)比賽場(chǎng)地。"); strcpy(G.vexs[9].name,"省高速路"); strcpy(G.vexs[9].introduction,"上面是省高速路，下面是人行隧道。"); strcpy(G.vexs[11].name,"食堂"); strcpy(G.vexs[11].introduction,"分1、2、3、4樓，價(jià)格有所不同，根據(jù)自己愛(ài)好，隨意點(diǎn)菜。"); strcpy(G.vexs[12].name,"女生宿舍"); strcpy(G.vexs[12].introduction,"樓下一“愛(ài)心”超市，價(jià)格絕對(duì)不便宜。樓上女同學(xué)居住，男生勿進(jìn)。"); strcpy(G.vexs[13].name,"教師村"); strcpy(G.vexs[13].introduction,"老師們的居住地，10多樓高。");//對(duì)有路的各景點(diǎn)之間的路徑長(zhǎng)度進(jìn)行設(shè)置,沒(méi)路的設(shè)置為無(wú)窮大for(i=1;i<=G.vexnum;i++)for(j=1;j<=G.vexnum;j++) G.arcs[i][j].adj=INFINITY; G.arcs[1][3].adj=100; G.arcs[1][2].adj=100; G.arcs[1][5].adj=200; G.arcs[2][4].adj=100; G.arcs[2][3].adj=150; G.arcs[3][5].adj=200; G.arcs[3][8].adj=300; G.arcs[4][5].adj=100; G.arcs[4][7].adj=150; G.arcs[5][6].adj=100; G.arcs[6][7].adj=150; G.arcs[6][8].adj=100; G.arcs[7][9].adj=50; G.arcs[8][9].adj=200; G.arcs[8][13].adj=200; G.arcs[9][10].adj=200; G.arcs[9][11].adj=150; G.arcs[9][12].adj=200; G.arcs[10][11].adj=100; G.arcs[11][12].adj=150; G.arcs[12][13].adj=150;//無(wú)向圖的路徑是相互的for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) G.arcs[j][i].adj=G.arcs[i][j].adj;returnG;}//InitGraphend//*******************************************************************/*//菜單函數(shù)，打印出導(dǎo)游項(xiàng)目菜單voidMenu(){ printf("\n瓊州學(xué)院校園導(dǎo)游圖\n"); printf("┏━━┳━━━━━━━━━━━━━━━━━━┓\n");printf("┃編號(hào)┃實(shí)現(xiàn)的功能┃\n"); printf("┣━━╋━━━━━━━━━━━━━━━━━━┫\n"); printf("┃1┃查看景點(diǎn)分布圖┃\n"); printf("┣━━╋━━━━━━━━━━━━━━━━━━┫\n"); printf("┃2┃查找兩景點(diǎn)間最短距離┃\n"); printf("┣━━╋━━━━━━━━━━━━━━━━━━┫\n");printf("┃3┃查看景點(diǎn)信息┃\n"); printf("┣━━╋━━━━━━━━━━━━━━━━━━┫\n");printf("┃4┃退出系統(tǒng)┃\n"); printf("┗━━┻━━━━━━━━━━━━━━━━━━┛\n"); printf("輸入你的操作編號(hào)：");}*///*******************************************************************//輸出所有景點(diǎn)信息voidBrowser(MGraph*G){ intv; printf("┏━━┳━━━━━━┓\n"); printf("┃編號(hào)┃景點(diǎn)名稱(chēng)┃\n"); for(v=1;v<=G->vexnum;v++){ printf("┃%-4d┃%-12s┃",G->vexs[v].num,G->vexs[v].name); switch(v+2){ case4:printf("瓊州學(xué)院校園導(dǎo)游圖\n");break; case5:printf("┏━━┳━━━━━━━━━━━━━━━━┓\n");break; case6:printf("┃編號(hào)┃實(shí)現(xiàn)的功能┃\n");break; case7:printf("┣━━╋━━━━━━━━━━━━━━━━┫\n");break; case8:printf("┃1┃查看景點(diǎn)分布圖┃\n");break; case9:printf("┣━━╋━━━━━━━━━━━━━━━━┫\n");break; case10:printf("┃2┃查找兩景點(diǎn)間最短距離┃\n");break; case11:printf("┣━━╋━━━━━━━━━━━━━━━━┫\n");break; case12:printf("┃3┃查看景點(diǎn)信息┃\n");break; case13:printf("┣━━╋━━━━━━━━━━━━━━━━┫\n");break; case14:printf("┃4┃退出系統(tǒng)┃\n");break; case15:printf("┗━━┻━━━━━━━━━━━━━━━━┛\n");break; default:printf("\n");break; }} printf("┗━━┻━━━━━━┛\n"); printf("輸入你的操作編號(hào)：");}//*******************************************************************/*//迪杰斯特拉算法來(lái)計(jì)算出起點(diǎn)到各個(gè)頂點(diǎn)之間的最短路徑,v0為起點(diǎn)voidShortestPath_DIJ(MGraph*G){ intv,w,i,min,t=0,x,flag=1,v0;intfinal[20],D[20],p[20][20]; while(flag) { printf("請(qǐng)輸入一個(gè)起始景點(diǎn)編號(hào):"); scanf("%d",&v0); if(v0<=0||v0>G->vexnum) { printf("景點(diǎn)編號(hào)不存在!請(qǐng)重新輸入景點(diǎn)編號(hào):"); scanf("%d",&v0); printf("\n"); } if(v0>0&&v0<=G->vexnum) flag=0; } for(v=1;v<=G->vexnum;v++) { final[v]=0; D[v]=G->arcs[v0][v].adj; for(w=1;w<=G->vexnum;w++) p[v][w]=0; if(D[v]<INFINITY) { p[v][v0]=1;p[v][v]=1; } } D[v0]=0;final[v0]=1; for(i=1;i<=G->vexnum;i++) { min=INFINITY; for(w=1;w<=G->vexnum;w++) if(!final[w]) if(D[w]<min){v=w;min=D[w];} final[v]=1; for(w=1;w<=G->vexnum;w++) if(!final[w]&&(min+G->arcs[v][w].adj<D[w])) { D[w]=min+G->arcs[v][w].adj; for(x=1;x<=G->vexnum;x++) p[w][x]=p[v][x]; p[w][w]=1; } } for(v=1;v<=G->vexnum;v++) { if(v0!=v)printf("%s",G->vexs[v0].name); for(w=v0;w>0;w--) { p[v][v0-v]=0; if(p[v][w]&&w!=v0)printf("-->%s",G->vexs[w].name); t++; printf("yyyy"); } for(w=v0-1;w<=G->vexnum;w++) { if(p[v][w]&&w!=v0)printf("-->%s",G->vexs[w].name); t++; printf("xxxx"); } if(t>G->vexnum-1&&v0!=v)printf("總路線長(zhǎng)%dm\n\n",D[v]); }}//ShortestPath_DIJend*///*******************************************************************voidFloyd(MGraph*G){ intv,u,i,w,k,j,flag=1,p[14][14][14],D[14][14]; for(v=1;v<=G->vexnum;v++) for(w=1;w<=G->vexnum;w++) { D[v][w]=G->arcs[v][w].adj; for(u=1;u<=G->vexnum;u++) p[v][w][u]=0; if(D[v][w]<INFINITY) { p[v][w][v]=1;p[v][w][w]=1; } } for(u=1;u<=G->vexnum;u++) for(v=1;v<=G->vexnum;v++) for(w=1;w<=G->vexnum;w++) if(D[v][u]+D[u][w]<D[v][w]) { D[v][w]=D[v][u]+D[u][w]; for(i=1;i<=G->vexnum;i++) p[v][w][i]=p[v][u][i]||p[u][w][i]; } while(flag) { printf("請(qǐng)輸入出發(fā)點(diǎn)和目的地的編號(hào):"); scanf("%d%d",&k,&j); if(k<=0||k>G->vexnum||j<=0||j>G->vexnum) { printf("景點(diǎn)編號(hào)不存在!請(qǐng)重新輸入出發(fā)點(diǎn)和目的地的編號(hào):"); scanf("%d%d",&k,&j); } if(k==j) { printf("出發(fā)點(diǎn)和目的地一樣!請(qǐng)重新輸入出發(fā)點(diǎn)和目的地的編號(hào):"); scanf("%d%d",&k,&j); } if(k>0&&k<=G->vexnum&&j>0&&j<=G->vexnum) flag=0; } printf("\n最短游覽路線：%s",G->vexs[k].name); if(k>j){ for(u=G->vexnum;u>0;u--) if(p[k][j][u]&&k!=u&&j!=u) printf("-->%s",G->vexs[u].name);} if(k<j){ for(u=1;u<=G->vexnum;u++) if(p[k][j][u]&&k!=u&&j!=u) printf("-->%s",G->vexs[u].name);} printf("-->%s",G->vexs[j].name); printf("總路線長(zhǎng)%dm\n",D[k][j]);}//Floydend//****************************************************************//尋找要查詢(xún)的景點(diǎn)，并輸出該景點(diǎn)的信息voidSearch(MGraph*G){ intk,flag=1; while(flag) { printf("請(qǐng)輸入要查詢(xún)的景點(diǎn)編號(hào):"); scanf("%d",&k); if(k<=0||k>G->vexnum) { printf("景點(diǎn)編號(hào)不存在!請(qǐng)重新輸入景點(diǎn)編號(hào):"); scanf("%d",&k); } if(k>0&&k<=G->vexnum) flag=0; } printf("\n┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃編號(hào)┃景點(diǎn)名稱(chēng)┃簡(jiǎn)介┃\n"); printf("┃%-4d┃%-16s┃%-62s┃\n",G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction); printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");}//Searchend//*******************************************************************intLocateVex(MGraph*G,char*v){ intc=-1,i; for(i=1;i<=G->vexnum;i++) if(strcmp(v,G->vexs[i].name)==0) {c=i;break;} returnc;}//******************************************************************MGraph*CreatUDN(MGraph*G)//初始化圖形，接受用戶輸入{ inti,j,k,w; charv1[20],v2[20]; printf("請(qǐng)輸入圖的頂點(diǎn)數(shù),弧數(shù):"); scanf("%d%d",&G->vexnum,&G->arcnum); printf("請(qǐng)輸入景點(diǎn)的編號(hào):、名稱(chēng)、簡(jiǎn)介:\n"); for(i=1;i<=G->vexnum;i++) { printf("景點(diǎn)編號(hào):"); scanf("%d",&G->vexs->num); printf("景點(diǎn)名稱(chēng):"); scanf("%s",G->vexs[i].name); printf("景點(diǎn)簡(jiǎn)介:"); scanf("%s",G->vexs->introduction); } for(i=1;i<=G->vexnum;i++) for(j=1;j<=G->vexnum;j++) G->arcs[i][j].adj=INFINITY; printf("請(qǐng)輸入路徑長(zhǎng)度:\n"); for(k=1;k<=G->arcnum;k++) { printf("第%d條邊:\n",k+1); printf("景點(diǎn)對(duì)(x,y):"); scanf("%s",v1); scanf("%s",v2); printf("路徑長(zhǎng)度:"); scanf("%d",&w); i=LocateVex(G,v1); j=LocateVex(G,v2); if(i>0&&j>0) { G->arcs[i][j].adj=w; G->arcs[j][i]=G->arcs[i][j]; } }returnG;}//*******************************************************************voidbrowse_view_distribute(){//查看景點(diǎn)分布圖，3 printf("§·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·§\n"); printf("§§\n"); printf("§┏━━━━━┓┏━━━━━┓┏━━━━━┓┏━━━━━┓§\n"); printf("§┃┃┃┃┃┃┃┃§\n"); printf("§┃┃┃┃┃┃┃┃§\n"); printf("§┃⒑男生宿舍┣┅┫⒒食堂┣┅┅┫⒓女生宿舍┣┅┅┫⒔教師村┃§\n"); printf("§┃┃┃┃┃┃┃┃§\n"); printf("§┃┃┃┃┃┃┃┃§\n"); printf("§┗━━┳━━┛┗━━┳━━┛┗━━┳━━┛┗━━━┳━┛§\n"); printf("§┏━━┻━━━━━━━┻━━━━━━━━┻━━━━━━━━━┇━┓§\n");printf("§┃┇┃§\n"); printf("§┃-----------⒐省高速路-----------┇-┃§\n");printf("§┃┇┃§\n");printf("§┗━━┳━━━━━━━━━━━━━━━━━━━━━━┳━━━┇━┛§\n"); printf("§┏━━┻━━┓┏━━━━━━━━━━━━┓┏┻━━━┻━┓§\n"); printf("§┃┃┃┃┃┃§\n"); printf("§┃┃┃┃┃┃§\n"); printf("§┃⒎琴房┣┅┅┫⒍圖書(shū)館