1、 概述

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

2、 塊狀鏈表的基本操作

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

基本操作：

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

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

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

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

3、 關鍵點和復雜度分析

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

4、 應用

（1）???? 文本編輯器設計：http://download.noi.cn/T/noi/noi2003A.pdf

程序實現(xiàn)參考：

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

（2）???? 維護隊列：http://download.noi.cn/T/noi/noi2005A.pdf

程序實現(xiàn)參考：

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

5、 總結

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

6、 參考資料

（1）?????論文《對塊狀鏈表的一點研究》

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

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

更多關于數(shù)據(jù)結構和算法的介紹，請查看：數(shù)據(jù)結構與算法匯總

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

原創(chuàng)文章，轉載請注明：?轉載自董的博客

本文鏈接地址:?http://dongxicheng.org/structure/blocklink/

總結

以上是生活随笔為你收集整理的数据结构之块状链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。