數(shù)據(jù)結構課程設計--弗洛伊德算法與最短路徑

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：10 大?。?59.00KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩9頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權，請進行舉報或認領

文檔簡介

1、　　《數(shù)據(jù)結構課程設計報告》　　學院：信息科學技術學院 　　題目：弗洛伊德算法與最短路徑 　　一、課程設計題目　　弗洛伊德算法與最短路徑&

2、lt;b>　　用途簡介　　1、最短路徑問題在生活中時常見到：比如，我們?nèi)ツ骋坏胤?，我們總是想知道到達目的地的最短路徑，或者是最短到達時間。　　2、設計思路:　　先用迪杰斯特拉算法，找到有向圖中某一頂點到別的頂點的最短路徑，再不斷的調(diào)用我們剛剛寫的迪杰

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

4、　　測試數(shù)據(jù)：　　測試數(shù)據(jù)表一：　　表一的頂點數(shù)據(jù)在數(shù)組中按下標從小到大存放的順序為abcdef。　　測試數(shù)據(jù)表二：

5、　　表一的頂點數(shù)據(jù)在數(shù)組中按下標從小到大存放的順序為ABC。　　四、概要設計　　1、元素類型、結點類型和指針類型：　　typedef struct arcnode　　{&l

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

43、>　　八、心得體會及總結　　在學習這門課程之前，腦海中認為只要根據(jù)問題用編程語言解決它就好了，談什么數(shù)據(jù)結構，有什么意義？現(xiàn)在看來這是多么的幼稚、荒唐的想法，同時也對這門有了全新的認識。　　下面是我的一點學習體會： 　　首先要意識到這門課

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

45、只有用實例走算法才能體會到它們之間的異同、才能掌握它。 　　其次我認為要理解、“吃透”有關的概念；因為所有的知識框架都建立在這些基礎概念之上，沒有了它，何談掌握？當然對這些概念絕不是那種死記硬背，那是沒用的。在這里，王教授的從實際中找例子的學習方法，我感覺就十分的好。比如隊列的“先進先出”的原則，就和現(xiàn)實生活中排隊買票、打飯等一樣嗎？通過與實際相結合方法，讓我們就能很輕松的理解它。&#

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

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結構課程設計--弗洛伊德算法與最短路徑

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結構課程設計--弗洛伊德算法與最短路徑

文檔簡介

溫馨提示

最新文檔

評論

免費下載