动态内存分配中的环形数据管理器及环形数据管理方法

技术领域

本发明涉及计算机动态内存分配领域，更具体地说，涉及一种动态内存分 配中的环形数据管理器及环形数据管理方法。

背景技术

环形数据是对通常情况下首尾相连的双向链表的抽象。它要么是空的，这 时候不包含任何元素；要么包含n（n>0）个元素，并拥有唯一的首元素，其 编号为0，按顺时针方向其后元素编号分别为1，2，…，n-1。环形数据允许 按指定编号访问元素；允许将新的元素插入到指定编号(其后元素编号自动加 1)；允许将指定编号的元素删除（其后元素编号自动减1）；允许将环“左旋” 或“右旋”指定的数量单位(即重新编号)等。

环形数据在一些领域的问题求解中具有不可替代的地位和独特的优势，例 如在计算机设备的动态内存分配等领域。

已有的实现环形数据管理的方案大体上有两类：一类是常规的使用首尾相 连的双向链表（如图1所示）；另一类是使用闭环动态数组。当使用双向链表 来管理环形数据时，每项操作的定位过程都是通过从编号为0的首元素开始遍 历来完成的；对于插入，删除和旋转操作，还涉及少量的修改链接操作。当使 用闭环动态数组来管理环形数据时，每项操作的定位过程都建立在高效的数组 元素随机访问的基础上；而对于插入和删除操作，则涉及大量代价高昂的元素 移动操作。

当出现大规模问题时，无论是采用双向链表，还是采用闭环动态数组，环 形数据往往都很难在按指定编号查找、插入、删除元素，以及按指定数量单位 将环旋转等各项基本操作上取得令人满意的效率。表1是采用双向链表和闭环 动态数组实现的双向链表的各项操作的时间复杂度：（n表示问题规模，i表示 操作指定的元素编号，m表示旋转的数量单位）。

表1：环形数据操作对应的时间复杂度

由上表可知，当问题规模达到一定数量级(如n＝100000000)时，几乎不再 可能利用现有的方案来管理环形数据。

发明内容

本发明要解决的技术问题在于，针对上述环形数据的各项基本操作效率较 低的问题，提供一种动态内存分配中的环形数据管理器及环形数据管理方法。

本发明解决上述技术问题的技术方案是，提供一种动态内存分配中的环形 数据管理器，所述环形数据为首尾相接的双向链表；包括数组创建模块以及元 素定位模块；其中：所述数组创建模块用于创建与所述双向链表对应的闭环动 态数组；所述闭环动态数组包括N个数据项且每一数据项包括一个指针，N为 sqrt(n+1)的整数部分，n为双向链表中元素的数量，该闭环动态数组中N个数据 项的指针分别指向所述双向链表中的不同元素，且相邻数据项的指针指向的双 向链表中的元素的序号间隔为xN，其中xN=max(N,n/N)；所述元素定位模块， 用于通过所述闭环动态数组定位双向链表中的元素。

在本发明所述的动态内存分配中的环形数据管理器中，所述元素定位模块 包括区间判断单元和数据遍历单元，其中：所述区间判断单元用于根据双向链 表中待定位元素的序号获取闭环动态数组中的两个数据项，所述待定位元素介 于所述两个数据项指向的双向链表中的两个元素之间；所述数据遍历单元用于 以区间判断单元获得的两个数据项中的一个所指向元素为起始元素遍历双向 链表获得待定位元素。

在本发明所述的动态内存分配中的环形数据管理器中，所述数据遍历单元 包括起始点获取子单元和步长获取子单元，其中：起始点获取子单元用于根据 所述待定位元素距离两个数据项指向的元素的距离确定起始元素以及遍历的 方向；所述步长获取子单元用于根据所述确定的起始元素、遍历方向以及待定 位元素与起始元素的位置关系确定遍历步长；所述数据遍历单元使用所述起始 元素、遍历方向及遍历步长遍历所述双向链表获得待定位元素。

