新數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---圖的遍歷和生成樹求解實現(xiàn)

1、<p><b>　　數(shù) 據(jù) 結(jié) 構(gòu)</b></p><p>　　課 程 設(shè) 計 說 明 書</p><p>　　2013年1月17日</p><p>　　設(shè)計目的(小標(biāo)題黑體五號字)</p><p>　　《數(shù)據(jù)結(jié)構(gòu)》課程主要介紹最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計算機中的存儲表示，以及在

2、其上進行各種運算時的實現(xiàn)算法，并對算法的效率進行簡單的分析和討論。進行數(shù)據(jù)結(jié)構(gòu)課程設(shè)計要達(dá)到以下目的：</p><p>　　了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；</p><p>　　初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；</p><p>　　提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；&

3、lt;/p><p>　　訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。</p><p>　　2 設(shè)計內(nèi)容和要求</p><p><b>　　設(shè)計內(nèi)容：</b></p><p>　　采用合適的存儲結(jié)構(gòu)來創(chuàng)建圖，并實現(xiàn)圖的遍歷；</p><p>　?。?）

4、計算圖的最小生成樹，求聯(lián)通分量</p><p><b>　　設(shè)計要求：</b></p><p>　?。?）先任意創(chuàng)建一個圖；</p><p>　?。?) 圖的DFS,BFS的遞歸和非遞歸算法的實現(xiàn)</p><p>　?。?) 最小生成樹（兩個算法）的實現(xiàn)，求連通分量的實現(xiàn)</p><

5、;p>　?。?) 要求用鄰接矩陣、鄰接表、十字鏈表多種結(jié)構(gòu)存儲實現(xiàn)</p><p>　　3．本設(shè)計所采用的數(shù)據(jù)結(jié)構(gòu)</p><p>　　(1) 選擇合適的數(shù)據(jù)結(jié)構(gòu)，并定義數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)體；</p><p>　　(2) 根據(jù)程序所要完成的基本要求和程序?qū)崿F(xiàn)提示，設(shè)計出完整的算法；</p><p>　　(3) 按格式要求寫出課程設(shè)

6、計說明書。</p><p><b>　　功能模塊詳細(xì)設(shè)計</b></p><p>　　4.1 詳細(xì)設(shè)計思想（個人負(fù)責(zé)模塊的NS流程圖）</p><p>　　4.2 核心代碼（個人負(fù)責(zé)模塊代碼）</p><p>　　//----------最小生成樹的普利姆算法-----------</p><p>

7、;　　typedef struct</p><p><b>　　{</b></p><p>　　int adjvex;</p><p>　　int lowcost;</p><p>　　}closedge;</p><p>　　int MiniSpanTree_PRIM(int g[][max],

8、int n)</p><p><b>　　{</b></p><p>　　int lowcost[max],prevex[max]; //lowcost[]存儲當(dāng)前集合分別到剩余結(jié)點的最小權(quán)值 //prevex[]存儲最短路徑的前一個結(jié)點</p><p>　　int i,j,k,min;</p><p>　　for(i=

9、2;i<=n;i++) //n個頂點，n-1條邊</p><p><b>　　{</b></p><p>　　lowcost[i]=g[1][i]; //初始化</p><p>　　prevex[i]=1; //頂點未加入到最小生成樹中</p><p><b>　　}</b></p>

10、;<p>　　lowcost[1]=0; //標(biāo)志頂點1加入U集合</p><p>　　for(i=2;i<=n;i++) //形成n-1條邊的生成樹</p><p><b>　　{</b></p><p><b>　　min=inf;</b></p><p><b>

11、　　k=0;</b></p><p>　　for(j=2;j<=n;j++) //尋找滿足邊的一個頂點在U,另一個頂點在V的最小邊</p><p>　　if((lowcost[j]<min)&&(lowcost[j]!=0))</p><p><b>　　{</b></p><p>

12、;　　min=lowcost[j];</p><p><b>　　k=j;</b></p><p><b>　　}</b></p><p>　　cout<<"("<<prevex[k]-1<<","<<k-1<<"

