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

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

2、(Heightfield).動態(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).隊列(Queue).優(yōu)先隊列(Priority queue).雙向隊列(Deque).間隙緩沖(Gap buffer)2 表(List)表是一個抽象數(shù)據(jù)結(jié)構(gòu)（ADT,

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

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

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

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

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

8、個數(shù)據(jù)的時候，如果空閑的空間 太多了，動態(tài)數(shù)組也可能申請一個新空間，然后刪除舊空間。申請新空間時，申請多大的空間是一個值得考慮的問題。目前來說，一般認 為申請的新空間為舊空間的1.4-4倍之間都是合適的，最常見的是2倍。在浪費空間上面，有人證明了至少需要浪費。(時1/2)這么多空間才能保證插 入和刪除都在常數(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動態(tài)數(shù)組還有很多變形，比如，為了加快刪除的速度，可以把開始的數(shù)據(jù)放 到中間(如圖)：這里，第一個數(shù)據(jù)放到數(shù)組的中間，第i個數(shù)據(jù)放到(i+n/2)%n的位置。當 刪除數(shù)據(jù)的時候，最多只需要移動n/2次就行了。當然了，需要保存一個開始的 位置和實際的數(shù)組長度。比如，刪除掉3,得到：5 6 7 1 2 4 *，刪除掉7得 到：* 5 6 1 2 4 *。平行數(shù)組(Parallel Array)平行數(shù)組最初是為了在不支持記錄(對象)的環(huán)境下面使用的。它把一個記 錄切分成多個基本數(shù)組，每個數(shù)組的長度一樣

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

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

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

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

14、的元素個數(shù)鏈表里面的每個節(jié)點對應(yīng)一個元素，而松散鏈表每個節(jié)點可以包含最多ma xElements個元素。從其定義可以看出，節(jié)點可以包含少于maxElement個元素。 那么，我們需要一個規(guī)則來決定如何包含元素到節(jié)點里面，同時盡量保證節(jié)點的 elements數(shù)組空間利用率高。基本的松散鏈表使用的是1-2規(guī)則，也就是說， 如果節(jié)點里面包含的元素個數(shù)將大于可以包含的元素個數(shù)，那么，就把這個節(jié)點 分裂成2個節(jié)點，而如果這個節(jié)點包含的元素數(shù)將小于maxElement/2，就從鄰 近的節(jié)點借一些元素過來，如果鄰近的節(jié)點在借給它之后，擁有的節(jié)點數(shù)小于m axElement/2的話，就把這2個節(jié)點合并成一個節(jié)

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

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

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

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