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

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

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

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

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

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

6、計說明書。</p><p><b>　　功能模塊詳細設計</b></p><p>　　4.1 詳細設計思想（個人負責模塊的NS流程圖）</p><p>　　4.2 核心代碼（個人負責模塊代碼）</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[]存儲當前集合分別到剩余結點的最小權值 //prevex[]存儲最短路徑的前一個結點</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; //標志頂點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到其他頂點邊的權值</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];//克魯斯卡爾弧標記數(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;//弧的一結點</p><p>　　int bak;//弧另一結點</p><p>　　int weight

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

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