1、<p>　　《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告》</p><p>　　學(xué) 院：信 息 科 學(xué) 技 術(shù) 學(xué) 院 </p><p>　　題 目： 弗洛伊德算法與最短路徑 </p><p><b>　　一、課程設(shè)計(jì)題目</b></p><p>　　弗洛伊德算法與最短路徑</p><p>&

2、lt;b>　　用途簡(jiǎn)介</b></p><p>　　1、最短路徑問(wèn)題在生活中時(shí)常見(jiàn)到：比如，我們?nèi)ツ骋坏胤剑覀兛偸窍胫赖竭_(dá)目的地的最短路徑，或者是最短到達(dá)時(shí)間。</p><p><b>　　2、設(shè)計(jì)思路:</b></p><p>　　先用迪杰斯特拉算法，找到有向圖中某一頂點(diǎn)到別的頂點(diǎn)的最短路徑，再不斷的調(diào)用我們剛剛寫的迪杰

3、斯特拉算法。最后輸出任意兩點(diǎn)之間的最短路徑。</p><p>　　迪杰斯特拉算法的實(shí)現(xiàn)方法是，對(duì)于有向圖采用鄰接矩陣的方法存放。然后建立兩個(gè)數(shù)組，其中一個(gè)數(shù)組存放的是某一頂點(diǎn)到這點(diǎn)的最短路徑的值。另一個(gè)數(shù)組定義為線性鏈表的表頭單元，然后再數(shù)組后面不斷加入頂點(diǎn)路徑。再在迪杰斯特拉算法內(nèi)部設(shè)一個(gè)數(shù)組，用來(lái)標(biāo)記頂點(diǎn)元素是否被訪問(wèn)。每次在尋找權(quán)值最小的且沒(méi)有被訪問(wèn)過(guò)得頂點(diǎn)。再加入新頂點(diǎn)后要修正那些還沒(méi)有被訪問(wèn)的點(diǎn)的權(quán)值。

4、</p><p><b>　　測(cè)試數(shù)據(jù)：</b></p><p><b>　　測(cè)試數(shù)據(jù)表一：</b></p><p>　　表一的頂點(diǎn)數(shù)據(jù)在數(shù)組中按下標(biāo)從小到大存放的順序?yàn)閍bcdef。</p><p><b>　　測(cè)試數(shù)據(jù)表二：</b></p><p>

5、　　表一的頂點(diǎn)數(shù)據(jù)在數(shù)組中按下標(biāo)從小到大存放的順序?yàn)锳BC。</p><p><b>　　四、概要設(shè)計(jì)</b></p><p>　　1、元素類型、結(jié)點(diǎn)類型和指針類型：</p><p>　　typedef struct arcnode</p><p><b>　　{</b></p>&l

6、t;p><b>　　int adj;</b></p><p><b>　　}arcnode;</b></p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　char vertex[max];</p>&

7、lt;p>　　arcnode arcs[max][max];</p><p>　　int vexnum,arcnum;</p><p><b>　　}matrix;</b></p><p>　　typedef struct linknode</p><p><b>　　{</b></p&

8、gt;<p>　　char data;</p><p>　　struct linknode *next;</p><p>　　}linklist;</p><p>　　2、建立一個(gè)頭結(jié)點(diǎn)數(shù)組path[max],和最短路徑數(shù)組dist[max]:</p><p>　　int dist[max],i;</p><

9、p>　　linklist path[max];</p><p>　　3、主函數(shù)和其他函數(shù)：</p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　matrix g;</b></p><p>　　creatdn(&

10、amp;g);</p><p>　　int dist[max],i;</p><p>　　linklist path[max];</p><p>　　for(i=1;i<=g.vexnum;i++)//不斷調(diào)用shortestpath(&g,i,dist,path);輸出各頂點(diǎn)間的最短路徑。</p><p><b>　

11、　{</b></p><p>　　shortestpath(&g,i,dist,path);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　五、程序代碼：</b></p><p

12、>　　#include "stdio.h"</p><p>　　#include "stdlib.h"</p><p>　　#include "conio.h"</p><p>　　#include "dos.h"</p><p>　　#define max

13、 10</p><p>　　#define inf 3767</p><p>　　#define null 0</p><p>　　typedef struct arcnode</p><p><b>　　{</b></p><p><b>　　int adj;</b><

14、;/p><p><b>　　}arcnode;</b></p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　char vertex[max];</p><p>　　arcnode arcs[max][max];</p

