一、概述

???????????有時候我們需要設計這樣一種數據結構：它能快速在要求位置插入或者刪除一段數據。先考慮兩種簡單的數據結構：數組和鏈表。數組的優點是能夠在O(1)的時間內找到所要執行操作的位置，但其缺點是無論是插入或刪除都要移動之后的所有數據，復雜度是O(n)的。鏈表優點是能夠在O(1)的時間內插入和刪除一段數據，但缺點是在尋找操作位置時，卻要遍歷整個鏈表，復雜度同樣時O(n)的。這兩種數據結構各有優缺點，我們可以把數組和鏈表的優點結合來，這就構成了一個新的數據結構：塊狀鏈表，結合數組和鏈表的優缺點的塊狀鏈表其各種操作的時間復雜度均為O(sqrt(n))。

二、塊狀鏈表的各種操作

???????????塊狀鏈表是結合了數組和鏈表的優缺點，塊狀鏈表本身是一個鏈表，但是鏈表儲存的并不是一般的數據，而是由這些數據組成的順序表。每一個塊狀鏈表的節點，也就是順序表，可以被叫做一個塊。塊狀鏈表通過使用可變的順序表的長度和特殊的插入、刪除方式，可以在達到的復雜度。塊狀鏈表另一個特點是相對于普通鏈表來說節省內存，因為不用保存指向每一個數據節點的指針。

1、定位操作

???????? 定位操作其實可以當作是查找，我們當然是先要定位到元素所在的節點，然后在該節點里面的數組里面尋找我們要的節點；

2、分裂節點

???????? 將某個節點分裂成兩個節點；

3、插入操作

???????? 首先定位要插入的位置，然后將所在節點分裂成兩個節點，并將數據放到第一個節點的末尾。 如果要插入的是一大塊數據，首先要將數據切成多個塊其中、每個塊對應一個塊狀鏈表的一個節點，并將這些塊鏈起來，然后將它們插入那兩個節點之間。插入的操作圖類似下面：

4、刪除操作

???????? 首先定位刪除元素的位置，然后按照數組刪除元素的方法刪除該數據。如果刪除一大塊數據，首先要定位數據塊首元素和末元素所在的位置，然后分別將它們所在的節點分裂成兩個節點，最后刪除首元素和末元素之間的節點即可。

三、關鍵技術

???????????從總體上來看，維護一個鏈表，鏈表中的每個單元中包含一段數組，以及這個數組中的數據個數。每個鏈表中的數據連起來就是整個數據。設鏈表長度為a，每個單元中的數組長度是b。無論是插入或刪除，在尋址時要遍歷整個鏈表，復雜度是O(a)；對于插入操作，直接在鏈表中加入一個新單元，復雜度是O(1)；對于刪除操作，會涉及多個連續的單元，如果一個單元中的所有數據均要刪除，直接刪除這個單元，復雜度是O(1)，如果只刪除部分數據，則要移動數組中的數據，復雜度是O(b)。總的復雜度是O(a+b)。因為ab=n，取a=b=√n，則總的復雜度是O(√n)。

???????? 問題是如何維護a和b大致等于√n？

???????? 在執行插入操作后，如果當前單元中的數據個數>2√n，則將當前單元分割成兩個新單元，每個單元中的數據個數保持為2√n。在執行刪除操作后，如果當前單元和當前單元的下一個單元的數據個數和<√n，則將兩個單元合并成一個新單元。執行上述維護操作需要移動數組中的數據，復雜度是O(b)，對于單元的分割和合并均是O(1)的，總的復雜度是O(b)的。這樣，維護操作并不會使總復雜度增加。最終得到一個復雜度是O(√n)的數據結構。

四、應用

1、文本編輯器：http://download.noi.cn/T/noi/noi2003A.pdf

另一種實現：http://www.byvoid.com/blog/noi-2003-editor/

2、維護數列：http://download.noi.cn/T/noi/noi2005A.pdf

另一種實現：http://www.byvoid.com/blog/noi-2005-sequence/

?轉載請注明：http://blog.csdn.net/w397090770/article/details/8299895