數(shù)據(jù)結(jié)構(gòu)之線性結(jié)構(gòu)

1、數(shù)據(jù)結(jié)構(gòu)之線性結(jié)構(gòu)(一，表結(jié)構(gòu))作者：沖出宇宙時(shí)間：2006-10-24修改：2006-11-3轉(zhuǎn)載請(qǐng)注明作者。作者主要參考了 上面的資料(因?yàn)閃ikipedia上不去)和部 分較新學(xué)術(shù)論文(一般來(lái)自于acm, IEEE和springer)，如果有什么疑問(wèn)，您 可以參考以上資料，我會(huì)努力的把重要的論文羅列在文章里面。本文主要介紹了線性數(shù)據(jù)結(jié)構(gòu)部分，線性數(shù)據(jù)的分類(lèi)來(lái)自于wikipedia，見(jiàn) 頁(yè)面：/topic/list-of-data-structures1線性數(shù)據(jù)結(jié)構(gòu)的分類(lèi)線性數(shù)據(jù)結(jié)構(gòu)的分類(lèi)如下：.表(List).數(shù)組(Array).位圖(Bitmaps).圖片(Images).數(shù)字高程模型

2、(Heightfield).動(dòng)態(tài)數(shù)組(Dynamic array).平行數(shù)組(Parallel array).向量(Vector).集合(Set).鏈表(Linked list).松散鏈表(Unrolled linked list).Xor 鏈表(Xor linked list).可變表(VList) .聯(lián)合數(shù)組(Associative array).散列表(Hash table).跳躍表(Skip list).棧(Stack).隊(duì)列(Queue).優(yōu)先隊(duì)列(Priority queue).雙向隊(duì)列(Deque).間隙緩沖(Gap buffer)2 表(List)表是一個(gè)抽象數(shù)據(jù)結(jié)構(gòu)（ADT,

3、 abstract data type，它表示的是一種接口， 而不是實(shí)現(xiàn)），它表示的是一個(gè)有序?qū)嶓w集合。但是，表并沒(méi)有一個(gè)確定的接口。 比如，可變的表會(huì)包含4種操作：1，建立空表；測(cè)試表十分為空；在前端插入一個(gè)數(shù)據(jù)到表里面去；返回一個(gè)新表，包含了除了第一個(gè)元素（也可能是最后一個(gè)元素）以外 的其它所有元素。在現(xiàn)實(shí)中，表通常由數(shù)組或者鏈表實(shí)現(xiàn)，因?yàn)樗鼈兌己捅砭哂幸恍┕餐c(diǎn)。 通常人們會(huì)把表當(dāng)成是鏈表的別名。序列也是表的另外一個(gè)名字，它突出了實(shí)體 之間的順序關(guān)系。數(shù)組（Array）AhOu L n-l+J rk和數(shù)組相關(guān)的有向量、表（一維數(shù)組實(shí)現(xiàn)）、矩陣（二維數(shù)組實(shí)現(xiàn)），數(shù)組 是一種最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)

4、。數(shù)組包含了一系列的數(shù)據(jù)元素，而且這些元素一般都 是同樣的大小和類(lèi)型。數(shù)組里面的元素通過(guò)索引來(lái)訪問(wèn)，一般的說(shuō)，索引是一段 連續(xù)的整數(shù)范圍，但是，它也可以為任何有序的數(shù)值。數(shù)組可以是多維的，比如， 2維數(shù)組。3維或者以上的數(shù)組很少被采用。時(shí)間復(fù)雜度：通過(guò)索引訪問(wèn)數(shù)組極快（o（1），但是，從數(shù)組里面插入或者刪除一個(gè)數(shù)據(jù)的 代價(jià)很高（o（n），特別是刪除數(shù)據(jù)可能會(huì)造成數(shù)組空閑太多，和插入數(shù)據(jù)造成數(shù) 組空間不夠。這些可以利用動(dòng)態(tài)數(shù)組來(lái)解決。鏈表雖然插入或者刪除數(shù)據(jù)較快， 可是訪問(wèn)其中的元素十分慢（o（n）。空間復(fù)雜度：數(shù)組是最不浪費(fèi)內(nèi)存的數(shù)據(jù)結(jié)構(gòu)，比較起來(lái)散列表是十分浪費(fèi)內(nèi)存的。數(shù)組 不占用任何額外的

