我在那日界線上奔跑之JS---鏈表

shinezejian 發(fā)布于2019-08-20 12:10 / 2296人閱讀

日界線是指日期的分界線，國(guó)際規(guī)定180度經(jīng)線，但這不是一條直線，是一條曲線
又是一個(gè)別人開(kāi)心ipo痛哭的日子嗚嗚嗚

先講個(gè)故事，公元1世紀(jì)猶太戰(zhàn)爭(zhēng)，猶太人被包圍了，不想被俘虜?shù)摹坝率俊睂幙勺詺ⅲ最I(lǐng)指著最近的一個(gè)說(shuō)

‘從你開(kāi)始往后數(shù)，數(shù)到第三個(gè)，他就自殺，再?gòu)乃乱粋€(gè)開(kāi)始數(shù)，數(shù)到第三個(gè)自殺，后面的一樣，開(kāi)始吧’

其中聰明的兩個(gè)人想辦法插隊(duì)，不想就這樣死了（其中一個(gè)就是約瑟夫）

呵呵這是在告訴我“最困難的一刻，只要去想，總有解決的辦法”

來(lái)吧，看聰明的ipo怎么解決的

通用的，n個(gè)人，第m個(gè)自殺，留下的是第幾個(gè)呢

 /*
    實(shí)例
    使用循環(huán)鏈表解決約瑟夫環(huán)問(wèn)題
     */
    function lastTwo(n, m) {
        var list = new LList();
        list.insert(1, "head");
        for (var i = 2; i <= n; i++) {
            list.insert(i, i - 1);
        }
        var currNode = list.head.next;
        var removeNode = null;
        while (list.length >= m) {
            removeNode = move(currNode, m);
            list.remove(removeNode.value);
            currNode = removeNode.next;
        }
        return list.display();
    }

    function move(currNode, m) {
        for (var i = 1; i < m; i++) {
            if (currNode.value === "head") {
                i -= 1;
            }
            currNode = currNode.next;
        }
        return currNode;
    }
    lastTwo(3, 3);

實(shí)現(xiàn)原理是什么的，慢慢從基礎(chǔ)理解

單向鏈表

主要闡述了鏈表是怎么一回事：節(jié)點(diǎn)+鏈

上代碼：

function Node(elem) {
//兩個(gè)類(lèi)：Node當(dāng)前節(jié)點(diǎn)數(shù)據(jù)以及下一個(gè)節(jié)點(diǎn)的引用,LList頭節(jié)點(diǎn)以及操作鏈表的方法
    this.elem = elem;
    this.next = null;
}

function LList() {
    this.head = new Node("head");
    this.find = find;
    this.findPrevious = findPrevious;
    this.insert = insert;
    this.remove = remove;
    this.display = display;
}

function find(item) {
    var currNode = this.head;
    while (currNode.elem !== item) {
        currNode = currNode.next;
    }
    return currNode;
}

function findPrevious(item) {
    var currNode = this.head;
    while (currNode.next !== null && currNode.next.elem !== item) {
        currNode = currNode.next;
    }
    return currNode;
}

function insert(newElem, item) {
    var newNode = new Node(newElem);
    var currNode = this.find(item);
    newNode.next = currNode.next;
    currNode.next = newNode;
}

function remove(item) {
    var prevNode = this.findPrevious(item);
    if (prevNode.next !== null) {
        prevNode.next = prevNode.next.next;
    }
}

function display() {
    var currNode = this.head;
    while (currNode.next !== null) {
        console.log(currNode.next.elem);
        currNode = currNode.next;
    }
}
/*
創(chuàng)建一個(gè)實(shí)例
 */
var cities = new LList();
cities.insert("Conway", "head");
cities.insert("Russellville", "Conway");
cities.display();

今天進(jìn)行了如下優(yōu)化，封裝，繼承

/*
        鏈表=節(jié)點(diǎn)+鏈
        節(jié)點(diǎn)=節(jié)點(diǎn)值+next(節(jié)點(diǎn)的引用指向后繼)
        鏈=頭結(jié)點(diǎn)聲明初始化+方法+屬性
         */
(function(window) {
    function Node(value) {
        this.value = value;
        this.next = null;
    }

    var uList = function() {
        this.head = new Node("head");
        this.length = 0;
    };
    uList.prototype.find = function(value) {
        if (value === "head") {
            return this.head;
        }
        var currNode = this.head.next;
        while (currNode !== null) {
            if (currNode.value === value) {
                return currNode;
            } else {
                currNode = currNode.next;
            }
        }
        return -1;
    };
    uList.prototype.insert = function(newValue, currValue) {
        var newNode = new Node(newValue);
        var currNode = this.find(currValue);
        if (currNode !== -1) {
            newNode.next = currNode.next;
            currNode.next = newNode;
        } else {
            alert("未找到要插入的位置元素");
        }
    };
    uList.prototype.findPrevious = function(value) {
        if (value === "head") {
            return -1;
        }
        var currNode = this.head;
        while (currNode.next !== null) {
            if (currNode.next.value === value) {
                return currNode;
            } else {
                currNode = currNode.next;
            }
        }
        return -1;
    };
    uList.prototype.remove = function(value) {
        var currNode = this.find(value);
        if (currNode !== -1) {
            var preNode = this.findPrevious(value);
            if (preNode !== -1) {
                preNode.next = currNode.next;
            } else {
                alert("未找到刪除的元素");
            }
        } else {
            alert("未找到刪除的元素");
        }
    };
    uList.prototype.display = function() {
        var currNode = this.head.next;
        while (currNode !== null) {
            console.log(currNode.value);
            currNode = currNode.next;
        }
    };

    var List = function() {
        uList.call(List);
    };
    List.prototype = new uList();
    window.List = List;
})(window);
/*
試一下
 */
