數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---以鄰接鏈表的方式確定一個無向網(wǎng)

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

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

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

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)總結(jié)報告　　設(shè)計(jì)題目：以鄰接鏈表的方式確定一個無向網(wǎng)　　學(xué)生姓名：　　學(xué) 院：　　專業(yè)：

2、;　　班級：　　學(xué) 號：　　指導(dǎo)教師：　　年月日　　一、設(shè)計(jì)題目

3、　　題目3．以鄰接鏈表的方式確定一個無向網(wǎng)，完成：　?、沤⒉@示出它的鄰接矩陣；　　⑵對該圖進(jìn)行廣度優(yōu)先遍歷，顯示遍歷的結(jié)果，（并隨時顯示隊(duì)列的入、出情況）； 　?、怯闷绽锬匪惴?gòu)造其最小生成樹，隨時顯示其構(gòu)造的過程；　?、扔?/p>

4、克魯斯卡爾算法構(gòu)造其最小生成樹，隨時顯示其構(gòu)造的過程；　　二、運(yùn)行環(huán)境（軟、硬件環(huán)境）　　硬件環(huán)境：　　CPU：1000MHz以上　　內(nèi)存：256MB以上　　硬盤：60G以上

5、　　軟件環(huán)境：　　系統(tǒng)平臺：Windows 2000 / Windows XP / Windows Vista / Windows 7 　　運(yùn)行環(huán)境：TC 3.0 / Microsoft Visual C++ 6.0<p&g

6、t;　　三、算法設(shè)計(jì)的思想　　存儲結(jié)構(gòu)：鄰接矩陣, 鄰接表。　　遍歷方式：廣度優(yōu)先搜索(BFS) 　　實(shí)現(xiàn)最小生成樹的方式：普里姆算法（Prime算法）和克魯斯卡爾算法（kruskai算法），具體實(shí)現(xiàn)見代碼。　　四

7、、算法的流程圖　　五、算法設(shè)計(jì)分析及截圖　?。?）鄰接表的建立.　　鄰接鏈表的頭結(jié)點(diǎn)所使用的結(jié)構(gòu)體：　　typedef struct node　　{ int adjvex;<p

8、>　　struct node *next;　　}JD;　　typedef struct tnode　　{ int vexdata;　　struct node *firstarc;&l

9、t;b>　　}TD;　　建立某無向圖的鄰接鏈表，所用函數(shù)：int crt_linklist(TD g[],int a[][M])，其中調(diào)用函數(shù)　　int loc_vertex(TD g[],int vex,int n)：找出邊的頭尾結(jié)點(diǎn)。主要利用for循環(huán)實(shí)現(xiàn)頂點(diǎn)和邊的輸出，在確定邊的時候，將該邊的權(quán)值取地址給a[i-1][j-

10、1]和a[j-1][i-1]。　　測試結(jié)果：　　鄰接表的建立：　　鄰接矩陣的建立：　?。?）廣度優(yōu)先遍歷</p&g

11、t;　　使用void traver(TD g[],int n)函數(shù)實(shí)現(xiàn)，調(diào)用函數(shù)void bfs(TD g[],int v,int visited[])：利用隊(duì)列實(shí)現(xiàn)遍歷過程，并用for循環(huán)輸出每次入隊(duì)出隊(duì)情況。　　測試結(jié)果：　?。?）最小生成樹的方式：普里姆算法（Prime算法）</p&

12、gt;　　. 使用函數(shù)： void minispantree_PRIM(int a[][M],int n)，利用鄰接矩陣實(shí)現(xiàn)　　測試結(jié)果：　　2---4；　　1---2；<

13、/p>　　3---4；　　最小生成樹的方式：克魯斯卡爾算法（kruskai算法）　　算法思想：設(shè)N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹中邊的集合　　初始令U={u0},(u0V), TE=　　在所

14、有uU,vV-U的邊(u,v)E中，找一條代價最小的邊(u0,v0)　　將(u0,v0)并入集合TE，同時v0并入U　　重復(fù)上述操作直至U=V為止，則T=(V,{TE})為N的最小生成樹　　算法實(shí)現(xiàn)：圖用鄰接矩陣表示　　邊的表示方式：typedef struct</

