數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-校園導(dǎo)航系統(tǒng)

1、<p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　課程名稱 《數(shù)據(jù)結(jié)構(gòu)》 </p><p>　　課題名稱 校園導(dǎo)航系統(tǒng) </p><p>　　專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) </p><p><b>　　目

2、 錄</b></p><p>　　1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書1</p><p><b>　　1.1、題目1</b></p><p><b>　　1.2、要求1</b></p><p><b>　　2、詳細(xì)設(shè)計(jì)1</b></p><p&

3、gt;　　2.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲結(jié)構(gòu)的說明1</p><p>　　2.2、算法的設(shè)計(jì)思想2</p><p>　　3、調(diào)試與測試：2</p><p>　　3.1、調(diào)試方法與步驟：2</p><p>　　3.2、測試結(jié)果的分析與討論：2</p><p>　　4、時間復(fù)雜度的分析：4</p&g

4、t;<p>　　5、源程序清單和執(zhí)行結(jié)果5</p><p>　　6、C程序設(shè)計(jì)總結(jié)9</p><p><b>　　7、致謝10</b></p><p><b>　　8、參考文獻(xiàn)10</b></p><p>　　1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書</p><p>

5、<b>　　1.1、題目</b></p><p><b>　　校園導(dǎo)航問題</b></p><p><b>　　1.2、要求</b></p><p>　　設(shè)計(jì)你的學(xué)校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達(dá)另一場所的最佳路徑（最短路徑）。&l

6、t;/p><p>　　1）設(shè)計(jì)校園平面圖，在校園景點(diǎn)選10個左右景點(diǎn)。以圖中頂點(diǎn)表示校園內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等有關(guān)信息。</p><p>　　2）為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。</p><p>　　3）為來訪客人提供任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€景點(diǎn)之間的一條最短路徑。</p><p&g

7、t;<b>　　2、詳細(xì)設(shè)計(jì)</b></p><p>　　模塊功能說明：如函數(shù)功能、入口及出口參數(shù)說明，函數(shù)調(diào)用關(guān)系描述等；</p><p>　　2.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲結(jié)構(gòu)的說明</p><p>　?。?）圖。采用鄰接矩陣存儲，其中圖所用到的結(jié)構(gòu)體為：</p><p>　　typedef struct &

8、lt;/p><p><b>　　{</b></p><p>　　SeqList vertices; //表示圖中的頂點(diǎn)</p><p>　　int Edge[MaxVertices][MaxVertices]; //表示圖中的邊</p><p>　　int numOfEdge;

9、 //表示圖中邊的數(shù)目</p><p>　　}AdjMGraph;</p><p>　?。?）景點(diǎn)。用順序表存儲。所用到的結(jié)構(gòu)體為：</p><p>　　typedef struct </p><p><b>　　{</b></p><p>　　char name[2

10、0]; //頂點(diǎn)名稱</p><p>　　int code; //頂點(diǎn)代號</p><p>　　char introduction[50]; //頂點(diǎn)信息簡介</p><p>　　}DataType; </p><p>　?。?）景點(diǎn)之間的連接描述，所用到的結(jié)構(gòu)體為

11、：</p><p>　　typedef struct </p><p><b>　　{</b></p><p><b>　　int row;</b></p><p><b>　　int col;</b></p><p>　　int weight;<

12、;/p><p>　　}RowColWeight;</p><p>　　用圖來存放所提供的所有景點(diǎn)，然后用線性表來存放每一個景點(diǎn)的信息，其中包括景點(diǎn)的名稱，代號，信息簡介，以及其它的一些信息。這樣就將對景點(diǎn)的操作，變成對圖中各頂點(diǎn)的操作 。 </p><p>　　2.2、算法的設(shè)計(jì)思想</p><p>　　根據(jù)題目分析，對于信息查詢與修改功能

13、，設(shè)計(jì)如下：</p><p><b>　　1，輸入景點(diǎn)名稱</b></p><p>　　2，從線性表頭掃描到表尾，</p><p>　　if(找到該景點(diǎn)) 輸出景點(diǎn)結(jié)構(gòu)體信息</p><p>　　else 輸出提示信息找不到該頂點(diǎn)</p><p>　　實(shí)現(xiàn)查找最短路徑，設(shè)計(jì)如下：</p&g

14、t;<p><b>　　1， 景點(diǎn)名稱</b></p><p>　　2，根據(jù)輸入的信息找到它們所在的線性表中的位置</p><p>　　3，調(diào)用Floyd算法找出最短路徑</p><p><b>　　4，輸出信息</b></p><p><b>　　3、調(diào)試與測試：<

