校園最短路徑問題研究報告與實現(xiàn)

1、個人資料整理 僅限學(xué)習(xí)使用校園最短路徑問題的研究與實現(xiàn)學(xué)生姓名：指導(dǎo)老師：摘 要 本課程設(shè)計主要解決求的校園任意地點問最短路徑的問題。在本程序中，對于任意一個 起點，如果不確定具體的終點，則以表格形式輸出從起點到其他各地點的最短路徑長度以及途經(jīng) 哪些地點；如果用戶確定終點，則只輸出從起點到具體地點的最短路徑長度以及途經(jīng)哪些地 點。同時還能實現(xiàn)對校園路徑圖的修改功能，如頂點以及邊的增刪、邊上權(quán)值的修改等。在程 序設(shè)計中，采用Visual C+程序設(shè)計語言，以及 Microsoft Visual C+ 6.0開發(fā)平臺進(jìn)行開發(fā)實 現(xiàn)。關(guān)鍵詞 校園最短路徑；起點；終點；路徑圖修改； C+目錄 TOC

2、o 1-5 h z HYPERLINK l bookmark16 o Current Document 1引言 3 HYPERLINK l bookmark18 o Current Document 課程設(shè)計目的 3 HYPERLINK l bookmark20 o Current Document 概要設(shè)計 3 HYPERLINK l bookmark8 o Current Document .詳細(xì)設(shè)計 5 HYPERLINK l bookmark24 o Current Document 功能流程圖 5 HYPERLINK l bookmark28 o Current Document 類

3、的定義 5 HYPERLINK l bookmark42 o Current Document 功能函數(shù)實現(xiàn) 7 HYPERLINK l bookmark55 o Current Document 算法分析 .14 HYPERLINK l bookmark57 o Current Document 程序調(diào)試 .14 HYPERLINK l bookmark59 o Current Document .測試運行 .16 HYPERLINK l bookmark61 o Current Document 開始界面測試 .16 HYPERLINK l bookmark53 o Current Doc

4、ument 輸出頂點信息功能測試 .16 HYPERLINK l bookmark63 o Current Document 輸出邊信息功能測試 .16 HYPERLINK l bookmark74 o Current Document 修改功能測試 .17個人資料整理 僅限學(xué)習(xí)使用 TOC o 1-5 h z HYPERLINK l bookmark81 o Current Document 求最短路徑功能測破 .17 HYPERLINK l bookmark92 o Current Document 刪除頂點功能測試 .18 HYPERLINK l bookmark106 o Curren

5、t Document 插入頂點功能測試 .19 HYPERLINK l bookmark116 o Current Document 刪除邊功能測試 .19 HYPERLINK l bookmark129 o Current Document 插入邊功能測試 .20 HYPERLINK l bookmark142 o Current Document 退出程序測試 21 HYPERLINK l bookmark150 o Current Document .結(jié)束語 .23 HYPERLINK l bookmark152 o Current Document 參考文獻(xiàn) .24附錄：程序清單.25

6、1引言本課程設(shè)計主要解決校園最短路徑的求取，校園中的各具體地點作為頂點，各頂點間的路 徑作為邊，可實現(xiàn)對頂點及邊的信息進(jìn)行添加、刪除及修改等功能，可顯示各頂點及邊的信 息，可求出每一對頂點間的最短路徑和單源點最短路徑1。課程設(shè)計目的.了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；.初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；.提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；4訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)工作方法和作風(fēng)20概要設(shè)計.問題描述圖的最短路徑問題是指從指定的某一點 v開始，求得從

7、該地點到圖中其它各地點的最短路 徑。并且給出求得的最短路徑的長度及途徑的地點。除了完成最短路徑的求解外，還能對該圖 進(jìn)行修改，如頂點以及邊的增刪、邊上權(quán)值的修改等。校園最短路徑問題中的數(shù)據(jù)元素有：1）頂點數(shù)2）邊數(shù)3）邊的長度.功能需求個人資料整理 僅限學(xué)習(xí)使用要求完成以下功能：1）輸出頂點信息：將校園內(nèi)各位置輸出。2）輸出邊的信息：將校園內(nèi)每兩個位置 若兩個位置之間有直接路徑）的距離輸出。3）修改：修改兩個位置 若兩個位置之間有直接路徑）的距離，并重新輸出每兩個位置若兩個位置之間有直接路徑）的距離；4）求最短路徑：輸出給定兩點之間的最短路徑的長度及途經(jīng)的地點或輸出任意一點與其 他各點的最短路

