数据结构和算法

发表于 2022-04-29 更新于 2022-08-19 分类于前端学习笔记，算法阅读次数： Changyan：本文字数： 9.2k 阅读时长 ≈ 8 分钟

数据结构和算法

数组

优点

便于存取

缺点

删除消耗性能
占用一段连续的存储空间

链表

优点

删除效率高
不占用连续的存储空间

缺点

查询效率低

创建一个链表

function Node(value) {
    this.value = value;
    this.next = null;
}

const list = new Node(0);

let temp = list;
for (let i = 0; i < 8; i++) {
    temp.next = new Node(i + 1);
    temp = temp.next;
}

遍历链表

普通while循环遍历

function traversal(root) {
    while (true) {
        if (root) {
            console.log(root.value);
        } else {
            break;
        }
        root = root.next
    }
}

递归遍历链表

function traversalRecursion(root) {
    if (root === null) {
        return;
    }
    console.log(root.value);
    traversalRecursion(root.next)
}

链表逆置

递归

function reverseLink(root) {
    if (!root.next.next) {
        root.next.next = root;
        return root.next;
    } else {
        const result = reverseLink(root.next);
        root.next.next = root;
        root.next = null;
        return result;
    }
}

function reverseLink(head) {
    if (head == null || head.next == null) {
        return head;
    }
    const newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
};

循环

function useWhileReverse(head){
    let prev = null;
    let cur = head;
    while(cur){
        let next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

排序

/**
 * 传入两个参数，比较是否需要交换，flag为1表示升序，flag = 0表示降序
 * @param {number} a 
 * @param {number} b 
 * @param {number} flag 1 }| 0
 */
function compare(a, b, flag = 1) {
    if (flag) {
        return a - b > 0;
    } else {
        return a - b < 0;
    }
}

/**
 * 交换数组链各个位置的数
 * @param {array} arr 
 * @param {number} a 
 * @param {number} b 
 */
function exchange(arr, a, b) {
    const temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

冒泡排序

每次将最大或最小的数，通过数组前后两两交换，冒泡到数组的最后一位。
数组顺序越混乱，效率越低。

/**
 * 冒泡排序
 * @param {array} arr 
 */
function sort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i; j++) {
            if (compare(arr[j], arr[j + 1])) {
                exchange(arr, j, j + 1);
            }
        }
    }
}

选择排序

通过找出数组中除去已排好位置中的最大值或最小值，把它放到数组中未排序部分的最前面。

/**
 * 选择排序
 * @param {array} arr 
 */
function sort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (compare(arr[i], arr[j], 0)) {
                exchange(arr, i, j);
                console.log(arr)
            }
        }
    }
}

快速排序

数组顺序越乱，效率越高。

一种简单的实现，消耗性能(创建多个数组)

每次都找一个领导者，大于这个数的都放在left数组中，大于这个数的都放在right数组中，再对left和right重复操作。

function quickSort(arr) {
    if (arr === null || arr.length === 0) {
        return [];
    }
    const leader = arr[0];
    let left = [];
    let right = [];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < leader) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    left = quickSort(left);
    right = quickSort(right);
    left.push(leader);
    return left.concat(right)

}

效率高

/**
 * 快速排序
 * @param {*} arr 数组
 * @param {*} begin 数组开始处理的位置
 * @param {*} end 数组结束处理的位置
 */
function quickSort(arr, begin, end) {
    if (begin >= end - 1) return;
    let left = begin;
    let right = end;
    do {
        // 找出连续的两段数组，左边一段比领导者，右边一段比领导者大，领导者为arr[begin]
        do {
            left++;
        } while (left < right && arr[left] < arr[begin]);
        do {
            right--;
        } while (right > left && arr[right] > arr[begin]);
        if (left < right) {
            exchange(arr, left, right);
        }
    } while (left < right);
    const swapPointer = left == right ? right - 1 : right;
    exchange(arr, begin, swapPointer);
    quickSort(arr, begin, swapPointer);
    quickSort(arr, swapPointer + 1, end);
}

栈

先进后出


function Stack() {
    this.arr = [];
    this.pop = function() {
        this.arr.pop();
    };
    this.push = function(item) {
        this.arr.push(item);
    }
}

队列

先进先出

function Queue() {
    this.arr = [];
    this.pop = function() {
        this.arr.shift();
    }
    this.push = function(item) {
        this.arr.push(item)
    }
}

双向链表

优点

无论给出哪一个节点，都能对整个链表进行遍历

缺点

多耗费一个引用空间，且构建较为麻烦

二叉树

创建一个二叉树

function Root(value) {
    this.value = value;
    this.leftChild = null;
    this.rightChild = null;
}


const a = new Root('a');
const b = new Root('b');
const c = new Root('c');
const d = new Root('d');
const e = new Root('e');
const f = new Root('f');
const g = new Root('g');

a.leftChild = b;
a.rightChild = c;
b.leftChild = d;
b.rightChild = e;
c.leftChild = f;
c.rightChild = g;

二叉树遍历

前序遍历

先根，再左子树点再遍历右子树

// 前序遍历
function frontTraversal(root) {
    if (root === null) {
        return;
    }
    console.log(root.value);
    frontTraversal(root.leftChild);
    frontTraversal(root.rightChild);
}

中序遍历

先左子树，再根节点，最后遍历右子树

// 中序遍历
function middleTraversal(root) {
    if (root === null) {
        return;
    }
    middleTraversal(root.leftChild);
    console.log(root.value);
    middleTraversal(root.rightChild);
}

后序遍历

先左子树，再右子树，最后是根节点

// 后序遍历
function lastTraversal(root) {
    if (root === null) {
        return;
    }
    lastTraversal(root.leftChild);
    lastTraversal(root.rightChild);
    console.log(root.value)
}