15、p>　　{ int vexh,vext;　　int weight;　　int flag;　　}EDGE;　　測試結(jié)果：</

16、p>　　六、源代碼 　　#include <stdio.h>　　#include<alloc.h>　　#define M 10　　#define MAX 100

17、　　typedef struct node　　{ int adjvex;　　struct node *next;　　}JD;　　typedef struct tnode

18、;　　{ int vexdata;　　struct node *firstarc;　　}TD;　　typedef struct　　{ int data;　　int j

19、ihe;　　}VEX;　　typedef struct　　{ int vexh,vext;　　int weight;　　int flag;</b&

20、gt;　　}EDGE;　　void minitree_KRUSKAL(void)　　{ int n,i,m,min,k,j;　　VEX t[M];

21、EDGE e[M];　　printf("Input number of vertex and edge:");　　scanf("%d,%d",&n,&m);　　for(i=1;i<=n;i++)　　{ p

22、rintf("t[%d].data=:",i);　　scanf("%d",&t[i].data);　　t[i].jihe=i;　　}　　for(i=0;i<m;i++)</p

23、>　　{ printf("vexh,vext,weight:");　　scanf("%d,%d,%d",&e[i].vexh,&e[i].vext,&e[i].weight);　　e[i].flag=0;<b&g

24、t;　　}　　i=1;　　while(i<n)　　{ min=MAX;　　for(j=0;j<m;j++)　　{ if(e[j].weight<mi

25、n && e[j].flag==0)　　{ min=e[j].weight;　　k=j;　　}　　}<p&g

26、t;　　printf("%d,%d :%d\n",e[k].vexh,e[k].vext,e[k].weight);　　if(t[e[k].vexh].jihe!=t[e[k].vext].jihe)　　{ e[k].flag=1;　　for(j=1;j<=n;j++)</p

27、>　　if(t[j].jihe==t[e[k].vext].jihe)　　t[j].jihe=t[e[k].vexh].jihe;　　t[e[k].vext].jihe=t[e[k].vexh].jihe;　　i++;<

28、;p>　　}　　else　　e[k].flag=2;　　}　　for(i=0;i<m;i++)　　if(

29、e[i].flag==1)　　printf("%d,%d :%d\n",e[i].vexh,e[i].vext,e[i].weight);　　}　　void bfs(TD g[],int v,int visited[])<p&

30、gt;　　{ int qu[M],i,f=0,r=0;　　JD *p;　　printf("%d ",v);　　visited[v]=1;　　qu[0]=v;</p&g

31、t;　　while(f<=r)　　{ v=qu[f++];　　p=g[v].firstarc;　　while(p!=NULL)　　{ v=p->adjvex;　　if(visited[v]==

32、0)　　{ visited[v]=1;　　printf("%d ",v);　　qu[++r]=v;　　}　　p=p->next;<p

33、>　　}　　}　　for(i=1;i<=r;i++)　　{ printf("%d ",qu[i]);　　printf("\n");}</p

34、>　　}　　void traver(TD g[],int n)　　{ int i;　　static int visited[M];　　for(i=1;i<=n;

35、i++)　　visited[i]=0;　　for(i=1;i<=n;i++)　　if(visited[i]==0)　　bfs(g,i,visited);　　}&l