8、徑。5）刪除：刪除任意一條邊。6）插入：插入任意一條邊。.實現(xiàn)要點1）對圖的創(chuàng)建采用鄰接矩陣的存儲結(jié)構(gòu)，而且對圖的操作設(shè)計成了模板類。為了便于處 理，對于圖中的每一個頂點和每一條邊均設(shè)置了初值。2）為了便于訪問，用戶可以先輸出所有的地點及距離。3）用戶可以隨意修改任意兩點之間的距離。4）用戶可以任意增加及刪除邊。5）當(dāng)用戶操作錯誤時，系統(tǒng)會出現(xiàn)出錯提示。.方案設(shè)計本程序采用Dijkstra算法實現(xiàn)最短路徑的求解，因此，校園分布圖采用鄰接矩陣進(jìn)行存 儲。在主程序中以菜單方式給出提示，進(jìn)入各功能要求用戶輸入現(xiàn)在的位置，以及是否有確定 的重點。主程序中對該圖進(jìn)行初始化，有一定的實驗數(shù)據(jù)3o2詳細(xì)設(shè)計

9、功能流程圖個人資料整理 僅限學(xué)習(xí)使用 畫2.1索經(jīng)叨能流源百類的定義其類定義如下:圖中最多頂點個數(shù)為構(gòu)建圖及最短路徑建立了圖的類其類定義如下:圖中最多頂點個數(shù)const int MaxSize=12。template class T class Graph ( public:/構(gòu)造函數(shù)，初始化具有/構(gòu)造函數(shù)，初始化具有n個頂點的圖/最小距離/修改路徑/刪除頂點pos的信息/在num的位置上插入一頂點，值為 name/4圖中刪除一條邊，其依附的兩個頂點的編號為i/4圖中插入一條邊，其依附的兩個頂點的編號Graph( 析構(gòu)函數(shù)void Dijkstra( int v,int endv。void P

10、utOutVexInfo(。/取頂點信息void PutOutArcInfo(。 輸出路徑void SetArc(int v1,int v2,int arclengthvoid DeleteVex(int pos。void InsertVex(int num,T name%void DeleteArc(int i, int j。和jvoid InsertArc(int i, int j,int n。為i和jprivate:/存放圖中頂點的數(shù)組/存放圖中邊的數(shù)組圖的頂點數(shù)和邊數(shù)/存放圖中頂點的數(shù)組/存放圖中邊的數(shù)組圖的頂點數(shù)和邊數(shù)int vertexNum。#endif在圖的類中，提供了如下成員

11、函數(shù)：1）函數(shù)聲明：Graph完成的功能：構(gòu)造函數(shù)，初始化具有 n個頂點的圖2）函數(shù)聲明：void Dijkstra完成的功能：求最短距離3）函數(shù)聲明：PutOutVexInfo完成的功能：取頂點信息個人資料整理 僅限學(xué)習(xí)使用4）函數(shù)聲明：PutOutArcInfo完成的功能：取邊信息5）函數(shù)聲明：SetArc完成的功能：修改路徑6）函數(shù)聲明：DeleteVex 完成的功能：刪除某頂點的信息7）函數(shù)聲明：InsertVex完成的功能：插入某個頂點8）函數(shù)聲明：DeleteArc 完成的功能：刪除某邊的信息9）函數(shù)聲明：InsertArc完成的功能：插入某邊及相應(yīng)頂點2.3功能函數(shù)實現(xiàn).構(gòu)造函數(shù)

12、定義 前置條件：圖不存在 輸入：無功能：圖的初始化輸出：無后置條件：構(gòu)造一個有值的圖Graph二Graph（int* a,T* v, int n 構(gòu)造圖int i,j。vertexNum=n。頌點數(shù)初始化鄰接矩陣/定義邊有儲頂點信息/船邊賦置初始化鄰接矩陣/定義邊有儲頂點信息/船邊賦置for (j=0 o j arcij = 10000。for ( i=0 o i vertexi=vi。for (i=0 o ifor (j=0 o jvvertexNum。j+ arcij=*(a+i*n+jint tt=0o個人資料整理 僅限學(xué)習(xí)使用).取頂點信息函數(shù)定義前置條件：圖已存在輸入：無功能：輸出圖

13、中所有頂點的數(shù)據(jù)信息輸出：圖中所有頂點的數(shù)據(jù)信息后置條件：圖保持不變void Graph:PutOutVexInfo(/瞰頂點(int i=0o川貿(mào)設(shè)源點是第0個頂點，即頂點序號是0if (ivertexNum throw 位置。/錯誤拋出異常elsefor(i=0。i輸出圖中所有的頂點coutvertexin。).修改路徑函數(shù)定義前置條件：圖已存在輸入：頂點v1,v2能：修改頂點v1、v2的路徑輸出：修改后圖中所有的路徑后置條件：圖保持不變void Graph:SetArc(int v1,int v2,int arclength/修改路徑/假設(shè)源點是第0個頂點，即頂點序號是0if ( v1v

14、ertexNum| v2vertexNum throw 位置。錯誤拋出異常else arcv1v2=arclength。/修改v1頂點到v2頂點的距離arcv2v1=arclength。).取邊函數(shù)定義前置條件：圖已存在輸入：無功能：輸出圖中所有的路徑個人資料整理 僅限學(xué)習(xí)使用輸出：圖中所有頂點的數(shù)據(jù)信息后置條件：圖保持不變void Graph:PutOutArcInfo(輸出圖中所有的路徑( int i=0o/假設(shè)源點是第0個頂點，即頂點序號是0int j=0o if ( ivertexNum| jvertexNum throw 位置。 錯誤拋出異常 else for(i=0。i輸出任意兩點

15、之間的路徑for(j=0o j if(arcij/兩點之間存在路徑cout從vertexi至vertexj的路徑長度為：arcijn 。/偌兩點間有路，則輸出該兩點間的路徑 .插入頂點函數(shù)定義 前置條件：圖已存在 輸入：頂點name位置i 功能：在圖中i位置插入一個頂點name輸出：如果插入不成功，拋出異常后置條件：如果插入成功，圖中增加了一個頂點void Graph:InsertVex(int num,T name /作圖中插入一個頂點，其編號為i,值為 value/汝口果num輸入不正確拋出異常 /假設(shè)源點是第0/汝口果num輸入不正確拋出異常if ( numvertexNum throw

16、 位置。int row。/行例/最后一個頂點所在的位置/num例/最后一個頂點所在的位置/num存在/頂點數(shù)加1/i從最后一個頂點的下一個位置開始循環(huán)int numv。numv = vertexNum-1。if(num-1vertexNum+0for(int i=numv。inum-1。i-vertexi=vertexi-1。的巴從vertexi=vertexi-1。的巴從num位置的頂點到最后一個頂點均向后移一位個人資料整理 僅限學(xué)習(xí)使用vertexnum=name。/后巴要插入的頂點的值放在 num位置上for(row=numv。row=0。row- 把從 num 列到最后一列的元素均向下

17、移一列 (for(col=numv。col=num。個人資料整理 僅限學(xué)習(xí)使用vertexnum=name。/后巴要插入的頂點的值放在 num位置上for(row=numv。row=0。row- 把從 num 列到最后一列的元素均向下移一列 (for(col=numv。col=num。col-arcrowcol+1=arcrowcol。arcrownum=10000。for(row=numv。row=num。 row- /把從 num行到最后一行的元素均向下移一行for(col=0 o colarcrow+1col=arcrowcol。for(col=0 o colarcnumcol=1000

18、0。/后巴num位置所在的行、列的值均置為無窮大6.刪除頂點函數(shù)的定義前置條件：圖已存在輸入：頂點pos功能：在圖中刪除頂點pos輸出：如果刪除不成功，拋出異常后置條件：如果刪除成功，圖中減少了一個頂點，相應(yīng)頂點所建立的邊也消去void Graph二DeleteVex(int pos/刪除第 pos個頂點 /假設(shè)源點是第0個頂點，即頂點序號是0if ( posMaxSize throw 位置。/收口果pos輸入不正確拋出異常int row。int col oint numv=vertexNum。/numv等于頂點數(shù)if(pos-1/pos# 在for(int i=pos。ivertexi=ve

19、rtexi+1。/把從pos到最后的每個點的位置依次向前移一位vertexNum-。頒點數(shù)減1for(row=0 o row/把從pos列到最后一列的元素均向前移一列for(col=pos。/把從pos列到最后一列的元素均向前移一列arcrowcol=arcrowcol+1arcrownumv-1=10000。個人資料整理 僅限學(xué)習(xí)使用/月巴posarcrownumv-1=10000。)for(row=poso rowfor(col=0。colarcrowcol=arcrow+1col。 把從pos行到最后一行的元素均向上移一行).求最短距離函數(shù)定義前置條件：圖已存在輸入：頂點v , endv

20、功能：假如endv存在，求v到endv的最短路徑；假如不輸入 endv,則求v到任意頂點的 最短路徑輸出：所求得的最短路徑及所經(jīng)歷的位置后置條件：圖保持不變void Graph:Dijkstra(int v,int endv 求最短路徑，從 v頂點到endv點的最短路徑 if ( vvertexNum throw 位置。/v頂點或endv頂點輸出不正確則拋出異常int numv=vertexNum。int numv=vertexNum。/rn點數(shù)int distMaxSize。int pathMaxSize。int distMaxSize。int pathMaxSize。int sMaxSiz

21、e。int max= 10000。/售前找到的最短路徑為v/兩則v與i頂點不存在路徑/給s集合確定初值0/等頂點v本身排除在外for(k =0 o k/求其他numv-1各頂點的最短路徑/服短長度/當(dāng)前找到的最短路徑/府放源點和已生成的終點的集合/代表無窮大int i,j,k,wm。for(i=0o i按網(wǎng)的鄰接矩陣確定各頂點最短路徑的初值disti=arcvi。if(i!=v& disti / 如果 v、i 之間有路pathi=v。elsepathi=-1。si = 0。)sv=1。distv=0。wm = max。j=vwm = max。j=v。for( i=0 o i(if(!si&di

22、sti(j=i owm = disti。sj=1。for(i =0。 i個人資料整理 僅限學(xué)習(xí)使用/詢定X前最后底徑wm 反而E向后號j/如果v、i之間有路/肥當(dāng)前找到的路徑確定為最大值/更新未確定最短路徑各頂點的當(dāng)前最短路徑(if(!si&distj+arcji / 如果v、i兩點的距離加上i、j小于從v點到j(luò)點的 距離(disti=distj+arcji 。 pathi=j。/disti取最小值if (endv =0 /endv 點存在(string mmm=。/初始化字符串int j =endv。while(j -1 (string nnn = vertexj。/膿次把頂點存放在 nnn

23、字符串中nnn+=mmm。mmm = +nnn。j = pathj ocout從至U ”的最短路徑長度：distendv路徑：n。 輸出從 v 點至U endv 點的最短路徑 elseendv 不存在for(i=0。i個人資料整理 僅限學(xué)習(xí)使用(string mmm=。/創(chuàng)始化字符串intj =i owhile(j -1 (string nnn = vertexj0/膿次把頂點存放在 nnn字符串中nnn+=mmm。mmm = +nnn。j = pathj ocout從到”的最短路徑長度：disti路徑：n。/輸出從v點到任意點的最短路徑.刪除邊信息函數(shù)定義前置條件：圖已存在輸入：頂點n、w功

24、能：在圖中刪除頂點n、w依附的邊輸出：如果刪除不成功，拋出異常后置條件：如果刪除成功，圖中減少了一條邊void Graph二DeleteArc(int n, int w刪除 i、j 兩頂點依附的邊(if ( nMaxSize| wMaxSize throw 位置。/如果輸入不正確拋出異常arcnw=arcwn=10000。/刪除w頂點和n頂點之間的路徑.插入邊及相應(yīng)頂點函數(shù)定義前置條件：圖已存在輸入：頂點i、j功能：在圖中插入頂點i、j及其所依附的邊輸出：如果插入不成功，拋出異常后置條件：如果插入成功，圖中增加了一條邊void Graph:InsertArc(int i, int j,int

25、n /在圖中插入一條邊，其依附的兩個頂點的 編號為i和j(個人資料整理 僅限學(xué)習(xí)使用if ( iMaxSize| jMaxSize throw 位置。/度口果輸入不正確拋出異常arcij=n。arc皿i=n。cout從vertexi至vertexj的路徑長度為：arcijn。 輸出所 插入的兩個頂點之間的距離算法分析.輸出邊信息功能算法分析根據(jù)Dijkstra算法求單源點最短路徑問題，設(shè) n是圖中頂點的個數(shù)，第一個循環(huán)執(zhí)行n-1次；第二個循環(huán)也執(zhí)行n-1次，內(nèi)嵌兩個并列的循環(huán)，第一個循環(huán)是在數(shù)組dist中求最小值，執(zhí)行n-1次，第二個循環(huán)是修改數(shù)組dist和path,需要執(zhí)行n次，所以總的時間

26、復(fù)雜度是 On2)。然后每次以一個頂點為源點，調(diào)用 Dijkstra算法n次。這樣，便可求得每一對頂點之 間的最短路徑，再顯示出來即為各邊的信息。顯然，時間復(fù)雜度為On3) o.求最短路徑功能算法分析求最短路徑即為單源點最短路徑問題，由上得時間復(fù)雜度為O函數(shù)中，當(dāng)要輸出所有頂點數(shù)據(jù)信息時，源點位置有可能超出范 圍，超出范圍則程序運行異常，因此要判斷源點位置是否超出，解決方法用判斷語句列出超出 條件，if (ivertexNum throw 位置。此句可防止位置超出范圍。此類問題還發(fā)生在該程序的 類封裝的各程序中，都采用相同的辦法解決范圍超出問題。在求最短路徑函數(shù) void Dijkstra(i

27、nt v,int endv中，求v頂點到endv點的最短路徑時，兩點 間可能不存在路徑，此時程序運行結(jié)果會異常。解決辦法是先判斷兩點間是否有路徑，再輸出 最短路徑，用語句if(i!=v& disti來列出有路徑的條件，否則即無路徑。3測試運行3.1開始界面測試開始界面如圖3.1所示個人資料整理 僅限學(xué)習(xí)使用圖3.1開始界面3.2個人資料整理 僅限學(xué)習(xí)使用圖3.1開始界面3.2輸出頂點信息功能測試根據(jù)菜單提示輸入0執(zhí)行頂點信息輸出功能，則顯示各頂點信息如圖3.2所示圖3.2頂點輸出功能測試結(jié)果則程序能正確輸出各頂點信息。3.3所小。輸出邊信息功能測試3.3所小。根據(jù)菜單提示輸入1執(zhí)行邊信息輸出功

28、能，則顯示各頂點信息如圖個人資料整理 僅限學(xué)習(xí)使用技技3畦唉&7 請請旅濡謂檜桂 a田H工苴窗畝 德帝“徑質(zhì)頂出過3 山忌技皆技技3畦唉&7 請請旅濡謂檜桂 a田H工苴窗畝 德帝“徑質(zhì)頂出過3 山忌技皆耳三柱 當(dāng)請聞某某某其in 士的率券，賒.出 稿遮一修T劃-sjeibl6 1 b 2 EW1隼 4 2 2 s 6 4 4 G 5聘| 苧 TTH1 ? 且!1W1 a2 32M-tfc(5ftsr3tfc3r$ fa iSGs i B 5 1 H 4 8 m 燈 2 7 3 ea M- 2 2 s H 15 9 111 .- 1 i 3 i 3!為：4M為為：1 ：10為 I為為為度為力為度

29、度劈長度內(nèi),度度度去長度珞格培役的培篇內(nèi)格略舉住的第珞的匆匆格富的的 -為打打苗蕾據(jù)冉內(nèi)格嘉的宿館福我書堂生育除體客魄If-Ia食華體中曼丑也慢篦情,宿宿館.淚樓 俄政書+堂一天二R可咬3園圓生生圖3.3邊信息輸出功能測試結(jié)果則程序能正確輸出各邊信息。修改功能測試根據(jù)菜單提示輸入2執(zhí)行修改功能，即可對兩頂點間的距離進(jìn)行修改，然后輸入要修改的兩頂點，再輸入修改的距離值，執(zhí)行結(jié)果如圖3.4所示。mul文愛要勇票要要要要不巨及韜朱婁按董里卷.1H 幫匕45 316 兩頂點，再輸入修改的距離值，執(zhí)行結(jié)果如圖3.4所示。mul文愛要勇票要要要要不巨及韜朱婁按董里卷.1H 幫匕45 316 7 按請 曾點

30、請譚寓反遁1H萼 屯曾口!?!? 怕輸工徑頂翳邊& utls q rIG丸lHA尸十莖基 國巴的L8 由色中黃吳軍三.妾要期 310!草蕈草單18宓車圖3.4修改功能測試結(jié)果此時則成功修改了兩頂點間的距離。求最短路徑功能測試根據(jù)菜單提示輸入3執(zhí)行求最短路徑功能，首先提示輸入源頂點，輸入始點后再提示“請輸入結(jié)束頂點，若要全部顯示請輸入 88:，分別輸入結(jié)束點和88后，則輸出相應(yīng)的最短路徑信息，運行結(jié)果如圖3.5和圖3.6所示。個人資料整理 僅限學(xué)習(xí)使用SS.出弟 u豆按單個 項信謂第某某等 SS.出弟 u豆按單個 項信謂第某某等 LLJ的聯(lián),屯 曹悌亭耨患通圖3.5輸入結(jié)束點求最短路徑運行結(jié)果序

31、路法路但實食堂 m芋主體句臉?biāo)蟀胩盟蘩偈程?極學(xué)生荷吉食堂路徑二碎樓學(xué)士宿舍食堂 路徑，實國楂學(xué)或宿舍食堂圖書館的袂路徑長度；335 ._. 食堂的最短恪役旨度二罌匕恪役;0 路皆|1SL路哈 實哈捺 孚段有舍官中技 ：334路隹 笑臉樓 學(xué)生有卷 名二寸圖3.5輸入結(jié)束點求最短路徑運行結(jié)果序路法路但實食堂 m芋主體句臉?biāo)蟀胩盟蘩偈程?極學(xué)生荷吉食堂路徑二碎樓學(xué)士宿舍食堂 路徑，實國楂學(xué)或宿舍食堂圖書館的袂路徑長度；335 ._. 食堂的最短恪役旨度二罌匕恪役;0 路皆|1SL路哈 實哈捺 孚段有舍官中技 ：334路隹 笑臉樓 學(xué)生有卷 名二寸入造束頂,點.若要全骸了示請稿人制;Daciaa.

32、n-nt 3 an.fi Sett injrAda.i ni at r nt d fi4DEhu g徑頂頂邊辿研匆班F刪費要要要要4- 53.噬后.，t7 授清請技校 普點富信輸值徑頂頂邊過W 點總按路r個犁按 .1:一攜某某某通嚓長到教學(xué)櫻的最麴路徑長度二審電學(xué)費或標(biāo)到行政樓的最短路校長度i 0圖3.6輸入88求最短路徑運行結(jié)果分別正確顯示了有結(jié)束點和無結(jié)束點時最短路徑。3.6刪除頂點功能測試根據(jù)菜單提示輸入4執(zhí)行刪除頂點功能，提示輸入要刪除的頂點，運行如圖3.7所示。員整鬻發(fā)包頂頂卷點按蹌個個*癡謂短基某某某消案將八釁八出rs員整鬻發(fā)包頂頂卷點按蹌個個*癡謂短基某某某消案將八釁八出rs要暑

33、(金LDEI* ?Enf c fr1圖3.7刪除頂點功能運行結(jié)果運行刪除該頂點成功。插入頂點功能測試個人資料整理 僅限學(xué)習(xí)使用根據(jù)菜單提示輸入5技行疝入偵點叨能，梃示輸入女方出偵點而立又未名稱，運行如圖所示。徜入要括人的項點的位置和名稱- 1皿要鹿要要要里HaaJ要3蠹； 工史中技工史中取息出篡點富 信箱2徑m頂邊邊8 吧徜入要括人的項點的位置和名稱- 1皿要鹿要要要里HaaJ要3蠹； 工史中技工史中取息出篡點富 信箱2徑m頂邊邊8 吧=.一 Wb常技 hu頂信請知其.其工呈清 W出的理I卷入除3出4 53技校6 7li 一茁*戊* In輸2徑頂頂邊邊g 加倍w盤某某某某請 e的改廢入除入出

34、將修索刷酊搞退 -建尊尊尊冕尊尊封一圖3.8插入頂點功能測試再根據(jù)菜單中提示輸入0圖3.8插入頂點功能測試再根據(jù)菜單中提示輸入0執(zhí)行輸出頂點信息功能，輸出結(jié)果如圖3.9所小。cuarnt j and intst Tsvt ftftDcbuEfr itph. nrr*施費退出箋枝E刖出的改鼠除AT出0 1 4 5刖出的改鼠除AT出0 1 4 5i號盍： sa由清點點修 信輸金徑頂頂建3 所點息按fa.r個條條按 駕川信請短英無英兄語含 媵磴愷近館筏 差書堂生育驗圖3.9插入頂點后頂點信息輸出則插入頂點信息成功。，即要刪除邊的頂點，輸入頂點后刪除邊功能測試，即要刪除邊的頂點，輸入頂點后根據(jù)菜單提示

35、輸入6執(zhí)行刪除邊功能，提示輸入兩個頂點運行結(jié)果如圖3.10所示個人資料整理 僅限學(xué)習(xí)使用工輸入兩頂點.S 3 督 67 工輸入兩頂點.S 3 督 67 藉.1H請鬻 H田田矍點工銀 但葡國徑頂頂噠邊出 點息捺蹈個個執(zhí) 項信請短某某某某請 7的曲急用八女； 鉗修照t.福刪福退 要要亮要追旭窘一要蒞.s請請橫請請襄 自由詩占息答 髓霹普 頂信請短采某某某請 出的改最欠藝出 常邊修求瑞冊插退 變要君.要若要黃要要. 6胃里草用草扁里而圖3.10刪除邊功能測試再選擇輸入1,進(jìn)入邊信息輸出功能，輸出各邊信息結(jié)果如圖3.11所示。輸入兩頂點:3對3 i JbJ 3 i203為為：工IB為1 為為為 度皆為

36、為.后方力度度度-H M - & 9 -培 .路略船埼路鑿此 的 有的的的有辛品的火 工的的路耨“wig的的 的一國座 鱉的宿格的宿飽堂$陛 笈十錮行黃土生表書wit輸入兩頂點:3對3 i JbJ 3 i203為為：工IB為1 為為為 度皆為為.后方力度度度-H M - & 9 -培 .路略船埼路鑿此 的 有的的的有辛品的火 工的的路耨“wig的的 的一國座 鱉的宿格的宿飽堂$陛 笈十錮行黃土生表書wit聒能仃圖阿能重 書第4WS星球就ztSM到tl.TI罰5lfi.tll第r*聿主至1+.中014 5霆i J EE商于一項fe 息出曹點落 Uzi 8 點點按踣個個累楂 罌募某某臬* 出的燮出

37、 s. S 尸驗抵醫(yī)醫(yī)醫(yī)產(chǎn)-外文史審工文亥5忘性踏個個8技 頂信道整茶某生缸曹點謂請 &的辱堂in:Ht 魚苗食fH!E i 5 為力.圖3.11刪除邊后邊信息輸出結(jié)果頂點為1, 2的邊被刪除，刪除指定邊功能運行成功。入邊功能測試根據(jù)菜單提示輸入7執(zhí)行插入邊功能，提示輸入兩個頂點，輸入頂點后提示輸入路徑，在輸入路徑則顯示相應(yīng)插入邊路徑信息，運行入圖 3.12所示。出清點點工里1R 信請短某某某某請 的營賈出油筆刪福瑞區(qū)要要要要修宴K01的舞3技技& 7 館請請接工展 育息出盲點工取泥 體信臨2_住瑞如他X 到點昱F蘆：冬箕悌 舍頂信請短某某某某請 宿出的著6攵出生a求退學(xué)要要要要要等要要要圖3

38、.12插入邊功能測試結(jié)果再選擇輸入1,進(jìn)入邊信息輸出功能，輸出各邊信息結(jié)果如圖3.13所示出清點點工里1R 信請短某某某某請 的營賈出油筆刪福瑞區(qū)要要要要修宴K01的舞3技技& 7 館請請接工展 育息出盲點工取泥 體信臨2_住瑞如他X 到點昱F蘆：冬箕悌 舍頂信請短某某某某請 宿出的著6攵出生a求退學(xué)要要要要要等要要要圖3.12插入邊功能測試結(jié)果再選擇輸入1,進(jìn)入邊信息輸出功能，輸出各邊信息結(jié)果如圖3.13所示宿舍到伴內(nèi)地的路徑長度為.某今頂點 某個頂力. 著部福人兩而中,請騎入路徑:，皿_ |口=|佳鬻靠瞿罵退Ihiv 即尊沙. 書bWHH育育舲甌醫(yī)醫(yī)醒流醫(yī)到 到到比,dJJJmnno 蚓需

39、樓隆府院摩院F -FT，白R 4 .F.FP -WT.-國昌T 體曜 x率或曲制皿巾附E皿1 2 bPS 田 G5K6aJ 與 U4Sa 對1H為為為為.塞 _LL-.Hi I- I- I p - I- I 尊母X.IHIWH至HrW至-+ 的昭略福 露配 室內(nèi)茯 堂譽體共猛串箱1r.i食 Ifpf-H制前事圖3.13插入邊后邊信息輸出結(jié)果邊4, 5）的信息被插入，插入邊功能運行成功。3.10退出程序測試根據(jù)菜單提示輸入8退出程序，運行結(jié)果如圖3.14所示個人資料整理 僅限學(xué)習(xí)使用n(z某某某某請出白雷15 傳輸n(z某某某某請出白雷15 傳輸2校頂頂北B 點息按路個個按-ti 1-書 第青個

40、人資料整理 僅限學(xué)習(xí)使用ftss mny key tn caniniu.E圖3.14退出程序測試結(jié)果退出程序成功。4結(jié)束語課程設(shè)計是培養(yǎng)學(xué)生綜合運用所學(xué)知識，發(fā)現(xiàn)，提出，分析和解決實際問題，鍛煉實踐能力的重 要環(huán)節(jié)，是對學(xué)生實際工作能力的具體訓(xùn)練和考察過程?；仡櫰鸫舜握n程設(shè)計，我感慨頗多，的 確，從理論到實踐，在整整兩星期的日子里，可以說得是苦多于甜，但是可以學(xué)到很多很多的 的東西，同時不僅可以鞏固以前所學(xué)過的知識，而且學(xué)到了很多在書本上所沒有學(xué)到過的知識 或以前沒有掌握的技能，如輸入信息時從文件中讀取相應(yīng)內(nèi)容的操作。通過這次課程設(shè)計使我 懂得了理論與實際相結(jié)合是很重要的，只有理論知識是遠(yuǎn)遠(yuǎn)不

41、夠的，只有把所學(xué)的理論知識與 實踐相結(jié)合起來，從理論中得出結(jié)論，將結(jié)論用于實踐，從而提高自己的實際動手能力和獨立 思考的能力。在設(shè)計的過程中當(dāng)然遇到了問題，可以說得是困難重重，畢竟這是不可避免的， 同時在設(shè)計的過程中發(fā)現(xiàn)了自己的不足之處，對以前所學(xué)過的知識理解得不夠深刻，掌握得不 夠牢固，比如說求最短路徑的算法，迪杰斯特拉算法與弗洛伊德算法在具體程序中的運用，有 邏輯錯誤時如何調(diào)試程序。同時，通過這次課程設(shè)計，把以前所學(xué)過的知識重新溫故了。參考文獻(xiàn)1王紅梅，胡明，王濤.數(shù)據(jù)結(jié)構(gòu)C+版）.北京：清華大學(xué)出版社，20072譚浩強.C+程序設(shè)計.北京：清華大學(xué)出版社，20063. C+程序設(shè)計思想與方法.北京：，2008附錄：程序清單/程序名稱：校園最短路徑問題的研究與實現(xiàn)/程序功能：實現(xiàn)最短路徑的求取以及適