版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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ù)書(shū)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)及存儲(chǔ)結(jié)構(gòu)的說(shuō)明1</p><p> 2.2、算法的設(shè)計(jì)思想2</p><p> 3、調(diào)試與測(cè)試:2</p><p> 3.1、調(diào)試方法與步驟:2</p><p> 3.2、測(cè)試結(jié)果的分析與討論:2</p><p> 4、時(shí)間復(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ù)書(shū)</p><p>
5、<b> 1.1、題目</b></p><p><b> 校園導(dǎo)航問(wèn)題</b></p><p><b> 1.2、要求</b></p><p> 設(shè)計(jì)你的學(xué)校的平面圖,至少包括10個(gè)以上的場(chǎng)所,每?jī)蓚€(gè)場(chǎng)所間可以有不同的路,且路長(zhǎng)也可能不同,找出從任意場(chǎng)所到達(dá)另一場(chǎng)所的最佳路徑(最短路徑)。&l
6、t;/p><p> 1)設(shè)計(jì)校園平面圖,在校園景點(diǎn)選10個(gè)左右景點(diǎn)。以圖中頂點(diǎn)表示校園內(nèi)各景點(diǎn),存放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息;以邊表示路徑,存放路徑長(zhǎng)度等有關(guān)信息。</p><p> 2)為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。</p><p> 3)為來(lái)訪客人提供任意景點(diǎn)的問(wèn)路查詢,即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短路徑。</p><p&g
7、t;<b> 2、詳細(xì)設(shè)計(jì)</b></p><p> 模塊功能說(shuō)明:如函數(shù)功能、入口及出口參數(shù)說(shuō)明,函數(shù)調(diào)用關(guān)系描述等;</p><p> 2.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)的說(shuō)明</p><p> ?。?)圖。采用鄰接矩陣存儲(chǔ),其中圖所用到的結(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)。用順序表存儲(chǔ)。所用到的結(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)代號(hào)</p><p> char introduction[50]; //頂點(diǎn)信息簡(jiǎn)介</p><p> }DataType; </p><p> (3)景點(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> 用圖來(lái)存放所提供的所有景點(diǎn),然后用線性表來(lái)存放每一個(gè)景點(diǎn)的信息,其中包括景點(diǎn)的名稱,代號(hào),信息簡(jiǎn)介,以及其它的一些信息。這樣就將對(duì)景點(diǎn)的操作,變成對(duì)圖中各頂點(diǎn)的操作 。 </p><p> 2.2、算法的設(shè)計(jì)思想</p><p> 根據(jù)題目分析,對(duì)于信息查詢與修改功能
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)試與測(cè)試:<
15、/b></p><p> 3.1調(diào)試過(guò)程中遇到的問(wèn)題與解決方案:</p><p> 關(guān)于最短路徑的輸出問(wèn)題。在進(jìn)行最短路徑輸出時(shí),我剛開(kāi)始時(shí)只能正序輸出,具體的描述為:比如,我要查尋從東區(qū)到東湖的最短路徑,那么它能正確輸出結(jié)果,他的形式為:東區(qū) ——>主樓 ——>西體育館 ——>隧道 ——>北大門(mén) ——>東湖。但是,當(dāng)我逆向輸出時(shí),得到的結(jié)果卻有點(diǎn)問(wèn)
16、題,經(jīng)過(guò)分析調(diào)試后,找到了錯(cuò)誤的所在。在找最短路徑的時(shí)候我用的是Floyd算法,在這個(gè)算法中有三重循環(huán),形式均為:for(k=0;k<n;k++),它們都是從零開(kāi)始的,所以在順序輸出時(shí)沒(méi)問(wèn)題,但是逆序的時(shí)候就需要進(jìn)行一個(gè)判斷,正序與逆序循環(huán)輸出是相反的。</p><p> 另外,在做這個(gè)題時(shí)也還出現(xiàn)過(guò)一些其他的小問(wèn)題,不過(guò)都比較容易解決,這里我就不再列出了……</p><p>
17、3.2、測(cè)試結(jié)果的分析與討論:</p><p> (測(cè)試要寫(xiě)出測(cè)試用例及每個(gè)用例結(jié)果的的截圖) </p><p> 4、時(shí)間復(fù)雜度的分析:</p><p> 1,相關(guān)信息的查詢。在這個(gè)操作中允許使用者輸入一個(gè)景點(diǎn)名稱,然后再根據(jù)景點(diǎn)名稱來(lái)或取其相關(guān)的信息,這個(gè)操作要掃描線性表,其時(shí)間復(fù)雜度為o(n),空間復(fù)雜度為o(n);</p><p
18、> 2,最短路徑查詢。實(shí)現(xiàn)這個(gè)功能用到了Floyd算法,他用到了一個(gè)三重的for()循環(huán),故其時(shí)間復(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)個(gè)數(shù)所允許的最大值</p><p&
22、gt; #define MaxWeight 1000 //無(wú)窮邊權(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,"一共有八棟"},{"操場(chǎng)",12,"最新的塑膠跑道和人工草坪"} ,{"物理樓",13,"擁有各種實(shí)驗(yàn)器材"},{"博學(xué)樓",14,"學(xué)生上課集中地
25、"},{"草地",15,"休閑娛樂(lè)的好地方"},{"老教",16,"學(xué)校最早的教學(xué)樓"},{"女生宿舍",17,"一共七棟"},{"小門(mén)",18,"可以通往半湯鎮(zhèn)"},{"圖書(shū)館",19,"藏書(shū)50萬(wàn)冊(cè)"}};</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("請(qǐng)輸入您所想要查詢的景點(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("請(qǐng)輸入你要查詢的兩景點(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("請(qǐng)選擇您想進(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 由于他們?cè)跁?shū)上已經(jīng)出現(xiàn)過(guò)了,這里我就不再把他們的源程序清單打印出來(lái)了 。</p><p><b> 6、C程序設(shè)計(jì)總結(jié)&l
63、t;/b></p><p> 本程序在剛開(kāi)始調(diào)試時(shí)有許多錯(cuò)誤,但在我的努力及同學(xué)的幫助下都被一一克服,現(xiàn)在在操作本程序時(shí)可根據(jù)提示進(jìn)行相關(guān)操作,能正確輸出結(jié)果。在剛開(kāi)始的幾次調(diào)試中曾經(jīng)出現(xiàn)過(guò)不能運(yùn)行、不能產(chǎn)生十以內(nèi)隨機(jī)數(shù)字、不能隨機(jī)出現(xiàn)加減、不會(huì)正確輸出結(jié)果、不能進(jìn)行循環(huán)練習(xí)等等問(wèn)題。經(jīng)過(guò)我的努力及同學(xué)的幫助,這些問(wèn)題得到克服,并且使程序的功能也得到了一定的完善?,F(xiàn)在它能對(duì)出錯(cuò)的題目發(fā)出報(bào)警聲,并且給出正
64、確答案。最后還能分別輸出對(duì)錯(cuò)的題數(shù)及所得分?jǐn)?shù)。</p><p> 在這次設(shè)計(jì)過(guò)程中,不僅復(fù)習(xí)課本上所學(xué)知識(shí),還通過(guò)查資料、問(wèn)同學(xué)學(xué)到了課本上沒(méi)有的知識(shí)。從而啟發(fā)我,要想寫(xiě)好程序,在寫(xiě)好課本知識(shí)的同時(shí)還需要多讀和專業(yè)有關(guān)的一些書(shū)籍,同時(shí)還需要多動(dòng)腦子,盡量把所學(xué)的知識(shí)綜合起來(lái)應(yīng)用,力爭(zhēng)寫(xiě)出完美的程序。除此之外,我還得到了一些有用的教訓(xùn):寫(xiě)程序時(shí)必須要細(xì)心,不能輸錯(cuò)一個(gè)字符標(biāo)點(diǎn),就連全角半角也得注意。在修改時(shí)要有耐
65、心,編譯出錯(cuò)后必須逐個(gè)錯(cuò)誤去改正,絕不能心急浮躁,否則修改之后還會(huì)有新的錯(cuò)誤。</p><p><b> 7、致謝</b></p><p> 能夠完成這次課程設(shè)計(jì)必須感謝C++語(yǔ)言課程老師徐榮泉、袁洪軍同學(xué)(他幫我修改了幾處重要錯(cuò)誤,同時(shí)啟發(fā)我完善了該程序的功能)。</p><p><b> 8、參考文獻(xiàn)</b>&l
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--校園導(dǎo)航系統(tǒng)
- 校園導(dǎo)航系統(tǒng)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--校園導(dǎo)航系統(tǒng)
- 校園導(dǎo)航系統(tǒng)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)導(dǎo)航系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)導(dǎo)航系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-校園導(dǎo)航
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)校園導(dǎo)航
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---校園導(dǎo)航問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)—校園導(dǎo)航問(wèn)題報(bào)告
- 校園導(dǎo)航系統(tǒng)課程設(shè)計(jì)
- 《校園導(dǎo)航系統(tǒng)》課程設(shè)計(jì)報(bào)告
- 校園導(dǎo)航系統(tǒng)課程設(shè)計(jì)報(bào)告
- 算法課程設(shè)計(jì)--校園導(dǎo)航系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)_校園導(dǎo)游系統(tǒng)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---校園導(dǎo)游系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu) 校園導(dǎo)游系統(tǒng)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)導(dǎo)航圖
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---校園導(dǎo)游系統(tǒng)設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---校園交通導(dǎo)游系統(tǒng)
評(píng)論
0/150
提交評(píng)論