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

1、安徽省巢湖學(xué)院計算機與信息工程學(xué)院課程設(shè)計報告課程名稱 數(shù)據(jù)結(jié)構(gòu) 課題名稱 校園導(dǎo)航系統(tǒng) 專業(yè) 計算機科學(xué)與技術(shù) 班級 10計本2班 學(xué)號10012097 姓名 聯(lián)系方式 指導(dǎo)教師20 11 年 12 月 29 日目 錄1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書11.1、題目11.2、要求12、詳細(xì)設(shè)計12.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲結(jié)構(gòu)的說明12.2、算法的設(shè)計思想23、調(diào)試與測試：23.1、調(diào)試方法與步驟：23.2、測試結(jié)果的分析與討論：24、時間復(fù)雜度的分析：45、源程序清單和執(zhí)行結(jié)果56、c程序設(shè)計總結(jié)97、致謝108、參考文獻(xiàn)101、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書1.1、題目校園導(dǎo)航問題1.2、要求設(shè)

2、計你的學(xué)校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達(dá)另一場所的最佳路徑（最短路徑）。1）設(shè)計校園平面圖，在校園景點選10個左右景點。以圖中頂點表示校園內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等有關(guān)信息。2）為來訪客人提供圖中任意景點相關(guān)信息的查詢。3）為來訪客人提供任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一條最短路徑。2、詳細(xì)設(shè)計模塊功能說明：如函數(shù)功能、入口及出口參數(shù)說明，函數(shù)調(diào)用關(guān)系描述等；2.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲結(jié)構(gòu)的說明（1）圖。采用鄰接矩陣存儲，其中圖所用到的結(jié)構(gòu)體為：typedef

3、 struct seqlist vertices; /表示圖中的頂點int edgemaxverticesmaxvertices; /表示圖中的邊int numofedge; /表示圖中邊的數(shù)目adjmgraph;（2）景點。用順序表存儲。所用到的結(jié)構(gòu)體為： typedef struct char name20; /頂點名稱 int code; /頂點代號 char introduction50; /頂點信息簡介datatype; （3）景點之間的連接描述，所用到的結(jié)構(gòu)體為： typedef struct int row; int col; int weight;rowcolweight;用圖

4、來存放所提供的所有景點，然后用線性表來存放每一個景點的信息，其中包括景點的名稱，代號，信息簡介，以及其它的一些信息。這樣就將對景點的操作，變成對圖中各頂點的操作 。 2.2、算法的設(shè)計思想根據(jù)題目分析，對于信息查詢與修改功能，設(shè)計如下：1，輸入景點名稱2，從線性表頭掃描到表尾，if(找到該景點) 輸出景點結(jié)構(gòu)體信息else 輸出提示信息找不到該頂點實現(xiàn)查找最短路徑，設(shè)計如下：1， 景點名稱2，根據(jù)輸入的信息找到它們所在的線性表中的位置3，調(diào)用floyd算法找出最短路徑4，輸出信息3、調(diào)試與測試：3.1調(diào)試過程中遇到的問題與解決方案： 關(guān)于最短路徑的輸出問題。在進(jìn)行最短路徑輸出時，我剛開始時只能

5、正序輸出，具體的描述為：比如，我要查尋從東區(qū)到東湖的最短路徑，那么它能正確輸出結(jié)果，他的形式為：東區(qū) 主樓 西體育館 隧道 北大門 東湖。但是，當(dāng)我逆向輸出時，得到的結(jié)果卻有點問題，經(jīng)過分析調(diào)試后，找到了錯誤的所在。在找最短路徑的時候我用的是floyd算法，在這個算法中有三重循環(huán)，形式均為：for(k=0;kn;k+)，它們都是從零開始的，所以在順序輸出時沒問題，但是逆序的時候就需要進(jìn)行一個判斷，正序與逆序循環(huán)輸出是相反的。另外，在做這個題時也還出現(xiàn)過一些其他的小問題，不過都比較容易解決，這里我就不再列出了3.2、測試結(jié)果的分析與討論：（測試要寫出測試用例及每個用例結(jié)果的的截圖） 4、時間復(fù)雜

6、度的分析：1，相關(guān)信息的查詢。在這個操作中允許使用者輸入一個景點名稱，然后再根據(jù)景點名稱來或取其相關(guān)的信息，這個操作要掃描線性表，其時間復(fù)雜度為o(n)，空間復(fù)雜度為o(n)；2，最短路徑查詢。實現(xiàn)這個功能用到了floyd算法，他用到了一個三重的for()循環(huán)，故其時間復(fù)雜度為o(n3)，空間復(fù)雜度為o(1)；5、源程序清單和執(zhí)行結(jié)果(清單中應(yīng)有足夠的注釋)school.cpp /程序源文件adjmgraph.h /圖的相關(guān)操作頭文件adjmgraphcreat.h /創(chuàng)建圖的頭文件seqlist.h /線性表操作頭文件floyd.h /floyd算法頭文件operation.h /自己所定義

