你可能知道的 javaScript 数据结构与算法

ifwinds 2019-07-01

本文已同步到github 你可能知道的 javaScript 数据结构与算法,欢迎Star。

如果想阅读笔者更多文章,欢迎猛戳这里

关于数据结构与算法,终于抽时间把之前看过的这两本书《学习JavaScript数据结构与算法》《数据结构与算法JavaScript描述》,整理出来了一部分内容,由于最近较忙,先把已整理出来的内容发一下。对于未整理出来的内容会在后续整理出来,并更新到此文,也会随着对数据结构与算法不断的学习,不断优化更新此文,感兴趣的小伙伴可以先收藏哦。这两本书对前端来讲是很好的入门数据结构与算法的书,个人感觉《学习JavaScript数据结构与算法》这本书从排版以及思路上更清晰一些。

另外,为了截图和验证方便,本文的例子大多是书中的例子。

本文较长,如果阅读起来不方便,可链接到我的github中,单独查看。

github
数据结构
队列
链表
集合
排序算法 冒泡排序
选择排序
插入排序

闲言少叙,直接开始了

JavaScript 数据结构

栈是一种遵从后进先出LIFO(Last In First Out,后进先出)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端就叫栈底。

定义一个栈的类,并为该栈声明一些方法,存储数据的底层数据结构使用数组

class Stack {
    constructor() {
        this.dataStore = []
    }

    // 向栈中添加一个或多个元素到栈顶
    push() {
        for (let i = 0; i < arguments.length; i++) {
            this.dataStore.push(arguments[i])
        }
    }

    // 移出栈顶元素,并返回被移出的元素
    pop() {
        return this.dataStore.pop()
    }

    // 返回栈顶元素,不对栈做修改
    peek() {
        return this.dataStore[this.dataStore.length - 1]
    }

    // 判断栈是否为空,如果为空返回true,否则返回false
    isEmpty() {
        return this.dataStore.length === 0
    }

    // 清空栈
    clear() {
        this.dataStore = []
    }

    // 返回栈中元素的个数

    size() {
        return this.dataStore.length
    }
}

// 栈的操作

let stack = new Stack()

stack.push(1, 2, 3)
console.log(stack.dataStore) // [1, 2, 3]
console.log(stack.pop())     // 3
console.log(stack.dataStore) // [1, 2]
console.log(stack.peek())    // 2
console.log(stack.dataStore) // [1, 2]
console.log(stack.size())    // 2
console.log(stack.isEmpty()) // false
stack.clear()
console.log(stack.dataStore)  // []
console.log(stack.isEmpty())  // true
console.log(stack.size())     // 0

栈的应用

本文举书中一个进制转换的例子并稍作修改,栈的类还是使用上面定义的Stack

function transformBase(target, base) {
    let quotient;                    // 商
    let remainder;                   // 余数
    let binaryStr = '';              // 转换后的值
    let digits = '0123456789ABCDEF'  // 对转换为16进制数做处理
    let stack = new Stack()
    while(target > 0) {
        remainder = target % base
        stack.dataStore.push(remainder)
        target = Math.floor(target / base)
    }

    while(!stack.isEmpty()) {
        binaryStr += digits[stack.dataStore.pop()].toString()
    }

    return binaryStr
}

console.log(transformBase(10, 2))   // 1010
console.log(transformBase(10, 8))   // 12
console.log(transformBase(10, 16))  // A

队列

队列是遵循FIFO(First In First Out,先进先出,也称为先来先服务)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾。

其实队列和栈类似,只是原则不同,队列是先进先出,用代码来实现一个队列及操作队列的一些方法,以下用代码实现一个队列的类, 测试和栈类似,就不做具体测试了。

class Queue {
    constructor() {
        this.dataStore = []
    }

    // 入队
    enqueue() {
        for (let i = 0; i < arguments.length; i++) {
            this.dataStore.push(arguments[i])
        }
    }

    // 出队
    dequeue() {
        return this.dataStore.shift()
    }

    // 返回队列第一个元素,不改变队列
    front() {
        return this.dataStore[0]
    }