var mylist = new List();
mylist.insert(1, "head");
mylist.display();

單向鏈表是最簡(jiǎn)單的鏈表，JS中把數(shù)組搞成對(duì)象，性能勢(shì)必不行了，可以自己造個(gè)鏈表替代數(shù)組。不過(guò)隨機(jī)訪問(wèn)一個(gè)元素還是數(shù)組好些。

雙向鏈表
雙向鏈表比單向鏈表相比node多了前置引用，方法刪除操作修改next的同時(shí)要修改pre

function Node(elem){
    this.elem=elem;
    this.previous=null;
    this.next=null;
}
function LList(){
    this.head=new Node("head");
    this.find=find;
    this.findPrevious=findPrevious;
    this.insert=insert;
    this.remove=remove;
    this.display=display;
    this.displayReverse=displayReverse;
}
function find(elem){
    var currNode=this.head;
    while(currNode.elem!==elem&&currNode.next!==null){
        currNode=currNode.next;
    }
    return currNode;
}
function findPrevious(){
    var currNode=this.head;
    while(currNode.next!==null){
        currNode=currNode.next;
    }
    return currNode;
}
function insert(newElem,item){
    var currNode=this.find(item);
    var newNode=new Node(newElem);
    if(currNode.next!==null){
        currNode.next.previous=newNode;
        newNode.next=currNode.next;
    }
    newNode.previous=currNode;
    currNode.next=newNode;
}
function remove(elem){
    var currNode=this.find(elem);
    if(currNode.next!==null){
        currNode.next.previous=currNode.previous;
    }
    currNode.previous.next=currNode.next;
}
function display(){
    var currNode=this.head;
    while(currNode.next!==null){
        console.log(currNode.next.elem);
        currNode=currNode.next;
    }
}
function displayReverse(){
    var currNode=this.findPrevious();
    while(currNode.previous!==null){
        console.log(currNode.previous.elem);
        currNode=currNode.previous;
    }    
}

循環(huán)鏈表
循環(huán)鏈表與單向鏈表相比，強(qiáng)調(diào)最后一個(gè)節(jié)點(diǎn)的引用后繼是head，所以初始化鏈表時(shí)頭結(jié)點(diǎn)時(shí)后繼是head本身

function Node(elem){
    this.elem=elem;
    this.next=null;
}
function LList(){
    this.head=new Node("head");
    this.head.next=this.head;
    this.find=find;
    this.insert=insert;
    this.findPrevious=findPrevious;
    this.remove=remove;
    this.display=display;
}
function find(elem){
    var currNode=this.head;
    while(currNode.next!==this.head&&currNode.elem!==elem){
        currNode=currNode.next;
    }
    return currNode;
}
function insert(newElem,item){
    var currNode=this.find(item);
    var newNode=new Node(newElem);
    if(currNode.next!==this.head){
        newNode.next=currNode.next;
        currNode.next=newNode;
    }else{
        currNode.next=newNode;
        newNode.next=this.head;
    }
}
function findPrevious(elem){
    var currNode=this.head;
    while(currNode.next.elem!==elem){
        currNode=currNode.next;
    }
    return currNode;
}
function remove(elem){
    var prevNode=this.findPrevious(elem);
    var currNode=this.find(elem);
    prevNode.next=currNode.next;
}
function display(){
    var currNode=this.head;
    while(currNode.next!==this.head){
        console.log(currNode.next.elem);
        currNode=currNode.next;
    }
}

優(yōu)化一下就是文章開(kāi)頭的例子中用到的了

   (function(window) {
        function Node(value) {
            this.value = value;
            this.next = null;
        }

        function list() {
            this.head = new Node("head");
            this.head.next = this.head;
            this.length = 0;
        }
        list.prototype.find = function(elem) {
            if (elem === "head") {
                return this.head;
            }
            var curr = this.head.next;
            while (curr !== this.head) {
                if (curr.value === elem) {
                    return curr;
                } else {
                    curr = curr.next;
                }
            }
            return -1;
        };
        list.prototype.insert = function(newValue, currValue) {
            var newNode = new Node(newValue);
            var currNode = this.find(currValue);
            if (currNode === -1) {
                alert("未找到插入位置的元素");
            } else {
                newNode.next = currNode.next;
                currNode.next = newNode;
                this.length++;
            }
        };
        list.prototype.findPrevious = function(currValue) {
            if (this.head.next.value === currValue) {
                return this.head;
            }
            var curr = this.head.next;
            while (curr !== this.head) {
                if (curr.next.value === currValue) {
                    return curr;
                } else {
                    curr = curr.next;
                }
            }
            return -1;
        };
        list.prototype.remove = function(elem) {
            var curr = this.find(elem);
            if (curr === -1) {
                alert("找不到要?jiǎng)h除的元素");
            } else {
                var pre = this.findPrevious(elem);
                if (pre === -1) {
                    alert("找不到要?jiǎng)h除的元素");
                } else {
                    pre.next = curr.next;
                    this.length--;
                }
            }
        };
        list.prototype.display = function() {
            var curr = this.head;
            while (curr.next !== this.head) {
                console.log(curr.next.value);
                curr = curr.next;
            }
        };

        var LList = function() {
            list.call(LList);
        };
        LList.prototype = new list();
        window.LList = LList;
    })(window);