IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 数据结构与算法基础知识(二):常见数据结构 -> 正文阅读

[数据结构与算法]数据结构与算法基础知识(二):常见数据结构

系列文章

数据结构与算法基础知识(一):时间复杂度和空间复杂度
数据结构与算法基础知识(二):常见数据结构
数据结构与算法基础知识(三):常见排序、搜索算法


本篇介绍一些对于前端工程师来说比较常用、常见的数据结构。

是一个后进先出的数据结构。JavaScript中没有,但是可以用Array实现的所有功能。

const stack = []

// 入栈
stack.push(0)
stack.push(1)

// 出栈
const val1 = stack.pop() // 1
const val2 = stack.pop() // 0

栈的典型应用

1047. 删除字符串中的所有相邻重复项

var removeDuplicates = function (s) {
    const stack = []
    for (const item of s) {
        if (item === stack[stack.length - 1]) stack.pop()
        else stack.push(item)
    }
    return stack.join('')
};

队列

队列是一个先进先出的数据结构。JavaScript中没有队列,但是可以用Array实现队列的所有功能。

const queue = []

// 入队
stack.push(0)
stack.push(1)

// 出队
const val1 = stack.shift() // 0
const val2 = stack.shift() // 1

队列的典型应用

933. 最近的请求次数

var RecentCounter = function() {
    this.queue = []
}

RecentCounter.prototype.ping = function(t) {
    this.queue.push(t)
    while(this.queue[0] < t - 3000)
        this.queue.shift()
    return this.queue.length
}

链表

链表是多个元素组成的列表,元素存储不连续,用next指针连在一起。JavaScript中没有链表,但是可以用Object模拟链表

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}

const a = new ListNode('a')
const b = new ListNode('b')
const c = new ListNode('c')
a.next = b
b.next = c

// 遍历链表节点
let pointer = a
while (pointer) {
    console.log(pointer.val)
    pointer = pointer.next
}

// 插入链表节点
const z = new ListNode('z')
a.next = z
z.next = b

// 删除链表节点
a.next = b

链表的典型应用

203. 移除链表元素

var removeElements = function(head, val) {
    const virtualHead = new ListNode(0, head)
    let pointer = virtualHead
    while (pointer.next) {
        if (pointer.next.val === val) {
            pointer.next = pointer.next.next
        } else {
            pointer = pointer.next
        }
    }
    return virtualHead.next
};

原型链
JavaScript中的原型链就是链表。我们知道instanceof运算符,用来检测某对象是否是某个类的实例。如果A沿着原型链能找到B.prototype, 那么A instanceof Btrueinstanceof实现原理如下。

function my_instanceof(a, b) {
    let p = a
    while (p) { // 指针 p 非空
        if (p.__proto__ === b.prototype) return true
        p = p.__proto__
    }
    return false
}

哈希表

哈希表Hash table,也叫散列表),是根据键(Key)对数据直接进行存取的数据结构,它通过把键映射到表中一个位置来存取其代表的数据,以加快数据存取的速度。这个映射函数叫做哈希函数
向哈希表中存储数据时,会根据数据的键和哈希函数得到一个下标,下标的含义是数据在哈希表中的存放的位置。若多个数据的下标相同导致发生了冲突,则再根据冲突处理规则(比如拉链法)来解决冲突。找到最终存放的位置后,将数据存放进去。在哈希表中查找数据时,会根据数据的键、哈希函数以及冲突处理规则来查找数据。
JavaScript中的SetMap以及ObjectV8引擎中的底层实现都是哈希结构,其增删改查的时间复杂度都为 O ( 1 ) O(1) O(1)

Set常见方法与属性
add() has() delete() clear() forEach() size属性

Map常见方法与属性(注意:Map是有序结构)
set() get() has() delete() clear() forEach() size属性

哈希表的典型应用

383. 赎金信

var canConstruct = function (ransomNote, magazine) {
    const obj = {}
    for (const char of magazine) {
        obj[char] = (obj[char] ?? 0) + 1
    }
    for (const char of ransomNote) {
        obj[char] = (obj[char] ?? 0) - 1
    }
    for (const prop in obj) {
        if (obj[prop] < 0) return false
    }
    return true
}

二叉树

是一种分层数据的抽象模型,二叉树是树的一种,其每个节点最多只能有两个子节点。在JavaScript中通常用Object来模拟二叉树。

const binaryTree = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 4,
            left: null,
            right: null,
        },
        right: {
            val: 5,
            left: null,
            right: null,
        },
    },
    right: {
        val: 3,
        left: {
            val: 6,
            left: null,
            right: null,
        },
        right: {
            val: 7,
            left: null,
            right: null,
        },
    },
}

// 深度优先遍历(1245367,递归)
const dfs = (node) => {
    if (!node) return
    console.log(node.val)
    dfs(node.left)
    dfs(node.right)
}

// 广度优先遍历(1234567,迭代:利用队列,逐层遍历)
const bfs = (root) => {
    if (!root) return
    const q = [root]
    while (q.length) {
        const node = q.shift()
        console.log(node.val)
        if (node.left) q.push(node.left)
        if (node.right) q.push(node.right)
    }
}

// 先序遍历:根左右(1245367,同深度优先遍历)
const preorder = (root) => {
    if (!root) return
    console.log(root.val)
    preorder(root.left)
    preorder(root.right)
}

// 中序遍历:左根右(4251637)
const inorder = (root) => {
    if (!root) return
    inorder(root.left)
    console.log(root.val)
    inorder(root.right)
}

// 后序遍历:左右根(4526731)
const postorder = (root) => {
    if (!root) return
    postorder(root.left)
    postorder(root.right)
    console.log(root.val)
}

二叉搜索树

二叉搜索树(Binary Search Tree),它或者是一棵空树,或者是具有下列性质的二叉树:

  • 若它的左子树不空,则左子树上所有结点的值均小于其根结点的值;
  • 若它的右子树不空,则右子树上所有结点的值均大于其根结点的值;
  • 它的左、右子树也分别为二叉搜索树。

简单来讲,即左边的结点永远比根结点以及右边的结点小,右边的结点永远比根结点以及左边的结点大。由此可知,二叉搜索树的中序遍历递增序列。

给出一棵二叉搜索树,我们可以快速找出树中的某个节点以及从根节点到该节点的路径。例如我们需要找到节点p

  • 我们从根节点开始遍历;
  • 如果当前节点就是p,那么成功地找到了节点;
  • 如果当前节点的值大于p的值,说明p应该在当前节点的左子树,因此将当前节点移动到它的左子节点;
  • 如果当前节点的值小于p的值,说明p应该在当前节点的右子树,因此将当前节点移动到它的右子节点。

在寻找节点的过程中,我们可以顺便记录经过的节点,这样就得到了从根节点到被寻找节点的路径。

二叉搜索树作为一种经典的数据结构,它既有链表的快速插入与删除操作的特点,又有数组快速查找的优势;所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

二叉树的典型应用

226. 翻转二叉树

var invertTree = function(root) {
    if(!root) return null
  
    const left = invertTree(root.left) // 递归左子树,并保存左子树根节点
    const right = invertTree(root.right) // 递归右子树,并保存右子树根节点
  
    // 左右子树交换
    root.left = right
    root.right = left
  
    return root // 返回当前节点
};

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-05-24 18:28:42  更:2022-05-24 18:31:32 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/30 0:44:30-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码