    // 队列是否为空
    isEmpty() {
        return this.dataStore.length === 0
    }

    // 返回队列的的元素个数
    size() {
        return this.dataStore.length
    }
}

优先队列

队列中在生活中有着大量应用,如登机时,商务舱要优于经济舱,这时候可以给队列中的元素设置优先级,下面用代码来实现一个优先队列的类

class PriorityQueue {

    constructor() {
        this.dataStore = []
    }

    isEmpty() {
        return this.dataStore.length === 0
    }

    enqueue(element, priority) {

        function QueueElement(element, priority) {
            this.element = element
            this.priority = priority
        }
        // 定义每次往队列里添加的元素
        let queueElement = new QueueElement(element, priority)

        if (this.isEmpty()) {
            // 如果每次队列为空直接添加到队列中
            this.dataStore.push(queueElement)
        } else {
            // 定一个是否被添加到队列的标志
            let isAdded = false
            for (let i = 0; i < this.dataStore.length; i++) {
                if (queueElement.priority < this.dataStore[i].priority) {
                    // 优先级数值越小,代表优先级越高
                    this.dataStore.splice(i, 0, queueElement)
                    isAdded = true
                    break;
                }
            }

            if (!isAdded) {
                // 如果被添加的新元素优先级最低,添加到队尾
                this.dataStore.push(queueElement)
            }
        }
    }
    //
}

let priorityQueue = new PriorityQueue()

priorityQueue.enqueue('a', 5)
priorityQueue.enqueue('b', 2)
priorityQueue.enqueue('c', 3)

console.log(priorityQueue.dataStore)

最后的队列如下图:

你可能知道的  javaScript 数据结构与算法

链表

你可能知道的  javaScript 数据结构与算法

直接上代码:

class LinkedList {
    constructor() {
        this.head = null // 链表的第一个元素
        this.length = 0
    }
    // 向链表尾部添加一个新元素
    append(element) {
        let Node = function(element) {
            this.element = element
            this.next = null
        }
        let node = new Node(element)
        let currentNode;
        if (this.head == null) {
            // 如果链表head为null,表示链表无元素,直接把node赋值给head即可
            this.head = node
        } else {
            currentNode = this.head
            while (currentNode.next) {
                // 每次循环会进行到链表的倒数第一个元素,把currentNode设置为倒数第一个元素
                currentNode = currentNode.next
            }
            // 把新增的node赋值给currentNode的next属性,最后一个元素的next永远为null
            currentNode.next = node
        }
        // 链表的元素个数每次append后 +1
        this.length++
    }
    // 从链表中按位置删除元素
    removeAt(position) {
        // position表示要移除元素的位置
        let index = 0
        let previous = null
        let currentNode = this.head
        if (position >= 0 && position < this.length) {
            while (index < position) {
                // 主要是找出position位置的元素,设置为currentNode
                previous = currentNode
                currentNode = currentNode.next
                index++
            }
            // 把currentNode的上一个元素的next指向currentNode的下一个元素,就对应删除了currentNode
            previous.next = currentNode.next
        } else {
            // 表示链表中不存在这个元素,直接return null
            return null
        }
        // 删除后链表的元素个数每次删除减1
        this.length--;
        // 返回删除的元素
        return currentNode
    }
    // 按元素值删除元素
    remove(element) {
        let index = this.indexOf(element)
        return this.removeAt(index)
    }
    // 向链表中插入新元素
    insert(element, position) {
        // element表示被插入元素的具体值
        // position表示被插入元素的位置
        if (position >= 0 && position < this.length) {
            let index = 0
            let previous = null
            let currentNode = this.head
            let Node = function(element) {
                this.element = element
                this.next = null
            }
            let node = new Node(element)
            while (index < position) {
                previous = currentNode
                currentNode = currentNode.next
                index++
            }
            // 把当前元素的上一个元素的next设置为被插入的元素
            previous.next = node
            // 把被插入元素的next设置为当前元素
            node.next = currentNode
            // 链表元素个数加1
            this.length++;
            // 如果插入元素成功,返回true
            return true
        } else {
            // 如果找不到插入元素位置,返回false
            return false
        }
    }
    // 查找元素在链表中的位置
    indexOf(element) {
        let currentNode = this.head
        let index = 0
        // 如果currentNode也就是head为空,则链表为空不会进入while循环,直接返回 -1
        while (currentNode) {
            if (element === currentNode.element) {
                // 如果被找到,返回当前index
                return index
            }
            // 每一轮循环如果被查找元素还没有被找到,index后移一位,currentNode指向后一位元素,继续循环
            index++
            currentNode = currentNode.next
        }
        // 如果一直while循环结束都没找到返回 -1
        return -1
    }
    // 链表是否为空
    isEmpty() {
        return this.length === 0
    }
    // 链表元素个数
    size() {
        return this.length
    }
}

