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

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

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

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

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

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

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

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