15、/b></p><p>　　3.1調(diào)試過程中遇到的問題與解決方案：</p><p>　　關(guān)于最短路徑的輸出問題。在進(jìn)行最短路徑輸出時，我剛開始時只能正序輸出，具體的描述為：比如，我要查尋從東區(qū)到東湖的最短路徑，那么它能正確輸出結(jié)果，他的形式為：東區(qū) ——>主樓 ——>西體育館 ——>隧道 ——>北大門 ——>東湖。但是，當(dāng)我逆向輸出時，得到的結(jié)果卻有點(diǎn)問

16、題，經(jīng)過分析調(diào)試后，找到了錯誤的所在。在找最短路徑的時候我用的是Floyd算法，在這個算法中有三重循環(huán)，形式均為：for(k=0;k<n;k++)，它們都是從零開始的，所以在順序輸出時沒問題，但是逆序的時候就需要進(jìn)行一個判斷，正序與逆序循環(huán)輸出是相反的。</p><p>　　另外，在做這個題時也還出現(xiàn)過一些其他的小問題，不過都比較容易解決，這里我就不再列出了……</p><p>　　

17、3.2、測試結(jié)果的分析與討論：</p><p>　?。y試要寫出測試用例及每個用例結(jié)果的的截圖） </p><p>　　4、時間復(fù)雜度的分析：</p><p>　　1，相關(guān)信息的查詢。在這個操作中允許使用者輸入一個景點(diǎn)名稱，然后再根據(jù)景點(diǎn)名稱來或取其相關(guān)的信息，這個操作要掃描線性表，其時間復(fù)雜度為o(n)，空間復(fù)雜度為o(n)；</p><p

18、>　　2，最短路徑查詢。實(shí)現(xiàn)這個功能用到了Floyd算法，他用到了一個三重的for()循環(huán)，故其時間復(fù)雜度為o(n^3)，空間復(fù)雜度為o(1)；</p><p>　　5、源程序清單和執(zhí)行結(jié)果</p><p>　　(清單中應(yīng)有足夠的注釋)</p><p>　　school.cpp //程序源文件</p><p&g

19、t;　　AdjMGraph.h //圖的相關(guān)操作頭文件</p><p>　　AdjMGraphCreat.h //創(chuàng)建圖的頭文件</p><p>　　SeqList.h //線性表操作頭文件</p><p>　　Floyd.h //Floyd算法頭文件</p>

20、<p>　　Operation.h //自己所定義的一些操作的頭文件</p><p>　　Inquiry.h //查詢信息包含的頭文件</p><p>　　// 詳細(xì)school.cpp 程序源文件</p><p>　　#include <stdio.h></p><p&g

21、t;　　#include <string.h></p><p>　　#include <malloc.h></p><p>　　#define MaxSize 20 //線性表的最大數(shù)組空間</p><p>　　#define MaxVertices 20 //景點(diǎn)個數(shù)所允許的最大值</p><p&

22、gt;　　#define MaxWeight 1000 //無窮邊權(quán)值</p><p>　　#include "Floyd.h" </p><p>　　#include "AdjMGraphCreat.h"</p><p>　　#include "Inquiry.h"</p><

23、p>　　AdjMGraph G;</p><p>　　#include "Operation.h"</p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　//初始景點(diǎn)信息 </b></p><p&

24、gt;　　DataType a[]={{“學(xué)生第二食堂",10,"學(xué)生的主要就餐點(diǎn)"},{"男生宿舍",11,"一共有八棟"},{"操場",12,"最新的塑膠跑道和人工草坪"} ,{"物理樓",13,"擁有各種實(shí)驗(yàn)器材"},{"博學(xué)樓",14,"學(xué)生上課集中地

25、"},{"草地",15,"休閑娛樂的好地方"},{"老教",16,"學(xué)校最早的教學(xué)樓"},{"女生宿舍",17,"一共七棟"},{"小門",18,"可以通往半湯鎮(zhèn)"},{"圖書館",19,"藏書50萬冊"}};</p>

26、<p><b>　　//鄰接矩陣的表示</b></p><p>　　RowColWeightrcw[]={{0,1,20},{0,2,30},{0,3,35},{1,0,20},{1,3,20},{2,0,30},{2,3,15},{2,4,30},{3,0,35},{3,1,20},{3,2,15},{3,4,30},{4,2,30},{4,3,30},{4,5,10},{5

27、,4,10},{5,6,35}</p><p>　　,{5,8,8},{6,5,35},{6,7,20},{6,8,25},{6,9,5},{7,6,20},{7,8,10},{8,5,8},{8,6,25},{8,7,10},{9,6,5};</p><p>　　int n=10,e=28; //景點(diǎn)數(shù)與邊數(shù)</p><p>　　Creat(&G

28、,a,rcw,n,e); //構(gòu)造圖</p><p><b>　　menu();</b></p><p><b>　　}</b></p><p>　　// 詳細(xì)Floyd.h頭文件</p><p>　　void Floyd(int cost[][MaxVertices],int n,int we

