首页 数据结构

数据结构是在计算机中存储和组织数据以使数据得以有效利用的一种方式。

# 分类

# 线性数据结构

数组、链表、栈、队列、双端队列、字符串等

# 非线性数据结构（结构性数据结构）

集合、字典、树、图、堆、跳表、哈希表

# 数组

# 栈

class Stack{
    #storage;
    constructor(arr=[]) {
        this.#storage = arr
    }
    push(vlaue) {
        this.#storage.push(vlaue);
    }
    pop() {
        this.#storage.pop();
    }
    peek() {
        return this.#storage[this.size()-1];
    }
    isEmpty() {
        return this.size()===0
    }
    size() {
        return this.#storage.length;
    }
    clear() {
        this.#storage = [];
    }
    print(str="") {
        return this.#storage.join(str)
    }
}

# 队列

class Queue{
    #storage;
    constructor(arr = []) {
        this.#storage = arr;
    }
    enqueue(item) {
        this.#storage.push(item)
    };
    dequeue() {
        this.#storage.shift();
    }
    front() {
        return this.#storage[0];
    }
    isEmpty() {
        return this.size() === 0;   
    }
    size() {
        return this.#storage.length;
    }
    print(str="") {
        return this.#storage.join(str);
    }
    clear(arr=[]) {
        this.#storage = arr;
    }
}

# set 集合

