外存儲算法中兩個(gè)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)研究.pdf

1、近年來,隨著信息科技的日益發(fā)展,人們已經(jīng)淹沒在數(shù)據(jù)的海洋里,各種各樣的數(shù)據(jù)充斥著人們的生活。其中一部分?jǐn)?shù)據(jù)由于其數(shù)據(jù)量比較龐大,需要海量的存儲空間,而目前的計(jì)算機(jī)內(nèi)存空間不足以滿足這種需求,只能將其存儲在外存儲器中。因此處于內(nèi)外存之間傳輸數(shù)據(jù)的I/O通道就成為了制約算法運(yùn)行效率的主要瓶頸。這種現(xiàn)象在如下幾個(gè)方面表現(xiàn)的尤為明顯,比如:空間數(shù)據(jù)庫中的海量幾何數(shù)據(jù)、數(shù)據(jù)庫、統(tǒng)計(jì)學(xué)、地理信息系統(tǒng)(GIS)、約束邏輯規(guī)劃、計(jì)算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)系

2、統(tǒng)等。由此產(chǎn)生了外存儲算法與數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)和分析領(lǐng)域,其主要目標(biāo)就是研究算法的有效性,以盡量減小程序運(yùn)行過程中的輸入/輸出代價(jià)。
　　 本文首先研究了已有的適用于外存儲算法的數(shù)據(jù)結(jié)構(gòu)?；贔ibonacci堆在內(nèi)存儲算法中的特點(diǎn),進(jìn)一步改進(jìn)得出了一種新的適合外存儲算法的數(shù)據(jù)結(jié)構(gòu),并分析了該數(shù)據(jù)結(jié)構(gòu)中各種操作的時(shí)間復(fù)雜度。并以這種數(shù)據(jù)結(jié)構(gòu)在Dijkstra算法中的應(yīng)用為實(shí)例證明了該數(shù)據(jù)結(jié)構(gòu)的可行性和有效性。
　　 其次,雙

3、端優(yōu)先級隊(duì)列是一種可同時(shí)支持針對最大、最小數(shù)據(jù)進(jìn)行插入,刪除操作的數(shù)據(jù)結(jié)構(gòu),本文利用外存儲算法中對堆的研究,設(shè)計(jì)了一種新的適合外存儲算法的雙端優(yōu)先級隊(duì)列。并分析它的操作復(fù)雜度,其中除查找操作具有單位時(shí)間的頁面置換次數(shù)以外,其他操作都具有對數(shù)時(shí)間的頁面置換次數(shù)。最后借助網(wǎng)絡(luò)傳輸中的包緩存實(shí)現(xiàn)了該數(shù)據(jù)結(jié)構(gòu)在外存中的應(yīng)用。
　　 本文的創(chuàng)新點(diǎn)主要包括以下兩個(gè)方面:
　　 (1)針對外存儲算法中的數(shù)據(jù)結(jié)構(gòu)問題,目前還沒有支持單位

4、時(shí)間操作復(fù)雜度的外存儲算法。本文根據(jù)Fibonacci堆在內(nèi)存儲算法中的特點(diǎn),設(shè)計(jì)出了一種針對海量數(shù)據(jù)支持單位時(shí)間操作復(fù)雜度的外存儲算法。并通過實(shí)例證明了算法的可行性和有效性。
　　 (2)基于外存儲算法中對堆的研究,經(jīng)過一些改進(jìn)得到了一種新的適應(yīng)于外存儲算法的雙端優(yōu)先級隊(duì)列。該數(shù)據(jù)結(jié)構(gòu)可以同時(shí)支持針對最大、最小數(shù)據(jù)的查找,刪除操作。并且其查找操作的頁面置換次數(shù)為O(1),其他操作的頁面置換次數(shù)為O(logN)。通過這種數(shù)據(jù)結(jié)構(gòu)