5、空間（最多增加一個(gè)保存數(shù)組的大小，4字節(jié)）。程序：大部分程序都內(nèi)置數(shù)組類(lèi)型。位圖（Bitmap）Op 1+j 1+j 0+j Ip 0+j Op 0+j-1+j 1+j 1+j 0+j Op位圖其實(shí)是一個(gè)數(shù)組，數(shù)組的每個(gè)元素都是布爾值（0/1）。常常使用字節(jié) 數(shù)組來(lái)表示位圖，因?yàn)槊總€(gè)字節(jié)可以表示8個(gè)位圖的元素。位圖最常用在空間處 理上，比如，磁盤(pán)分配。根據(jù)位圖的個(gè)性，所有用來(lái)表示是和否的地方都可以使 用它。因?yàn)橐粋€(gè)字節(jié)的位圖可以表示8個(gè)是和否，所以，它也常常用來(lái)壓縮數(shù)據(jù)。 不過(guò)，訪問(wèn)一位比訪問(wèn)一個(gè)字節(jié)會(huì)慢很多，訪問(wèn)一個(gè)字節(jié)比訪問(wèn)一個(gè)int會(huì)慢很 多（如果32位機(jī)器）。圖片（Images）圖片也

6、叫數(shù)字圖片。圖片是一個(gè)2維結(jié)構(gòu)，每個(gè)元素對(duì)應(yīng)于圖片上的某點(diǎn)。 每個(gè)元素的大小根據(jù)其要顯示的效果而變化，主要有1位，8位，16位，24位， 32位幾種。根據(jù)顯示色彩的不同，一般可以分為黑白、灰度、彩色（8位，16 位，24位，32位）、抖動(dòng)色這幾種。一般的圖片都由很多像素組成，所以，一 個(gè)圖片占用的空間十分大。一般情況下，壓縮是必須的。最常見(jiàn)的幾種壓縮格式 為：gif（lzw 壓縮）、png （未知）、jpg（DCT 壓縮）、jpg2000 （小波壓縮）。數(shù)字高程模型（Heightfield 也叫：Digital Elevation Model, or DEM）DEM也是一個(gè)位圖，只是，它每個(gè)點(diǎn)

7、表示的意思是高度。動(dòng)態(tài)數(shù)組(Dynamic Array)它同時(shí)的名字還有：可增數(shù)組(growable array),可變長(zhǎng)數(shù)組(resizable array),動(dòng)態(tài)表(dynamic table),數(shù)組表(array list)。它是一種能夠自動(dòng) 調(diào)整自己大小的數(shù)組。當(dāng)加入一個(gè)新數(shù)據(jù)時(shí)，如果動(dòng)態(tài)數(shù)組沒(méi)有空間了，它會(huì)申請(qǐng)一個(gè)新的空間， 然后把舊數(shù)據(jù)全部拷貝過(guò)去，釋放舊空間(有些動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)并不會(huì)拷貝舊數(shù) 據(jù)過(guò)去，也不會(huì)釋放舊空間)。一般的時(shí)候，新分配的空間大小都是原來(lái)空間大 小的一個(gè)倍數(shù)，保證有一部分空間是空閑的。簡(jiǎn)單的計(jì)算一下，就能發(fā)現(xiàn)加入一 個(gè)數(shù)據(jù)的平均花銷(xiāo)是0(1)。同樣的道理，刪除一

8、個(gè)數(shù)據(jù)的時(shí)候，如果空閑的空間 太多了，動(dòng)態(tài)數(shù)組也可能申請(qǐng)一個(gè)新空間，然后刪除舊空間。申請(qǐng)新空間時(shí)，申請(qǐng)多大的空間是一個(gè)值得考慮的問(wèn)題。目前來(lái)說(shuō)，一般認(rèn) 為申請(qǐng)的新空間為舊空間的1.4-4倍之間都是合適的，最常見(jiàn)的是2倍。在浪費(fèi)空間上面，有人證明了至少需要浪費(fèi)。(時(shí)1/2)這么多空間才能保證插 入和刪除都在常數(shù)時(shí)間內(nèi)完成。Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, and R obert Sedgewick. Resizable Arrays in Optimal Time and Space (1999). W