15、><p>　　int vexnum,arcnum;</p><p><b>　　}matrix;</b></p><p>　　void creatdn(matrix *g)</p><p><b>　　{</b></p><p>　　int i,j,k=0,weight;<

16、/p><p>　　printf("%s\n","輸入頂點(diǎn)數(shù)和邊數(shù)");</p><p>　　scanf("%d,%d",&g->vexnum,&g->arcnum);</p><p>　　for(i=1;i<=g->vexnum;i++)</p><p

17、>　　for(j=1;j<=g->vexnum;j++)</p><p><b>　　{</b></p><p>　　g->arcs[i][j].adj=inf;</p><p><b>　　}</b></p><p>　　printf("%s\n",&q

18、uot;頂點(diǎn)信息");</p><p>　　for(k=0;k<=g->vexnum;k++)</p><p><b>　　{</b></p><p>　　scanf("%c",&g->vertex[k]);</p><p><b>　　}</b&g

19、t;</p><p>　　printf("%s\n","頂點(diǎn)i與j之間的權(quán)值");</p><p>　　for(k=1;k<=g->arcnum;k++)</p><p><b>　　{</b></p><p>　　scanf("%d,%d,%d",

20、&i,&j,&weight);</p><p>　　g->arcs[i][j].adj=weight;</p><p><b>　　} </b></p><p>　　//printf("%c",g->vertex[0]);</p><p>　　//printf(&q

21、uot;%c",g->vertex[1]);</p><p>　　//printf("%c",g->vertex[2]);</p><p>　　//printf("%c",g->vertex[3]);</p><p>　　//printf("%d",g->arcs[0][1

22、]);</p><p><b>　　}</b></p><p>　　typedef struct linknode</p><p><b>　　{</b></p><p>　　char data;</p><p>　　struct linknode *next;</p&

23、gt;<p>　　}linklist;</p><p>　　void init(linklist *l)</p><p><b>　　{</b></p><p>　　//l=(linklist*)malloc(sizeof(linknode));</p><p>　　l->next=null;<

24、/p><p><b>　　}</b></p><p>　　void link(linklist *p,char x)</p><p><b>　　{</b></p><p>　　linklist *q;</p><p>　　q=(linklist*)malloc(sizeof(l

25、inknode));</p><p>　　while(p->next!=null)</p><p><b>　　{</b></p><p>　　p=p->next;</p><p><b>　　}</b></p><p>　　//q->next=p->

26、next;</p><p>　　p->next=q;</p><p>　　q->data=x;</p><p>　　q->next=null;</p><p><b>　　}</b></p><p>　　void shortestpath(matrix *g,int c,int

27、dist[max],linklist path[max])</p><p><b>　　{ </b></p><p>　　printf("頂點(diǎn)%d到各個(gè)點(diǎn)的最短距離\n",c);</p><p>　　int i,t,min,k;</p><p>　　int s[max]={0};</p>

28、<p>　　linklist *b;</p><p>　　for(i=1;i<=g->vexnum;i++)</p><p><b>　　{</b></p><p>　　init(&path[i]);</p><p>　　dist[i]=g->arcs[c][i].adj;<

29、/p><p>　　if(dist[i]!=inf)</p><p><b>　　{</b></p><p>　　link(&path[i],g->vertex[c]);</p><p>　　link(&path[i],g->vertex[i]);</p><p><b

30、>　　}</b></p><p><b>　　}</b></p><p><b>　　s[c]=1;</b></p><p>　　for(t=1;t<g->vexnum-1;t++)</p><p><b>　　{</b></p>&

31、lt;p><b>　　min=inf;</b></p><p>　　for(i=1;i<=g->vexnum;i++)</p><p>　　if((s[i]==0)&&dist[i]<min)</p><p><b>　　{</b></p><p><b

32、>　　k=i;</b></p><p>　　min=dist[i];</p><p><b>　　}</b></p><p>　　if(min==inf)</p><p><b>　　return;</b></p><p><b>　　s[k]=1

33、;</b></p><p>　　for(i=1;i<=g->vexnum;i++)</p><p>　　if((s[i]==0)&&g->arcs[k][i].adj!=inf&&(dist[k]+g->arcs[k][i].adj<dist[i]))</p><p><b>　　{

34、</b></p><p>　　dist[i]=dist[k]+g->arcs[k][i].adj;</p><p>　　b=&path[k];</p><p>　　path[i].next=null;</p><p>　　while(b->next!=null)</p><p><

35、b>　　{</b></p><p>　　b=b->next;</p><p>　　link(&path[i],b->data);</p><p><b>　　}</b></p><p>　　link(&path[i],g->vertex[i]);</p>

36、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=1;i<=g->vexnum;i++)</p><p><b>　　{</b></p><p>　　printf("%d,%d\n"

37、,i,dist[i]);</p><p><b>　　}</b></p><p>　　for(i=1;i<=g->vexnum;i++)</p><p><b>　　{ </b></p><p>　　printf("%d",i);</p><p&g

38、t;　　linklist *p;</p><p>　　p=&path[i];</p><p>　　while((p->next!=null))</p><p><b>　　{ </b></p><p>　　p=p->next;</p><p>　　printf("%c

39、",p->data);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>&l

40、t;b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　matrix g;</b></p><p>　　creatdn(&g);</p><p>　　int dist[m

41、ax],i;</p><p>　　linklist path[max];</p><p>　　for(i=1;i<=g.vexnum;i++)</p><p><b>　　{</b></p><p>　　shortestpath(&g,i,dist,path);</p><p>&l

42、t;b>　　}</b></p><p><b>　　}</b></p><p><b>　　六、測(cè)試結(jié)果：</b></p><p><b>　　測(cè)試數(shù)據(jù)表一結(jié)果：</b></p><p><b>　　測(cè)試數(shù)據(jù)表二結(jié)果:</b></p

43、><p><b>　　八、心得體會(huì)及總結(jié)</b></p><p>　　在學(xué)習(xí)這門課程之前，腦海中認(rèn)為只要根據(jù)問(wèn)題用編程語(yǔ)言解決它就好了，談什么數(shù)據(jù)結(jié)構(gòu)，有什么意義？現(xiàn)在看來(lái)這是多么的幼稚、荒唐的想法，同時(shí)也對(duì)這門有了全新的認(rèn)識(shí)。</p><p>　　下面是我的一點(diǎn)學(xué)習(xí)體會(huì)： </p><p>　　首先要意識(shí)到這門課

44、程的重要性及實(shí)踐性；如何合理地組織數(shù)據(jù)、高效地處理數(shù)據(jù)是擴(kuò)大計(jì)算機(jī)應(yīng)用領(lǐng)域、提高軟件效率的關(guān)鍵。正如我參加的“ACM程序設(shè)計(jì)大賽”一樣，雖然你能把那個(gè)問(wèn)題解決，但是當(dāng)它給你規(guī)定一定的時(shí)間時(shí)，就解決不了，而其它的人卻能實(shí)現(xiàn)，這是為什么呢？這里面就是在算法的時(shí)間性能上存在很大的差距，你不會(huì)選擇合理的數(shù)據(jù)結(jié)構(gòu)、有效地組織數(shù)據(jù)，當(dāng)然是無(wú)法實(shí)現(xiàn)的。還有這門課程的實(shí)踐性很強(qiáng)，如果只是“聽(tīng)”和“讀”，那根本是不可能掌握它的。例如關(guān)于排序的那幾種算法，

45、只有用實(shí)例走算法才能體會(huì)到它們之間的異同、才能掌握它。 </p><p>　　其次我認(rèn)為要理解、“吃透”有關(guān)的概念；因?yàn)樗械闹R(shí)框架都建立在這些基礎(chǔ)概念之上，沒(méi)有了它，何談?wù)莆?？?dāng)然對(duì)這些概念絕不是那種死記硬背，那是沒(méi)用的。在這里，王教授的從實(shí)際中找例子的學(xué)習(xí)方法，我感覺(jué)就十分的好。比如隊(duì)列的“先進(jìn)先出”的原則，就和現(xiàn)實(shí)生活中排隊(duì)買票、打飯等一樣嗎？通過(guò)與實(shí)際相結(jié)合方法，讓我們就能很輕松的理解它。&#

46、160;</p><p>　　接下來(lái)是關(guān)于算法的學(xué)習(xí)；對(duì)于一個(gè)算法，在上課時(shí)聽(tīng)老師講過(guò)之后，可能感覺(jué)自己已經(jīng)掌握了，但當(dāng)自己再去看它時(shí)又似懂非懂的說(shuō)不明白。這就是很顯然的沒(méi)有掌握嘛！記得王教授經(jīng)常說(shuō)，回來(lái)以后找例子走一遍，只有付出努力，才能真正掌握它。這是絕對(duì)有效的，當(dāng)多走幾遍后，不僅能更加深入領(lǐng)會(huì)算法思想，而且還能發(fā)現(xiàn)算法的巧妙之處，從而對(duì)其產(chǎn)生興趣。 </p><p>　　最