用跳表实现的动态数组

用类似跳表的数据结构来实现动态数组。该数组的插入、删除、以及用索引访问元素的平均时间复杂性均为O(logn)。比起一般的线性动态数组，它的插入和删除要快很多（一般数组的插入和删除的平均时间复杂性均为O(n)），可用于插入和删除操作比较多的场合。

using System;
using System.Collections;

namespace ClassData.Index
{

 public class SkipIndexList
 {
  static Random r=new Random();
  public  IEnumerator GetEnumerator()
  {
   return (new SkipIndexListEnumerator(this));
  }
  public class SkipIndexListEnumerator:IEnumerator
  {
   private SkipListNode ln;
   private SkipListNode head;
   public SkipIndexListEnumerator(SkipIndexList SkipIndexList)
   {
    head=SkipIndexList.head;
    ln=head;
   }
   public bool MoveNext()
   {
    ln=ln.nodelink[0].nextlink;
    return (!(ln.nodelink[0].nextlink==null));
   }
   public void Reset()
   {
    ln=head;
   }
   public object Current
   {
    get
    {
     return ln;
    }
   }
  }

  public class SkipListNode
  {

   public struct link
   {
    public SkipListNode nextlink;
    public SkipListNode previewlink;
    public int distance;
   }
   public object data;
   public int level;

   public link[] nodelink;

   public SkipListNode(int Level)
   {
    nodelink=new link[Level+1];
    level=Level;
   }

   public  int Index
   {
    get
    {
     int i=0,l=0;
     for(SkipListNode ln=this;ln.nodelink[l].distance>0;ln=ln.nodelink[l].previewlink)
      if (ln.level>=l)
      {
       l=ln.level;
       i+=ln.nodelink[l].distance;
      }
     return i;
    }
   }
  }

  protected int MaxLevel;
  private SkipListNode head,tail;
  private int Levels;
  private int mCount;

  public SkipIndexList()
  {
   newSIL(32);
  }
  public SkipIndexList(int maxCount)
  {
   newSIL((int)System.Math.Log(maxCount,2)+1);
  }
  private void newSIL(int maxlevel)
  {
   MaxLevel=maxlevel;
   head=new SkipListNode(MaxLevel);
   tail=new SkipListNode(MaxLevel);
   for(int i=0;i<=MaxLevel;i++)
   {
    head.nodelink[i].nextlink=tail;
    head.nodelink[i].distance=0;
    head.level=MaxLevel;
    tail.nodelink[i].previewlink=head;
    tail.nodelink[i].distance=1;
    tail.level=MaxLevel;
   }
  }
  public  SkipListNode ItemAt(int Index)
  {
   if (Index>mCount)
    return null;
   SkipListNode ln=head;
   for(int i=0,l=Levels;l>=0;l--)
    while (ln.nodelink[l].nextlink.nodelink[l].distance+i<=Index)
    {
     ln=ln.nodelink[l].nextlink;
     i+=ln.nodelink[l].distance;
    }
   return ln;
  }
  public  SkipListNode Insert(object data,int Index)
  {
   if (Index<=0) return null;
   int level;
   for(level=0;r.NextDouble()<=0.5 && level<MaxLevel;level++);
   SkipListNode newln=new SkipListNode(level);
   SkipListNode Insertln,pln;
   newln.data=data;
   if (Index>mCount)
    Insertln=tail;
   else
    Insertln=(SkipListNode)ItemAt(Index);
   int newl=newln.level;
   if (Levels<newl)
    Levels=newl;
   int l=0,d=1;
   for(;l<=newl;l++)
   {
    if (l>Insertln.level)
     for(;Insertln.level < l;Insertln=Insertln.nodelink[Insertln.level].nextlink)
      d+=Insertln.nodelink[Insertln.level].nextlink.nodelink[Insertln.level].distance;
    newln.nodelink[l].nextlink=Insertln;
    pln=Insertln.nodelink[l].previewlink;
    newln.nodelink[l].previewlink=pln;
    pln.nodelink[l].nextlink=newln;
    Insertln.nodelink[l].previewlink=newln;
    newln.nodelink[l].distance=Insertln.nodelink[l].distance-d+1;
    Insertln.nodelink[l].distance=d;
   }
   for(l=newl+1;l<=MaxLevel;l++)
   {
    for(;Insertln.level < l;Insertln=Insertln.nodelink[Insertln.level].nextlink);
    Insertln.nodelink[l].distance+=1;
   }
   mCount++;
   return newln;
  }
  public  SkipListNode Insert(object data)
  {
   return Insert(data,mCount+1);
  }
  public  bool Delete(int Index)
  {
   if ((Index<=0) || (Index>mCount))
    return false;
   SkipListNode delln=(SkipListNode)ItemAt(Index);
   SkipListNode nnl=head;
   SkipListNode pnl;
   for(int l=delln.level;l>=0;l--)
   {
    nnl=delln.nodelink[l].nextlink;
    pnl=delln.nodelink[l].previewlink;
    nnl.nodelink[l].distance+=delln.nodelink[l].distance;
    nnl.nodelink[l].distance-=1;
    nnl.nodelink[l].previewlink=pnl;
    pnl.nodelink[l].nextlink=nnl;
   }
   for(int l=delln.level+1;l<=MaxLevel;l++)
   {
    for(;nnl.level < l;nnl=nnl.nodelink[nnl.level].nextlink);
    nnl.nodelink[l].distance-=1;
   }
   mCount--;
   return true;
  }
  public  int Count
  {
   get
   {
    return mCount;
   }
  }
  public  void Clear()
  {
   newSIL(MaxLevel);
  }

 }
}

本文地址：http://com.8s8s.com/it/it37168.htm