9、orkshop on Algorithms and Data Structures, pp.37 48動(dòng)態(tài)數(shù)組還有很多變形，比如，為了加快刪除的速度，可以把開(kāi)始的數(shù)據(jù)放 到中間(如圖)：這里，第一個(gè)數(shù)據(jù)放到數(shù)組的中間，第i個(gè)數(shù)據(jù)放到(i+n/2)%n的位置。當(dāng) 刪除數(shù)據(jù)的時(shí)候，最多只需要移動(dòng)n/2次就行了。當(dāng)然了，需要保存一個(gè)開(kāi)始的 位置和實(shí)際的數(shù)組長(zhǎng)度。比如，刪除掉3,得到：5 6 7 1 2 4 *，刪除掉7得 到：* 5 6 1 2 4 *。平行數(shù)組(Parallel Array)平行數(shù)組最初是為了在不支持記錄(對(duì)象)的環(huán)境下面使用的。它把一個(gè)記 錄切分成多個(gè)基本數(shù)組，每個(gè)數(shù)組的長(zhǎng)度一樣

10、。比如，struct Infoint char*age;name;Info person2;我們可以使用平行數(shù)組表示為：int ages = 1,2;char *names = good,zzp;平行數(shù)組擁有的結(jié)構(gòu)簡(jiǎn)單，訪問(wèn)速度快速，同時(shí)，還能夠節(jié)省結(jié)構(gòu)可能需要 使用的指針(某些語(yǔ)言需要指針，某些不需要。比如，c語(yǔ)言不需要指針，而j ava語(yǔ)言需要指針)。但是，它的最大缺點(diǎn)是當(dāng)記錄含有很多域的時(shí)候，平行數(shù) 組將變得極難維護(hù)，同時(shí)，對(duì)它的順序訪問(wèn)并不會(huì)實(shí)際問(wèn)順序的位置，對(duì)基于訪 問(wèn)局部性的緩沖策略是一大妨礙。向量(Vector)向量是一個(gè)十分基本的動(dòng)態(tài)數(shù)組，它具有和動(dòng)態(tài)數(shù)組一樣的性質(zhì)。集合(Se

11、t)集合是包含了一系列的數(shù)據(jù)，這些數(shù)據(jù)沒(méi)有經(jīng)過(guò)排序而且也沒(méi)有重復(fù)的數(shù) 據(jù)。它比較嚴(yán)格的對(duì)應(yīng)于數(shù)學(xué)上的集合的概念。集合必須是有限的，這點(diǎn)和數(shù)學(xué) 上的集合不同。集合一般來(lái)說(shuō)必須支持以下幾種操作：1)判斷一個(gè)元素是否在 集合里面；2)對(duì)集合的所有元素進(jìn)行遍歷；3) 2個(gè)集合之間的交和并操作。雖 然聯(lián)合數(shù)組是通常的建立集合的數(shù)據(jù)結(jié)構(gòu)，但是，它并不能很好的支持集合之間 的交并操作。鏈表(Linked list)鏈表是計(jì)算機(jī)科學(xué)里面最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)之一。它包含一系列的節(jié)點(diǎn)，每個(gè) 節(jié)點(diǎn)含有任意多個(gè)的域和一個(gè)或者兩個(gè)的指針。指針可能指向前面一個(gè)節(jié)點(diǎn)也可 能指向后面一個(gè)節(jié)點(diǎn)。增加或者刪除一個(gè)指定節(jié)點(diǎn)都是常數(shù)時(shí)間

12、，但是隨機(jī)訪問(wèn) 一個(gè)節(jié)點(diǎn)的代價(jià)是o(n)。常用的3種鏈表為：?jiǎn)捂湵?、雙向鏈表和循環(huán)鏈表。見(jiàn) 圖。單鏈表是最簡(jiǎn)單的鏈表形式，每個(gè)節(jié)點(diǎn)有一個(gè)指針，指向后一個(gè)節(jié)點(diǎn)。最后的那個(gè)節(jié)點(diǎn)的指針指向null。它訪問(wèn)任何節(jié)點(diǎn)都必須從頭開(kāi)始，一步一步的走到 待訪問(wèn)的節(jié)點(diǎn)。雙向鏈表是一個(gè)復(fù)雜一點(diǎn)的結(jié)構(gòu)，它的每個(gè)節(jié)點(diǎn)包含2個(gè)指針，一個(gè)指向前 一個(gè)節(jié)點(diǎn)，一個(gè)指向后一個(gè)節(jié)點(diǎn)。同樣，第一個(gè)節(jié)點(diǎn)的前向指針指向null，最后 那個(gè)節(jié)點(diǎn)的后向指針指向null。它可以從頭遍歷也可以從尾遍歷。循環(huán)鏈表把第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)鏈接了起來(lái)。它可以在單向鏈表或者 雙向鏈表的基礎(chǔ)上構(gòu)建。第一個(gè)節(jié)點(diǎn)的前向指針指向最后的那個(gè)節(jié)點(diǎn)，而最后那 個(gè)