在本发明所述的动态内存分配中的环形数据管理器中，所述环形数据管理 器还包括数组维护模块，该数组维护模块包括位置获取单元、数据维护单元以 及指针修改单元，其中：所述位置获取单元用于通过元素定位模块获得待插入 或删除的元素在所述双向链表中的位置；所述数据维护单元用于在所述获得的 位置插入或删除元素；所述指针修改单元用于根据所述双向链表的变化调整所 述闭环动态数组中对应数据项的指针。

在本发明所述的动态内存分配中的环形数据管理器中，所述数组维护模块 包括旋转定位单元以及重定位单元，其中：所述旋转定位单元用于将指定数量 单位对n求模，并将求模的结果作为待定位元素；所述重定位单元用于通过元 素定位模块定位所述待定位元素，并将所述定位获得的元素作为双向链表的首 元素。

本发明还提供一种动态内存分配中的环形数据管理方法，所述环形数据为 首尾相接的双向链表；包括以下步骤：

（a）创建双向链表对应的闭环动态数组，其中所述闭环动态数组包括N 个数据项且每一数据项包括一个指针，N为sqrt(n+1)的整数部分，n为双向链表 中元素的数量；

（b）使所述闭环动态数组中N个数据项的指针分别指向所述双向链表中 的不同元素，且相邻数据项的指针指向的双向链表中的元素的序号间隔为xN， 其中xN=max(N,n/N)；

（c）通过所述闭环动态数组定位双向链表中的元素。

在本发明所述的动态内存分配中的环形数据管理方法中，所述步骤（c） 中，通过所述闭环动态数组定位双向链表中的元素包括以下步骤：

（c1）根据双向链表中待定位元素的序号获取闭环动态数组中的两个数据 项，所述待定位元素介于所述两个数据项指向的双向链表中的两个元素之间；

（c2）以步骤（c1）中获得的两个数据项中的一个所指向元素为起始元素 遍历双向链表获得待定位元素。

在本发明所述的动态内存分配中的环形数据管理方法中，所述步骤（c2） 包括：

（c21）根据所述待定位元素距离两个数据项指向的元素的距离确定起始 元素以及遍历的方向；

（c22）根据所述确定的起始元素、遍历方向以及待定位元素与起始元素 的位置关系确定遍历步长；

（c23）使用所述确定的起始元素、遍历方向及遍历步长遍历所述双向链 表获得待定位元素。

在本发明所述的动态内存分配中的环形数据管理方法中，所述方法还包 括：通过所述闭环动态数组向双向链表中插入元素或从双向链表中删除元素， 具体包括以下步骤：

通过所述闭环动态数组定位待插入或删除的元素在所述双向链表中的位 置；

在所述定位获得的双向链表中的位置插入或删除元素；

根据所述双向链表的变化调整所述闭环动态数组中对应数据项的指针。

在本发明所述的动态内存分配中的环形数据管理方法中，所述方法还包括 通过所述闭环动态数组将双向链表按指定数量单位旋转，具体包括以下步骤：

将指定数量单位对n求模，并将求模的结果作为待定位元素；

使用所述闭环动态数组定位所述待定位元素；

将所述定位获得的元素作为双向链表的首元素。

本发明的动态内存分配中的环形数据管理器及方法，通过在环形数据的双 向链表的基础上引入闭环动态数组，从而在大规模问题上，使环形数据在完成 按指定编号查找、插入、删除元素以及按指定数量单位将环旋转等基本操作时 具有出色的效率。

附图说明

图1是本发明现有双向链表的示意图。

图2是本发明动态内存分配中的环形数据管理器实施例的示意图。

图3是使用本发明的环形数据管理器进行元素定位的示意图。

图4是本发明动态内存分配中的环形数据管理方法实施例的流程图。

图5是图4中使用闭环动态数组定位元素的流程图。

图6是图5中以一个数据项为起始元素遍历获得元素的流程图。

图7是本发明动态内存分配中的环形数据管理方法中双向链表维护的流 程图。

