最小生成樹問題

《最小生成樹問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

1、河南城建學院課程設(shè)計報告書專業(yè)：計算機科學與技術(shù)課程設(shè)計名稱：《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》題目：最小生成樹問題班級：學　　　　號：姓　　　　名：同組人員:指導老師：完成時間：2012年2月17日摘要本課程設(shè)計主要解決圖的關(guān)鍵路徑的實現(xiàn)。在項目管理中，編制網(wǎng)絡(luò)計劃的基本思想就是在一個龐大的網(wǎng)絡(luò)圖中找出關(guān)鍵路徑，并對各關(guān)鍵活動，優(yōu)先安排資源，挖掘潛力，采取相應措施，盡量壓縮需要的時間。而對非關(guān)鍵路徑的各個活動，只要在不影響工程完工時間的條件下，抽出適當?shù)娜肆Α⑽锪拓斄Φ荣Y源，用在關(guān)鍵路徑上，以達到縮短工程工期，合理利用資源等目的。在執(zhí)行計劃過程中，可以明確工作重點，對各個關(guān)鍵活動加以有效控制和調(diào)度。關(guān)鍵

2、路徑法將項目分解成為多個獨立的活動并確定每個活動的工期，然后用邏輯關(guān)系（結(jié)束-開始、結(jié)束-結(jié)束、開始-開始和開始結(jié)束）將活動連接，從而能夠計算項目的工期、各個活動時間特點（最早最晚時間、時差）等。在關(guān)鍵路徑法的活動上加載資源后，還能夠?qū)椖康馁Y源需求和分配進行分析。在本程序設(shè)計中，要求實現(xiàn)圖的關(guān)鍵路徑，最小生成樹，判斷兩點之間是否有路徑，程序由2個模塊組成，分別為主函數(shù)的創(chuàng)建及其他相關(guān)函數(shù)的設(shè)計。程序通過調(diào)試運行，初步實現(xiàn)了設(shè)計目標。在課程設(shè)計中，系統(tǒng)開發(fā)平臺為Windows2000，程序設(shè)計設(shè)計語言采用VisualC++，程序運行平臺為Windows98/2000/XP。關(guān)鍵詞程序設(shè)計；C+

3、+；圖；關(guān)鍵路徑目錄目錄-3-第一章開發(fā)環(huán)境和開發(fā)工具41.1C/C++語言簡介41.1開發(fā)背景41.3開發(fā)環(huán)境5第二章算法思想62.1系統(tǒng)需求分析62.2系統(tǒng)總體設(shè)計72.2.1系統(tǒng)設(shè)計目標72.2.2開發(fā)設(shè)計思想72.2.3系統(tǒng)功能模塊設(shè)計92.3算法思想描述9第三章算法實現(xiàn)113.1數(shù)據(jù)結(jié)構(gòu)113.2程序模塊121.insertsort函數(shù)123.3各模塊之間的調(diào)用關(guān)系173.4源程序代碼17第四章測試與分析274.1測試數(shù)據(jù)選擇27總結(jié)30心得體會31參考文獻32第一章開發(fā)環(huán)境和開發(fā)工具1.1C/C++語言簡介C語言是一種計算機程序設(shè)計語言。它既具有高級語言的特點，又具有匯編語言的特點

4、。它由美國貝爾研究所的D.M.Ritchie于1972年推出。1978后，C語言已先后被移植到大、中、小及微型機上。它可以作為工作系統(tǒng)設(shè)計語言，編寫系統(tǒng)應用程序，也可以作為應用程序設(shè)計語言，編寫不依賴計算機硬件的應用程序。它的應用范圍廣泛，具備很強的數(shù)據(jù)處理能力，不僅僅是在軟件開發(fā)上，而且各類科研都需要用到C語言，適于編寫系統(tǒng)軟件，三維，二維圖形和動畫。具體應用比如單片機以及嵌入式系統(tǒng)開發(fā)C++語言是一種優(yōu)秀的面向?qū)ο蟪绦蛟O(shè)計語言，它在C語言的基礎(chǔ)上發(fā)展而來，但它比C語言更容易為人們學習和掌握。C++以其獨特的語言機制在計算機科學的各個領(lǐng)域中得到了廣泛的應用。面向?qū)ο蟮脑O(shè)計思想是在原來結(jié)構(gòu)化程

5、序設(shè)計方法基礎(chǔ)上的一個質(zhì)的飛躍，C++完美地體現(xiàn)了面向?qū)ο蟮母鞣N特性。1.1開發(fā)背景數(shù)據(jù)結(jié)構(gòu)課程是計算機專業(yè)最重要的基礎(chǔ)課之一，主要研究分析計算機存儲、組織數(shù)據(jù)的方式，使學生能夠根據(jù)數(shù)據(jù)對象的特征，選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)及相應算法，初步掌握各種算法在時間和空間上的分析技巧，并能夠進行算法和程序設(shè)計，使所涉及的程序結(jié)構(gòu)清楚，正確易讀[3]。數(shù)據(jù)的組織方法和現(xiàn)實世界問題在計算機內(nèi)部的表示方法，并能針對應用問題，選擇合適的數(shù)據(jù)邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其算法，掌握解決復雜問題的程序設(shè)計方法和技術(shù)。選擇合適的數(shù)據(jù)結(jié)構(gòu)更容易設(shè)計出更高效運行或存儲效率的算法；圖是一種較線性表和樹更為復雜的數(shù)據(jù)結(jié)構(gòu)。在圖形

6、結(jié)構(gòu)中，結(jié)點之間的關(guān)系可以是任意的，圖中的任意兩個元素之間都可能相關(guān)。在社會主義建設(shè)時期，各個城市建設(shè)問題尤其是網(wǎng)絡(luò)建設(shè)尤為重要。在保證各個城市能互相連通的情況下，怎么保證建設(shè)網(wǎng)絡(luò)，怎么建設(shè)最省錢是建設(shè)工程公司所需考慮的重大情況。從而能節(jié)省更多的錢來投資其他地方建設(shè)，如農(nóng)村交通建設(shè)。各個各個城市建設(shè)好之后，則可再根據(jù)將城市作為一個結(jié)點和其它城市再次運用最小生成樹。最小生成樹則能有效的解決此問題。例如，以盡可能低的總價建設(shè)若干網(wǎng)絡(luò)管道，把n個城市聯(lián)系在一起。1.3開發(fā)環(huán)境本文所采用的開發(fā)環(huán)境主要是基于WindowsXP系統(tǒng)，編程環(huán)境主要是在VC6.0++中。第二章算法思想2.1系統(tǒng)需求分析根據(jù)課

7、設(shè)題目要求，擬將整體程序分為三大模塊。以下是三個模塊的大體分析：1.要確定圖的存儲形式，通過對題目要求的具體分析。發(fā)現(xiàn)該題的主要操作是路徑的輸出，因此采用邊集數(shù)組（每個元素是一個結(jié)構(gòu)體，包括起點、終點和權(quán)值）和鄰接矩陣比較方便以后的編程。2.Kruskal算法。該算法設(shè)置了集合A，該集合一直是某最小生成樹的子集。在每步?jīng)Q定是否把邊（u,v）添加到集合A中，其添加條件是A∪{（u,v）}仍然是最小生