javascript數(shù)據(jù)結(jié)構(gòu)

desdik 發(fā)布于2019-08-23 13:50 / 773人閱讀

摘要：數(shù)據(jù)結(jié)構(gòu)棧一種遵從先進(jìn)后出原則的有序集合隊(duì)列遵從先進(jìn)先出原則的有序項(xiàng)優(yōu)先隊(duì)列修改版的隊(duì)列，設(shè)置優(yōu)先級(jí)循環(huán)隊(duì)列基于隊(duì)列，克服假溢出想象的隊(duì)列。這種數(shù)據(jù)結(jié)構(gòu)非常方便，提供了一個(gè)便利的語法來訪問它的元素。

javascript數(shù)據(jù)結(jié)構(gòu) 棧

一種遵從先進(jìn)后出原則的有序集合

隊(duì)列

遵從先進(jìn)先出原則的有序項(xiàng)

優(yōu)先隊(duì)列

修改版的隊(duì)列，設(shè)置優(yōu)先級(jí)

循環(huán)隊(duì)列

基于隊(duì)列，克服‘假溢出’想象的隊(duì)列。例如隊(duì)列長(zhǎng)度為5，取第6個(gè)數(shù)據(jù)時(shí)，會(huì)取第一個(gè)數(shù)據(jù)

鏈表

要存儲(chǔ)多個(gè)元素，數(shù)組（或列表）可能是最常用的數(shù)據(jù)結(jié)構(gòu)

每種語言都實(shí)現(xiàn)了數(shù)組。這種數(shù)據(jù)結(jié)構(gòu)非常方便，提供了一個(gè)便利的[]語法來訪問它的元素。

然后，這種數(shù)據(jù)結(jié)構(gòu)有一個(gè)缺點(diǎn)：在大多數(shù)語言中，數(shù)組的大小是固定的，從數(shù)組的起點(diǎn)或中間插入或移除項(xiàng)的成本很高，因需要移動(dòng)元素。

盡管javascript中的Array類方法可以幫我們做這些事，但背后的處理機(jī)制同樣如此。

鏈表儲(chǔ)存有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中不是連續(xù)放置的。每個(gè)元素由一個(gè)儲(chǔ)存元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用（也稱指針或鏈接）組成

相對(duì)于傳統(tǒng)的數(shù)組，鏈表的一個(gè)好處在于，添加或移除元素的時(shí)候不需要移動(dòng)其他元素。然而，鏈表需要使用指針，因此實(shí)現(xiàn)鏈表時(shí)需要額外注意。

數(shù)組的另一個(gè)細(xì)節(jié)是可以直接訪問任意位置的任何元素，而要想訪問鏈表中間的一個(gè)元素，需要從起點(diǎn)（表頭）開始迭代列表直到找到所需的元素

// 鏈表節(jié)點(diǎn)
class Node {
    constructor(element) {
        this.element = element
        this.next = null
    }
}

// 鏈表
class LinkedList {

    constructor() {
        this.head = null
        this.length = 0
    }

    // 追加元素
    append(element) {
        const node = new Node(element)
        let current = null
        if (this.head === null) {
            this.head = node
        } else {
            current = this.head
            while(current.next) {
                current = current.next
            }
            current.next = node
        }
        this.length++
    }

    // 任意位置插入元素
    insert(position, element) {
        if (position >= 0 && position <= this.length) {
            const node = new Node(element)
            let current = this.head
            let previous = null
            let index = 0
            if (position === 0) {
                this.head = node
            } else {
                while (index++ < position) {
                    previous = current
                    current = current.next
                }
                node.next = current
                previous.next = node
            }
            this.length++
            return true
        }
        return false
    }

    // 移除指定位置元素
    removeAt(position) {

        // 檢查越界值
        if (position > -1 && position < length) {
            let current = this.head
            let previous = null
            let index = 0
            if (position === 0) {
                this.head = current.next
            } else {
                while (index++ < position) {
                    previous = current
                    current = current.next
                }
                previous.next = current.next
            }
            this.length--
            return current.element
        }
        return null
    }

    // 尋找元素下標(biāo)
    findIndex(element) {
        let current = this.head
        let index = -1
        while (current) {
            if (element === current.element) {
                return index + 1
            }
            index++
            current = current.next
        }
        return -1
    }

    // 刪除指定文檔
    remove(element) {
        const index = this.indexOf(element)
        return this.removeAt(index)
    }

    isEmpty() {
        return !this.length
    }

