国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

認識與實現Skip List

Yangyang / 1463人閱讀

摘要:跳表全稱叫做跳躍表,簡稱跳表。跳表在原有的有序鏈表上面增加了多級索引,通過索引來實現快速查找。跳表不僅能提高搜索性能,同時也可以提高插入和刪除操作的性能。每個節點包含兩個指針,一個指向同一鏈表中的下一個元素,一個指向下面一層的元素。

前言

增加了向前指針的鏈表叫作跳表。跳表全稱叫做跳躍表,簡稱跳表。跳表是一個隨機化的數據結構,實質就是一種可以進行二分查找的有序鏈表。跳表在原有的有序鏈表上面增加了多級索引,通過索引來實現快速查找。跳表不僅能提高搜索性能,同時也可以提高插入和刪除操作的性能。

1. 跳表的樣兒

2. 跳表具有如下性質:

1.由很多層結構組成
2.每一層都是一個有序的鏈表
3.最底層(第一層)的鏈表包含所有元素
4.如果一個元素出現在 第 i 層 的鏈表中,則它在第 i 層 之下的鏈表也都會出現。
5.每個節點包含兩個指針,一個指向同一鏈表中的下一個元素,一個指向下面一層的元素。

3. 來一個栗子,你將豁然開朗

栗子:查找元素 6
1.頭指針最開始在第一層最小值INT_MIN處
2.于是和旁邊的1比較,當然了1大嘛,于是指針移向1
3.再和當前層4比較, 比 4 大,跳到4
4.與7比較,比7小,于是向下跳到第二層4
5..與5比較,比5大,跳到5
6.與7比較,比7小,跳到最低層5
7.只能依次向后比較了,于是找到了6

4. 筆者的Java實現,慢慢看,很清晰

1.節點定義,共三個成員變量:value,right,down

package crabapple;

/*
 * Copyright (c) This is zhaoxubin"s Java program.
 * Copyright belongs to the crabapple organization.
 * The crabapple organization has all rights to this program.
 * No individual or organization can refer to or reproduce this program without permission.
 * If you need to reprint or quote, please post it to zhaoxubin2016@live.com.
 * You will get a reply within a week,
 *
 */

import java.util.Random;

/**
 * 節點類定義
 */
class Node {

    //值
    public int value = 0;

    //當前層下一個節點
    public Node right;

    //下一層,直連的節點
    public Node down;

    //構造函數
    public Node() {

    }

    public Node(int value) {
        this.value = value;
    }
}

2.跳表類 定義,大家可以清晰的看請代碼邏輯結構,該類只暴露insert()和search()兩個方法,其它變量及方法均設為私有.

/**
 * 跳表定義
 */
public class SkipTable {

    //表層數
    private int levelCount;
    
    //表的頭指針
    private Node firstNode;

    //初始化:層數為1,共前后兩個節點,一個最小值,一個最大值
    private void init() {
        levelCount = 1;
        firstNode=new Node();
        firstNode.value = Integer.MIN_VALUE;
        firstNode.right = new Node(Integer.MAX_VALUE);
    }

    public SkipTable() {
        init();
    }

    /**
     * 查找值
     * @param value
     * @return
     */
    public boolean search(int value) {

        Node current = firstNode;
        return toSearch(current, value);
    }

    private boolean toSearch(Node node, int value) {
        if (node.value == value)
            return true;
        else if (node.right!=null&&value >= node.right.value)
            return toSearch(node.right, value);
        else if (node.down != null)
            return toSearch(node.down, value);
        return false;
    }

    
    
    /**
     * 插入值
     * @param value
     * @return
     */
    public boolean insert(int value) {

        //判斷是否有這個元素
        if (search(value))
            return false;

        //隨機獲取一個層數
        int willLevel = updateLevelCount();

        //判斷是否添加新層
        if (willLevel > levelCount) {
            Node newFirstNode = new Node();
            addLevel(firstNode, newFirstNode);
            firstNode=newFirstNode;
            levelCount = willLevel;
        }

        //插入新元素
        Node port = firstNode;
        int skipLevel = levelCount - willLevel;

        //迭代到指定層
        while ((skipLevel--) > 0)
            port = port.down;

        //上下層新節點的橋梁
        Node insertNode = null;

        while (port != null) {

            //獲取當前層第一個節點指針
            Node curPort = port;

            //迭代到右邊的節點值比自己大為止
            while (port.right.value < value)
                port = port.right;

            //準備插入的新節點
            Node curInNode = new Node(value);

            //更新當前節點和前節點指針指向
            curInNode.right = port.right;
            port.right = curInNode;

            //將當前節點引用給上層節點
            if (insertNode != null)
                insertNode.down = curInNode;

            //將新插入的節點指針更新到insertNode,以備在下一層建立指向
            insertNode = curInNode;

            //行頭指針向下迭代
            port = port.down;
        }
        return true;

    }

