启程动态数组V2.0

副标题#e#

简介

大量数据的打点是许多措施员的心病，很难找到一个速度快、效率高、支持超大局限数据的表，在1.0版本的基本上，启程花血本写下了这个强化了数据插入与删除的批改版，启程动态数组是一个成果强大的列表形数据打点链表，操作它可以轻松实现超大数据量的随机插入、删除、修改等操纵，它别的一个特点就是速度极快，内存操作率高。

大量数据的打点一定需要占用大量的内存空间，假如这些数据占用的空间巨细是随各类条件变革的，我们就不能利用数组来打点这些数据了（原理就不多说了），这时我们需要一个动态数组。MFC提供了一个很好的动态数组类CArray，对付少量数据，利用CArray就足够好用了，可是对付大量数据（10W级）它就力有未逮了，因为它的本质就是一个数组，只不外对常用的插入、删除等操纵举办了一个巨大的包装。为了办理这个问题，启程动态数组开创性地将链表与数组巧妙的团结起来，既有数组的高速随机索引的利益，又有链表的数据量机动多变的特点。

事情道理

启程动态数组的数据布局如图（这是1.0版本的示意图，2.0版在结点中增加了一个指示当前数据段中已经利用的空间变量）。为了办理大量数据的动态存储问题，启程动态数组将数据分段存放在链表的节点中，每一段可以生存必然数量的数据，假如数据量增加，则在内存中分派一个新数据段，假如数据淘汰则释放空闲的数据段，从而有效地办理了该问题。相对付1.0版，2.0版中引入了每个结点中已利用空间用和总空闲空间两个变量，颠末这个处理惩罚，在举办数据的插入删除时就不再需要对整个数组中的数据举办移动而只需要对方针数据段做一个简朴的处理惩罚。

插入数据

假如方针数据段有空闲位置，那么只需要将该段举办曲整理并插入数据；假如方针段没有空闲空间，启程动态数据自动在内存中申请一段新的数据，并将该数据段链接到链表中。

删除数据

找到方针段后，从方针数据段中删除方针数据，假如方针段中只包括方针数据，启程动态数组自动删除方针段，并维护好链表的完整性。

添加数据

查抄最后一个数据段，假如有空间就不再分派，没有就申请订报的数据段。

#p#副标题#e#

随机索引（数据定位）

对较量普通链表在随机索引方面的不敷，启程动态数组在这方面可以说是趋于完美。由于启程动态数组在数据布局上的优势，它在数据定位的时候是段式跳跃的搜索，因此它的速度获得了有力的保障。另一方面，为了加快索引速度它还颠末尾出格的优化，就是配置了一个当前位置的指针，这样不只在普通的索引中可以成倍的提高速度，出格是在遍历类的操纵时甚至可以到达数组的速度。

数据压缩

假如细心的人必然会发明，凭据上面的模式中大概存在很严重的空间滥废，事实上假如不作处理惩罚也是如此，因为在的插入数据时，我只需要插入一个数据，功效却申请了一个完整的数据段，这在空间有限的计较机中将会造成很大的问题。还记得上面提到的新引入的用来记录空闲空间数量的变量吗？好了，有了它，我们就可以掌握有几多空间没有操作到，当这个值到达一个的范畴时，启程动态数组自动对它占用的空间举办整理，颠末整理后不再需要的空间自动接纳。虽然您可也可强制整理，只需要挪用一个简朴的接口就好了。

参数配置

启动动态数组的机能很洪流平上依赖于参数的配置，要害的参数有勇有2个，一是数据段的巨细，一是空闲空间压缩阀，这两个参数应该也是较量好领略的。数据段的巨细主要应该按照方针数据的容量及计较机的内存来配置，压缩阀则要思量你的呆板的内存以及插入、删除操纵的频率。对付10万级的数据量，数据段设成100就差不多了，假如需要大量举办插入、删除压缩阀可适应加大，不然反之。

执行机能

代码的机能预计是各人最为体贴的问题，同时也是它存在的基础。由于没有其实的代码做参考，这里只能与MFC的CArray举办较量。在10万级综合操纵测试中，启程动态数组耗时300MS阁下，而CArray则需要3000MS，并且因为启程动态数组的耗时与数据量根基是线性干系，而CArray则根基是指数干系，因此数据量越大启程动态数组的机能优势越明明。

测试措施

在开拓这个措施时写了一个相应的测试东西，界面如下图：

“efficiency compare”部门是举办机能较量的，其它的都是举办措施正确性测试用的。做完测试后可以用刷新来显示内存中的数据。

版本汗青

2.0：2004-6-3

加强插入删除

1.0：2003- 09-25

包管

本代码可以任意利用、修改、流传，但作者差池利用该链表造成的效果包袱当何直接或间接责任。

写在最后

#p#分页标题#e#

这是我觉得写得最好的一段代码，拿出来共享只但愿可以或许给各人带来一点点利便。假如各人以为它有代价将是我最大的快乐！假如发明措施的bug请必然汇报我！但愿大空用的开心。

本文配套源码