    size() {
        return this.length
    }

    // 轉(zhuǎn)為字符串
    toString() {
        let current = this.head
        let string = ""
        while (current) {
            string += ` ${current.element}`
            current = current.next
        }
        return string
    }
}

雙向鏈表

與普通鏈表的區(qū)別在于，雙向鏈表的鏈接是雙向的，一個(gè)鏈向下一個(gè)元素，一個(gè)鏈向上一個(gè)元素。

雙向鏈表提供了兩種迭代列表的方法，從頭到尾或反過來。在單向鏈表中，如果迭代列表時(shí)錯(cuò)過了要找的元素，就需要回到列表起點(diǎn)，重新開始迭代。

循環(huán)鏈表

循環(huán)鏈表可以是單向鏈表一樣只有單向引用，也可以向雙向鏈表有雙向引用。循環(huán)鏈表和鏈表之間唯一的區(qū)別在于，最后元素指向下一個(gè)元素的指針(tail.next)不是引用null，而是指向第一個(gè)元素(head)

鏈表相比數(shù)組最重要的優(yōu)點(diǎn)，就是無需移動(dòng)鏈表中的元素，就能輕松地添加移除元素。因此，當(dāng)你需要添加移除很多元素時(shí)，最好的選擇就是鏈表，而不是數(shù)組

集合

集合是由一組無序且唯一（不能重復(fù)）的項(xiàng)組成的。這個(gè)數(shù)據(jù)結(jié)構(gòu)使用了與優(yōu)先集合相同的數(shù)學(xué)概念，但應(yīng)用在計(jì)算機(jī)科學(xué)的數(shù)據(jù)結(jié)構(gòu)中

class Set {

    constructor() {
        this.items = {}
    }

    has(value) {
        return this.items.hasOwnProperty(value)
    }

    add(value) {
        if (!this.has(value)) {
            this.items[value] = value
            return true
        }     
        return false
    }

    remove(value) {
        if (this.has(value)) {
            delete this.items[value]
            return true
        }
        return false
    }

    get size() {
        return Object.keys(this.items).length
    }

    get values() {
        return Object.keys(this.items)
    }
}

字典

集合，字典，散列表都可以存儲(chǔ)不重復(fù)的數(shù)據(jù)。字典和集合很像，集合是以{ value: value }的形式存儲(chǔ)數(shù)據(jù)，而字典是以{ key: value}的形式存儲(chǔ)數(shù)據(jù)，字典也稱為映射。

object對(duì)象便是字典在javascript中的實(shí)現(xiàn)

樹

一個(gè)樹結(jié)構(gòu)包含一系列存在父子關(guān)系的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)（除頂部的第一個(gè)節(jié)點(diǎn)）以及零個(gè)或者多個(gè)子節(jié)點(diǎn)

二叉樹和二叉搜索樹

二叉樹中的節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)：一個(gè)是左側(cè)子節(jié)點(diǎn)，另一個(gè)是右側(cè)子節(jié)點(diǎn)。二叉樹在計(jì)算機(jī)科學(xué)中應(yīng)用非常廣泛

二叉搜索樹（BST）是二叉樹的一種，但是它只允許你在左側(cè)節(jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)小的值，右側(cè)節(jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)大的值

下圖展示二叉搜索樹的組織結(jié)構(gòu)方式

代碼實(shí)現(xiàn)二叉搜索樹

class Node {
    constructor(key) {
        this.key = key
        this.left = null
        this.right = null
    }
}

class BinarySearchTree {

    constructor() {
        this.root = null
    }

    insert(key) {
        const newNode = new Node(key)
        const insertNode = (node, newNode) => {
            if (newNode.key < node.key) {
                if (node.left === null) {
                    node.left = newNode
                } else {
                    insertNode(node.left, newNode)
                }
            } else {
                if (node.right === null) {
                    node.right = newNode
                } else {
                    insertNode(node.right, newNode)
                }
            }
        }
        if (!this.root) {
            this.root = newNode
        } else {
            insertNode(this.root, newNode)
        }
    }
}

使用二叉搜索樹

const tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(5)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(12)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)

構(gòu)建的樹如下圖：

樹的遍歷

遍歷一顆樹是指訪問樹的每一個(gè)節(jié)點(diǎn)并對(duì)它們進(jìn)行某種操作的過程。

訪問樹的所有節(jié)點(diǎn)有三種方式：中序、先序、后序

中序遍歷