    /**
     * 添加新層
     *
     * @param oldFirst
     * @param newFirst
     */
    private void addLevel(Node oldFirst, Node newFirst) {

        newFirst.value = oldFirst.value;
        newFirst.down = oldFirst;
        if (oldFirst.right != null) {
            Node newRightNode = new Node();
            newFirst.right = newRightNode;
            addLevel(oldFirst.right, newRightNode);
        }
    }

    /**
     * 以一定概率使得獲取一個和老層數差值不超過1的新層數
     * @return
     */
    private int updateLevelCount() {

        Random random=new Random();
        int v = random.nextInt(10);
        return v ==0 ? random.nextInt(levelCount) + 2 : random.nextInt(levelCount)+1 ;
    }
}

3.測試類

package crabapple;


public class Main {
    
    public static void main(String[] args) {
        //測試
        SkipTable skipTable=new SkipTable();
        skipTable.insert(1);
        skipTable.insert(2);
        skipTable.insert(3);
        skipTable.insert(4);
        skipTable.insert(5);
        skipTable.insert(6);
        skipTable.insert(7);
        skipTable.insert(8);
        skipTable.insert(9);
        skipTable.insert(10);

        //健壯性邊界值測試
        System.out.println(skipTable.search(0));
        System.out.println(skipTable.search(1));
        System.out.println(skipTable.search(2));
        System.out.println(skipTable.search(5));
        System.out.println(skipTable.search(9));
        System.out.println(skipTable.search(10));
        System.out.println(skipTable.search(11));
    }
}

//output:
/**
 * false
 * true
 * true
 * true
 * true
 * true
 * false
 *
 * Process finished with exit code 0
 */
結語

上面的代碼,大家是可以直接運行,筆者能力有限,代碼也許還有不足,望大家多多指教.

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/73978.html

相關文章

  • 轉 | Java8初體驗(二)Stream語法詳解

    摘要:第一個函數生成一個新的實例第二個函數接受兩個參數,第一個是前面生成的對象,二個是中包含的元素,函數體就是把中的元素加入對象中。 感謝同事【天錦】的投稿。投稿請聯系 tengfei@ifeve.com 上篇文章[Java8初體驗(一)lambda表達式語法]()比較詳細的介紹了lambda表達式的方方面面,細心的讀者會發現那篇文章的例子中有很多Stream的例子。這些Stream的例子可...

    taoszu 評論0 收藏0
  • 程序員的算法趣題Q39: 反復排序

    摘要:中的統一的終點是全白狀態。比如說,的第個數恰好是,它可以由根據題設規則重排而得。上一篇填充白色填充白色下一篇優雅的地址本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 2. 解題分析 2.1??Naive Approach--正向全量搜索 ...

    gitmilk 評論0 收藏0
  • Java多線程進階(二五)—— J.U.C之collections框架:ConcurrentSkip

    摘要:同時,也提供了一個基于的實現類,底層基于紅黑樹設計,是一種有序的。可以看成是并發版本的,但是和不同是,并不是基于紅黑樹實現的,其底層是一種類似跳表的結構。上述所有構造器都調用了方法方法將一些字段置初始化,然后將指針指向新創建的結點。 showImg(https://segmentfault.com/img/remote/1460000016201159); 本文首發于一世流云專欄:ht...

    huashiou 評論0 收藏0
  • JavaScript DOM2和DOM3——“遍歷”的注意要點

    摘要:級遍歷和范圍模塊定義了兩個用于輔助完成順序遍歷結構的類型和這兩個類型能夠基于給定的起點對結構執行深度優先的遍歷操作。其中的屬性,表示任何遍歷方法在上一次遍歷中返回的接待你。通過設置這個屬性也可以修改遍歷繼續進行的節點。 DOM2級遍歷和范圍模塊定義了兩個用于輔助完成順序遍歷DOM結構的類型:NodeIterator和TreeWalker;這兩個類型能夠基于給定的起點對DOM結構執行深度...

    antz 評論0 收藏0

發表評論

0條評論

Yangyang

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<