顺序表

passby — Fri, 12 Nov 2010 05:42:00 GMT

一.寄存数组
         这是我们最常见的顺序表表现方式，一般的大数据量程序，如果不能有边读边处理的方法，就需要首先保留所有的输入，从而能够在而后的过程中进行处理。
         主要应用：
                           a、各类算法的线性预处理
                           b、保留线性逻辑关系
                           c、记忆化辅助
          优点：
                    1、静态
                    2、随机
                    3、高效
          缺点：
                    1、插入与删除操作效率极度低下
                    2、内存分配不灵活
         技巧：
                   1、满足递推与DP内存需求
         滚动数组
                   2、满足图的快速判重
                   化行为数状态压缩

二.哈希数组
            从广义上说哈希是一种键值对应的操作，是从数域到值域的一一映射，也就是我们通常称其为哈希函数的由来。
            数组满足哈希的3个必要条件：
                     1、键——index
                     2、值——value
                     3、键值映射（index->value）O（1）
            散列函数的选用
            一般情况下我们使用哈希数组，采用的是开放散列策略，也就是说内存与键是一一对应，即hash[key]=value,在对于key值要求不大的情况下是很好的选择。
            然而当要求的key很大时该怎么办，此时就应该选用一个好的映射函数使hash[f(key)]=value，且f(key)的值必定均匀分布在映射区间内。当然要找到这样的函数是十分困难的，我们无法了解到数据的具体信息，因此一般的f(key)为key%p，p为一个质数，结合数论知识，我们可以知道当gcd(key,p)=1时，key是一个循环群生成元，使用这个性质，我们可以少了许多因大多数冲突而引发避免策略造成的效率问题。

三、树状数组
           对于序列a，我们设一个数组C定义C[i] = a[i – 2^k + 1] + … + a[i]，k为i在二进制下末尾0的个数。
           K的计算可以这样:
                                           2^k=x and (x xor (x-1))
                                           以6为例
                                           (6)10=(0110)2
                                           xor    6-1=(5)10=(0101)2
                                           (0011)2
                                           and          (6)10=(0110)2
                                           (0010)2

         function Lowbit(x: Integer): Integer;
         begin
                Lowbit := x and (x xor (x – 1));
         end;
         若要修改a[i]的值,则C数组的修改是:
          Procedure change(k,delta:integer);
          Begin
                   while k<=n do
                    begin
                            C[k]:=C[k]+delta;
                            k:=k+lowbit(k);
                    End;
          End;
         若要求I..j的元素和的值,则求出1..I-1的值和1..j的值.
         Function getsum(k:integer):integer;
         Var t:integer;
         Begin
                  t:=0;
                  while k>0 do
                  begin
                          t:=t+c[k];
                          k:=k-lowbit(k);
                  end;
                  getsum:=t;
         End;

passby 2010-11-12 13:42 发表评论

C++博客-passby

顺序表