let linkedList = new LinkedList()

linkedList.append('a')
linkedList.append('b')
linkedList.append('c')
linkedList.append('d')
linkedList.removeAt(2)
linkedList.insert('e', 2)
console.log('bIndex', linkedList.indexOf('b'))
console.log('fIndex', linkedList.indexOf('f'))
linkedList.remove('d')
console.log(linkedList)

上述代码测试结果如下图所示:

你可能知道的  javaScript 数据结构与算法

集合

你可能知道的  javaScript 数据结构与算法
class Set {
    constructor() {
        this.items = {}
    }

    has(val) {
        return val in this.items
    }

    // 向集合中添加一个新的项
    add(val) {
        this.items[val] = val
    }

    // 从集合中移除指定项
    remove(val) {
        if (val in this.items) {
            delete this.items[val]
            return true
        }
        return false
    }

    // 清空集合
    clear() {
        this.items = {}
    }

    // 返回集合中有多少项
    size() {
        return Object.keys(this.items).length
    }

    // 提取items对象的所有属性,以数组的形式返回
    values() {
        return Object.keys(this.items)
    }

    // 取当前集合与其他元素的并集
    union(otherSet) {
        let unionSet = new Set()
        let values = this.values()
        for (let i = 0; i < values.length; i++) {
            unionSet.add(values[i])
        }

        let valuesOther = otherSet.values()
        for (let i = 0; i < valuesOther.length; i++) {
            unionSet.add(valuesOther[i])
        }
        return unionSet
    }

    // 取当前集合与其他元素的交集
    intersection(otherSet) {
        let intersectionSet = new Set()
        let values = this.values()
        for (let i = 0; i < values.length; i++) {
            if (otherSet.has(values[i])) {
                intersectionSet.add(values[i])
            }
        }
        return intersectionSet
    }

    // 取当前集合与其他元素的差集
    diff(otherSet) {
        let intersectionSet = new Set()
        let values = this.values()
        for (let i = 0; i < values.length; i++) {
            if (!otherSet.has(values[i])) {
                intersectionSet.add(values[i])
            }
        }
        return intersectionSet
    }

    // 判断当前集合是否是其他集合的子集
    isSubSet(otherSet) {
        // 如果当前集合项的个数大于被比较的otherSet的项的个数,则可判断当前集合不是被比较的otherSet的子集
        if (this.size() > otherSet.size()) {
            return false
        } else {
            let values = this.values()
            for (let i = 0; i < values.length; i++) {
                // 只要当前集合有一项不在otherSet中,则返回false
                if (!otherSet.has(values[i])) {
                    return false
                }
            }
            // 循环判断之后,当前集合每一项都在otherSet中,则返回true
            return true
        }
    }
}
// 测试
let setA = new Set()
setA.add('a')
setA.add('b')
setA.add('c')
setA.remove('b')
console.log(setA.values()) // ['a', 'c']
console.log(setA.size()) // 2

let setB = new Set()
setB.add('c')
setB.add('d')
setB.add('e')

let unionAB = setA.union(setB)
console.log(unionAB.values()) // ['a', 'c', 'd', 'e']
let intersectionAB = setA.intersection(setB)
console.log(intersectionAB.values()) // ['c']

let diffAB = setA.diff(setB)
console.log(diffAB.values()) // ['a']

