启程动态数组V2.0[组图](2)

　　随机索引（数据定位）

　　相比较普通链表在随机索引方面的不足，启程动态数组在这方面可以说是趋于完美。由于启程动态数组在数据结构上的优势，它在数据定位的时候是段式跳跃的搜索，因此它的速度得到了有力的保障。另一方面，为了加速索引速度它还经过了特别的优化，就是设置了一个当前位置的指针，这样不仅在普通的索引中可以成倍的提高速度，特别是在遍历类的操作时甚至可以达到数组的速度。

　　数据压缩

　　如果细心的人一定会发现，按照上面的模式中可能存在很严重的空间滥废，事实上如果不作处理也是如此，因为在的插入数据时，我只需要插入一个数据，结果却申请了一个完整的数据段，这在空间有限的计算机中将会造成很大的问题。还记得上面提到的新引入的用来记录空闲空间数量的变量吗？好了，有了它，我们就可以把握有多少空间没有利用到，当这个值达到一个的范围时，启程动态数组自动对它占用的空间进行整理，经过整理后不再需要的空间自动回收。当然您可也可强制整理，只需要调用一个简单的接口就好了。

　　参数设置

　　启动动态数组的性能很大程度上依赖于参数的设置，关键的参数有勇有2个，一是数据段的大小，一是空闲空间压缩阀，这两个参数应该也是比较好理解的。数据段的大小主要应该根据目标数据的容量及计算机的内存来设置，压缩阀则要考虑你的机器的内存以及插入、删除操作的频率。对于10万级的数据量，数据段设成100就差不多了，如果需要大量进行插入、删除压缩阀可适应加大，否则反之。

　　执行性能

　　代码的性能估计是大家最为关心的问题，同时也是它存在的根本。由于没有其实的代码做参考，这里只能与MFC的CArray进行比较。在10万级综合操作测试中，启程动态数组耗时300MS左右，而CArray则需要3000MS，而且因为启程动态数组的耗时与数据量基本是线性关系，而CArray则基本是指数关系，因此数据量越大启程动态数组的性能优势越明显。

　　测试程序

　　在开发这个程序时写了一个相应的测试工具，界面如下图：

　　“efficiency compare”部分是进行性能比较的，其它的都是进行程序正确性测试用的。做完测试后可以用刷新来显示内存中的数据。

　　版本历史

2.0：2004-6-3

增强插入删除

1.0：2003- 09-25

　　担保

　　本代码可以任意使用、修改、传播，但作者不对使用该链表造成的后果承担任何直接或间接责任。

　　写在最后

　　这是我以为写得最好的一段代码，拿出来共享只希望能够给大家带来一点点方便。如果大家觉得它有价值将是我最大的快乐！如果发现程序的bug请一定告诉我！希望大空用的开心。