1、 概述

在進(jìn)行算法設(shè)計(jì)時(shí)，我們常用的兩種線性數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表。它們各有優(yōu)缺點(diǎn)。數(shù)組特點(diǎn)是元素在內(nèi)存中緊挨著存儲(chǔ)，因而優(yōu)點(diǎn)是定位快（O(1)），缺點(diǎn)是插入刪除慢（O(n)）；而鏈表則不同，它通過指針將不同位置的元素鏈接起來，因而優(yōu)缺點(diǎn)與數(shù)組正好相反：定位慢（O(n)），插入刪除快（O(1)）。本文介紹一種新的數(shù)據(jù)結(jié)構(gòu)：塊狀鏈表，它將數(shù)組和鏈表的優(yōu)點(diǎn)結(jié)合來，各種操作的時(shí)間復(fù)雜度均為O(sqrt(n))。

2、 塊狀鏈表的基本操作

塊狀鏈表整合了數(shù)組和鏈表的優(yōu)缺點(diǎn)，使得各種那個(gè)操作的時(shí)間復(fù)雜度均為O(sqrt(n))。 從整體上看，塊狀鏈表是一個(gè)鏈表， 而在鏈表的每個(gè)節(jié)點(diǎn)上，以數(shù)組的形式存儲(chǔ)一組元素。具體如下：

基本操作：

（1）定位：先定位元素所在的鏈表節(jié)點(diǎn)，然后再定位該元素在數(shù)組中的位置。

（2）分裂：將某個(gè)鏈表節(jié)點(diǎn)分裂成兩個(gè)節(jié)點(diǎn)。

（3）插入：首先定位要插入的位置，然后將所在節(jié)點(diǎn)分裂成兩個(gè)節(jié)點(diǎn)，并將數(shù)據(jù)放到第一個(gè)節(jié)點(diǎn)的末尾。 如果要插入的是一大塊數(shù)據(jù)，首先要將數(shù)據(jù)切成多個(gè)block（每個(gè)block對應(yīng)一個(gè)塊狀鏈表的一個(gè)節(jié)點(diǎn)）并將這些block鏈起來，然后將它們插入那兩個(gè)節(jié)點(diǎn)之間。

（4）刪除：首先定位刪除元素的位置，然后按照數(shù)組刪除元素的方法刪除該數(shù)據(jù)。如果刪除一大塊數(shù)據(jù)，首先要定位數(shù)據(jù)塊首元素和末元素所在的位置，然后分別將它們所在的節(jié)點(diǎn)分裂成兩個(gè)節(jié)點(diǎn)，最后刪除首元素和末元素之間的節(jié)點(diǎn)即可。

3、 關(guān)鍵點(diǎn)和復(fù)雜度分析

該算法的核心是確定鏈表長度和每個(gè)節(jié)點(diǎn)的數(shù)組長度，以及怎么保證這個(gè)長度值？設(shè)塊狀鏈表中元素總個(gè)數(shù)為X，鏈表長度為n，每個(gè)節(jié)點(diǎn)中數(shù)據(jù)長度為m，則當(dāng)m=n=sqrt(X)時(shí)，可保證m和n同時(shí)最小，此時(shí)各種操作的時(shí)間復(fù)雜度最低。在實(shí)際應(yīng)用時(shí)，需維持塊狀鏈表的每個(gè)節(jié)點(diǎn)大小在[sqrt(n)/2, 2*sqrt(n)]，否則，塊狀鏈表會(huì)退化。維護(hù)方法是，適當(dāng)?shù)臅r(shí)候，對節(jié)點(diǎn)進(jìn)行合并與分裂（維護(hù)本身不會(huì)使復(fù)雜度增加）。

4、 應(yīng)用

（1）     文本編輯器設(shè)計(jì)：http://download./T/noi/noi2003A.pdf

程序?qū)崿F(xiàn)參考：

http://hi.baidu.com/wuyijia/blog/item/7085fa004423cd86e850cdeb.html

（2）     維護(hù)隊(duì)列：http://download./T/noi/noi2005A.pdf

程序?qū)崿F(xiàn)參考：

http://hi.baidu.com/zbwmqlw/blog/item/54cce1004e799c0c1d9583b7.html

5、 總結(jié)

由于塊狀鏈表的每個(gè)節(jié)點(diǎn)存儲(chǔ)的是一個(gè)數(shù)組，如果數(shù)組是靜態(tài)的（的大小固定），則會(huì)浪費(fèi)存儲(chǔ)空間；如是動(dòng)態(tài)的，則需要頻繁的申請或者釋放空間，嚴(yán)重降低系能。因此，當(dāng)數(shù)據(jù)量非常龐大時(shí)，設(shè)計(jì)合理的數(shù)組空間維護(hù)策略顯得尤為重要。

6、 參考資料

（1）     論文《對塊狀鏈表的一點(diǎn)研究》

（2）     數(shù)組+鏈表=塊狀數(shù)組：http://starforever.blog.hexun.com/3184024_d.html

————————————————————————————————————-

更多關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法的介紹，請查看：數(shù)據(jù)結(jié)構(gòu)與算法匯總

————————————————————————————————————-