跳躍表的定義及實作

跳躍表:

Skip List是一種随機化的資料結構，基于并聯的連結清單，其效率可比拟于二叉查找樹（對于大多數操作需要O(log n)平均時間）。

基本上，跳躍清單是對有序的連結清單增加上附加的前進連結，增加是以随機化的方式進行的，是以在清單中的查找可以快速的跳過部分清單(是以得名)。

所有操作都以對數随機化的時間進行。Skip List可以很好解決有序連結清單查找特定值的困難。

一個跳表，應該具有以下特征：

1.一個跳表應該有幾個層（level）組成；

2. 跳表的第一層包含所有的元素；

3. 每一層都是一個有序的連結清單；

4.如果元素x出現在第i層，則所有比i小的層都包含x；

5.第i層的元素通過一個down指針指向下一層擁有相同值的元素；

6.在每一層中，都有INT_MIN作為起始結點，INT_MAX作為結束結點。 //這裡其實也可以用初始化的方式直接把排序過的連結清單的最小值作為起始結點，最大值作為結束結點，并且最大層為maxlevel

7.root指針指向最高層的第一個元素。

基于以上，我對這個跳躍表的了解，認為這種資料結構 主要用于存儲擁有大量結點，并且需要增删減查功能的連結清單。建立的跳躍表結點結構體:

typedef struct Slnode
{
int data;           //資料
unsigned level;     //層
struct Slnode *next;
struct Slnode *down;
Slnode(int d,unsigned lev):data(d),level(lev),next(NULL),down(NULL){}
Slnode(int d):data(d),level(1),next(NULL),down(NULL){}
}Slnode;
           

每個結點都需要儲存目前的資料和層數，以及橫向(next)以及縱向(down)指針資訊。

邊寫才邊發現，其實我用于存儲的 int data，應該要作為資料索引更改為 int key，并且不允許插入相同的key,然後在結點中再增加一項typedef data作為需要存儲的資料才是一個正确的跳躍表（感覺有點象哈希了hahah），

不過由于時間原因，我就先放這了，大略思想應該是對的。

/*
跳躍表方法:
    Skitlist(unsigned max = 3) //構造函數，可以自定義最大層次，預設為3
    addnode(int data) //插入結點，資料為data
    size()  //傳回第一層資料個數
    findnode(int data) //查找結點，根據特定的資料查找到該結點并傳回（就是這裡覺得不對勁的,開始我寫得函數原型是用data查data，hahah簡直有病，是以覺得data應該更改為key，并且結點中增加一項 typedef data;）
    deledata(int data) //根據data删除該結點
    PrBottom() //顯示第一層元素排列情況
    Prtotol()  //顯示所有層元素排列情況
*/

#include<iostream>
#include<cstdlib>   //需要利用rand()
#include<ctime>     //利用系統時間擷取随機數種子
typedef struct Slnode
{
int data;         //資料
unsigned level;   //層
struct Slnode *next;
struct Slnode *down;
Slnode(int d,unsigned lev):data(d),level(lev),next(NULL),down(NULL){}
Slnode(int d):data(d),level(),next(NULL),down(NULL){}
}Slnode;


