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

資訊專欄INFORMATION COLUMN

數據結構-鏈表

stormzhang / 3524人閱讀

摘要：猶太士兵決定寧可自殺也不做俘虜，于是商量出了一個自殺方案。他們圍成一個圈，從一個人開始，數到第三個人時將第三個人殺死，然后再數，直到殺光所有人。使用循環鏈表解決該問題。首先我們看到他們圍成一個圈判斷應該使用循環鏈表來處理改問題完整代碼前移

本章將討論另一種列表: 鏈表 . 解釋為什么有時鏈表優于數組, 還會實現一個基于對象的鏈表.
數組的缺點

數組不總是組織數據的最佳數據結構, 原因如下. 在很多編程語言中, 數組的長度是固定的, 所以當數組已被數據填滿時, 再要加入新的元素就會非常困難. 在數組中, 添加和刪除元素也很麻煩, 因為需要將數組中的其他元素向前或向后平移, 以反映數組剛剛進行了添加或刪除操作. 然而, JS的數組不存在上述問題. 因為使用splice()方法不需要再訪問數組中的其它元素了.

定義鏈表

由一組節點組成的集合. 每一個節點都使用一個對象的引用指向它的后繼. 指向另一個節點的引用叫做鏈.
圖片名稱

數組元素靠它們的位置進行引用, 鏈表元素則是靠相互之間的關系進行引用. 在上圖中, 我們說99跟在12后面, 而不說99是鏈表中的第二個元素. 遍歷鏈表, 就是跟著連接, 從鏈表的首元素一直走到尾元素(但這不包含鏈表的頭結點, 頭結點常常永愛作為鏈表的接入點). 值得注意的是, 鏈表的尾元素指向一個null節點.

然鵝要標識出鏈表的起始節點卻有點麻煩, 許多鏈表的實現都是在鏈表最前面有一個特殊節點, 叫做 頭節點.

鏈表中插入一個節點的效率很高. 向鏈表中插入一個節點, 需要修改它前面的節點(前驅), 使其事項新加入的節點, 而新加入的節點則指向原來前驅指向的節點.

從鏈表中刪除一個元素也很簡單. 將待刪除元素的前驅節點指向待刪除元素的后繼節點, 同時將待刪除元素指向null, 元素就刪除成功了.

設計一個基于對象的鏈表

我們設計的鏈表包含兩個類. Node類用于表示節點, LinkedList類提供了插入節點、刪除節點、顯示列表元素的方法, 以及其他一些輔助方法.

Node類

Node類包含兩個屬性: element用來保存節點上的數據, next用來保存指向下一個節點的鏈接.

class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
    }
};
LinkedList類

LList類提供了對鏈表進行操作的方法. 該類的功能包括插入刪除節點、在列表中查找給定的值.

class LList {
    constructor() {
        this._head = new Node("head");
    }
    _find(item) {
        let currNode = this._head;
        while (currNode.element != item) {
            currNode = currNode.next;
        };
        return currNode;
    }
    _findPrevious(item) {
        let currNode = this._head;
        while (currNode.next !== null && currNode.next.element !== item) {
            currNode = currNode.next;
        };
        return currNode;  
    }
    insert(newElement, item) {
        const newNode = new Node(newElement);
        const current = this._find(item);
        newNode.next = current.next;
        current.next = newNode
    }
    remove(item) {
        const prevNode = this._findPrevious(item);
        if (prevNode.next !== null) {
            prevNode.next = prevNode.next.next
        }
    }
    display() {
        let currNode = this._head;
        while (!(currNode.next === null)) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    }
};

插入新節點insert()
該方法向鏈表中插入一個節點. 向鏈表中插入新節點時, 需要明確指出要在哪個節點前面或后面插入元素.

在一個已知節點后面插入元素時, 先要找到 后面 的節點. 為此, 創建一個輔助方法find(), 該方法遍歷鏈表, 查找給定數據. 如果找到數據, 該方法就返回保存該數據的節點.
find()方法演示了如何在鏈表上進行移動. 首先, 創建一個新節點, 并將鏈表的頭節點賦給這個新創建的節點. 然后再鏈表上進行循環, 如果當前節點的element屬性和我們要找的信息不符, 就從當前節點移動到下一個節點. 如果查找成功, 則返回該數據的節點; 否則返回null.

