【正文】 t%c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c\n,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3)。 printf(\t\t%c\t\t學校概況\t\t%c\n,6,6)。 printf(\t\t%c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c\n,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3)。 for(i=1。iNUM。i++) { printf(\t\t%c\t\t(%2d)%20s%c\t\t\t,1,i,[i].sight,1)。 // 輸出景點列表 } printf(\t\t%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c\n\n,1,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,1)。}void ShortestPath(int num) // 迪杰斯特拉算法最短路徑函數(shù) num為入口點的編號 { int v,w,i,t。 // i、w和v為計數(shù)變量 int final[NUM]。 int min。 for(v=1。vNUM。v++) { final[v]=0。 // 假設從頂點num到頂點v沒有最短路徑 D[v]=[num][v].adj。// 將與之相關的權值放入D中存放 for(w=1。wNUM。w++) // 設置為空路徑 P[v][w]=0。 if(D[v]32767) // 存在路徑 { P[v][num]=1。 // 存在標志置為一 P[v][v]=1。 // 自身到自身 } } D[num]=0。 final[num]=1。 // 初始化num頂點屬于S集合 // 開始主循環(huán)，每一次求得num到某個頂點的最短路徑，并將其加入到S集合 for(i=1。iNUM。++i) // { min=Max。 // 當前所知離頂點num的最近距離 for(w=1。wNUM。++w) if(!final[w]) // w頂點在vs中 if(D[w]min) // w頂點離num頂點更近 { v=w。 min=D[w]。 } final[v]=1。 // 離num頂點更近的v加入到s集合 for(w=1。wNUM。++w) // 更新當前最短路徑極其距離 if(!final[w]amp。amp。((min+[v][w].adj)D[w]))// 不在s集合，并且比以前所找到的路徑都短就更新當前路徑 // { D[w]=min+[v][w].adj。 for(t=0。tNUM。t++) P[w][t]=P[v][t]。 P[w][w]=1。 } }}void output(int sight1,int sight2) // 輸出函數(shù) { int a,b,c,d,q=0。 a=sight2。 // 將景點二賦值給a if(a!=sight1) // 如果景點二不和景點一輸入重合，則進行... { printf(\n\t從%s到%s的最短路徑是,[sight1].sight,[sight2].sight)。// 輸出提示信息 printf(\t(最短距離為 %dm.)\n\n\t,D[a])。 // 輸出sight1到sight2的最短路徑長度，存放在D[]數(shù)組中 printf(\t%s,[sight1].sight)。 // 輸出景點一的名稱 d=sight1。 // 將景點一的編號賦值給d for(c=0。cNUM。++c) {gate:。 // 標號，可以作為goto語句跳轉的位置 P[a][sight1]=0。 for(b=0。bNUM。b++) { if([d][b].adj32767amp。amp。P[a][b]) // 如果景點一和它的一個臨界點之間存在路徑且最短路徑 { printf(%s,[b].sight)。 // 輸出此節(jié)點的名稱 q=q+1。 // 計數(shù)變量加一，滿8控制輸出時的換行 P[a][b]=0。 d=b。 // 將b作為出發(fā)點進行下一次循環(huán)輸出，如此反復 if(q%8==0) printf(\n)。 goto gate。 } } } }}第四章 測試與分析 測試數(shù)據(jù)選擇 測試結果分析在系統(tǒng)的設計中考慮到道路網的復雜性，故采用鄰接矩陣作為存儲結構，其空間復雜度為O（e）此時的空間復雜度也為O(e)。構建鄰接矩陣的時間復雜度為O（n2+e*n），故本系統(tǒng)在構件圖的時候的時間復雜度為O（n2+e*n）。由于本系統(tǒng)在執(zhí)行的時候，需要用戶臨時輸入求最短的路徑。迪杰斯特拉算法的時間復雜度比弗洛伊德算法的時間復雜度低。從這一角度考慮用地杰斯特拉算法更為合適。且其算法的時間復雜度為O（n3）.總 結特色：我們組在完成設計球最短路徑的函數(shù)后，又實現(xiàn)了交互界面的設計，方便用戶個不夠好的使用本程序進行在校導航。另外我們還實現(xiàn)了查詢校園中各景點間的距離以及信息查詢等功能。改進之處：在我們設計的導航系統(tǒng)中不能實現(xiàn)增加景點、刪除道路以及修改景點信息等功能。另外在見圖的時候算法的時間復雜度太大。如果能用鄰接多重表的存儲方式建立圖的其時間復雜度會更好，算法也更加先進?？偨Y：本次數(shù)據(jù)結構課程設計針對具體的項目來進行需求分析、測試計劃、概要設計、詳細設計、測試分析等具體的步驟走下來，我從中收獲巨大。首先在編寫函數(shù)之前要充分利用各種資源、其次。應該更詳細的考慮實際情況。才能使程序更具有實用性。當然更多的是組員之間要有合作的精神。編程是一件和枯燥的事情，但是只要我們認真的專研，我們會從中學到很多在課本上無法學到的東西，同時也能從中感受到編程的樂趣。在今后的工作、學習中我將認真總結經驗教訓，努力使自己成為一名技術過硬、工作嚴謹、思維活躍的工程人員，為提高人們的生活質量做出更大的貢獻。心得體會通過本次課程設計，我更熟練的應用了C語言中函數(shù)調用、函數(shù)聲明、函數(shù)自定義類型、全局變量、局部變量，以及數(shù)據(jù)結構中圖和迪杰斯特拉算法。圖能夠在計算機中存在，首先要知道他有哪些具體化、數(shù)字化的信息，比如說權值、頂點的個數(shù)等。這也就是說明了要想把生活中的信息轉化到計算機中必須用數(shù)字來完整的構成一個信息庫，而圖的存儲。又涉及到定點之間的聯(lián)系。圖分為有向圖和無向圖，而無向圖又是有向圖在權值雙向想等下的一種特例。而在系統(tǒng)中我所選用的數(shù)據(jù)結構就是無向有權圖。迪杰斯特拉算法始終都是核心內容，從頂點一步一步找最近的路線并與其直線距離相比較，但是，在計算機中實現(xiàn)這么一個簡單的想法就需要涉及到很多的專業(yè)知識。為了完成設計在前期的工作中基本都是以學習C語言為主，所以浪費了很多的時間。比如在程序中打印出最短路徑經過的景點。在起初的時候只能以數(shù)字代替景點的名稱。卻無法直接打出要經過的景點的名稱。最后通過查資料最終完成了程序的設計任務。通過課程設計 再次夯實了C語言基礎以及數(shù)據(jù)結構的應用能力，讓我看清了自己的能力以及不足之處，看到了以后編程該走的路找到了通向成功的航標。其實這次更大的收獲是編程必須有耐心，程序運行有很多漏洞不足是不可避免的，但是只要你有耐心，一步一步腳踏實地的做下去，一個一個語法的改總會成功。參考文獻 [1]嚴蔚敏、（C語言版）.北京:[2]++[3][4] 高寒弢. 30