class Set{
    #storage;
    constructor(arr = []) {
        this.#storage = arr;
    }
    has(item) {
        return this.#storage.includes(item)
    }
    hasProperty(item) {
        return item in this;
    }
    add(item) {
        if (!this.has(item)) {
            this.#storage.push(item);
            return true;
        }
        return false
    }
    remove(value) {
        const index = this.#storage.indexOf(value);
        if (index === -1) return false;
        this.#storage.splice(index, 1);
        return true;
    }
    clear() {
        this.#storage = []
    }
    size() {
        return this.#storage.length;
    }
    values() {
        return Object.values(this.#storage);
    }
    // 并集
    union(otherSet) {
        const values = otherSet.values();
        const res = new Set(this.#storage);
        for(let item of values){
            res.add(item);
        }
        return res;
    }
    // 交集
    intersection(otherSet) {
        const values = otherSet.values();
        const res = new Set();
        for (let item of values) {
            if (this.has(item)) {
                res.add(item)
            }
        }
        return res;
    }
    // 差集
    difference(otherSet) {
        const values = otherSet.values();
        const res = new Set(this.#storage);
        for (let item of values) {
            res.remove(item)
        }
        return res;
    }
}

# 优先级队列

class PriorityElement{
    #element; #priority;
    constructor(element, priority) {
        this.#element = element;
        this.#priority = priority;
    }
}
class PriorityQueue{
    #storage;
    constructor(arr = [],priority=0) {
        this.#storage = arr;
    };
    enqueue(item,priority) {
        const element = new PriorityElement(item, priority);
        if (this.isEmpty) {
            this.#storage.push(element);
        } else {
            let added = false;
            for (let i = 0; i < this.#storage.length; i++){
                if (item[i].priority > element.priority) {
                    item.splice(i, 0, element);
                    added = true;
                    break;
                }
            }
            if (!added) item.push(element);
        }
    }
    dequeue() {
        this.#storage.shift();
    }
    front() {
        return this.#storage[0];
    }
    isEmpty() {
        return this.#storage.length === 0;
    }
    size() {
        return this.#storage.length;
    }
    print(str="") {
        return this.#storage.join(str);
    }
    clear() {
        this.#storage = [];
    }
}

# 哈希表

class HashTable {
    // 属性
    #storage; #count; #limit;
    constructor() {
        this.#storage = [];
        this.#count = 0; // 计算已经存储的元素个数    
        this.#limit = 7; // 初始长度
    }
    hashFunc(str, size) {
        let hashCode = 0;
        for (let i = 0; i < str.length; i++) {
            hashCode = 37 * hashCode + str.charCodeAt(i); // 质数乘以 hashCode 递归加上字符编码
        }
        let index = hashCode % size; // 将总和对 size 大小取余，找出 index 的位置。
        return index;
    };
    put(key, value) {
        let index = this.hashFunc(key, this.#limit);
        let bucket = this.#storage[index];
        if (bucket == null) {
            bucket = [];
            this.#storage[index] = bucket;
        }
        for (let i = 0; i < bucket.length; i++) {
            let tuple = bucket[i];
            if (tuple[0] == key) {
                tuple[1] = value;
                return; // 不用返回值
            }
        }
        bucket.push([key, value]);
        this.#count += 1;
        if (this.#count > this.#limit * 0.75) { // 哈希表扩容以减少哈希冲突
            let newSize = this.#limit * 2;
            let newPrime = this.getPrime(newSize);
            this.resize(newPrime);
        }
    };
    get(key) {
        let index = this.hashFunc(key, this.#limit);
        let bucket = this.#storage[index];
        if (bucket == null) {
            return null;
        }
        for (let i = 0; i < bucket.length; i++) {
            let tuple = bucket[i];
            if (tuple[0] == key) {
                return tuple[1];
            }
        }
        return null;
    };
    remove(key) {
        let index = this.hashFunc(key, this.#limit);
        let bucket = this.#storage[index];
        if (bucket == null) {
            return null;
        }
        for (let i = 0; i < bucket.length; i++) {
            let tuple = bucket[i];
            if (tuple[0] == key) {
                bucket.splice(i, 1);
                this.#count -= 1;
                return tuple[1];
            }
        }
        if (this.#limit > 7 && this.#count < this.#limit * 0.25) {
            let newSize = Math.floor(this.#limit / 2);
            let newPrime = this.getPrime(newSize);
            this.resize(newPrime);
        }
        return null;
    };
    isEmpty() {
        return this.#count == 0;
    };
    size() {
        return this.#count;
    };
    resize(newLimit) {
        let oldStorage = this.#storage;
        this.#storage = [];
        this.#count = 0;
        this.#limit = newLimit;
        for (let i = 0; i < oldStorage.length; i++) {
            const bucket = oldStorage[i];
            if (bucket == null) {
                continue;
            }
            for (let j = 0; j < bucket.length; j++) {
                const tuple = bucket[j];
                this.put(tuple[0], tuple[1]); // 插入数据的 key 和 value
            }
        }
    };
    isPrime(num) {
        if (num <= 1) {
            return false;
        }
        //1. 获取 num 的平方根：Math.sqrt (num)
        //2. 循环判断
        for (var i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    };
    // 获取质数的方法
    getPrime(num) {
        //7*2=14,+1=15,+1=16,+1=17 (质数)
        while (!this.isPrime(num)) {
            num++;
        }
        return num;
    };
}

# 链表

class ListNode{
    #value;
    constructor(value,next=null) {
        this.#value = value;
        this.next = next;
    }
}
class LinkedList{
    #head; #length;
    constructor(head=null,length=0) {
        this.#head = head;
        this.#length = length;
    };
    append(element) {
        const node = new ListNode(element);
        if (this.#head === null) {
            this.#head = node;
        } else {
            let lastNode = this.#head;
            while (lastNode.next !== null) {
                lastNode = lastNode.next;
            }
            lastNode.next = node;
        }
        this.#length++;
    }
    indexOf(element) {
        let lastNode = this.#head, index = 0;
        while (lastNode) {
            if (element === lastNode) {
                return index;
            }
            index++;
            lastNode = lastNode.next;
        }
        return -1;
    }
    removeAt(position) {
        if (position > -1 && position < this.#length) {
            let current = this.#head, previous, 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;
        } else {
            return null;
        }
    }
    insert(position, element) {
        if (position >= 0 && position <= this.#length) {
            let node = new Node(element), current = this.#head, previous, index = 0;
            if (position === 0) {
                node.next = current;
                this.#head = node;
            } else {
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
            }
            this.#length++;
            return true;
        } else {
            return false;
        }
    }
    isEmpty() {
        return this.#length === 0;
    }
    size() {
        return this.#length;
    }
    toString() {
        let current = this.#head, string = "";
        while (current) {
            string += current.value;
            current = current.next;
        }
        return string;
    }
    getHead() {
        return this.#head;
    }
    remove(element) {
        let index = this.indexOf(element);
        return this.removeAt(index);
    }
}

# map 字典

class Dictionary{
    #storage
    constructor(obj = {}) {
        this.#storage = obj;
    }
    has(key) {
        return key in this.#storage;
    }
    set(key, value) {
        this.#storage[key] = value;
    }
    remove(key) {
        if (this.has(key)) {
            delete this.#storage[key];
            return true;
        }
        return false;
    }
    get(key) {
        return this.has(key) ? this.#storage[key] : undefined;
    }
    values() {
        let values = [];
        for (let key in this.#storage) {
            if (this.has(key)) {
                values.push(this.#storage[k]);
            }
        }
        return values;
    }
    getItems() {
        return this.#storage;
    }
    clear() {
        this.#storage = {};
    }
    size() {
        return Object.keys(this.#storage).length;
    }
    keys() {
        return Object.keys(this.#storage);
    }
}

# 树

# 二叉树

# 哈夫曼树

# 哈夫曼编码

普通的二进制编码过程中，由于可能出现前缀的原因，使得编出来的二进制编码存在歧义，可以采用等长编码来取消前缀的可能，但是等长编码方案不是最短最优的编码方案，因此有了哈夫曼编码，它将出现次数越多的字符编的码越短

# 哈夫曼树

对一段字符进行编码，每次合并出现次数最少的两个字符作为树的底部，以此方法来构造一个树，树的左分支记为 0, 右分支记为 1

# 二叉搜索树

# 堆

堆分为最大堆和最小堆，通常有数组和二叉树两种表示方法

class Heap {
    #compareFn; #heap;
    constructor(compareFn = (a, b) => a - b) {
        this.#compareFn = compareFn;
        this.#heap = []; // 二叉树的数组表示
    }
    getLeftIndex(index) {
        return 2 * index + 1;
    }
    getRightIndex(index) {
        return 2 * index + 1;
    }
    getParentIndex(index) {
        if (index === 0) return undefined;
        return Math.floor((index - 1) / 2);
    }
    insert(value) {
        if (value !== null) {
            this.#heap.push(value);
            this.shifUp(this.#heap.length - 1);
            return true;
        } else {
            return false;
        }
    }
    shifUp(index) {
        if (index <= 0) return;
        let parentIndex = this.getParentIndex(index);
        while (index > 0 && this.#compareFn(this.#heap[parentIndex],this.#heap[index]) > Number.EPSILON) {
            this.#swap(index, parentIndex);
            index = parentIndex;
            parentIndex = this.getParentIndex(index);
        }
    }
    #swap(index1, index2) {
        [this.#heap[index1], this.#heap[index2]] = [this.#heap[index2], this.#heap[index1]];
    }
    size() {
        return this.#heap.length;
    }
    isEmpty() {
        return this.#heap.length === 0;
    }
    findMiniNum() {
        return this.isEmpty() ? undefined : this.#heap[0];
    }
    extract() {
        if (this.isEmpty()) {
            return undefined;
        }
        if (this.size() === 1) {
            return this.#heap.shift();
        }
        const removeValue = this.#heap.shift();
        this.shifDown(0);
        return removeValue;
    }
    shifDown(index) {
        let element = index;
        const leftIndex = this.getLeftIndex(index);
        const rightIndex = this.getRightIndex(index);
        if (leftIndex < this.size() && this.#compareFn(this.#heap[element], this.#heap[leftIndex]) > Number.EPSILON) {
            element = leftIndex;
        }
        if (rightIndex > this.size() && this.#compareFn(this.#heap[element], this.#heap[rightIndex]) > Number.EPSILON) {
            element = rightIndex;
        }
        if (index !== element) {
            this.#swap(index, element);
            this.shifDown(element);
        }
    }
    values() {
        return this.#heap;
    }
}

# 二叉平衡搜索树

二叉搜索树在极端情况下会退化为链表，导致时间复杂度为 O (n)，这时候就需要进行平衡

# 红黑树

https://github.com/ADHongyang/ADHongyang.github.io/tree/main

红黑树是二叉平衡搜索树之一，不同于传统的二叉平衡搜索树，红黑树使用颜色进行平衡判定，相比于二叉平衡搜索树，不用频繁地进行平衡调整，红黑树的事件复杂度为：O (log (n))，其具有以下 5 条性质：

  • 每个节点不是黑色就是红色
  • 根节点是黑色的
  • 叶节点是黑色的空节点
  • 所有红色节点的两个孩子都是黑色的
  • 任意节点到其可到达的叶节点之间有相同数量的黑色节点

这五条性质决定了红黑树的平衡：最长边不能大于最短边的两倍

# B 树

# 背景

当数据量很大时，树的深度就会变得很深，会导致大量的磁盘访问，B 树通过增加树的路数来减少树的高度，以降低磁盘访问的次数，B 树就是一个有序的多路查询树，它的每个节点可以存储多个关键字，使得每个磁盘块可以存储更多的数据，提高了存储空间的利用率

# B + 树

# 背景

B 树在处理范围查询和顺序访问时效率不高，因为数据分散在各个节点中，需要逐层遍历，B + 树对 B 树进行升级：

  • 所有数据都存储在叶子节点中
  • 叶子节点形成链表

B + 树在数据库和文件系统中的应用比 B 树更加广泛，主要是因为它在处理大量数据和频繁的范围查询时具有更好的性能

# 跳表

# 背景

B + 树主要是为了减少磁盘的 I/O 次数，不过有些场景（例如内存数据库 redius）是没必要减少磁盘 I/O 的，使用 B + 树反而会使得插入操作消耗较大，这时候使用跳表更加合适

# 理解

B + 树中叶节点都相当于叶节点的索引，用于快速定位到叶节点，叶节点中存储的才是需要的数据

# 图

图分为有向图和无向图，通常有邻接矩阵和邻接表两种表示方法

class Graph{
    #isDirected; #vertices; #adjList;
    constructor(isDirected = false) {
        this.#isDirected = isDirected; // 是否是有向图
        this.#vertices = new Set();
        this.#adjList = new Map();
    }
    addVertex(value) { // 添加一个顶点
        if (!this.#vertices.has(value)) {
            this.#vertices.add(value);
            this.#adjList.set(value, new Set());
        }
    }
    addEdge(v, w) { // 为某个顶点添加一个边
        if (!this.#adjList.get(v)) {
            this.addVertex(v);
        }
        if (!this.#adjList.get(w)) {
            this.addVertex(w);
        }
        this.#adjList.get(v).add(w);
        if (!this.#isDirected) {
            this.#adjList.get(w).add(v);
        }
    }
    getVertices() {
        return this.#vertices;
    }
    getAdjList() {
        return this.#adjList;
    }
    toString() {
        let s = "";
        const values = Array.from(this.#vertices);
        for (let i = 0; i < values.length; i++){
            s += `${values[i]} -> `;
            const neighbors = this.#adjList.get(values[i]);
            for (let item of neighbors) {
                s += item + " ";
            }
            s += "\n";
        }
        return s;
    }
}

图也分为带权图和非带权图，其中带权图可以根据某些算法求得其最小生成树

# 最小生成树

最小生成树并不唯一。

# Prim 普利姆算法

加点法：每一次去找哪个点，距离点亮 (已联通) 的部分最近，就加入这个点

  • Prim 算法更适合稠密图 (边比点多很多，判断点的过程很少)

# Kruskal 克鲁斯卡尔算法

加边法：每一次按照边从小到大的顺序去加边，如果边所在的两点目前不可达，就进行添加

  • Kruskal 算法更适合稀疏图 (边少，判定过程就少)

# 最短路径

# Dijkstra 迪杰斯特拉算法

DIjKstra 算法用于求某一个点到其他点的最短路径，也就是从某个点开始到其他点的最短路径长度，核心是：每次都记录 (表格) 从 a 到其他点的路径，选距离最短的点进行点亮，然后去做更新

# Floyd 佛洛依德算法

Floyd 算法用于求任意两个点之间的最短路径，核心是：依次将每个点作为:"中间点" 去做更新，更新最短路径和最短路径的长度

# 随机算法

const shuffle = (arr) => {
    for (let i = arr.length - 1; i > 0; i--){
        const randomIndex = Math.floor(Math.random() * (i + 1));
        [arr[randomIndex], arr[i]] = [arr[i], arr[randomIndex]];
    }
    return arr;
}
更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*

dmq 微信支付

微信支付

dmq 支付宝

支付宝