数据结构和算法完全教程 - 从零基础到精通

前言：为什么需要学习

🤔 数据结构和算法的重要性

数据结构和算法是编程的基础和灵魂。它们直接影响代码的性能、可维护性和可扩展性。

学习的收益

提高代码效率：选择合适的数据结构和算法
解决复杂问题：分解问题、设计方案
面试必备：大厂面试的核心内容
系统设计：架构设计的基础
代码优化：性能优化的关键

学习路线

基础数据结构：数组、链表、栈、队列
高级数据结构：树、图、堆、哈希表
基础算法：排序、搜索、递归
高级算法：动态规划、贪心、分治

💡 重点：理解原理比记住代码更重要。

复杂度分析

时间复杂度

// O(1) - 常数时间
function getFirst(arr) {
    return arr[0];
}

// O(n) - 线性时间
function findMax(arr) {
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

// O(n²) - 平方时间
function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
}

// O(log n) - 对数时间
function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// O(n log n) - 线性对数时间
function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

复杂度对比

O(1)：最快，常数时间
O(log n)：非常快，对数时间
O(n)：快，线性时间
O(n log n)：中等，线性对数时间
O(n²)：慢，平方时间
O(2^n)：非常慢，指数时间
O(n!)：最慢，阶乘时间

空间复杂度

O(1)：常数空间，不使用额外空间
O(n)：线性空间，使用与输入大小成正比的空间
O(n²)：平方空间，使用二维数组

数组和链表

数组

// 数组操作
const arr = [1, 2, 3, 4, 5];

// 访问：O(1)
console.log(arr[0]);

// 搜索：O(n)
arr.indexOf(3);

// 插入：O(n)
arr.splice(2, 0, 2.5);

// 删除：O(n)
arr.splice(2, 1);

// 数组的优点：快速随机访问
// 数组的缺点：插入和删除慢

链表

// 链表节点
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

// 链表
class LinkedList {
    constructor() {
        this.head = null;
    }
    
    // 插入：O(1)
    insertAtHead(value) {
        const node = new Node(value);
        node.next = this.head;
        this.head = node;
    }
    
    // 搜索：O(n)
    search(value) {
        let current = this.head;
        while (current) {
            if (current.value === value) return true;
            current = current.next;
        }
        return false;
    }
    
    // 删除：O(n)
    delete(value) {
        if (!this.head) return;
        if (this.head.value === value) {
            this.head = this.head.next;
            return;
        }
        let current = this.head;
        while (current.next) {
            if (current.next.value === value) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }
}

// 链表的优点：快速插入和删除
// 链表的缺点：随机访问慢

栈和队列

栈（LIFO）

// 栈实现
class Stack {
    constructor() {
        this.items = [];
    }
    
    push(element) {
        this.items.push(element);
    }
    
    pop() {
        return this.items.pop();
    }
    
    peek() {
        return this.items[this.items.length - 1];
    }
    
