补丁数组(增删改查都较快的数组)

1 简介
    补丁数组是一种数据结构,封装后可以像普通数组一样使用,效率又较高。
2 效率
    假设N为数组长度,M为以前对数组增删的总次数
    普通数组:
        /:O(N);查:O(1)
    链表:
        /:O(1);查:O(N)
    补丁数组:
        /:O(M);查:O(M)
3 实现
    假设封装后用户看到的数组为数组a[]。(方便起见,假设为整形数组)
    开数组b[N]为实际储存数组;c[]为下标补丁数组;d[]为数据补丁数组。其中b.length=Nc.lengthd.length需要大于增/删总次数。
3.1 
    假设在a[i]a[i+1]中增加一个值为x
1c[]中增加一条数据:表示从i+1开始的所有下标,在a映射到b时全部-1。(如i=2之后查a[5],那么应取出b[4]
2d[]中增加一条数据:表示a[i+1]的值为x,并且只计算了c[k]以前的偏移。(意味着:如果后来c[]又有新补丁数据,那么还得计算后面的) 3.2 假设删除a[i] 1c[]中增加一条数据:表示从i+1开始的所有下标,在a映射到b时全部+1。(如i=2之后查a[5],那么应取出b[6] 3.3 如正常数组。 3.4 假设查a[i]。假设最终取出b[j] 1)j=i; 2)遍历c[],适时地修改(就是+1/-1)j值。 4 样例 1 语句:建立数组,N=8,并赋值 实现: a[]=[3,4,2,1,7,0,6,8]
b[]=[3,4,2,1,7,0,6,8]
c[]={}
d[]={} 2 语句:删除a[1] 实现: a[]=[3,2,1,7,0,6,8] b[]=[3,NULL,2,1,7,0,6,8] c[]={所有a[i]i>=1的在查询时+1”} d[]={} 3 语句:增加a[3]a[4]之间一个数为9 实现: a[]=[3,2,1,7,9,0,6,8] b[]=[3,NULL,2,1,7,0,6,8] c[]={“所有a[i]i>=1的在查询时+1”,所有a[i]i>4的在查询时-1”} d[]={“a[3]a[4]之间的为9,而且此时计算的偏移只计算了c[0]c[1]”} 4 语句:查询a[2] 实现: a[]=[3,2,1,7,9,0,6,8] b[]=[3,NULL,2,1,7,0,6,8] c[]={“所有a[i]i>=1的在查询时+1”,“所有a[i]i>4的在查询时-1”} d[]={“a[3]a[4]之间的为9,而且此时计算的偏移只计算了c[0]c[1]”} 执行算法: j=2; 查看c[0]得:j=3; 查看c[1]得:j=3; 读取b[3]得:a[2]=1; 5 用途 适用于同时需要 增删 和 改查 的地方。当N很大,增删较少时有优势。

补丁数组(增删改查都较快的数组)

上一篇:报喜鸟集团有限公司_百度百科


下一篇:在CentOS 6 中安装 Apache,Mysql, PHP