數(shù)據(jù)結構課程設計-校園導航系統(tǒng)

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

2、 錄</b></p><p>　　1、數(shù)據(jù)結構課程設計任務書1</p><p><b>　　1.1、題目1</b></p><p><b>　　1.2、要求1</b></p><p><b>　　2、詳細設計1</b></p><p&

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、t;　　AdjMGraph.h //圖的相關操作頭文件</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>　　// 詳細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 //景點個數(shù)所允許的最大值</p><p&

22、gt;　　#define MaxWeight 1000 //無窮邊權值</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>　　//初始景點信息 </b></p><p&

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

25、"},{"草地",15,"休閑娛樂的好地方"},{"老教",16,"學校最早的教學樓"},{"女生宿舍",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; //景點數(shù)與邊數(shù)</p><p>　　Creat(&G

28、,a,rcw,n,e); //構造圖</p><p><b>　　menu();</b></p><p><b>　　}</b></p><p>　　// 詳細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>　　//詳細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("您輸入的景點的名稱是： %s\n",G.vertices.list[i].name);</p><p>　　printf(&

37、quot;您輸入的景點的代碼為： %d\n",G.vertices.list[i].code);</p><p>　　printf("您輸入的景點的相關信息有： %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("您所查詢的景點不在我們所提供的范圍內！\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 點到 %s 景點的最短路徑為：\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 點到 %s 景點的最短路徑為：\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>　　//詳細Operation.h頭文件</p><p>　　void menu();</p><p>　　//查詢景點信息的函數(shù)</p><p>　　void Information1()

53、</p><p><b>　　{</b></p><p>　　char sceneryname[20];</p><p>　　printf("請輸入您所想要查詢的景點的名稱： ");</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("請輸入你要查詢的兩景點的名稱： ");</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,相關信息查詢");</p><p>　　puts("\t\t\t2,最短路徑查詢");</p><p>　　puts("\t\t*******************************************\n");</p>

59、;<p>　　printf("請選擇您想進行的操作： ");</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 由于他們在書上已經出現(xiàn)過了，這里我就不再把他們的源程序清單打印出來了 。</p><p><b>　　6、C程序設計總結&l

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

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

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