一旦找到 后面 的節點, 就可以將新的節點插入鏈表了. 首先, 將新節點的next屬性設置為 后面 節點的next屬性對應的值. 然后設置 后面 節點的next屬性指向新節點.

在測試之前我們定義一個display()方法, 該方法用來顯示鏈表中的元素.
display()先將列表的頭節點賦給一個變量, 然后循環遍歷鏈表, 當節點的next屬性為null時循環結束. 為了只顯示包含數據的節點(換句話說, 不顯示頭節點), 程序只訪問當前節點的下一個節點中保存的數據: currNode.next.element.

測試程序:

const letters = new LList();
letters.insert("a", "head");
letters.insert("b", "a");
letters.insert("c", "b");
letters.insert("d", "c");
letters.display();

輸出:

a
b
c
d

刪除一個節點remove()
從鏈表中刪除節點時, 需要先找到待刪除節點前面的節點. 找到這個節點后, 修改它的next屬性, 使其不再事項待刪除節點, 而是指向待刪除節點的下一個節點. 我們定義一個方法findPrevious(). 該方法遍歷鏈表中的元素, 檢查每一個節點的下一個節點中是否存儲待刪除數據. 如果找到, 返回該節點(即 前一個 節點), 這樣就可以修改它的next屬性了.

remove()方法中最重要的一行代碼prevNode.next = prevNode.next.next;
這里跳過了待刪除節點, 讓 前一個 節點指向了待刪除節點的后一個節點.

測試程序:

const letters = new LList();
letters.insert("a", "head");
letters.insert("b", "a");
letters.insert("c", "b");
letters.insert("d", "c");
letters.display();

letters.remove("d");
console.log("")
letters.display();

輸出:

a
b
c
d

a
b
c
雙向鏈表

盡管從鏈表的頭節點到尾節點很簡單, 但反過來, 從后向前遍歷則沒那么簡單. 通過給Node對象增加一個屬性, 該屬性存儲指向前驅節點的鏈接, 這樣就容易多了. 此時向鏈表中插入一個節點需要更多的工作, 我們需要指出該節點正確的前驅和后繼. 但是刪除節點時效率提高了, 不需要再查找待刪除節點的前驅節點了.

首先我們要為Node類增加一個previous屬性:

class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
        this.previous = null;
    };
};

insert()方法和單向鏈表的類似, 但是需要設置新節點的previous屬性, 使其指向該節點的前驅.

...
insert(newElement, item) {
    const newNode = new Node(newElement);
    const current = this._find(item);
    newNode.next = current.next;
    newNode.previous = current;
    current.next = newNode;
}
...

remove()方法比單向鏈表的效率更高, 因為不需要查找前驅節點了. 首先需要在鏈表中找出存儲待刪除數據的節點, 然后設置該節點前驅的next屬性, 使其指向待刪除節點的后繼; 設置該節點后繼的previous屬性, 使其指向待刪除節點的前驅.

...
remove(item) {
    const currNode = this._find(item);
    if(currNode.next != null) {
        currNode.previous.next = currNode.next;
        currNode.next.previous = currNode.previous;
        currNode.next = null;
        currNode.previous = null;
    }
}
...

為了反序顯示鏈表中元素, 需要給雙向鏈表增加一個工具方法, 用來查找最后的節點. findLast()方法找出了鏈表中的最后一個節點, 同時免除了從前往后遍歷鏈表之苦:

...
_findLast() {
    let currNode = this._head;
    while (currNode != null) {
        currNode = currNode.next;
    };

    return currNode;
}
...

有了這個工具方法, 就可以寫一個方法, 反序顯示雙向鏈表中的元素. dispReverse()方法:

...
dispReverse() {
    let currNode = this._head;
    currNode = this._findLast();
    while (currNode.previous != null) {
        console.log(currNode.element);
        currNode = currNode.previous;
    }
}
...

全部代碼:

class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
        this.previous = null;
    }
};