    isEmpty() {
        return this.items.length === 0;
    }
}

// 应用：括号匹配、表达式求值、回溯
function isValidParentheses(s) {
    const stack = new Stack();
    const pairs = { ')': '(', '}': '{', ']': '[' };
    
    for (const char of s) {
        if (char === '(' || char === '{' || char === '[') {
            stack.push(char);
        } else {
            if (stack.isEmpty() || stack.pop() !== pairs[char]) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

队列（FIFO）

// 队列实现
class Queue {
    constructor() {
        this.items = [];
    }
    
    enqueue(element) {
        this.items.push(element);
    }
    
    dequeue() {
        return this.items.shift();
    }
    
    front() {
        return this.items[0];
    }
    
    isEmpty() {
        return this.items.length === 0;
    }
}

// 应用：BFS、任务队列、消息队列
function bfs(graph, start) {
    const visited = new Set();
    const queue = new Queue();
    
    queue.enqueue(start);
    visited.add(start);
    
    while (!queue.isEmpty()) {
        const node = queue.dequeue();
        console.log(node);
        
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                queue.enqueue(neighbor);
                visited.add(neighbor);
            }
        }
    }
}

树和二叉树

二叉树节点

// 二叉树节点
class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// 二叉搜索树
class BST {
    constructor() {
        this.root = null;
    }
    
    insert(value) {
        const node = new TreeNode(value);
        if (!this.root) {
            this.root = node;
            return;
        }
        
        let current = this.root;
        while (true) {
            if (value < current.value) {
                if (!current.left) {
                    current.left = node;
                    return;
                }
                current = current.left;
            } else {
                if (!current.right) {
                    current.right = node;
                    return;
                }
                current = current.right;
            }
        }
    }
    
    search(value) {
        let current = this.root;
        while (current) {
            if (value === current.value) return true;
            if (value < current.value) current = current.left;
            else current = current.right;
        }
        return false;
    }
}

树的遍历

// 前序遍历（根-左-右）
function preorder(node) {
    if (!node) return;
    console.log(node.value);
    preorder(node.left);
    preorder(node.right);
}

// 中序遍历（左-根-右）
function inorder(node) {
    if (!node) return;
    inorder(node.left);
    console.log(node.value);
    inorder(node.right);
}

// 后序遍历（左-右-根）
function postorder(node) {
    if (!node) return;
    postorder(node.left);
    postorder(node.right);
    console.log(node.value);
}

// 层序遍历（BFS）
function levelOrder(root) {
    if (!root) return;
    const queue = [root];
    while (queue.length) {
        const node = queue.shift();
        console.log(node.value);
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
}

图

图的表示

// 邻接表表示
const graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C', 'E'],
    'E': ['D']
};

// 邻接矩阵表示
const matrix = [
    [0, 1, 1, 0, 0],
    [1, 0, 0, 1, 0],
    [1, 0, 0, 1, 0],
    [0, 1, 1, 0, 1],
    [0, 0, 0, 1, 0]
];

// DFS（深度优先搜索）
function dfs(graph, node, visited = new Set()) {
    visited.add(node);
    console.log(node);
    
    for (const neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    }
}

// BFS（广度优先搜索）
function bfs(graph, start) {
    const visited = new Set([start]);
    const queue = [start];
    
    while (queue.length) {
        const node = queue.shift();
        console.log(node);
        
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}

排序算法

冒泡排序 - O(n²)

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

快速排序 - O(n log n)

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    
    const pivot = arr[0];
    const left = arr.slice(1).filter(x => x < pivot);
    const right = arr.slice(1).filter(x => x >= pivot);
    
    return [...quickSort(left), pivot, ...quickSort(right)];
}

归并排序 - O(n log n)

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    
    return merge(left, right);
}

function merge(left, right) {
    const result = [];
    let i = 0, j = 0;
    
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
    
    return result.concat(left.slice(i), right.slice(j));
}

排序算法对比

冒泡排序：O(n²)，简单，不稳定
选择排序：O(n²)，简单，不稳定
插入排序：O(n²)，简单，稳定
快速排序：O(n log n)，快速，不稳定
归并排序：O(n log n)，稳定，需要额外空间
堆排序：O(n log n)，原地排序，不稳定

搜索算法

线性搜索 - O(n)

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

二分搜索 - O(log n)

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

深度优先搜索（DFS）

function dfs(node, target, visited = new Set()) {
    if (node === target) return true;
    visited.add(node);
    
    for (const neighbor of node.neighbors) {
        if (!visited.has(neighbor)) {
            if (dfs(neighbor, target, visited)) return true;
        }
    }
    return false;
}

广度优先搜索（BFS）

function bfs(start, target) {
    const visited = new Set([start]);
    const queue = [start];
    
    while (queue.length) {
        const node = queue.shift();
        if (node === target) return true;
        
        for (const neighbor of node.neighbors) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return false;
}

动态规划

斐波那契数列

// 递归（低效）- O(2^n)
function fib(n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

// 动态规划（高效）- O(n)
function fibDP(n) {
    if (n <= 1) return n;
    const dp = [0, 1];
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// 空间优化 - O(1)
function fibOptimized(n) {
    if (n <= 1) return n;
    let prev = 0, curr = 1;
    for (let i = 2; i <= n; i++) {
        [prev, curr] = [curr, prev + curr];
    }
    return curr;
}

背包问题

// 0/1背包问题
function knapsack(weights, values, capacity) {
    const n = weights.length;
    const dp = Array(capacity + 1).fill(0);
    
    for (let i = 0; i < n; i++) {
        for (let w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

动态规划步骤

定义状态：dp[i]表示什么
状态转移方程：如何从前面的状态推导
初始化：dp[0]的值
填表：按顺序计算所有状态
返回答案：dp[n]

实战项目：LeetCode题目

必做题目

数组：两数之和、最长子数组、合并区间
链表：反转链表、合并链表、检测环
树：二叉树遍历、最近公共祖先、路径和
图：岛屿数量、拓扑排序、最短路径
动态规划：爬楼梯、打家劫舍、最长递增子序列

学习建议

先理解原理，再写代码
多做题，找规律
分析时间和空间复杂度
学习多种解法
定期复习

✨ 实战总结：

数据结构和算法需要大量练习。坚持每天做题，逐步提升。

🎉 数据结构和算法学习完成

现在你已经掌握了编程的基础知识。

✅ 你现在可以：

✓ 分析时间和空间复杂度
✓ 使用常见数据结构
✓ 实现经典排序和搜索算法
✓ 解决动态规划问题
✓ 优化代码性能

🚀 下一步学习

在LeetCode上刷题
学习高级数据结构（红黑树、B树）
学习图算法（最短路径、最小生成树）
学习贪心算法和分治算法

💡 建议：

算法是编程的灵魂。投入时间学习，会终身受益。

📊 数据结构和算法完全教程

📚 完整教程目录

前言：为什么需要学习

🤔 数据结构和算法的重要性

学习的收益

学习路线

复杂度分析

时间复杂度

复杂度对比

空间复杂度

数组和链表

数组

链表

栈和队列

栈（LIFO）

队列（FIFO）

树和二叉树

二叉树节点

树的遍历

图

图的表示

排序算法

冒泡排序 - O(n²)

快速排序 - O(n log n)

归并排序 - O(n log n)

排序算法对比

搜索算法

线性搜索 - O(n)

二分搜索 - O(log n)

深度优先搜索（DFS）

广度优先搜索（BFS）

动态规划

斐波那契数列

背包问题

动态规划步骤

实战项目：LeetCode题目

必做题目

学习建议

🎉 数据结构和算法学习完成

✅ 你现在可以：

🚀 下一步学习