class Skitlist
{
private:
    Slnode *root;  //root指針指向最高層的第一個元素。
    unsigned Maxlevel;
    unsigned nodecount;

public:
Skitlist(unsigned max = ):Maxlevel(max),nodecount()  //預設三層   構造函數給出了跳躍表開始的頭和尾
{
      root = new Slnode(INT_MIN,Maxlevel);         //初始跳表第一個頂層結點
      root->next = new Slnode(INT_MAX,Maxlevel);   //初始跳表第二個頂層結點

      Slnode *temph = root;
      Slnode *templ = root->next;

      for(int i = ;i<Maxlevel;i++)
      {
        Slnode *temp = new Slnode(root->next->data,root->next->level-i); //最後一個結點不用指向後面的結點了，是以先解決最後的結點
        templ->down = temp;
        /*root->next向下一層複制結點*/
        temp = new Slnode(root->data,root->level-i);
        temph->down = temp;
         /*root向下一層複制結點*/
        templ = templ->down;
        temph = temph->down;
        temph->next = templ;  //同層也用next連接配接
      }
}

unsigned randomLevel()  //利用随機數産生一個不大于Maxlevel的數
{
 // srand((unsigned)time(NULL));
  unsigned k=;
  while (rand()%)
    k++;
  k=(k<Maxlevel)?k:Maxlevel;
    return k;
}


void addnode(int data)  //插入結點，自動配置設定層次和位置
{
      Slnode *node = new Slnode(data,randomLevel());//建立結點，并且确定層次
      Slnode *dnode = node;

      Slnode *temp = root;

      std::cout<<"新添加結點資料："<<node->data<<"  level:"<<node->level<<std::endl;

      for(;temp&&temp->next;temp=temp->down)        //右下角一直走，但不能走到最後一個結點之後
      {
        while(temp->next->data < node->data)      //把新結點按大小順序插傳入連結表中(插到最底層的temp->next中)
        {
         temp = temp->next;
        }                                       //沒到底層前需要下移了，可以把data結點插進來
       if(temp->level == node->level)
       {
      // Slnode *nodez = new Slnode(node->data,temp->level);
       node->next = temp->next;
       temp->next = node;
       }
       else if(temp->level < node->level)
       {
         Slnode *nodez = new Slnode(node->data,temp->level);
          nodez->next = temp->next;
          temp->next = nodez;
          dnode->down = nodez;
          dnode = nodez;
       }
      }
     nodecount++;
}

unsigned size(){return nodecount;}

Slnode* findnode(int data)  //傳回元素的指針
{
  Slnode *temp = root;
  int findcount = ;
  while(temp)
  {
      while(temp->next->data<=data && temp->next->data!=INT_MAX)
      {
         temp = temp->next;
          findcount++;
          std::cout<<"前進一步"<<std::endl;
          if(data==temp->data)
            {
              std::cout<<"總共走了"<<findcount<<"步"<<std::endl;
              return temp;
            }
      }

   temp = temp->down;
   std::cout<<"下走一步"<<"temp.level:"<<temp->data<<std::endl;
   findcount++;
  }

  return NULL;
}


void deledata(int data)  //删除data的元素
{
  Slnode *del = findnode(data);  //需要删除的結點
  if(!del) return;  //找不到該結點

  //std::cout<<"找到該結點,del->level:"<<del->level<<std::endl;

  Slnode *temp = root;
  for(unsigned i =del->level,j = root->level;j-i;i++)
   temp = temp->down;                   //先把temp移動到和del結點平齊的level

  //std::cout<<"目前temp->level:"<<temp->level<<std::endl;

  while(del)
  {
      Slnode *temp2 = temp;
      while(temp2->next->data!=INT_MAX)
      {
          if(temp2->next==del)
            {
              temp2->next = del->next;
              Slnode *temp3 = del;
              del = del->down;
              delete temp3;
              break;
            }
        temp2 = temp2->next;
      }
   temp = temp->down;
  // std::cout<<"下移"<<std::endl;
  }

nodecount--;
}


void PrBottom()  //顯示底層元素排列情況
{
  Slnode *temp = root;
  while(temp->down)
    temp = temp->down;
  std::cout<<"底層元素排列:";
  while(temp->next&&temp->next->data!=INT_MAX)
  {
      temp = temp->next;
      std::cout<<temp->data<<" ";
  }
}


void Prtotol()  //顯示所有層元素排列情況
{
  Slnode *temp = root;
  while(temp)
  {
      Slnode *temp2 = temp;
      while(temp2->next && temp2->next->data!=INT_MAX)
      {
         temp2 = temp2->next;
         std::cout<<temp2->data<<" ";
      }
       std::cout<<std::endl;
   temp = temp->down;
  }
}



};