class LList {
    constructor() {
        this._head = new Node("head");
    }
    _find(item) {
        let currNode = this._head;
        while (currNode.element != item) {
            currNode = currNode.next;
        };
        return currNode;
    }
    _findPrevious(item) {
        let currNode = this._head;
        while (currNode.next !== null && currNode.next.element !== item) {
            currNode = currNode.next;
        };
        return currNode;  
    }
    _findLast() {
        let currNode = this._head;
        while (currNode.next != null) {
            currNode = currNode.next;
        };

        return currNode;
    }
    insert(newElement, item) {
        const newNode = new Node(newElement);
        const current = this._find(item);
        newNode.next = current.next;
        newNode.previous = current;
        current.next = newNode
    }
    remove(item) {
        const currNode = this._find(item);
        if (currNode.next !== null) {
            currNode.previous.next = currNode.next;
            currNode.next.previous = currNode.previous;
            currNode.next = null;
            currNode.previous = null;
        } else {
            currNode.previous.next = null;
        }
    }
    display() {
        let currNode = this._head;
        while (!(currNode.next === null)) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    }
    dispReverse() {
        let currNode = this._head;
        currNode = this._findLast();
        while (currNode.previous !== null) {
            console.log(currNode.element);
            currNode = currNode.previous;
        }
    }
};

const letters = new LList();
letters.insert("a", "head");
letters.insert("b", "a");
letters.insert("c", "b");
letters.insert("d", "c");
letters.display();
letters.dispReverse();

letters.remove("d");
letters.remove("b");
console.log("")
letters.dispReverse();

程序輸出:

a
b
c
d
d
c
b
a

c
a
循環鏈表

循環鏈表和單向鏈表相似, 節點類型都是一樣的. 唯一的區別是, 在創建循環鏈表時, 讓其頭節點的next屬性指向它本身.
_head.next = _head
這種行為會傳導至鏈表中的每一個節點, 使得每一個節點的next屬性都是指向鏈表的頭節點. 換句話說, 鏈表的尾節點指向頭節點, 形成了一個循環鏈表.

如果你希望可以從后面向前遍歷鏈表, 但是又不想付出額外代價來創建一個雙向鏈表, 那么就需要使用循環鏈表. 從循環鏈表的尾節點向后移動, 就等于從后向前遍歷鏈表.

創建循環鏈表, 只需要修改單向鏈表的LList類的構造函數:

class LList {
    constructor() {
        this._head = new Node("head");
        this._head.next = this._head;
    }
    ...
}

只要修改一處, 就將單向鏈表變成了循環鏈表. 但是其它一些方法需要修改才能工作正常. eg: display()就需要修改, 原來的方式在循環鏈表里會陷入死循環. while循環條件需要修改, 需要檢查頭節點, 當循環到頭節點時退出循環.

...
display() {
    let currNode = this._head;
    while (currNode.next !== null && currNode.next.element !== "head") {
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
}
...
鏈表的其它方法 advance()前移

單向鏈表就可以完成該功能. 但是為了配合后移功能我們采用雙向鏈表.

...
advance(n) {
    while ( n && this._head.next != null) {
        this._head = this._head.next;
        n--;
    };
}
...

使整個鏈表向前移動, 從頭結點開始, 移動幾位就是頭節點賦值為第幾個next節點.

back()后移

與前移不同的后移功能需要在雙向鏈表上實現.

...
back(n) {
    while ( n && this._head.element != "head") {
        this._head = this._head.previous;
        n--;
    };
}
...

是整個鏈表向后移動, 如果第一個節點(當前節點)為頭節點(head)則不移動.

show()只顯示當前節點數據 
...
show() {
    return this._head;
}
...
循環鏈表解決猶太歷史學家弗拉維奧·約瑟夫基和他的同伴生存問題.

傳說在公元1 世紀的猶太戰爭中，猶太歷史學家弗拉維奧·約瑟夫斯和他的40個同胞被羅馬士兵包圍。猶太士兵決定寧可自殺也不做俘虜，于是商量出了一個自殺方案。他們圍成一個圈，從一個人開始，數到第三個人時將第三個人殺死，然后再數，直到殺光所有人。約瑟夫和另外一個人決定不參加這個瘋狂的游戲，他們快速地計算出了兩個位置，站在那里得以幸存。寫一段程序將n 個人圍成一圈，并且第m個人會被殺掉，計算一圈人中哪兩個人最后會存活。使用循環鏈表解決該問題。
首先我們看到他們圍成一個圈判斷應該使用循環鏈表來處理改問題.
完整代碼:

window.log = console.log.bind(console);
class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
    }
};

