数据结构学习记录

🕗 发布于 2024-04-19 17:32 数据结构 学习

数据结构

数组 & 链表
相连性 | 指向性
数组可以迅速定位到数组中某一个节点的位置
链表则需要通过前一个元素指向下一个元素，需要前后依赖顺序查找，效率较低

实现链表

//    head => node1 => node2 => ... => null

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


class LinkList {
    constructor() {
        this.length = 0;
        //    1.空链表特征 => 判断链表的长度
        this.head = null;
    }
    
    //    返回索引对应的元素
    getElementAt(position) {
        //    边缘检测
        if (position < 0 || position >= this.length) {
            return null;
        }
        
        let _current = this.head;
        for (let i = 0; i < position; i++) {
            _current = _current.next;
        }
        
        return _current;
    }
    
    //    查找元素所在位置
    indexOf(element) {
        let _current = this.head;
        for (let i = 0; i < this.length; i++) {
            if (_current === element) return i;
            _current = _current.next;
        }
        return -1;
    }
    
    //    添加节点 在尾部加入
    append(element) {
        _node = new Node(element);
        
        if (this.head === null) {
            this.head = _node;
        } else {
            this.getElementAt(this.length - 1);
            _current.next = _node;
        }
        this.length++;   
    }
    
    //    插入节点    在中间插入
    insert(position, element) {
        if (position < 0 || position > this.length) return false;
        
        let _node = new Node(element);
        if (position === 0) {
            _node.next = this.head;
            this.head = _node;
        } else {
            let _previos = this.getElementAt(position - 1);
            _node.next = _previos;
            _previos.next = _node;
        }
        this.length++;
        return true;
    }
    
    //    删除指定位置元素
    removeAt(position) {
        if (position < 0 || position > this.length) return false;
        
        if (position === 0) {
            this.head = this.head.next;
        } else {
            _previos = this.getElementAt(position - 1);
            let _current = _previos.next;
            _previos.next = current.next;            
        }
        this.length--;
        return true;
    }
    
    //    删除指定元素
    remove(element) {
    }
}

栈

特点：先入后出（薯片桶）

队列

特点：先入先出（排队）

哈希

特点：快速匹配定位

树

遍历前序遍历（中左右）中序遍历（左中右）后序遍历（左右中）
1.二叉树 or 多子树
2.结构定义
a.树是非线性结构
b.每个节点都有0个或多个后代

面试真题：

判断括号是否有效自闭合

算法流程：
1.确定需要什么样的数据结构，满足模型的数据 - 构造变量 & 常量
2.运行方式简单条件执行 | 遍历 | 递归 - 算法主体结构
3.确定输入输出 - 确定流程

    //    '{}[]' 和 '[{}]' true,   
    //    '{{}[]' false
const stack = [];

const brocketMap = {
    '{': '}',
    '[': ']',
    '(': ')'
};

let str = '{}';

function isClose(str) {
    for (let i = 0; i < str.length; i++) {
        const it = str[i];
        if (!stack.length) {
            stack.push(it);
        } else {
            const last = stack.at(-1);
            if (it === brocketMap[last]) {
                stack.pop();
            } else {
                stack.push(it);
            }
        }
    }
    
    if (!stack.length) return true;

    return false;
}

isClose(str);

遍历二叉树

//    前序遍历
class Node {
    constructor(node) {
        this.left = node.left;
        this.right = node.right;
        this.value = node.value;
    }
}
//    前序遍历
const PreOrder = function(node) {
    if (node !== null) {
        console.log(node.value);
        PreOrder(node.left);
        PreOrder(node.right);
    }
}
//    中序遍历
const InOrder = function(node) {
    if (node !== null) {
        InOrder(node.left);
        console.log(node.value);
        InOrder(node.right);
    }
}
//    后序遍历
const PostOrder = function(node) {
    if (node !== null) {
        PostOrder(node.left);
        PostOrder(node.right);
        console.log(node.value);
    }
}

树结构深度遍历

const tree = {
    value: 1,
    children: [
        {
            value: 2,
            children: [
                { value: 3 },
                {
                    value: 4, children: [
                        { value: 5 }
                    ]
                }
            ]
        },
        { value: 5 },
        {
            value: 6, 
            children: [
                { value: 7 }
            ]
        }
    ]
}
//    优先遍历节点的子节点 => 兄弟节点
//    递归方式
function dfs(node) {
    console.log(node.value);
    if (node.children) {
        node.children.forEach(child => {
            dfs(child);
        })   
    }
}

//    遍历 - 栈
function dfs() {
    const stack = [node];
    while (stack.length > 0) {
        const current = stack.pop();
        console.log(current.value);
        if (current.children) {
            const list = current.children.reverse();
            stack.push(...list);
        }
    }
 }

树结构广度优先遍历

const tree = {
    value: 1,
    children: [
        {
            value: 2,
            children: [
                { value: 3 },
                {
                    value: 4, children: [
                        { value: 5 }
                    ]
                }
            ]
        },
        { value: 5 },
        {
            value: 6, 
            children: [
                { value: 7 }
            ]
        }
    ]
}

