二項(xiàng)堆和fibonacci堆的分析與實(shí)現(xiàn)畢業(yè)設(shè)計(jì)論文-資料下載頁(yè)
2025-06-18 06:35本頁(yè)面
【正文】 較函數(shù)：實(shí)現(xiàn)的操作。在二項(xiàng)堆中為le()，在斐波納契堆為_(kāi)le()。遍歷函數(shù)：用于對(duì)根鏈進(jìn)行遍歷，同時(shí)格式化輸出根鏈上的節(jié)點(diǎn)的關(guān)鍵字值和度數(shù)。在二項(xiàng)堆中為repr()，在斐波那契堆中為_(kāi)repr()。報(bào)錯(cuò)函數(shù)：通過(guò)stdout的重定位，將內(nèi)存不足的情況寫(xiě)入stdout的緩沖區(qū)，同時(shí)進(jìn)行flush操作。在代碼中為raise()。性能測(cè)試函數(shù)：通過(guò)對(duì)100000個(gè)隨機(jī)數(shù)進(jìn)行Push和Pop操作，計(jì)算出兩種操作所耗費(fèi)的掛鐘時(shí)間。重復(fù)這個(gè)這個(gè)操作多遍，取平均值。在代碼中實(shí)現(xiàn)為profiler()。第6章 性能測(cè)試我們對(duì)二項(xiàng)堆和斐波那契堆的Push和Pop操作進(jìn)行測(cè)試。我們先利用rand()函數(shù)生成大量的隨機(jī)數(shù)，然后對(duì)數(shù)據(jù)進(jìn)行Push和Pop操作，并且利用clock()函數(shù)來(lái)測(cè)試相應(yīng)操作的掛鐘時(shí)間，并將結(jié)果用CLOCK_PER_SEC去除得到最后的時(shí)間。重復(fù)這樣的測(cè)試多次取平均值。在具體代碼中對(duì)應(yīng)的測(cè)試函數(shù)為profiler()。它有2個(gè)參數(shù)，分別是t即實(shí)驗(yàn)重復(fù)次數(shù)，mode即表明是對(duì)二項(xiàng)堆還是對(duì)斐波那契堆進(jìn)行測(cè)試，或者以比較模式進(jìn)行測(cè)試。全局變量SIZE_FOR_TEST為測(cè)試數(shù)據(jù)規(guī)模。通過(guò)對(duì)100000個(gè)數(shù)據(jù)進(jìn)行測(cè)試的實(shí)驗(yàn)，我們得到下列結(jié)果。Binomial size: 100000clocks clocks sds sds all 31 156 32 156 31 140 31 141 31 140 Fibonacci size: 100000clocks clocks sds sds all 15 94 15 94 31 78 31 94 16 93 Compare size: 100000 format: b fclocks clocks sds sds all 46 156 16 94 31 172 15 94 31 172 15 94 31 140 31 94 31 140 16 78 上面的數(shù)據(jù)對(duì)于的是對(duì)二項(xiàng)堆（Binomial），斐波納契堆（Fibonacci）和在比較模式下通過(guò)對(duì)100000數(shù)據(jù)進(jìn)行5次重復(fù)測(cè)試的結(jié)果。其中clocks代表push操作耗費(fèi)的掛鐘時(shí)間，clocks代表pop操作耗費(fèi)的掛鐘時(shí)間， sds代表push操作耗費(fèi)了幾秒， sds代表pop操作耗費(fèi)了幾秒， all代表一次實(shí)驗(yàn)總共耗費(fèi)的時(shí)間。總結(jié)與展望 數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)是一門(mén)創(chuàng)造性的學(xué)問(wèn)，需要良好的數(shù)學(xué)背景和清晰的邏輯思維同時(shí)對(duì)抽象現(xiàn)實(shí)問(wèn)題的能力提出很高的要求。面對(duì)日益增加的數(shù)據(jù)處理規(guī)模，常規(guī)的數(shù)據(jù)結(jié)構(gòu)和算法無(wú)法滿足運(yùn)行時(shí)間的要求。因此精心設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)算法成為解決問(wèn)題的利器。從計(jì)算機(jī)科學(xué)誕生伊始，數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)也隨之產(chǎn)生，一代一代的計(jì)算機(jī)科學(xué)家，工程師為了解決問(wèn)題提出了許許多多的精巧的數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)。 堆作為一種應(yīng)用廣泛的數(shù)據(jù)結(jié)構(gòu)，得到許多人研究。人們不停的在探索這種抽象數(shù)據(jù)結(jié)構(gòu)更好的實(shí)現(xiàn)算法。本文在認(rèn)真學(xué)習(xí)二項(xiàng)堆與斐波那契堆的數(shù)據(jù)結(jié)構(gòu)，數(shù)學(xué)性質(zhì)和實(shí)現(xiàn)算法的基礎(chǔ)上給出了具體的代碼實(shí)現(xiàn)并且對(duì)效率進(jìn)行了分析。二項(xiàng)堆解決了離散空間上面堆的實(shí)現(xiàn)問(wèn)題，與二叉堆有相同的漸近時(shí)間復(fù)雜度。斐波納契堆在不涉及刪除操作的情況下有O(1)的均攤時(shí)間復(fù)雜度，無(wú)疑是對(duì)效率的極大提升。但是相對(duì)而言斐波納契堆有著復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和算法是其主要的不足。 如果能夠開(kāi)發(fā)一種堆的算法，既有比較簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)有能高效支持對(duì)應(yīng)的操作是再好不過(guò)的事情了。而這也是我們要努力的目標(biāo)。致 謝首先，我要誠(chéng)摯地感謝我的導(dǎo)師陳歡老師！本論文是在陳歡老師的悉心指導(dǎo)下完成的，從論文的構(gòu)思、準(zhǔn)備、編寫(xiě)到最后的定稿，都得到了陳歡老師的大力支持和熱心指導(dǎo)。在論文的編寫(xiě)過(guò)程中，陳歡老師提出了許多的寶貴意見(jiàn)和建議，使我得到了很大的啟發(fā)。在此，我要向陳歡老師致以衷心的感謝！ 同時(shí)我也要感謝我的一些同學(xué)和朋友，他們?cè)谖易霎呍O(shè)的過(guò)程之中給我許多幫助，同他們討論問(wèn)題使我受益匪淺。 最后，感謝各位評(píng)審老師在百忙之中抽出寶貴的時(shí)間對(duì)本論文進(jìn)行審閱和參加答辯。在此，對(duì)各位參加審閱和答辯的老師表示感謝！參考文獻(xiàn)[1] Tomas , Charles E. Leiserson Ronald L. Rivest《算法導(dǎo)論》第二版，機(jī)械工業(yè)出版社。[2] Jon Bentley 《編程珠璣》第三版，人民郵電出版社。[3] Mark Allen Weiss 《Data Structures and Algorithm Analysis in C》第二版機(jī)械工業(yè)出版社。[4] 嚴(yán)蔚敏 吳偉民 《數(shù)據(jù)結(jié)構(gòu)》 清華大學(xué)出版社。[5]Sartaj Sahni 《數(shù)據(jù)結(jié)構(gòu)，算法與應(yīng)用》 機(jī)械工業(yè)出版社。27
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1