13、節(jié)點(diǎn)的后向指針指向第一個(gè)節(jié)點(diǎn)。哨兵節(jié)點(diǎn)(Sentinel Nodes)是一個(gè)額外的未使用的節(jié)點(diǎn)，它常常在鏈表的 開(kāi)頭或者結(jié)尾。它用來(lái)加快或者簡(jiǎn)化某些計(jì)算的過(guò)程。 松散鏈表(unrolled linked list)鏈表的最大問(wèn)題是訪問(wèn)非聚集(即連續(xù)的訪問(wèn)并不是訪問(wèn)連續(xù)的內(nèi)存空間)， 松散鏈表的主要目的是為了解決這個(gè)問(wèn)題(從而顯著的提高緩沖性能)。松散鏈表改進(jìn)了普通鏈表的結(jié)構(gòu)，現(xiàn)在每個(gè)節(jié)點(diǎn)可以包含多個(gè)數(shù)據(jù)。每個(gè)節(jié) 點(diǎn)包含多個(gè)元素。其基本結(jié)構(gòu)為：struct NodeNode next;/下一個(gè)節(jié)點(diǎn)int maxElement; /節(jié)點(diǎn)包含的最大元素個(gè)數(shù)Array Elements; /本節(jié)點(diǎn)包含

14、的元素個(gè)數(shù)鏈表里面的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)元素，而松散鏈表每個(gè)節(jié)點(diǎn)可以包含最多ma xElements個(gè)元素。從其定義可以看出，節(jié)點(diǎn)可以包含少于maxElement個(gè)元素。 那么，我們需要一個(gè)規(guī)則來(lái)決定如何包含元素到節(jié)點(diǎn)里面，同時(shí)盡量保證節(jié)點(diǎn)的 elements數(shù)組空間利用率高?；镜乃缮㈡湵硎褂玫氖?-2規(guī)則，也就是說(shuō)， 如果節(jié)點(diǎn)里面包含的元素個(gè)數(shù)將大于可以包含的元素個(gè)數(shù)，那么，就把這個(gè)節(jié)點(diǎn) 分裂成2個(gè)節(jié)點(diǎn)，而如果這個(gè)節(jié)點(diǎn)包含的元素?cái)?shù)將小于maxElement/2，就從鄰 近的節(jié)點(diǎn)借一些元素過(guò)來(lái)，如果鄰近的節(jié)點(diǎn)在借給它之后，擁有的節(jié)點(diǎn)數(shù)小于m axElement/2的話，就把這2個(gè)節(jié)點(diǎn)合并成一個(gè)節(jié)

15、點(diǎn)?？傊?-2規(guī)則就是保證 (只有一個(gè)節(jié)點(diǎn)例外)每個(gè)節(jié)點(diǎn)至少空間利用在1/2。按照這個(gè)規(guī)律，最常使用 的還有2-3規(guī)則和3-4規(guī)則。再大一些的規(guī)則就十分難以控制了，因?yàn)楣P者曾經(jīng) 寫(xiě)過(guò)3-4規(guī)則的B*樹(shù)，代碼的復(fù)雜程度讓我不敢重新再看一遍了。至于空間性能方面，每個(gè)節(jié)點(diǎn)至少有1/2的空間利用率，在平衡的情況下， 每個(gè)節(jié)點(diǎn)的利用率應(yīng)該是(1+1/2)/2=3/4。但是，如果我們的插入和刪除僅僅發(fā)生 在表頭和表尾的話，那每個(gè)節(jié)點(diǎn)就幾乎都是滿(mǎn)的了。假設(shè)每個(gè)節(jié)點(diǎn)都是滿(mǎn)的，鏈 表總共表示了 N個(gè)元素，每個(gè)元素的空間占用為e，同時(shí)，每個(gè)節(jié)點(diǎn)的指針和計(jì) 算開(kāi)銷(xiāo)為r，松散鏈表里每個(gè)節(jié)點(diǎn)最大可以包含的元素為M個(gè)，