29、ight[][MaxVertices],int path[][MaxVertices])</p><p><b>　　{</b></p><p><b>　　//初始化</b></p><p>　　int i,j,k;</p><p>　　for(i=0;i<n;i++)</p>

30、<p><b>　　{</b></p><p>　　for(j=0;j<n;j++)</p><p><b>　　{</b></p><p>　　weight[i][j]=cost[i][j];</p><p>　　path[i][j]=-1;</p><p&g

31、t;<b>　　}</b></p><p><b>　　}</b></p><p><b>　　//n次遞推</b></p><p>　　for(k=0;k<n;k++)</p><p><b>　　{</b></p><p>

32、;　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　for(j=0;j<n;j++)</p><p><b>　　{</b></p><p>　　if(weight[i][j]>weight[i][k]+weight[k][j])&l

33、t;/p><p><b>　　{</b></p><p>　　weight[i][j]=weight[i][k]+weight[k][j];</p><p>　　path[i][j]=k;</p><p><b>　　}</b></p><p><b>　　}</

34、b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//詳細(xì)Inquiry.h 頭文件</p><p>　　void Information(AdjMG

35、raph G, char scenery[])</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　for(i=0;i<G.vertices.size;i++)</p><p><b>　　{</b></p&

36、gt;<p>　　if(strcmp(G.vertices.list[i].name,scenery)==0)</p><p><b>　　{</b></p><p>　　printf("您輸入的景點(diǎn)的名稱是： %s\n",G.vertices.list[i].name);</p><p>　　printf(&

37、quot;您輸入的景點(diǎn)的代碼為： %d\n",G.vertices.list[i].code);</p><p>　　printf("您輸入的景點(diǎn)的相關(guān)信息有： %s\n\n",G.vertices.list[i].introduction);</p><p><b>　　break;</b></p><p>&l

38、t;b>　　}</b></p><p><b>　　}</b></p><p>　　if(i==G.vertices.size)</p><p><b>　　{</b></p><p>　　printf("您所查詢的景點(diǎn)不在我們所提供的范圍內(nèi)！\n\n");&l

39、t;/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void Path(AdjMGraph G,char sceneryname[], char sceneryname1[])</p><p><b>　　{</b></p&g

40、t;<p>　　int i,j,k,n,m,count=0;</p><p>　　n=G.vertices.size;</p><p>　　int weight[MaxVertices][MaxVertices],path[MaxVertices][MaxVertices];</p><p>　　int value[MaxVertices];</

41、p><p>　　for(i=0;i<G.vertices.size;i++)</p><p><b>　　{</b></p><p>　　if(strcmp(G.vertices.list[i].name,sceneryname)==0)</p><p><b>　　{</b></p>

42、<p><b>　　j=i;</b></p><p><b>　　}</b></p><p>　　if(strcmp(G.vertices.list[i].name,sceneryname1)==0)</p><p><b>　　{</b></p><p><

43、;b>　　k=i;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　Floyd(G.Edge,n,weight,path);</p><p>　　m=path[j][k];</p><p>　　pr

44、intf("最短路徑為： %d\n",weight[j][k]);</p><p><b>　　if(m==-1)</b></p><p><b>　　{</b></p><p>　　printf("從 %s 點(diǎn)到 %s 景點(diǎn)的最短路徑為：\n",sceneryname,scener

45、yname1);</p><p>　　printf("%s ——>%s\n",sceneryname,sceneryname1);</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b&g

46、t;</p><p>　　while(m!=-1)</p><p><b>　　{</b></p><p>　　value[count]=m;</p><p>　　if(j<k)k=m;</p><p>　　else j=m;</p><p>　　m=path

47、[j][k];</p><p><b>　　count++;</b></p><p><b>　　}</b></p><p>　　printf("從 %s 點(diǎn)到 %s 景點(diǎn)的最短路徑為：\n",sceneryname,sceneryname1);</p><p>　　printf

48、("%s——>",sceneryname);</p><p><b>　　if(j<k)</b></p><p><b>　　{</b></p><p>　　for(i=count-1;i>=0;i--)</p><p><b>　　{</b&

49、gt;</p><p>　　printf("%s——>",G.vertices.list[value[i]].name);</p><p><b>　　}</b></p><p>　　printf("%s\n",sceneryname1);</p><p><b>

50、　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　for(i=0;i<count;i++)</p><p><b>　　{</b></p><p>　　print

51、f("%s——>",G.vertices.list[value[i]].name);</p><p><b>　　}</b></p><p>　　printf("%s\n",sceneryname1);</p><p><b>　　}</b></p><p&

52、gt;<b>　　}</b></p><p><b>　　}</b></p><p>　　//詳細(xì)Operation.h頭文件</p><p>　　void menu();</p><p>　　//查詢景點(diǎn)信息的函數(shù)</p><p>　　void Information1()

53、</p><p><b>　　{</b></p><p>　　char sceneryname[20];</p><p>　　printf("請輸入您所想要查詢的景點(diǎn)的名稱： ");</p><p>　　scanf("%s",sceneryname);</p>&l

54、t;p>　　Information(G ,sceneryname);</p><p><b>　　menu();</b></p><p><b>　　}</b></p><p>　　//查詢最短路徑的函數(shù)</p><p>　　void Path1()</p><p>&

55、lt;b>　　{</b></p><p>　　char sceneryname[20],sceneryname1[20];</p><p>　　printf("請輸入你要查詢的兩景點(diǎn)的名稱： ");</p><p>　　scanf("%s%s",sceneryname,sceneryname1);</

56、p><p>　　Path(G,sceneryname,sceneryname1);</p><p><b>　　menu();</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　

57、　//菜單</b></p><p>　　void menu()</p><p><b>　　{</b></p><p><b>　　int n;</b></p><p>　　puts("\t\t****************菜單**********************\n

58、");</p><p>　　puts("\t\t\t1,相關(guān)信息查詢");</p><p>　　puts("\t\t\t2,最短路徑查詢");</p><p>　　puts("\t\t*******************************************\n");</p>

59、;<p>　　printf("請選擇您想進(jìn)行的操作： ");</p><p>　　scanf("%d",&n);</p><p><b>　　switch(n)</b></p><p><b>　　{</b></p><p><b&

60、gt;　　case 1:</b></p><p><b>　　{</b></p><p>　　Information1();</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b

61、>　　case 2:</b></p><p><b>　　{</b></p><p><b>　　Path1();</b></p><p><b>　　break;</b></p><p><b>　　}</b></p>&

62、lt;p><b>　　}</b></p><p><b>　　}</b></p><p>　　另外，還有AdjMGraphCreat.h ，AdjMGraph.h和SeqList.h 由于他們在書上已經(jīng)出現(xiàn)過了，這里我就不再把他們的源程序清單打印出來了 。</p><p><b>　　6、C程序設(shè)計(jì)總結(jié)&l

63、t;/b></p><p>　　本程序在剛開始調(diào)試時有許多錯誤，但在我的努力及同學(xué)的幫助下都被一一克服，現(xiàn)在在操作本程序時可根據(jù)提示進(jìn)行相關(guān)操作，能正確輸出結(jié)果。在剛開始的幾次調(diào)試中曾經(jīng)出現(xiàn)過不能運(yùn)行、不能產(chǎn)生十以內(nèi)隨機(jī)數(shù)字、不能隨機(jī)出現(xiàn)加減、不會正確輸出結(jié)果、不能進(jìn)行循環(huán)練習(xí)等等問題。經(jīng)過我的努力及同學(xué)的幫助，這些問題得到克服，并且使程序的功能也得到了一定的完善?，F(xiàn)在它能對出錯的題目發(fā)出報(bào)警聲，并且給出正

64、確答案。最后還能分別輸出對錯的題數(shù)及所得分?jǐn)?shù)。</p><p>　　在這次設(shè)計(jì)過程中，不僅復(fù)習(xí)課本上所學(xué)知識，還通過查資料、問同學(xué)學(xué)到了課本上沒有的知識。從而啟發(fā)我，要想寫好程序，在寫好課本知識的同時還需要多讀和專業(yè)有關(guān)的一些書籍，同時還需要多動腦子，盡量把所學(xué)的知識綜合起來應(yīng)用，力爭寫出完美的程序。除此之外，我還得到了一些有用的教訓(xùn)：寫程序時必須要細(xì)心，不能輸錯一個字符標(biāo)點(diǎn)，就連全角半角也得注意。在修改時要有耐

65、心，編譯出錯后必須逐個錯誤去改正，絕不能心急浮躁，否則修改之后還會有新的錯誤。</p><p><b>　　7、致謝</b></p><p>　　能夠完成這次課程設(shè)計(jì)必須感謝C++語言課程老師徐榮泉、袁洪軍同學(xué)（他幫我修改了幾處重要錯誤，同時啟發(fā)我完善了該程序的功能）。</p><p><b>　　8、參考文獻(xiàn)</b>&l