启程动态数组V2.0
作者：黄建雄
大量数据的管理是很多程序员的心病，很难找到一个速度快、效率高、支持超大规模数据的表，在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请一定告诉我！希望大空用的开心。
e-mail：huangjianxiong@sina.com.cn
