跳表的java实现，转载自网络，仅供自己学习使用

文档结构：

1、代码结构

2、代码实现

1、代码结构

节点类：

String key 键值 对跳跃表的操作都是根据键值进行的

Int value  实际值

Node  up,down,left,right; 每个节点都有四个方向

String tou;

String wei; 每层链表的头和尾节点

跳跃表类：

Head 头节点

Tail 尾结点

H 层数

Size 元素个数

Random 随机数，用来确定需不需要增加层数 即：掷硬币

findF () 按从小到大的顺序找到应该插入的位置 插入排序法

Add () 添加节点函数，在最底层插入结点后，进行掷硬币来确定是否需要曾增加层数，直到掷硬币不能增加层数为止，增加层数的同事需要把增加之后的节点进行连接。

Find() 根据跳跃表进行查找并打印路线。查找从最上层开始然后找到被查找节点的前个节点小于被查找节点，然后被查找节点的后一个节点大于其被查找节点，则从被查找节点的前一个节点向下走down，然后继续向右查找，直到找到为止。

2、代码实现

  1. package 跳跃表;  
  2. import java.util.*;  
  3. public class SkipList {  
  4.     public Node head;   //头节点  
  5.     public Node tail;   //尾结点  
  6.     public int h;   //层数  
  7.     public int size;    //元素个数  
  8.     public Random rand; //每次的随机数用来确定需不需要增加层数  
  9.     public SkipList(){  
  10.         Node p1 = new Node(Node.tou,0);  
  11.         Node p2 = new Node(Node.wei, 0);  
  12.         head=p1;  
  13.         tail=p2;  
  14.         head.setRight(tail);  
  15.         tail.setLeft(head);  
  16.         h=0;  
  17.         size=0;  
  18.         rand = new Random();  
  19.     }  
  20.     public boolean isEmpty(){  
  21.         if(size==0){  
  22.             return true;  
  23.         }  
  24.         return false;  
  25.     }  
  26.     //找到需要插入位置的前一个节点  
  27.     public Node findF(String k){  
  28.         Node temp;  
  29.         temp=head;  
  30.         while(true){  
  31.             while(temp.getRight().key!=Node.wei&&temp.getRight().key.compareTo(k)<=0){  
  32.                 /* 
  33.                  * 当链表最底层不为空的时候，从当前层向尾部方向开始查找，直到查找temp.getRight的下一个值大于 当前k的值为止，此时temp小于或等于当前k的值 
  34.                  *  要插入的位置即为temp之后的位置了 
  35.                  */  
  36.                 temp=temp.getRight();  
  37.             }  
  38.             if(temp.getDown()!=null){  
  39.                 temp=temp.getDown();  
  40.             }else{  
  41.                 break;  
  42.             }  
  43.               
  44.         }  
  45.         return temp;    //找到节点并返回  
  46.           
  47.     }  
  48.     public int add(String k, int v){  
  49.         Node temp, temp1;  
  50.         temp=findF(k);  
  51.         int i;  //当前层数  
  52.         if(k.equals(temp.getKey())){  
  53.             System.out.println("对象属性完全相同无法添加！");  
  54.             int a=temp.value;  
  55.             temp.value=v;  
  56.             return  a;  
  57.         }  
  58.         temp1=new Node(k,v);  
  59.         temp1.setLeft(temp);  
  60.         temp1.setRight(temp.getRight());  
  61.         temp.getRight().setLeft(temp1);  
  62.         temp.setRight(temp1);  
  63.         i=0;  
  64.           
  65.         while(rand.nextDouble()<0.5){    //进行随机，是否需要 在上层添加  
  66.             if(i>=h){    //若当前层数超出了高度，则需要另建一层  
  67.                 Node p1 ,p2 ;  
  68.                 h=h+1;  
  69.                 p1=new Node(Node.tou,0);  
  70.                 p2=new Node(Node.wei,0);  
  71.                   
  72.                 p1.setRight(p2);  
  73.                 p1.setDown(head);  
  74.                   
  75.                 p2.setLeft(p1);  
  76.                 p2.setDown(tail);  
  77.                   
  78.                 head.setUp(p1);  
  79.                 tail.setUp(p2);  
  80.                   
  81.                 head=p1;  
  82.                 tail=p2;  
  83.             }  
  84.             while(temp.getUp() == null){  
  85.                 temp=temp.getLeft();  
  86.             }  
  87.             temp=temp.getUp();  
  88.             Node node=new Node(k,v);  
  89.             node.setLeft(temp);  
  90.             node.setRight(temp.getRight());  
  91.             node.setDown(temp1);  
  92.               
  93.             temp.getRight().setLeft(node);  
  94.             temp.setRight(node);  
  95.             temp1.setUp(node);  
  96.               
  97.             temp1=node;  
  98.             i=i+1;    
  99.               
  100.         }  
  101.               
  102.         size=size+1;  
  103.         return  0;  
  104.     }  
  105.     //节点查找  
  106.     public Node find(String k){  
  107.         Node temp=head;  
  108.         Node node;  
  109.         node=temp;  
  110.         System.out.println("查找路线"); //用于测试  
  111.         while(temp!=null){  
  112.             while(node.getRight().key!=Node.wei&&node.getRight().getKey().compareTo(k)<=0){//&&node.getRight().getValue()!=v  
  113.                 node=node.getRight();  
  114.                 System.out.print("--->"+node.getKey());  
  115.             }  
  116.               
  117.             if(node.getDown()!=null){  
  118.                 node=node.getDown();  
  119.                 System.out.print("--->"+node.getKey());  
  120.             }else{  
  121.                 if(node.key.equals(k)){//&&node.getRight().value==v  
  122.                     //node.setValue(111111111); //修改  
  123.                     System.out.println("--->"+node.getKey());  
  124.                     System.out.print("--->"+node.getValue());  
  125.                       
  126.                     return node;                                                      
  127.                 }  
  128.                 return null;  
  129.             }  
  130.               
  131.               
  132.         }  
  133.         return null;  
  134.     }  
  135.     //节点删除  
  136.     public void delNode(String k){  //调用查找函数，删除最底层的某个节点，并把其节点的左右相连，和链表操作一样，只是其上方若有则都需要调整  
  137.         Node temp=find(k);  
  138.         while(temp!=null){  
  139.             temp.getLeft().setRight(temp.getRight());  
  140.             temp.getRight().setLeft(temp.getLeft());  
  141.             temp=temp.getUp();  
  142.         }  
  143.     }  
  144.     public void print(){  
  145.         Node node;  
  146.         Node node1=head;  
  147.           
  148.           
  149.         while(node1!=null){  
  150.             int k=0;  
  151.             node=node1;  
  152.             while(node!=null){  
  153.                 System.out.print(node.getKey()+" ");  
  154.                 k++;  
  155.                 node=node.getRight();  
  156.             }  
  157.               
  158.             System.out.print(" ");  
  159.             System.out.print("("+k+")");  
  160.             //System.out.print(node.getKey());  
  161.             System.out.println();  
  162.             //node=node1.getDown();  
  163.             node1=node1.getDown();  
  164.               
  165.         }  
  166.     }  
  167.       
  168. }  
  169. class Node{  
  170.     public String key;  
  171.     public int value;  
  172.     public Node up, down,left , right;  
  173.     public static String tou=new String("--头--");  
  174.     public static String wei=new String("--尾--");  
  175.     public Node(String k, int v){  
  176.         this.key=k;  
  177.         this.value=v;  
  178.         up=down=left=right=null;  
  179.     }  
  180.     public void setUp(Node up){  
  181.         this.up=up;  
  182.     }  
  183.     public Node getUp(){  
  184.         return up;  
  185.     }  
  186.     public void setDown(Node down){  
  187.         this.down=down;  
  188.     }  
  189.     public Node getDown(){  
  190.         return down;  
  191.     }  
  192.     public void setLeft(Node left){  
  193.         this.left=left;  
  194.     }  
  195.     public Node getLeft(){  
  196.         return left;  
  197.     }  
  198.     public void setRight(Node right){  
  199.         this.right=right;  
  200.     }  
  201.     public Node getRight(){  
  202.         return right;  
  203.     }  
  204.     public void setKey(String k){  
  205.         this.key=k;  
  206.     }  
  207.     public String getKey(){  
  208.         return key;  
  209.     }  
  210.     public void setValue(int v){  
  211.         this.value=v;  
  212.     }  
  213.     public int getValue(){  
  214.         return value;  
  215.     }  
  216.       
  217. }  
  218.   
  219. package 跳跃表;  
  220.   
  221. public class Test {  
  222.     public static void main(String[] args){  
  223.         SkipList s = new SkipList();  
  224. //      s.add("AAA", 122);  
  225.         int i=0;  
  226.         for(;i<30;i++){  //随机数字进行测试  
  227.             s.add(String.valueOf(i), i);  
  228.         }  
  229.         s.print();  
  230.         System.out.println(" ---------- ");               
  231.         if(s.find("22")!=null){ //查找  
  232.             System.out.println(" OK");  
  233.         }else{//找不到  
  234.             System.out.println(" false");  
  235.               
  236.         }  
  237.         s.delNode("0"); //删除  
  238.         s.print();  
  239.     }  
  240. }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/blackdd/p/8477431.html