还原二叉树

根据前序和中序遍历结果还原二叉树

function Node(value) {
    this.value = value;
    this.leftChild = null;
    this.rightChild = null;
}

// 根据树的中序和前序遍历结果还原二叉树
function frontMiddleToTree(front, middle) {
    if (front === null || middle === null || front.length === 0 || middle.length === 0 || front.length !== middle.length) return;
    const root = new Node(front[0]);
    const rootIndex = middle.indexOf(root.value); //在中序遍历中找到根节点的位置
    const frontLeft = front.slice(1, rootIndex + 1); //在前序遍历中的左子树
    const frontRight = front.slice(rootIndex + 1); //在前序遍历中的右子树
    const middleLeft = middle.slice(0, rootIndex); //在中序遍历中的左子树
    const middleRight = middle.slice(rootIndex + 1); // 在中序遍历中的右子树
    root.leftChild = frontMiddleToTree(frontLeft, middleLeft);
    root.rightChild = frontMiddleToTree(frontRight, middleRight);
    return root;
}

根据后序和中序遍历结果还原二叉树

const middle = ['F', 'C', 'G', 'A', 'D', 'B', 'E'];
const last = ['F', 'G', 'C', 'D', 'E', 'B', 'A'];

function Node(value) {
    this.value = value;
    this.leftChild = null;
    this.rightChild = null;
}


// 根据树的中序和后序遍历结果还原二叉树
function middleLastToTree(middle, last) {
    if (middle === null || last === null || middle.length === 0 || last.length === 0 || middle.length !== last.length) return;
    const root = new Node(last[last.length - 1]);
    const rootIndex = middle.indexOf(root.value); //找到根节点在中序遍历中的位置
    const lastLeft = last.slice(0, rootIndex);
    const lastRight = last.slice(rootIndex, last.length - 1);
    const middleLeft = middle.slice(0, rootIndex);
    const middleRight = middle.slice(rootIndex + 1);
    root.leftChild = middleLastToTree(middleLeft, lastLeft);
    root.rightChild = middleLastToTree(middleRight, lastRight);
    return root;
}

二叉树的搜索

深度优先搜索

搜索未知，和前序遍历顺序一致

/**
 * 深度优先搜索
 * @param {*} root 二叉树的根节点
 * @param {*} target 要查找的值
 * @returns true | false
 */
function dfs(root, target) {
    console.log(root)
    if (root === null) return false;
    if (root.value === target) return true;
    const left = dfs(root.leftChild, target);
    const right = dfs(root.rightChild, target);
    return left || right;
}

广度优先搜索

搜索局域；

/**
 * 广度优先搜索
 * @param {array} rootList 根节点数组
 * @param {*} target 要查询的值
 * @return true | false
 */
function bfs(rootList, target) {
    if (rootList == null || rootList.length === 0) return false;
    let childrenList = []; //存放子节点
    for (let i = 0; i < rootList.length; i++) {
        if (rootList[i] !== null && rootList[i].value === target) {
            return true;
        } else {
            if (rootList[i].leftChild) {
                childrenList.push(rootList[i].leftChild);
            }
            if (rootList[i].rightChild) {
                childrenList.push(rootList[i].rightChild);
            }

        }
    }
    return bfs(childrenList, target);
}

二叉树的比较

区分左右子树的比较

/**
 * 在区分左右子树的情况下，比较两个树是否相等
 * @param {*} root1 根节点1
 * @param {*} root2 根节点2
 */
function compare(root1, root2) {
    if (root1 === root2) return true;
    if (root1 === null && root2 !== null || root1 !== null && root2 === null) return false;
    if (root1.value !== root2.value) return false;
    return compare(root1.leftChild, root2.leftChild) && compare(root1.rightChild, root2.rightChild)
}

不区分左右子树的比较

/**
 * 在不区分左右子树的情况下，比较两个树是否相等
 * @param {*} root1 根节点1
 * @param {*} root2 根节点2
 */
function compare(root1, root2) {
    if (root1 === root2) return true;
    if (root1 === null && root2 !== null || root1 !== null && root2 === null) return false;
    if (root1.value !== root2.value) return false;
    return (compare(root1.leftChild, root2.leftChild) && compare(root1.rightChild, root2.rightChild)) ||
        (compare(root1.leftChild, root2.rightChild) && compare(root1.rightChild, root2.leftChild))
}

diff算法

/**
 * 找出两棵树不同的地方
 * @param {*} root1 
 * @param {*} root2 
 * @param {array} diffList 存放不同的数组
 */
function diff(root1, root2, diffList) {
    if (root1 === root2) return diffList
    if (root1 === null && root2 !== null) {
        return diffList.push({ type: '新增', origin: null, now: root2 });
    } else if (root1 !== null && root2 === null) {
        return diffList.push({ type: '删除', origin: root1, now: null });
    } else if (root1.value !== root2.value) {
        return diffList.push({ type: '修改', origin: root1, now: root2 });
        diff(root1.leftChild, root2.leftChild, diffList);
        diff(root1.rightChild, root2.rightChild, diffList);
    }
    diff(root1.leftChild, root2.leftChild, diffList);
    diff(root1.rightChild, root2.rightChild, diffList);
}

图

最小生成树问题

普利姆算法

加点法

任意找一个点做为起点
找到以当前选中点为起点路径最短的边
如果这个边的另一端没有被连通，那么久连接
如果已经被连通，则继续寻找第二短路径的边
重复寻找

克鲁斯卡尔算法

加边法

选择最小的边进行连接
要保证连接的两端至少有一个点是新的点，或者这个边将两个部落相连
重复，直到所有点都加入