解決空間規(guī)模問題的幾種常用的存儲結(jié)構(gòu)

1、1解決空間規(guī)模問題的幾種常用的存儲結(jié)構(gòu)廣西柳州鐵路第一中學龍翀【關(guān)鍵字】空間規(guī)模、存儲結(jié)構(gòu)【摘要】空間規(guī)模型問題是近年來國際國內(nèi)比賽的熱點。這類問題對選手們掌握運用各種數(shù)據(jù)存儲結(jié)構(gòu)的能力提出了更高的要求，本文站在解決空間規(guī)模型問題的角度，深入分析了幾種常用的數(shù)據(jù)存儲結(jié)構(gòu)，在這一類特殊問題當中表現(xiàn)出來的一些新的特點，總結(jié)了鏈式結(jié)構(gòu)中的單鏈表、雙鏈表和樹型結(jié)構(gòu)，矩陣結(jié)構(gòu)各自的長處和短處，特別是通過一題多解比較說明了矩陣結(jié)構(gòu)具有很大的潛力。論

2、文對三道國際國內(nèi)競賽題作了詳細的分析總結(jié)，這對于參加國際或國內(nèi)比賽的選手來說具有很強的現(xiàn)實意義正文一、引論一、引論“規(guī)?！币辉~在《現(xiàn)代漢語詞典》里的解釋為“某一事物包括的范圍”，而在計算機程序設(shè)計中，我們可以把它理解為程序運行時在空間和時間等方面的開銷。它主要包括兩個方面：空間規(guī)模和時間規(guī)模。它們都是在設(shè)計算法、編制程序時經(jīng)常要考慮到的問題。存儲結(jié)構(gòu)，就是數(shù)據(jù)元素和元素之間的關(guān)系在計算機中的表示，它是為解決空間規(guī)模問題，或是通過解決空間

3、規(guī)模問題間接地解決時間規(guī)模問題而總結(jié)的一些存儲方法。近年來，在信息學競賽中出現(xiàn)了一類新型問題，這些問題的共同特點就是輸入數(shù)據(jù)非常之大，可達到1M甚至幾M，我們不妨稱這類問題為空間規(guī)模型問題。眾所周知，用TurboPal編程時僅使用最大為640K的常規(guī)內(nèi)存，而僅憑這點有限的內(nèi)存完全不可能把它們一一都存下來，這給我們對數(shù)據(jù)存儲結(jié)構(gòu)和以及設(shè)計算法提出了更高的要求。(見注1)程序是算法和數(shù)據(jù)結(jié)構(gòu)的有機結(jié)合，而本文著重從數(shù)據(jù)結(jié)構(gòu)的角度出發(fā)，針對數(shù)

4、據(jù)規(guī)模型問題，重新研究一下幾種常用的存儲結(jié)構(gòu)的運用情況和它們體現(xiàn)出來的新的特點。二、幾種常用的數(shù)據(jù)結(jié)構(gòu)二、幾種常用的數(shù)據(jù)結(jié)構(gòu)3的局限性，對于難度較大的題目則很難用它來實現(xiàn)。但是作為如此高效的結(jié)構(gòu)，它仍是我們設(shè)計程序時努力的一個方向。鏈式結(jié)構(gòu)中的雙向鏈表也是在程序設(shè)計中應(yīng)用頻繁的數(shù)據(jù)結(jié)構(gòu)，它可以表示為：其中每個單元除了存放元素外，還有一個前趨和后繼指針，這在一定程序上解決了單鏈表表示元素之間的關(guān)系過于簡單的缺陷，但使用雙鏈表時應(yīng)當注意盡量

5、控制向前查找的深度，因為此類問題輸入數(shù)據(jù)中包含的元素十分龐大，處理不當會大大增加程序時間規(guī)模。因此雙向鏈表也有一定的局限性，為了進一步把它的特點分析透徹，我們將在下文繼續(xù)論述。２樹型結(jié)構(gòu)樹是我們熟悉的數(shù)據(jù)結(jié)構(gòu)，其中最有代表性的是二叉樹，這是一種特殊的非線性結(jié)構(gòu)，在程序設(shè)計中有著廣泛的應(yīng)用?！締栴}2】Contact（IOI’98第一試第一題）從由01串構(gòu)成的文件中，找出長度介于A和B之間出現(xiàn)次數(shù)最多的N個不同頻率的子串，子串可以相互覆蓋，

6、輸出結(jié)果必須按子串出現(xiàn)頻率的降序排列，頻率相同的子串按長度降序排列，頻率和長度均相同的子串則按其對應(yīng)數(shù)值降序排列。其中0＜A≤B≤12，0＜N≤20，輸入文件可達到2MB?！痉治觥窟@道題要求完成以下兩步操作：①找出所有滿足條件的子串，并統(tǒng)計各子串出現(xiàn)的頻率；②把所有不同子串按要求排序輸出。其中第①步是關(guān)鍵。讓我們先從具體實例開始研究，長度為1的串只有兩個：“0”和“1”。長度為2的串有4個：“00”、“01”、“10”、“11”，它們可

7、以看成是在長度為1的子串后添加“0”或“1”得到。同樣，長度為3的串又可以看成是在長度為2的子串后添加上“0”或“1”得到，例如“101”是在“10”之后添加“1”得到，以后也可依此類推。這樣層層遞進的關(guān)系使我們想到了樹。以下是一棵二叉樹，最上的為根結(jié)點，定義每個結(jié)點的左枝為0右枝為1，這樣一個子串可以與這棵二叉樹中的一條路徑一一對應(yīng)，如圖21所示：樹中的每個點賦予一定的權(quán)值，表示該點對應(yīng)的子中在文件中出現(xiàn)的頻率，那么我們可以得到一些累