let setC = new Set()
setC.add('d')
setC.add('e')

let isSubSetCB = setC.isSubSet(setB)
console.log(isSubSetCB) // true

let isSubSetAB = setA.isSubSet(setB)
console.log(isSubSetAB) // false

一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点)以及零个或多个子节点
你可能知道的  javaScript 数据结构与算法

二叉树

你可能知道的  javaScript 数据结构与算法
// 创建一个键
function createNode(key) {
    this.key = key
    this.left = null
    this.right = null
}

// 向树中插入键
function 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)
        }
    }
}

// 遍历回调
function printNode(value) {
    console.log(value)
}

// 中序遍历
function inOrderTraverseNode(node, callback) {
    if (node !== null) {
        inOrderTraverseNode(node.left, callback)
        callback(node.key)
        // debugger 可以加入debugger,用浏览器控制观察Call Stack(执行环境栈)来分析程序执行过程
        inOrderTraverseNode(node.right, callback)
    }
}

// 先序遍历
function prevOrderTraverseNode(node, callback) {
    if (node !== null) {
        // 先访问节点本身
        callback(node.key)
        // 再访问左侧节点
        prevOrderTraverseNode(node.left, callback)
        // 然后再访问右侧节点
        prevOrderTraverseNode(node.right, callback)
    }
}

// 后序遍历
function postOrderTraverseNode(node, callback) {
    if (node !== null) {
        // 先访问左侧节点
        postOrderTraverseNode(node.left, callback)
        // 再访问右侧节点
        postOrderTraverseNode(node.right, callback)
        // 然后再访问节点本身
        callback(node.key)
    }
}

class BinarySearchTree {
    constructor() {
        this.key = null
    }
    insert(key) {
        let newNode = new createNode(key)
        if (this.key === null) {
            this.key = newNode
        } else {
            insertNode(this.key, newNode)
        }
    }
    // 中序遍历访问节点(结果为按值由小到大访问)
    inOrderTraverse(callback) {
        inOrderTraverseNode(this.key, callback)
    }
    // 先序遍历访问节点(结果为先访问节点本身,再左侧节点,然后再访问右侧节点)
    prevOrderTraverse(callback) {
        prevOrderTraverseNode(this.key, callback)
    }
    // 后序遍历访问节点(结果为先访问左侧节点,再访问右侧节点,然后再访问节点本身)
    postOrderTraverse(callback) {
        postOrderTraverseNode(this.key, callback)
    }
    // 查找树中的最小值
    findMin(node) {
        if (node) {
            while(node && node.left !== null) {
                node = node.left
            }
            return node.key
        }
        return null
    }
    // 查找树中的最小值对应的节点
    findMinNode(node) {
        if (node) {
            while(node && node.left !== null) {
                node = node.left
            }
            return node
        }
        return null
    }

    // 查找树中的最大值
    findMax(node) {
        if (node) {
            while(node && node.right !== null) {
                node = node.right
            }
            return node.key
        }
        return null
    }

    // 查找树中的特定值,如果存在返回true,否则返回false
    search(node, key) {
        if (node === null) {
            return false
        }

        if (key < node.key) {
            // 如果被查找的key小于节点值,从节点的左侧节点继续递归查找
            return this.search(node.left, key)
        } else if (key > node.key) {
            // 如果被查找的key大于节点值,从节点的左侧节点继续递归查找
            return this.search(node.right, key)
        } else {
            // 被查找的key等于node.key
            return true
        }
    }

    // 移除树中的特定节点
    removeNode(node, key) {
        if (node === null) {
            return null
        }

        if (key < node.key) {
            node.left = this.removeNode(node.left, key)
        } else if (key > node.key) {
            node.right = this.removeNode(node.right, key)
        } else {
            // console.log(node)
            // 移除叶子节点(无左右节点的节点)
            if (node.left === null && node.right === null) {
                node = null
                return node
            }

            // 移除只有一个节点的节点(只有左节点或只有右节点)
            if (node.left === null) {
                node = node.right
                return node
            } else if (node.right === null) {
                node = node.left
                return node
            }

            // 移除有两个节点(既有左节点又有右节点)
            if (node.left && node.right) {
                // 1. 找到被移除节点的右节点下的最小节点,替换被移除的节点
                let minRightNode = this.findMinNode(node.right)
                // 2. 把被移除节点的key设置为 被移除节点的右节点下的最小节点的key
                node.key = minRightNode.key
                // 3. 移除找到的那个最小节点
                this.removeNode(node.right, node.key)
                // 4. 向被移除节点的父节点返回更新后节点的引用
                return node
            }
        }
    }
}