7、的一些操作的頭文件inquiry.h /查詢信息包含的頭文件/ 詳細(xì)school.cpp 程序源文件#include #include #include #define maxsize 20 /線性表的最大數(shù)組空間#define maxvertices 20 /景點個數(shù)所允許的最大值#define maxweight 1000 /無窮邊權(quán)值#include floyd.h #include adjmgraphcreat.h#include inquiry.hadjmgraph g;#include operation.hvoid main() /初始景點信息 datatype a=“學(xué)生第二食

8、堂,10,學(xué)生的主要就餐點,男生宿舍,11,一共有八棟,操場,12,最新的塑膠跑道和人工草坪 ,物理樓,13,擁有各種實驗器材,博學(xué)樓,14,學(xué)生上課集中地,草地,15,休閑娛樂的好地方,老教,16,學(xué)校最早的教學(xué)樓,女生宿舍,17,一共七棟,小門,18,可以通往半湯鎮(zhèn),圖書館,19,藏書50萬冊; /鄰接矩陣的表示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,4,10,5,6,35,5,8,8,

9、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;int n=10,e=28; /景點數(shù)與邊數(shù) creat(&g,a,rcw,n,e); /構(gòu)造圖 menu();/ 詳細(xì)floyd.h頭文件void floyd(int costmaxvertices,int n,int weightmaxvertices,int pathmaxvertices)/初始化int i,j,k;for(i=0;in;i+)for(j=0;jn;j+)weightij=costij;pathij=-1;/n次遞推for(k=0;kn;

10、k+)for(i=0;in;i+)for(j=0;jweightik+weightkj)weightij=weightik+weightkj;pathij=k;/詳細(xì)inquiry.h 頭文件void information(adjmgraph g, char scenery)int i;for(i=0;ig.vertices.size;i+)if(strcmp(g.,scenery)=0)printf(您輸入的景點的名稱是： %sn,g.);printf(您輸入的景點的代碼為： %dn,g.vertices.list

11、i.code);printf(您輸入的景點的相關(guān)信息有： %snn,g.roduction);break;if(i=g.vertices.size)printf(您所查詢的景點不在我們所提供的范圍內(nèi)！nn);void path(adjmgraph g,char sceneryname, char sceneryname1)int i,j,k,n,m,count=0;n=g.vertices.size;int weightmaxverticesmaxvertices,pathmaxverticesmaxvertices;int valuemaxvertices

12、;for(i=0;i%sn,sceneryname,sceneryname1); else while(m!=-1) valuecount=m;if(j,sceneryname);if(j=0;i-) printf(%s,g.); printf(%sn,sceneryname1);else for(i=0;i,g.); printf(%sn,sceneryname1);/詳細(xì)operation.h頭文件void menu();/查詢景點信息的函數(shù)void information1()char sce

13、neryname20; printf(請輸入您所想要查詢的景點的名稱： ); scanf(%s,sceneryname); information(g ,sceneryname);menu();/查詢最短路徑的函數(shù)void path1()char sceneryname20,sceneryname120;printf(請輸入你要查詢的兩景點的名稱： );scanf(%s%s,sceneryname,sceneryname1); path(g,sceneryname,sceneryname1);menu();printf(n);/菜單void menu()int n;puts(tt*菜單*n);

14、puts(ttt1,相關(guān)信息查詢);puts(ttt2,最短路徑查詢);puts(tt*n);printf(請選擇您想進(jìn)行的操作： );scanf(%d,&n);switch(n) case 1: information1(); break; case 2: path1();break;另外，還有adjmgraphcreat.h ，adjmgraph.h和seqlist.h 由于他們在書上已經(jīng)出現(xiàn)過了，這里我就不再把他們的源程序清單打印出來了 。6、c程序設(shè)計總結(jié)本程序在剛開始調(diào)試時有許多錯誤，但在我的努力及同學(xué)的幫助下都被一一克服，現(xiàn)在在操作本程序時可根據(jù)提示進(jìn)行相關(guān)操作，能正確輸出結(jié)果。在剛開始的幾次調(diào)試中曾經(jīng)出現(xiàn)過不能運行、不能產(chǎn)生十以內(nèi)隨機數(shù)字、不能隨機出現(xiàn)加減、不會正確輸出結(jié)果、不能進(jìn)行循環(huán)練習(xí)等等問題。經(jīng)過我的努力及同學(xué)的幫助，這些問題得到克服，并且使程序的功能也得到了一定的完善?，F(xiàn)在它能對出錯的題目發(fā)出報警聲，并且給出正確答案。最后還能分別輸出對錯的題數(shù)及所得分?jǐn)?shù)。在這次設(shè)計過程中，不僅復(fù)習(xí)課本上所學(xué)知識，還通過查資料、問同學(xué)學(xué)到了課本上沒有的知識。從而啟發(fā)我，要想寫好程序，在寫好課本知識的同時還需要多讀和專業(yè)有關(guān)的一些書籍，同時還需要多動腦子，盡量把所學(xué)的知識綜合起來應(yīng)用，力爭寫出完美的程序。除此