图8是本发明动态内存分配中的环形数据管理方法中双向链表旋转的流 程图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实 施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅 仅用以解释本发明，并不用于限定本发明。

本发明在环形数据的双向链表的基础上，引入闭环动态数组作为控制管理 中心(CMC)，从而使动态环形数据在进行查找、插入、删除和旋转等基本操作 时，不再通过从编号为0的首元素开始遍历双向链表来完成。

如图2所示，是本发明动态内存分配中的环形数据管理器实施例的示意 图，其中环形数据为首尾相接的双向链表，该双向链表包括n个元素，该n 个元素按顺序排列且首尾相连（n为大于1的整数）。需要说明的是，对于双 向链表中的元素，没有任何特殊要求，可以是任何驻留于动态内存中的数据实 例，或者用于访问这些数据实例的链接（如C指针）。

本实施例中的环形数据管理器包括数组创建模块21以及元素定位模块 23，其中数组创建模块21用于创建与双向链表对应的闭环动态数组。闭环动 态数组包括N个数据项且每一数据项包括一个指针，其中N为sqrt(n+1)的整 数部分。

例如闭环动态数组的第一个数据项da[0]保存的指针所指的元素在双向 链表中的编号为xindex；除da[0]外的其它数据项的N-1个指针，其中的任意 一个数据项da[x]的指针所指的元素在双向链表中的编号为：从其相邻左侧指 针（可以是da[0]）da[x-1]所指元素顺时针到达的第xN个元素的编号。在双 向链表的动态变化过程中，闭环动态数组的数据项的指针隐含的这种编号关系 必须由始至终地得到维持，即闭环动态数组中N个数据项的指针分别指向双 向链表中的不同元素，且相邻数据项的指针指向的双向链表中的元素的序号间 隔为xN，其中，xN与N，n具有如下关系：

xN=max(N n/N的整数部分)。

上述<n，<N，xN>>关系，使得闭环动态数组相对容易实现，并且可在 0(sqrt(n))时间复杂度内完成每一个基本操作。

元素定位模块23用于通过闭环动态数组（da）定位双向链表中的元素。 该元素定位模块23的定位操作首先通过少量的逻辑计算，并利用闭环动态数 组da的随机访问特性，将范围快速锁定在0(sqrt(n))规模的元素区间；再通 过微量的逻辑计算，将范围进一步缩小到0(sqrt(n)/2)规模的元素区间；最 后，通过遍历这个元素区间，来完成指定元素的定位。整个定位过程的时间复 杂度为0(sqrt(n)/4)。

在具体实现时，上述元素定位模块23可包括区间判断单元和数据遍历单 元，上述数据遍历单元进一步包括起始点获取子单元和步长获取子单元。该元 素定位模块23的工作过程如图3所示。

区间判断单元用于根据双向链表中待定位元素的序号获取闭环动态数组 中的两个数据项，待定位元i素介于上述两个数据项指向的双向链表中的两个 元素之间，即获得闭环动态数组中da区间［j，k］，待定位元素i位于数据项 da[j]和da[k]的指针指向的双向链表的两个元素之间。该起始点获取单元执 行操作可以用伪代码表示为：

起始点获取子单元根据待定位元素距离两个数据项指向的元素的距离确 定起始元素以及遍历的方向，即选择da[j]和da[k]两者之一所指向的元素作 为遍历的起始元素，同时确定遍历方向（即以指针指向的元素靠近待定位元素 i的数据项为起始元素，并以从起始元素指向待定位元素i的方向为遍历方 向）。具体地，起始点获取子单元执行操作可以用伪代码表示为：

步长获取子单元用于根据确定的起始元素、遍历方向以及待定位元素与起 始元素的位置关系确定遍历步长(loop)。该步长获取子单元执行操作可以用伪 代码表示为：

数据遍历单元综合以上区间判断单元、起始点获取子单元和步长获取子单 元的执行结果，即使用起始点获取子单元获得的起始元素、以步长获取子单元 获得的遍历步长，并沿着起始点获取子单元获得的遍历方向遍历双向链表获得 待定位元素i，就可以完成基于待定位元素i的定位过程。