class LList {
    constructor() {
        this._head = new Node("head");
        this._head.next = this._head;
        this.currentNode = this._head;
    }
    _find(item) {
        let currNode = this._head;
        while (currNode.element != item) {
            currNode = currNode.next;
        };
        return currNode;
    }
    _findPrevious(item) {
        let currNode = this._head;
        while (currNode.next !== null && currNode.next.element !== item) {
            currNode = currNode.next;
        };
        return currNode;  
    }
    insert(newElement, item) {
        const newNode = new Node(newElement);
        const current = this._find(item);
        newNode.next = current.next;
        current.next = newNode;
    }
    remove(item) {
        const prevNode = this._findPrevious(item);
        if (prevNode.next !== null) {
            prevNode.next = prevNode.next.next
        }
    }
    // 前移
    advance(n) {
        while ( n ) {
            if(this.currentNode.next.element == "head") {
                this.currentNode = this.currentNode.next.next;
            } else {
                this.currentNode = this.currentNode.next;
            } 
            n--;
        };
    }
    show() {
        return this.currNode;
    }
    count() {
        let currNode = this._head;
        let i = 0;
        while (currNode.next.element != "head") {
            currNode = currNode.next;
            ++i
        };
        
        return i;
    }
    display() {
        let currNode = this._head;
        
        while (currNode.next !== null && currNode.next.element !== "head") {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    }
};

const p = new LList();

const peopleNum = 40;
for(let i = 1; i <= peopleNum; i++) {
    if(i === 1) {
        p.insert(`people${i}`, "head");
    } else {
        p.insert(`people${i}`, `people${i - 1}`);
    }
};

p.display();
while (p.count() > 2) {
    p.advance(3);
    p.remove(p.currentNode.element);
    log("http://///////////////")
    p.display();
};

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

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

相關文章

  • 學習JavaScript數據結構與算法（二）：鏈表

    摘要：實現移除給定的元素要移除的元素返回值表示移除成功方法說明移除單向鏈表中某個位置的元素。的前端樂園原文鏈接寒假前端學習學習數據結構與算法二鏈表 本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列第二篇文章：學習JavaScript數據結構與算法（二）：鏈表第三篇文章：學習JavaScript數據結構與算法（三）：集合第四篇文章：學習JavaScript數據結構與...

    lolomaco 評論0 收藏0

  • JavaScript數據結構04 - 鏈表

    摘要：類表示要加入鏈表的項。循環鏈表和普通鏈表之間唯一的區別在于，最后一個元素指向下一個元素的指針不是引用，而是指向第一個元素。這里就不進行代碼實現了，大家可以結合上面的單向鏈表和雙向鏈表自己實現一個循環鏈表。 一、定義 1.1 概念 前面我們學習了數組這種數據結構。數組（或者也可以稱為列表）是一種非常簡單的存儲數據序列的數據結構。在這一節，我們要學習如何實現和使用鏈表這種動態的數據結構，這...

    cheukyin 評論0 收藏0

  • JavaScript的數據結構與算法（三） —— 單向鏈表

    摘要：鏈表鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素在內存中并不是連續放置的。相對于傳統的數組，鏈表的一個好處在于，添加或者刪除元素的時候不需要移動其他元素。 鏈表 鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素在內存中并不是連續放置的。每個元素由一個存儲元素本事的節點和一個指向下一個元素的引用組成。相對于傳統的數組，鏈表的一個好處在于，添加或者刪除元素的時候不需要移動其他元素。...

    李濤 評論0 收藏0

  • JavaScript的數據結構與算法（四） —— 雙向鏈表

    摘要：鏈表鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素在內存中并不是連續放置的。鏈表又包括單向鏈表和雙向鏈表雙向鏈表雙向鏈表與單向鏈表很是相像。但在雙向鏈表中，還有指向上一個節點的鏈接，是雙向的。 鏈表 鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素在內存中并不是連續放置的。每個元素由一個存儲元素本事的節點和一個指向下一個元素的引用組成。相對于傳統的數組，鏈表的一個好處在于，添加或...

    Youngdze 評論0 收藏0

發表評論

0條評論

stormzhang

男|高級講師

TA的文章

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