36、t;p>　　int loc_vertex(TD g[],int vex,int n)　　{ int i,j;　　for(i=1;i<=n;i++)　　if(g[i].vexdata==vex)　　return(i);

37、;　　return(0);　　}　　int crt_linklist(TD g[],int a[][M])　　{ int n,e,i,j,k,vt,vh,flag;　　JD *p;</p

38、>　　printf("Input flag and the number of node,arc:");　　scanf("%d,%d,%d",&flag,&n,&e);　　for(i=1;i<=n;i++)　　{

39、printf("g[%d].vexdata=",i);　　scanf("%d",&g[i].vexdata);　　g[i].firstarc=NULL;　　}　　for(k=1;k<

40、;=e;k++)　　{ printf("Vt,Vh:");　　scanf("%d,%d",&vt,&vh);　　i=loc_vertex(g,vt,n);　　j=loc_vertex(g,vh,n);</p

41、>　　printf("the right of one edge:");　　scanf("%d",&a[i-1][j-1]);　　a[j-1][i-1]=a[i-1][j-1];　　if(flag)&

42、lt;/p>　　{ p=(JD *)malloc(sizeof(JD));　　p->adjvex=j;　　p->next=g[i].firstarc;　　g[i].firstarc=p;　　}

43、;　　else　　{ p=(JD *)malloc(sizeof(JD));　　p->adjvex=j;　　p->next=g[i].firstarc;　　g[i].first

44、arc=p;　　p=(JD *)malloc(sizeof(JD));　　p->adjvex=i;　　p->next=g[j].firstarc;　　g[j].firstarc=p;　　}</b

45、>　　}　　for(i=0;i<n;i++)　　{　　for(j=0;j<n;j++)　　{<

46、;/p>　　printf("%-6d ",a[i][j]);　　}　　printf("\n");　　}　　return(n);&

47、lt;/p>　　}　　void minispantree_PRIM(int a[][M],int n)　　{ int i,j,k,p,q,wm;　　q=p=n-1;

48、　a[q][q]=1;　　for(k=0;k<(n-1);k++)　　{ wm=MAX;　　for(i=0;i<n;i++)　　if(a[i][i]==1)　　for(j=0;j<n;j++)

49、;　　if((a[j][j]==0)&&(a[i][j]<wm))　　{ wm=a[i][j];　　p=i;　　q=j;　　}&l

50、t;/b>　　a[q][q]=1;　　printf("%d %d %d\n",p+1,q+1,a[p][q]);　　if(p>q) a[p][q]=-a[p][q];　　else a[q][p]=-a[q][p];</p&g

51、t;　　}　　}　　void main()　　{ int n,i,j;　　static inta[][M];

52、TD g[M];　　for(i=0;i<M;i++)　　for(j=0;j<M;j++)　　a[i][j]=MAX;　　n=crt_linklist(g,a);　　traver(g,n);</

53、p>　　minispantree_PRIM(a,n);　　for(i=0;i<n;i++)　　{ for(j=0;j<n;j++)　　printf("%-6d",a[i][j]);　　printf("

54、\n");　　}　　minitree_KRUSKAL();　　} 　　七、收獲及體會　　在進(jìn)行這次課程設(shè)計(jì)的過程中，我真正學(xué)到了

55、教科書上所沒有或者真正用到了課本上的知識。這樣，既鞏固了舊知識，又掌握了新知識。所以，數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是我們的重中之重，是提高我們專業(yè)知識與實(shí)踐相結(jié)合的重要手段。　　這次課程設(shè)計(jì)，對我進(jìn)行了結(jié)構(gòu)化程序設(shè)計(jì)的初步訓(xùn)練，培養(yǎng)了我的數(shù)據(jù)抽象能力。在實(shí)際操作過程中，遇到很多問題，通過查書，上網(wǎng)查資料，最后問老師，把問題解決，在這個過程中，把課堂上的知識很好的運(yùn)用到實(shí)際上，還通過解決問題，學(xué)習(xí)到很多課外知

56、識，引導(dǎo)和激發(fā)我對數(shù)據(jù)結(jié)構(gòu)的興趣，同時還要培養(yǎng)我搜索分析信息、查閱幫助文檔、整理經(jīng)驗(yàn)編寫文檔、合作交流的能力。　　課程設(shè)計(jì)中我遇見了一些難點(diǎn)，比方說輸入數(shù)據(jù)時錯誤的輸入可能就會讓程序崩潰，經(jīng)過仔細(xì)思考，查閱資料，請教同學(xué)，最后都圓滿的解決當(dāng)然，這是我收獲比較大一點(diǎn)。除此之外，我覺得一個好程序不僅在于它的功能的實(shí)現(xiàn)，更重要的是，很好的容錯能力，人機(jī)交互界面。這次課程設(shè)計(jì)由于比較簡單，時間比較充裕

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

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---以鄰接鏈表的方式確定一個無向網(wǎng)

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---以鄰接鏈表的方式確定一個無向網(wǎng)

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載