中序遍歷是一種以上行順序訪問BST所有節(jié)點(diǎn)的遍歷方式，也就是以從小到最大的順序訪問所有的節(jié)點(diǎn)。中序遍歷的一種應(yīng)用就是對(duì)樹進(jìn)行排序操作。實(shí)現(xiàn)如下：

inOrderTraverse(callback) {
    const inOrderTraverseNode = (node, callback) => {
        if (node !== null) {
            inOrderTraverseNode(node.left, callback)
            callback(node.key)
            inOrderTraverseNode(node.right, callback)
        }
    }
    inOrderTraverseNode(this.root, callback)
}

inOrderTraverse方法接受一個(gè)回調(diào)函數(shù)作為參數(shù)，回掉函數(shù)用來定義我們對(duì)便利到的每個(gè)節(jié)點(diǎn)進(jìn)行的操作，這也叫做訪問者模式

在之前展示的樹上執(zhí)行下面的方法：

tree.inOrderTraverse(value => { console.log(value) })

控制臺(tái)將會(huì)按照順序輸出：3 5 6 7 8 9 10 11 12 13 14 15 18 20 25

下圖描述了inOrderTraverse方法的訪問路徑

先序遍歷

先序遍歷是以優(yōu)先于后代節(jié)點(diǎn)的順序訪問每個(gè)節(jié)點(diǎn)的，先序遍歷的一種應(yīng)用是打印一個(gè)結(jié)構(gòu)化的文檔。

preOrderTraverse(callback) {
    const preOrderTraverseNode = (node, callback) => {
        if (node !== null) {
            callback(node.key)
            preOrderTraverseNode(node.left, callback)
            preOrderTraverseNode(node.right, callback)
        }
    }
    preOrderTraverseNode(this.root, callback)
}

下面的圖描繪了 preOrderTraverse 方法的訪問路徑:

后序遍歷

后序遍歷是先訪問節(jié)點(diǎn)的后代節(jié)點(diǎn)，再訪問節(jié)點(diǎn)本身。后續(xù)遍歷的一種應(yīng)用是計(jì)算一個(gè)目錄和它的子目錄所有文件所占空間的大小

postOrderTraverse(callback) {
    const postOrderTraverseNode = (node, callback) => {
        if (node !== null) {
            postOrderTraverseNode(node.left, callback)
            postOrderTraverseNode(node.right, callback)
            callback(node.key)
        }
    }
    postOrderTraverseNode(this.root, callback)
}

這個(gè)例子中，后續(xù)遍歷會(huì)先訪問左側(cè)節(jié)點(diǎn)，然后是右側(cè)節(jié)點(diǎn)，最后是父節(jié)點(diǎn)本身。

中序遍歷、先序遍歷、后續(xù)遍歷的實(shí)現(xiàn)方式相似的，唯一不同是三行代碼的執(zhí)行順序。

下圖描繪postOrderTraverse方法的訪問路徑

三種遍歷訪問順序的不同

先序遍歷：節(jié)點(diǎn)本身 => 左側(cè)子節(jié)點(diǎn) => 右側(cè)子節(jié)點(diǎn)

中序遍歷：左側(cè)子節(jié)點(diǎn) => 節(jié)點(diǎn)本身 => 右側(cè)子節(jié)點(diǎn)

后序遍歷：左側(cè)子節(jié)點(diǎn) => 節(jié)點(diǎn)本身 => 右側(cè)子節(jié)點(diǎn)

搜索樹中的值

在樹中，有三種經(jīng)常執(zhí)行的搜索順序：

最大值

最小值

搜索特定值

搜索最大值和最小值

用下圖的樹作為示例

實(shí)現(xiàn)方法：

min(node) {
    const minNode = node => {
        return node ? (node.left ? minNode(node.left) : node) : null
    }
    return minNode(node || this.root)
}

max(node) {
    const maxNode = node => {
        return node ? (node.right ? maxNode(node.right) : node) : null
    }
    return maxNode(node || this.root)
}

搜索一個(gè)特定的值

search(key) {
    const searchNode = (node, key) => {
        if (node === null) return false
        if (node.key === key) return node
        return searchNode((key < node.key) ? node.left : node.right, key)
    }
    return searchNode(root, key)
}

移除一個(gè)節(jié)點(diǎn)