根据<n，<N，xN>>关系，可见基于闭环动态数组的定位过程的时间复杂 度为O(sqrt(n)/4)。

当然，上述数据遍历单元也可仅以区间判断单元获得的两个数据项中的任 一个所指向的双向链表中的元素为起始元素遍历双向链表获得待定位元素（遍 历方向为起始元素指向另一数据项指向的元素，遍历步长为1）。但此时数据 遍历单元的效率稍差。

上述的动态内存分配中的环形数据管理器中，还可包括数组维护模块，该 数组维护模块包括位置获取单元、数据维护单元以及指针修改单元，其中：位 置获取单元用于通过元素定位模块获得待插入或删除的元素在双向链表中的 位置；数据维护单元用于在位置获取单元获得的位置插入或删除元素；指针修 改单元用于根据双向链表的变化调整闭环动态数组中对应数据项的指针。

按指定编号向双向链表插入元素和从双向链表删除元素的过程当中，因为 <n，<N，xN>>具有“平滑”的动态变化关系，这使得对于任意的N，当n产 生变化时，只可能出现如下三种情况：当n变化时，N和xN保持不变；当n 变化时，N不变，xN加1(插入操作)或减1(删除操作)；当n变化时，N加1(插 入操作)或减1(删除操作)，xN不变。相应地，指针修改单元执行不同的操作。

1.具体地，当n变化时，N和xN保持不变，此时，为了维持闭环动态数组 da的数据项的指针与双向链表的元素的编号关系：

A．针对插入操作，在插入操作完成之后，指针修改单元执行操作可用如 下伪代码表示，其中da[k]->rlink和da[k]->llink分别表示指向da[k]所指 元素的相邻右侧和相邻左侧元素的指针：

B．针对删除操作，在删除操作完成之后，指针修改单元执行操作可用如 下伪代码表示(如果被删除的元素为da[j]所指的元素，则da[j]在删除操作之 前应该被替换为da[j]->rlink)：

以上两部分算法的时间复杂度是相同的，具体是:

0(2*(1+2+…N/2)/N)=0(N/4+1/2)=0(N/4)=0(sqrt(n)/4)。

2.当n变化时，N不变，xN加1(插入操作)或减1(删除操作)，此时，为 了维持闭环动态数组数据项的指针与双向链表的元素的编号关系，

A．针对插入操作，在插入操作完成之后，指针修改单元执行操作可用如 下伪代码表示：

B．针对删除操作，在删除操作完成之后，指针修改单元执行操作可用如

下伪代码表示(如果被删除的元素为da[j]所指的元素，则da[j]在删除操作之 前应该被替换为da[j]->rlink)：

以上两部分算法的时间复杂度也是相同的，具体是:

0(2*(1+2+…N/2))=0(N*N/4+N/2)=0(N*N/4)=0(n/4)。

3．当n变化时，N加1(插入操作)或减1(删除操作)，xN不变，此时，为 了维持闭环动态数组da的数据项的指针与双向链表的元素的编号关系，

A．针对插入操作，在插入操作完成之后，指针修改单元执行操作可使用 如下伪代码表示：

B．针对删除操作，在删除操作完成之后，指针修改单元执行操作可采用 如下伪代码表示(如果被删除的元素为da[j]所指的元素，则da[j]在删除操作

之前应该被替换为da[j]->rlink)：

以上两部分算法的时间复杂度只相差0(xN)，具体分别是:

A．0((2*(1+2+…+N/2)/N+xN)=0(N/4+1/2+xN)=0(N/4+xN)

考虑到N≈xN，以上时间复杂度等价于：

0(5*N/4)=O(5*sqrt(n)/4)。

B．0((2*(1+2+…+N/2)/N)=O(N/4+1/2)=0(N/4)=0(sqrt(n)/4)。

基于对以上三种情况指针修改单元的操作的分析，可以计算用于闭环动态 数组维护的代价：

A．插入操作

0(((2*N-1)*N/4+N*N/4+5*N/4)/(2*N+1))=0(3*N/8)=0(3*sqrt(n)/8)

B．删除操作

0(((2*N-1)*N/4+N*N/4+N/4)/(2*N+1))=0(3*N/8)=O(3*sqrt(n)/8)

上述数组维护模块还可包括单元旋转定位单元以及重定位单元，以实现双 向链表按指定数据单位旋转。上述旋转定位单元用于将指定数量单位对n求 模，并将求模的结果作为待定位元素；重定位单元用于通过元素定位模块使用 所述待定位元素，并将定位获得的元素作为双向链表的首元素。

综上，上述动态内存分配中的环形数据管理器对于按指定编号查找、插入、 删除元素以及按指定数量单位将环旋转等基本操作，和已有技术在算法时间复 杂度上的比较具体如下：

特别地，本发明的动态内存分配中的环形数据管理器在n>=4时优于现有方 案；而闭环动态数组合理的创建点可以设置在某次插入操作之后；另外，创建 闭环动态数组时，可以将xindex初始化为0，与此同时，da[0]应该设置为指向 双向链表首元素的指针。

如图4所示，是本发明动态内存分配中的环形数据管理方法实施例的流程 示意图，其中环形数据为首尾相接的双向链表，该双向链表包括n个元素，该n 个元素按顺序排列且首尾相连（n为大于1的整数）。需要说明的是，对于双向 链表中的元素，没有任何特殊要求，可以是任何驻留于动态内存中的数据实例， 或者用于访问这些数据实例的链接（如C指针）。

本实施例中的方法包括以下步骤：

步骤S41：创建双向链表对应的闭环动态数组，其中所述闭环动态数组包 括N个数据项且每一数据项包括一个指针，N为sqrt(n+1)的整数部分，n为双向 链表中元素的数量。

步骤S42：使所述闭环动态数组中N个数据项的指针分别指向所述双向链 表中的不同元素，且相邻数据项的指针指向的双向链表中的元素的序号间隔为 xN，其中xN=max(N,n/N)。

步骤S43：通过所述闭环动态数组定位双向链表中的元素。

如图5所示，是图4中定位双向链表中元素的具体流程，其包括以下步骤：

步骤S431：根据双向链表中待定位元素的序号获取闭环动态数组中的两个 数据项，所述待定位元素介于所述两个数据项指向的双向链表中的两个元素之 间。

步骤S432：以步骤S431中获得的两个数据项中的一个所指向元素为起始 元素遍历双向链表获得待定位元素。

如图6所示，图5中的双向链表遍历步骤包括：

步骤S4321：根据所述待定位元素距离两个数据项指向的元素的距离确定 起始元素以及遍历的方向。

步骤S4322：根据所述确定的起始元素、遍历方向以及待定位元素与起始 元素的位置关系确定遍历步长。

步骤S4323：使用步骤S4321及步骤S4322中确定的起始元素、遍历方向及 遍历步长遍历所述双向链表获得待定位元素。

如图7所示，本发明动态内存分配中的环形数据管理方法还包括：通过闭 环动态数组向双向链表中插入元素或从双向链表中删除元素，包括以下步骤：

步骤S71：通过闭环动态数组定位待插入或删除的元素在所述双向链表中 的位置。

步骤S72：在定位获得的双向链表中的位置插入或删除元素。

步骤S73：根据双向链表的变化调整闭环动态数组中对应数据项的指针。

如图8所示，本发明动态内存分配中的环形数据管理方法还包括：通过闭 环动态数组将双向链表按指定数量单位旋转，包括以下步骤：

步骤S81：将指定数量单位对n求模，并将求模的结果作为待定位元素。

步骤S82：使用闭环动态数组定位所述待定位元素。

步骤S83：将定位获得的元素作为双向链表的首元素。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局 限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易 想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护 范围应该以权利要求的保护范围为准。