簡介
大量數據的管理是很多程序員的心病，很難找到一個速度快、效率高、支持超大規模數據的表，在1.0版本的基礎上，啟程花血本寫下了這個強化了數據插入與刪除的修正版，啟程動態數組是一個功能強大的列表形數據管理鏈表，利用它可以輕松實現超大數據量的隨機插入、刪除、修改等操作，它另外一個特點就是速度極快，內存利用率高。
大量數據的管理必然需要占用大量的內存空間，如果這些數據占用的空間大小是隨各種條件變化的，我們就不能使用數組來管理這些數據了（道理就不多說了），這時我們需要一個動態數組。MFC提供了一個很好的動態數組類CArray，對於少量數據，使用CArray就足夠好用了，但是對於大量數據（10W級）它就力不從心了，因為它的本質就是一個數組，只不過對常用的插入、刪除等操作進行了一個復雜的包裝。為了解決這個問題，啟程動態數組開創性地將鏈表與數組巧妙的結合起來，既有數組的高速隨機索引的優點，又有鏈表的數據量靈活多變的特點。
工作原理
啟程動態數組的數據結構如圖（這是1.0版本的示意圖，2.0版在結點中增加了一個指示當前數據段中已經使用的空間變量）。為了解決大量數據的動態存儲問題，啟程動態數組將數據分段存放在鏈表的節點中，每一段可以保存一定數量的數據，如果數據量增加，則在內存中分配一個新數據段，如果數據減少則釋放空閒的數據段，從而有效地解決了該問題。相對於1.0版，2.0版中引入了每個結點中已使用空間用和總空閒空間兩個變量，經過這個處理，在進行數據的插入刪除時就不再需要對整個數組中的數據進行移動而只需要對目標數據段做一個簡單的處理。
插入數據
如果目標數據段有空閒位置，那麼只需要將該段進行曲整理並插入數據；如果目標段沒有空閒空間，啟程動態數據自動在內存中申請一段新的數據，並將該數據段鏈接到鏈表中。
刪除數據
找到目標段後，從目標數據段中刪除目標數據，如果目標段中只包含目標數據，啟程動態數組自動刪除目標段，並維護好鏈表的完整性。
添加數據
檢查最後一個數據段，如果有空間就不再分配，沒有就申請訂報的數據段。
隨機索引（數據定位）
相比較普通鏈表在隨機索引方面的不足，啟程動態數組在這方面可以說是趨於完美。由於啟程動態數組在數據結構上的優勢，它在數據定位的時候是段式跳躍的搜索，因此它的速度得到了有力的保障。另一方面，為了加速索引速度它還經過了特別的優化，就是設置了一個當前位置的指針，這樣不僅在普通的索引中可以成倍的提高速度，特別是在遍歷類的操作時甚至可以達到數組的速度。
數據壓縮
如果細心的人一定會發現，按照上面的模式中可能存在很嚴重的空間濫廢，事實上如果不作處理也是如此，因為在的插入數據時，我只需要插入一個數據，結果卻申請了一個完整的數據段，這在空間有限的計算機中將會造成很大的問題。還記得上面提到的新引入的用來記錄空閒空間數量的變量嗎？好了，有了它，我們就可以把握有多少空間沒有利用到，當這個值達到一個的范圍時，啟程動態數組自動對它占用的空間進行整理，經過整理後不再需要的空間自動回收。當然您可也可強制整理，只需要調用一個簡單的接口就好了。
參數設置
啟動動態數組的性能很大程度上依賴於參數的設置，關鍵的參數有勇有2個，一是數據段的大小，一是空閒空間壓縮閥，這兩個參數應該也是比較好理解的。數據段的大小主要應該根據目標數據的容量及計算機的內存來設置，壓縮閥則要考慮你的機器的內存以及插入、刪除操作的頻率。對於10萬級的數據量，數據段設成100就差不多了，如果需要大量進行插入、刪除壓縮閥可適應加大，否則反之。
執行性能
代碼的性能估計是大家最為關心的問題，同時也是它存在的根本。由於沒有其實的代碼做參考，這裡只能與MFC的CArray進行比較。在10萬級綜合操作測試中，啟程動態數組耗時300MS左右，而CArray則需要3000MS，而且因為啟程動態數組的耗時與數據量基本是線性關系，而CArray則基本是指數關系，因此數據量越大啟程動態數組的性能優勢越明顯。
測試程序
在開發這個程序時寫了一個相應的測試工具，界面如下圖：
“efficiency compare”部分是進行性能比較的，其它的都是進行程序正確性測試用的。做完測試後可以用刷新來顯示內存中的數據。
版本歷史
2.0：2004-6-3
增強插入刪除
1.0：2003- 09-25
擔保
本代碼可以任意使用、修改、傳播，但作者不對使用該鏈表造成的後果承擔任何直接或間接責任。
寫在最後
這是我以為寫得最好的一段代碼，拿出來共享只希望能夠給大家帶來一點點方便。如果大家覺得它有價值將是我最大的快樂！如果發現程序的bug請一定告訴我！希望大空用的開心。
本文配套源碼
