二項(xiàng)堆和fibonacci堆的分析與實(shí)現(xiàn)畢業(yè)設(shè)計(jì)論文-閱讀頁(yè)
2025-07-03 06:35本頁(yè)面
【正文】 同度數(shù)的節(jié)點(diǎn)進(jìn)行進(jìn)一步合并。bin_size(),此函數(shù)返回二項(xiàng)堆的節(jié)點(diǎn)數(shù)目。bin_delete()，此函數(shù)刪除某個(gè)給定的節(jié)點(diǎn)，通過(guò)進(jìn)一步的操作來(lái)保證二項(xiàng)堆的數(shù)學(xué)性質(zhì)和結(jié)構(gòu)。bin_func_test(),二項(xiàng)堆的測(cè)試函數(shù)，不包括效率測(cè)試，主要是對(duì)Push,Pop，Top接口函數(shù)的測(cè)試。 struct fib_node *right。 struct fib_node *father。 int degree。}。 int size。 主要涉及到的函數(shù)如下：fib_Make(),此函數(shù)在內(nèi)存中分配一個(gè)fib_heap的結(jié)構(gòu)體并且初始化，函數(shù)返回對(duì)應(yīng)結(jié)構(gòu)體的指針。fib_replace(),此函數(shù)改變某個(gè)節(jié)點(diǎn)的關(guān)鍵值，同時(shí)經(jīng)過(guò)級(jí)聯(lián)剪切的操作的維護(hù)斐波那契堆的數(shù)學(xué)性質(zhì)和結(jié)構(gòu)。_listsize(),此函數(shù)接受一個(gè)fib_heap結(jié)構(gòu)體指針，通過(guò)遍歷根鏈得到根鏈長(zhǎng)度的最大度數(shù)，通過(guò)這些計(jì)算要用到的臨時(shí)數(shù)組的大小。fib_Push(), fib_Pop(), fib_Top()實(shí)現(xiàn)對(duì)斐波那契堆的基本操作進(jìn)行封裝，提供抽象的接口。 代碼還涉及到的其他函數(shù)：比較函數(shù)：實(shí)現(xiàn)的操作。遍歷函數(shù)：用于對(duì)根鏈進(jìn)行遍歷，同時(shí)格式化輸出根鏈上的節(jié)點(diǎn)的關(guān)鍵字值和度數(shù)。報(bào)錯(cuò)函數(shù)：通過(guò)stdout的重定位，將內(nèi)存不足的情況寫(xiě)入stdout的緩沖區(qū)，同時(shí)進(jìn)行flush操作。性能測(cè)試函數(shù)：通過(guò)對(duì)100000個(gè)隨機(jī)數(shù)進(jìn)行Push和Pop操作，計(jì)算出兩種操作所耗費(fèi)的掛鐘時(shí)間。在代碼中實(shí)現(xiàn)為profiler()。我們先利用rand()函數(shù)生成大量的隨機(jī)數(shù)，然后對(duì)數(shù)據(jù)進(jìn)行Push和Pop操作，并且利用clock()函數(shù)來(lái)測(cè)試相應(yīng)操作的掛鐘時(shí)間，并將結(jié)果用CLOCK_PER_SEC去除得到最后的時(shí)間。在具體代碼中對(duì)應(yīng)的測(cè)試函數(shù)為profiler()。全局變量SIZE_FOR_TEST為測(cè)試數(shù)據(jù)規(guī)模。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é)果?？偨Y(jié)與展望 數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)是一門(mén)創(chuàng)造性的學(xué)問(wèn)，需要良好的數(shù)學(xué)背景和清晰的邏輯思維同時(shí)對(duì)抽象現(xiàn)實(shí)問(wèn)題的能力提出很高的要求。因此精心設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)算法成為解決問(wèn)題的利器。 堆作為一種應(yīng)用廣泛的數(shù)據(jù)結(jié)構(gòu)，得到許多人研究。本文在認(rèn)真學(xué)習(xí)二項(xiàng)堆與斐波那契堆的數(shù)據(jù)結(jié)構(gòu)，數(shù)學(xué)性質(zhì)和實(shí)現(xiàn)算法的基礎(chǔ)上給出了具體的代碼實(shí)現(xiàn)并且對(duì)效率進(jìn)行了分析。斐波納契堆在不涉及刪除操作的情況下有O(1)的均攤時(shí)間復(fù)雜度，無(wú)疑是對(duì)效率的極大提升。 如果能夠開(kāi)發(fā)一種堆的算法，既有比較簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)有能高效支持對(duì)應(yīng)的操作是再好不過(guò)的事情了。致 謝首先，我要誠(chéng)摯地感謝我的導(dǎo)師陳歡老師！本論文是在陳歡老師的悉心指導(dǎo)下完成的，從論文的構(gòu)思、準(zhǔn)備、編寫(xiě)到最后的定稿，都得到了陳歡老師的大力支持和熱心指導(dǎo)。在此，我要向陳歡老師致以衷心的感謝！ 同時(shí)我也要感謝我的一些同學(xué)和朋友，他們?cè)谖易霎呍O(shè)的過(guò)程之中給我許多幫助，同他們討論問(wèn)題使我受益匪淺。在此，對(duì)各位參加審閱和答辯的老師表示感謝！參考文獻(xiàn)[1] Tomas , Charles E. Leiserson Ronald L. Rivest《算法導(dǎo)論》第二版，機(jī)械工業(yè)出版社。[3] Mark Allen Weiss 《Data Structures and Algorithm Analysis in C》第二版機(jī)械工業(yè)出版社。[5]Sartaj Sahni 《數(shù)據(jù)結(jié)構(gòu)，算法與應(yīng)用》 機(jī)械工業(yè)出
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1