remove(key) {
    const removeNode = (node, key) => {
        if (node === null) return false
        if (node.key === key) {
            console.log(node)
            if (node.left === null && node.right === null) {
                let _node = node
                node = null
                return _node
            } else {
                console.log("key", key)
            }
        } else if (node.left !== null && node.key > key) {
            if (node.left.key === key) {
                node.left.key = this.min(node.left.right).key
                removeNode(node.left.right, node.left.key)
                return node.left
            } else {
                return removeNode(node.left, key)
            }
        } else if (node.right !== null && node.key < key) {
            if (node.right.key === key) {
                node.right.key = this.min(node.right.right).key
                removeNode(node.right.right, node.right.key)
                return node.right
            } else {
                return removeNode(node.right, key)
            }
        } else {
            return false
        }
        return removeNode((key < node.key) ? node.left : node.right, key)
    }
    return removeNode(this.root, key)
}

完整寫法：

var removeNode = function(node, key){

  if (node === null){ //{2}
    return null;
  }
  if (key < node.key){ //{3}
    node.left = removeNode(node.left, key); //{4}
    return node; //{5}

  } else if (key > node.key){ //{6}
    node.right = removeNode(node.right, key); //{7}
    return node; //{8}

  } else { //鍵等于node.key

    //第一種情況——一個(gè)葉節(jié)點(diǎn)
    if (node.left === null && node.right === null){ //{9}
      node = null; //{10}
      return node; //{11}
    }

    //第二種情況——一個(gè)只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
    if (node.left === null){ //{12}
      node = node.right; //{13}
      return node; //{14}

    } else if (node.right === null){ //{15}
      node = node.left; //{16}
      return node; //{17}
    }

    //第三種情況——一個(gè)有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
    var aux = findMinNode(node.right); //{18}
    node.key = aux.key; //{19}
    node.right = removeNode(node.right, aux.key); //{20}
    return node; //{21}
  }
};

var findMinNode = function(node){
  while (node && node.left !== null) {
    node = node.left;
  }
  return node;
};

自平衡二叉搜索樹和紅黑樹

TODO

javascript中的閉包、訪問器、工廠模式、構(gòu)造函數(shù)模式、原型模式、動(dòng)態(tài)原型模式

云服務(wù)器 GPU云服務(wù)器 javascript數(shù)據(jù)結(jié)構(gòu) javascript圖片數(shù)據(jù) javascript數(shù)據(jù)綁定 javascript數(shù)據(jù)類型

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/99634.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

desdik

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

tensorflow是什么語言

閱讀 2663·2023-04-26 00:07
先轉(zhuǎn)行從零基礎(chǔ)入門學(xué)編程可以嗎？

閱讀 2443·2021-11-15 11:37
野草云：香港特惠云服務(wù)器年付138元起,獨(dú)立服務(wù)器月付399元起

閱讀 656·2021-10-19 11:44
電信給的主機(jī)地址是什么情況-什么叫主機(jī)地址？

閱讀 2183·2021-09-22 15:56
軟件測(cè)試報(bào)告怎么編寫，最新軟件測(cè)試模板推薦【建議收藏】

閱讀 1740·2021-09-10 10:50
Ceraus：818上新美國(guó)CN2+GAI新用戶五五折續(xù)費(fèi)七折

閱讀 1513·2021-08-18 10:21
less學(xué)習(xí)

閱讀 2580·2019-08-30 15:53
常見的CSS預(yù)處理器之Less初體驗(yàn)

閱讀 1643·2019-08-30 11:11

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

javascript數(shù)據(jù)結(jié)構(gòu)

相關(guān)文章

JS程序

**什么是 JAVASCRIPT？**

**前端每周清單半年盤點(diǎn)之 JavaScript 篇**

javascript功能插件大集合，寫前端的親們記得收藏

javascript功能插件大集合前端常用插件 js常用插件

javascript功能插件大集合前端常用插件 js常用插件

發(fā)表評(píng)論

0條評(píng)論

desdik

男|高級(jí)講師

TA的文章

tensorflow是什么語言

先轉(zhuǎn)行從零基礎(chǔ)入門學(xué)編程可以嗎？

野草云：香港特惠云服務(wù)器年付138元起,獨(dú)立服務(wù)器月付399元起

電信給的主機(jī)地址是什么情況-什么叫主機(jī)地址？

軟件測(cè)試報(bào)告怎么編寫，最新軟件測(cè)試模板推薦【建議收藏】

Ceraus：818上新美國(guó)CN2+GAI新用戶五五折續(xù)費(fèi)七折

less學(xué)習(xí)

常見的CSS預(yù)處理器之Less初體驗(yàn)

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

javascript數(shù)據(jù)結(jié)構(gòu)

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！