//    1. 递归
function bfs(nodes) {
    const list = []
    nodes.forEach(child => {
        console.log(child.value);
        if (child.children && child.children.length) {
            list.push(...child.children);
        }
    })
    if (list.length) {
        bfs(list);    
    }
}
bfs([tree]);

//    1.递归 - 方法2
function bfs(node, queue = [node]) {
    if (!queue.length) return;
    
    const current = queue.shift();
    if (current.children) {
        queue.push(...current.children);
    }
    
    bfs(null, queue);
}
bfs(tree);


//    2. 递归
function bfs(node) {
    const queue = [node];
    while(queue.length > 0) {
        const current = queue.shift();
        if (current.children) {
            queue.push(...current.children);
        }
    }
}

实现快速构造一个二叉树

1.若他的左子树非空，那么他的所有左子节点的值应该小于根节点的值
2.若他的右子树非空，那么他的所有右子节点的值应该大于根节点的值
3.他的左 / 右子树各自又是一颗满足下面两个条件的二叉树

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

class BinaryTree {
    constructor() {
    //    根节点
        this.root = null;
    }
    
    //    新增节点
    insert(key) {
        const newNode = new Node(key);
        
        const insertNode = (node, newNode) => {
            if (newNode.key < node.key) {
    //    没有左节点的场景 => 成为左节点
                node.left ||= newNode;
                
    //    已有左节点的场景 => 递归改变参照物，与左节点进行对比判断插入位置
                inertNode(node.left, newNode);
            } else {
    //    没有左节点的场景 => 成为左节点
                node.right ||= newNode;
                
    //    已有左节点的场景 => 递归改变参照物，与左节点进行对比判断插入位置
                inertNode(node.right, newNode);
            }
        }
        
        this.root ||= newNode;
        //    有参照物后进去插入节点
        insertNode(this.root, newNode);
    }
    
    //    查找节点
    contains(node) {        
        const searchNode = (referNode, currentNode) => {
            if (currentNode.key === referNode.key) {
                return true;
            }
            if (currentNode.key > referNode.key) {
                 return searchNode(referNode.right, currentNode);
            }
            
            if (currentNode.key < referNode.key) {
                 return searchNode(referNode.left, currentNode);
            }
            
            return false;
        }
        return searchNode(this.root, node);
    }
    
    //    查找最大值
    findMax() {
        let max = null;
        
        //    深度优先遍历
        const dfs = node => {
            if (node === null) return;
            if (max === null || node.key > max) {
                max = node.key;
            }
            dfs(node.left);
            dfs(node.right);
        }
        
        dfs(this.root);
        return max;
    }
    
    //    查找最小值
    findMin() {
        let min = null;
        
        //    深度优先遍历
        const dfs = node => {
            if (node === null) return;
            if (min === null || node.key < min) {
                min = node.key;
            }
            dfs(node.left);
            dfs(node.right);
        }
        
        dfs(this.root);
        return min;
    }
    
    //    删除节点
    remove(node) {
        const removeNode = (referNode, current) => {
            if (referNode.key === current.key) {
                if (!node.left && !node.right) return null;
                if (!node.left) return node.right;
                if (!node.right) return node.left;
                
            }
        }
        
        return removeNode(this.root, node);
    }
}

平衡二叉树

在这里插入图片描述

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


class AVL {
    constructor() {
        this.root = null;
    }
    
    // 插入节点
    insert(key, node = this.root) {
    if (node === null) {
    this.root = new Node(key);
    return;
    }
    
    if (key < node.key) {
    node.left = this.insert(key, node.left);
    } else if (key > node.key) {
    node.right = this.insert(key, node.right);
    } else {
    return;
    }
    
    // 平衡调整
    const balanceFactor = this.getBalanceFactor(node);
    if (balanceFactor > 1) {
    if (key < node.left.key) {
    node = this.rotateRight(node);
    } else {
    node.left = this.rotateLeft(node.left);
    node = this.rotateRight(node);
    }
    } else if (balanceFactor < -1) {
    if (key > node.right.key) {
    node = this.rotateLeft(node);
    } else {
    node.right = this.rotateRight(node.right);
    node = this.rotateLeft(node);
    }
    }
    
    this.updateHeight(node);
    return node;
    }
    
    // 获取节点平衡因子
    getBalanceFactor(node) {
        return this.getHeight(node.left) - this.getHeight(node.right);
    }
    
    rotateLeft(node) {      
        const newRoot = node.right;        
        node.right = newRoot.left;        
        newRoot.left = node;
        
        //    这里是为了校准更新的这两个节点的高度。只需要把他的左右节点的高度拿来 加1即可
        node.height = Math.max(
            this.getHeight(node.left),
            this.getHeight(node.right)
        ) + 1;
        newRoot.height = Math.max(
            this.getHeight(newRoot.left),
            this.getHeight(newRoot.right)
        ) + 1;

        return newRoot;
    }
    