13、)"<<min;</p><p>　　lowcost[k]=0; //頂點k加入U</p><p>　　for(j=2;j<=n;j++) //修改由頂點k到其他頂點邊的權(quán)值</p><p>　　if(g[k][j]<lowcost[j])</p><p><b>　　{</b><

14、/p><p>　　lowcost[j]=g[k][j];</p><p>　　prevex[j]=k;</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p><p>

15、<b>　　return 0;</b></p><p><b>　　}</b></p><p>　　//---------------------最小生成樹的克魯斯卡爾算法------------------------</p><p>　　int acrvisited[max];//克魯斯卡爾弧標(biāo)記數(shù)組</p>

16、;<p>　　int find(int acrvisited[],int f)</p><p><b>　　{</b></p><p>　　while(acrvisited[f]>0)f=acrvisited[f];</p><p><b>　　return f;</b></p><

17、p><b>　　}</b></p><p>　　typedef struct acr</p><p><b>　　{</b></p><p>　　int pre;//弧的一結(jié)點</p><p>　　int bak;//弧另一結(jié)點</p><p>　　int weight

18、;//弧的權(quán)</p><p><b>　　}edg;</b></p><p>　　void MiniSpanTREE_KRUSCAL(MGraph_L G,ALGraph gra)</p><p><b>　　{</b></p><p>　　edg edgs[max];</p><

19、;p>　　int i,j,k=0;</p><p>　　for(i=0;i!=G.vexnum;++i)</p><p>　　for(j=i;j!=G.vexnum;++j)</p><p><b>　　{</b></p><p>　　if(G.arcs[i][j].adj!=int_max)</p>

20、<p><b>　　{</b></p><p>　　edgs[k].pre=i;</p><p>　　edgs[k].bak=j;</p><p>　　edgs[k].weight=G.arcs[i][j].adj;</p><p><b>　　++k;</b></p>&

21、lt;p><b>　　}</b></p><p><b>　　}</b></p><p>　　int x,y,m,n;</p><p>　　int buf,edf;</p><p>　　for(i=0;i!=gra.arcnum;++i)</p><p>　　acrvi

22、sited[i]=0;</p><p>　　for(j=0;j!=G.arcnum;++j)</p><p><b>　　{</b></p><p>　　m=int_max;</p><p>　　for(i=0;i!=G.arcnum;++i)</p><p><b>　　{</b

23、></p><p>　　if(edgs[i].weight<m)</p><p><b>　　{</b></p><p>　　m=edgs[i].weight;</p><p>　　x=edgs[i].pre;</p><p>　　y=edgs[i].bak;</p>&

24、lt;p><b>　　n=i;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　buf=find(acrvisited,x);</p><p>　　edf=find(acrvisited,y);</p>

25、;<p>　　edgs[n].weight=int_max;</p><p>　　if(buf!=edf)</p><p><b>　　{</b></p><p>　　acrvisited[buf]=edf;</p><p>　　cout<<"("<<x<&

26、lt;","<<y<<")"<<m;</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</

27、b></p><p>　　4.3運行結(jié)果（抓圖顯示）</p><p>　　5．課程設(shè)計心得及存在問題</p><p>　　緊張而又充實的課程設(shè)計就要結(jié)束了，在這兩周的時間里，不僅檢驗了我這學(xué)期所學(xué)的知識，也培養(yǎng)了我如何把握一件事情，如何把一件事情做的更好。在課程設(shè)計中，和同學(xué)們相互討論，相互學(xué)習(xí)，相互監(jiān)督，和老師相互交流，使得我學(xué)會了運籌帷幄，學(xué)會了寬容，學(xué)會

28、了理解。這次課程設(shè)計對我來說受益良多。</p><p>　　我這次課程設(shè)計所選的題目是圖的遍歷和生成樹的求解實現(xiàn)，這個題目是用我們這學(xué)期所學(xué)過的知識再加上我們之前所學(xué)過的編譯語言完成的。這其中包括，鄰接矩陣的定義和輸出，鄰接表的定義和輸出，隊列的定義，圖的兩種遍歷方法，包括圖的深度遍歷，圖的廣度遍歷，連通分量的求解，在求連通分量時又用到了圖的深度遍歷，最小生成樹的實現(xiàn)，包括普里木算法和克魯斯卡爾算法。</p