• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

(数据结构与算法)跳表实现

开发技术 开发技术 3小时前 1次浏览

————恢复内容开始————

  跳表是一种不太常用的数据结构。

  跳表的基本概念:

  定义:(SkipList)增加了向前指针的链表叫做指针。跳表全称叫做跳跃表,简称跳表。跳表是一个随机化的数据结构,实质是一种可以进行二分查找的有序链表。跳表在原有的有序链表上增加了多级索引。通过索引来实现快速查询。跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。

  详解:对于一个单链表来说,即使链表的数据 是有序的,如果我们想找一个数据,也得必须从头到尾遍历链表。这样子的时间复杂度为O(n)。

 我们可以对链表建立索引,也就是说每两个结点提取一个结点到上一级,我们把抽出来的那一级叫做索引或者索引层。

 

 

 

第一级索引:  1———->4———->7———>9——–>13———>17

                       |                |               |             |               |                 |  

                       |                |               |             |               |                 |

原始链表:     1–3——–4—–5—–7—–8—-9—10—13—-16—–17

 

 

       假设我们现在要查找16这个节点,我们现在第一级索引(索引层)开始遍历查找,当到13时,发现下一级索引为17,因为本身链表有序,所以,就降到原始链表开始查找,只需要两个节点就可以找到16这个节点。如果使用原来的链表方式进行查找值为16的话,则需要便利10个节点才能找到,但是现在只需要遍历7个节点就可以找到,从而提高了查找效率。

       所以我们可以根据以上发现来继续创造第二级索引层,也就是每两个一级索引节点就抽到一个节点到第二级索引中,再来查找16。只需要遍历6个节点就可以了。

 

第二级索引:1————————-7———————-13————–17

                      |                               |                            |                    |

                      |                               |                             |                   |

第一级索引:  1———->4———->7———>9——–>13———>17

                       |                |               |             |               |                 |  

                       |                |               |             |               |                 |

原始链表:     1–3——–4—–5—–7—–8—-9—10—13—-16—–17

 

以此类推。

 

跳表的JAVA代码实现:

// 跳表中存储的是正整数,并且存储的数据是不重复的
public class SkipList {
	
	private static final int MAX_LEVEL = 16;    // 结点的个数
	
	private int levelCount = 1;   // 索引的层级数
	
	private Node head = new Node();    // 头结点
	
	private Random random = new Random();
 
	// 查找操作
	public Node find(int value){
		Node p = head;
		for(int i = levelCount - 1; i >= 0; --i){
			while(p.next[i] != null && p.next[i].data < value){
				p = p.next[i];
			}
		}
		
		if(p.next[0] != null && p.next[0].data == value){
			return p.next[0];    // 找到,则返回原始链表中的结点
		}else{
			return null;
		}
	}
	
	// 插入操作
	public void insert(int value){
		int level = randomLevel();
		Node newNode = new Node();
		newNode.data = value;
		newNode.maxLevel = level;   // 通过随机函数改变索引层的结点布置
		Node update[] = new Node[level];
		for(int i = 0; i < level; ++i){
			update[i] = head;
		}
		
        Node p = head;
        for(int i = level - 1; i >= 0; --i){
        	while(p.next[i] != null && p.next[i].data < value){
        		p = p.next[i];
        	}
        	update[i] = p;
        }
        
        for(int i = 0; i < level; ++i){
        	newNode.next[i] = update[i].next[i];
        	update[i].next[i] = newNode;
        }
        if(levelCount < level){
        	levelCount = level;
        }
	}
	
	// 删除操作
	public void delete(int value){
		Node[] update = new Node[levelCount];
		Node p = head;
		for(int i = levelCount - 1; i >= 0; --i){
			while(p.next[i] != null && p.next[i].data < value){
				p = p.next[i];
			}
			update[i] = p;
		}
		
		if(p.next[0] != null && p.next[0].data == value){
			for(int i = levelCount - 1; i >= 0; --i){
				if(update[i].next[i] != null && update[i].next[i].data == value){
					update[i].next[i] = update[i].next[i].next[i];
				}
			}
		}
	}
	
	// 随机函数
	private int randomLevel(){
		int level = 1;
		for(int i = 1; i < MAX_LEVEL; ++i){
			if(random.nextInt() % 2 == 1){
				level++;
			}
		}
		
		return level;
	}
	
	// Node内部类
	public class Node{
		private int data = -1;
		private Node next[] = new Node[MAX_LEVEL];
		private int maxLevel = 0;
		
		// 重写toString方法
		@Override
		public String toString(){
			StringBuilder builder = new StringBuilder();
			builder.append("{data:");
			builder.append(data);
			builder.append("; leves: ");
			builder.append(maxLevel);
			builder.append(" }");
			return builder.toString();
		}
	}
	
	// 显示跳表中的结点
	public void display(){
		Node p = head;
		while(p.next[0] != null){
			System.out.println(p.next[0] + " ");
			p = p.next[0];
		}
		System.out.println();
	}
	
}

  

 

  


程序员灯塔
转载请注明原文链接:(数据结构与算法)跳表实现
喜欢 (0)