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

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

2、;<p><b>　　班 級(jí)：</b></p><p><b>　　學(xué) 號(hào)：</b></p><p><b>　　指導(dǎo)教師：</b></p><p>　　年 月 日</p><p><b>　　一、設(shè)計(jì)題目</b>

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

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

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

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

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

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

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

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

11、t;<p>　　使用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)遍歷過(guò)程，并用for循環(huán)輸出每次入隊(duì)出隊(duì)情況。</p><p><b>　　測(cè)試結(jié)果：</b></p><p>　?。?）最小生成樹(shù)的方式：普里姆算法（Prime算法）</p&

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

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

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

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

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

17、<p>　　typedef struct node</p><p>　　{ int adjvex;</p><p>　　struct node *next;</p><p><b>　　}JD;</b></p><p>　　typedef struct tnode</p><p>

18、;　　{ int vexdata;</p><p>　　struct node *firstarc;</p><p><b>　　}TD;</b></p><p>　　typedef struct</p><p>　　{ int data;</p><p><b>　　int j

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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