    getHeight(node) {
        if (!node) return 0;
        return node.height;
    }
}

红黑树

参考写法

let RedBlackTree = (function() {
    let Colors = {
        RED: 0,
        BLACK: 1
    };

    class Node {
        constructor(key, color) {
            this.key = key;
            this.left = null;
            this.right = null;
            this.color = color;

            this.flipColor = function() {
                if(this.color === Colors.RED) {
                    this.color = Colors.BLACK;
                } else {
                    this.color = Colors.RED;
                }
            };
        }
    }

    class RedBlackTree {
        constructor() {
            this.root = null;
        }

        getRoot() {
            return this.root;
        }

        isRed(node) {
            if(!node) {
                return false;
            }
            return node.color === Colors.RED;
        }

        flipColors(node) {
            node.left.flipColor();
            node.right.flipColor();
        }

        rotateLeft(node) {
            var temp = node.right;
            if(temp !== null) {
                node.right = temp.left;
                temp.left = node;
                temp.color = node.color;
                node.color = Colors.RED;
            }
            return temp;
        }

        rotateRight(node) {
            var temp = node.left;
            if(temp !== null) {
                node.left = temp.right;
                temp.right = node;
                temp.color = node.color;
                node.color = Colors.RED;
            }
            return temp;
        }

        insertNode(node, element) {

            if(node === null) {
                return new Node(element, Colors.RED);
            }

            var newRoot = node;

            if(element < node.key) {

                node.left = this.insertNode(node.left, element);

            } else if(element > node.key) {

                node.right =this.insertNode(node.right, element);

            } else {
                node.key = element;
            }

            if(this.isRed(node.right) && !this.isRed(node.left)) {
                newRoot = this.rotateLeft(node);
            }

            if(this.isRed(node.left) && this.isRed(node.left.left)) {
                newRoot = this.rotateRight(node);
            }
            if(this.isRed(node.left) && this.isRed(node.right)) {
                this.flipColors(node);
            }

            return newRoot;
        }

        insert(element) {
            this.root = insertNode(this.root, element);
            this.root.color = Colors.BLACK;
        }
    }
    return RedBlackTree;
})()

原文地址：https://blog.csdn.net/weixin_44273392/article/details/137916648

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：通过阿里云向量检索 Milvus 版和通义千问快速构建基于专属知识库的问答系统
下一篇：springboot结合vue实现文件上传下载功能

【已为网站上传证书,却显示不安全】
【已为网站上传证书,却显示不安全】
阅读更多2024-11-16
Jtti：服务器总是自动重启怎么办?
1.查看系统日志：通过查看系统日志文件(如/var/log/syslog、/var/log/messages或Windows Event Viewer)获取错误信息，找出重启原因。解决方案：查看系统日
阅读更多2024-11-16
Scala的Array(1)
Scala的Array表示长度不可变的数组，若需要定义可变数组需要倒包。
阅读更多2024-11-16
Scala中的Array
Array是一种在Scala中用于存储固定大小，相同类型元素的数据结构，Array是可变。类型有两种：Array表示长度不可变的数组，和ArrayBuffer表示长度可变的数组。(一)Array的定义
阅读更多2024-11-16
llama factory lora 微调 qwen2.5 7B Instruct模型
项目背景甲方提供一台三卡4080显卡需要进行qwen2.5 7b Instruct模型进行微调。以下为整体设计。要使用对进行，流程与之前提到的模型类似。LoRA 微调是一种高效的微调方法，通过低秩
阅读更多2024-11-16
大数据中的时序数据，以及时序数据架构设计解决方案
时序数据架构设计需根据具体的应用场景、数据量和实时性要求来选择合适的方案。如果数据量较小且不需要实时处理，关系型数据库可能足够；如果数据量大且需要高效实时查询，可以选择时序数据库；而对于大规模分布式处
阅读更多2024-11-16
Linux网络——网络初识
在谈及网络之前，我们要先对学的知识有一个了解网络的本质就是获取数据，而系统的本质就是加工数据。
阅读更多2024-11-16
革新预测领域：频域融合时间序列预测，深度学习新篇章，科研涨点利器
2024发论文&模型涨点之——频域+时间序列频域+时间序列不仅能提供更丰富的信息，还能提高模型性能和预测准确性。对于论文er来说，是个可发挥空间大、可挖掘创新点多的研究方向。当前，学术界的目光
阅读更多2024-11-16
本地启动浏览器，并禁用web安全性，解决本地启动时，服务端强制要求https协议导致请求不通的问题
本地启动浏览器，并禁用web安全性，解决本地启动时，服务端强制要求https协议导致请求不通的问题
阅读更多2024-11-16
推荐一款来自韩国的影音全能播放器：KMPlayer播放器
来自韩国的影音全能播放器，与Mplayer一样从linux平台移植而来的Kmplayer(简称KMP)几乎可以播放您系统上所有的影音文件。通过各种插件扩展KMP可以支持层出不穷的新格式。强大的插件功能
阅读更多2024-11-16