测试如下:

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

tree.inOrderTraverse(printNode)   // 3  5 6 7 8  9 10 11 12 13 14 15 18 20 25
tree.prevOrderTraverse(printNode) // 11 7 5 3 6  9 8  10 15 13 12 14 20 18 25
tree.postOrderTraverse(printNode) // 3  6 5 8 10 9 7  12 14 13 18 25 20 15 11

// tree.key为根节点,为了保持树不同层的结构一致,没有使用root为属性,使用了key
let minNodeVal = tree.findMin(tree.key)
console.log('minNodeVal', minNodeVal)

let maxNodeVal = tree.findMax(tree.key)
console.log('maxNodeVal', maxNodeVal)

let isHasNodeVal = tree.search(tree.key, 7)
console.log(isHasNodeVal)   // true

tree.removeNode(tree.key, 15)
console.log(tree) // 可以查看树的结构,15的这个节点的key已经被替换为18,并且key为18的节点已经被删除

树的遍历

1. 中序遍历

你可能知道的  javaScript 数据结构与算法

2. 先序遍历

你可能知道的  javaScript 数据结构与算法

3. 后序遍历

你可能知道的  javaScript 数据结构与算法

移除节点的过程

1. 移除以一个叶节点
你可能知道的  javaScript 数据结构与算法

2. 移除只有一个左侧子节点或右侧子节点的节点
你可能知道的  javaScript 数据结构与算法

3. 移除有两个子节点的节点
你可能知道的  javaScript 数据结构与算法

JavaScript 算法

排序算法

1.冒泡排序

你可能知道的  javaScript 数据结构与算法

冒泡排序的执行过程

你可能知道的  javaScript 数据结构与算法

代码如下:

let arr = [5, 4, 3, 2, 1]

// 交换元素的位置
function swap(arr, index1, index2) {
    var temp = arr[index1]
    arr[index1] = arr[index2]
    arr[index2] = temp
}

function bubbleSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1)
            }
        }
    }
}

bubbleSort(arr)
console.log(arr)  // [1, 2, 3, 4, 5]

2.选择排序

你可能知道的  javaScript 数据结构与算法

选择排序的执行过程

你可能知道的  javaScript 数据结构与算法

代码如下:

let arr = [5, 4, 3, 2, 1]

function swap(arr, index1, index2) {
    var temp = arr[index1]
    arr[index1] = arr[index2]
    arr[index2] = temp
}

function changeSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        let minIndex = i
        for (let j = i; j < arr.length; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j
            }
        }

        if (i !== minIndex) {
            swap(arr, i, minIndex)
        }
    }
}

changeSort(arr)
console.log(arr)  // [1, 2, 3, 4, 5]

3.插入排序

你可能知道的  javaScript 数据结构与算法

插入排序的执行过程

你可能知道的  javaScript 数据结构与算法

代码如下:

let arr = [5, 4, 3, 2, 1]

function swap(arr, index1, index2) {
    var temp = arr[index1]
    arr[index1] = arr[index2]
    arr[index2] = temp
}

function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let j = i
        let temp = arr[i]
        while (j > 0 && arr[j - 1] > temp) {
            arr[j] = arr[j - 1]
            j--
        }
        arr[j] = temp
    }
}

insertSort(arr)
console.log(arr)  // [1, 2, 3, 4, 5]

由于功力有限,本文有错误和不合理的地方,欢迎各位大神多多指正,非常感谢。

参考文章:

学习JavaScript数据结构与算法
数据结构与算法JavaScript描述

相关推荐