16、那么，基本鏈表 占用的空間為：(e+r)*N，而松散鏈表的空間占用為：(e*M+r)*(N/M)。在時(shí)間性能方面，顯然查找一個(gè)元素，基本的鏈表需要花費(fèi)o(n)的時(shí)間，而 松散鏈表為o(n/M); XOR鏈表(XOR linked list或者zip鏈表，拉鏈?zhǔn)芥湵?雙向鏈表雖然每個(gè)節(jié)點(diǎn)只包含了 2個(gè)指針，可是在內(nèi)存緊張的地方(比如手 機(jī)或者單片機(jī))還是占用了太多空間。于是，Xor鏈表就被設(shè)計(jì)出來(lái)減少空間的 占用，它使用一個(gè)值(前向指針xor后向指針)來(lái)同時(shí)保存前向指針和后向指 針。傳統(tǒng)的雙向鏈表中，每個(gè)節(jié)點(diǎn)需要2個(gè)指針來(lái)指向前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn): TOC o 1-5 h z ABCD-|-|

17、-|-|-| -xor鏈表試圖把節(jié)點(diǎn)的前后指針合并起來(lái)(利用xor操作)：ABCD * xor滿(mǎn)足如下性質(zhì)：X xor ( X xor Y) = Y;這樣，只要知道了.的值，就能夠從前往后遍歷整個(gè)鏈表，只要知道了 *， 就能夠從后往前遍歷節(jié)點(diǎn)。這種方式類(lèi)似于拉拉鏈，所以，有人把它稱(chēng)為zip鏈 表。AdA9 O BaD Dp CH和T分別表示頭和尾數(shù)據(jù)小為什么這種操作可行呢？因?yàn)閤or的性質(zhì)。xor有如下幾個(gè)性質(zhì)：1，m xor 0 = m; 2, m xor m = 0; 3, m xor n = n xor m;于是，就有了 m xor (m xor n) = n。在給定一個(gè)后向指針的初始值

18、m的時(shí)候，我們就能夠根據(jù)上面的 這個(gè)式子一步一步的得到下一個(gè)節(jié)點(diǎn)的指針。xor的性質(zhì)的另外一個(gè)運(yùn)用就是swap函數(shù)。swap函數(shù)的版本有很多，但是， 最簡(jiǎn)單的還是下面的這種方式：swap(x,y)x = x xor y;y = x xor y;x = x xor y;建議不使用xor鏈表，因?yàn)樗速M(fèi)計(jì)算時(shí)間及影響緩存性能。如果真的要節(jié) 省空間的話，推薦使用松散鏈表。2.2 可變表(VList)Ba$e Offset 一VList的顯然是基于松散表的，它的每個(gè)節(jié)點(diǎn)都包含多個(gè)元素。下面是一個(gè)VList的例子：*-*2001000130這里有3個(gè)元素，為1000，130，200。共2個(gè)節(jié)點(diǎn)，第一個(gè)節(jié)點(diǎn)可以最多 包含2個(gè)元素，第2個(gè)最多可以包含一個(gè)元素。那么，在刪除200的時(shí)候，VLi st會(huì)變成：*1000130這里，表示第一個(gè)節(jié)點(diǎn)的第一個(gè)元素為空。簡(jiǎn)單的說(shuō)，VList包含多個(gè)節(jié)點(diǎn)，除了第一個(gè)節(jié)點(diǎn)以外，其他第i個(gè)節(jié)點(diǎn)包 含的空間是第i+1個(gè)節(jié)點(diǎn)的r倍。r是固定的，一般可以為2。每個(gè)節(jié)點(diǎn)包含的還 有下一個(gè)節(jié)點(diǎn)的指針及其有效數(shù)據(jù)的開(kāi)始位置。同時(shí)，它還包含本節(jié)點(diǎn)的數(shù)組長(zhǎng) 度，和當(dāng)前數(shù)據(jù)的最大的