跳转至

算法与数据结构

基础概念

什么是算法？

算法是解决特定问题的一系列明确指令，具有以下特征：
- 有穷性 - 算法必须在有限步骤内结束
- 确定性 - 每一步都有确定的含义
- 可行性 - 每一步都可以执行
- 输入 - 有零个或多个输入
- 输出 - 有一个或多个输出

什么是数据结构？

数据结构是计算机存储、组织数据的方式，影响算法的效率。

时间复杂度和空间复杂度

大O表示法

  • O(1) - 常数时间
  • O(log n) - 对数时间
  • O(n) - 线性时间
  • O(n log n) - 线性对数时间
  • O(n²) - 平方时间
  • O(2^n) - 指数时间

复杂度分析示例

// O(1) - 常数时间
int getFirst(vector<int>& arr) {
    return arr[0];
}

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

// O(n²) - 平方时间
void bubbleSort(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        for (int j = 0; j < arr.size() - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

基本数据结构

数组 (Array)

// 静态数组
int arr[10];
arr[0] = 1;

// 动态数组 (C++)
vector<int> dynamicArr;
dynamicArr.push_back(1);
dynamicArr.push_back(2);

// 遍历数组
for (int i = 0; i < dynamicArr.size(); i++) {
    cout << dynamicArr[i] << " ";
}

链表 (Linked List)

// 单链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 单链表操作
class LinkedList {
private:
    ListNode* head;

public:
    LinkedList() : head(nullptr) {}

    // 插入节点
    void insert(int val) {
        ListNode* newNode = new ListNode(val);
        newNode->next = head;
        head = newNode;
    }

    // 删除节点
    void deleteNode(int val) {
        if (!head) return;

        if (head->val == val) {
            ListNode* temp = head;
            head = head->next;
            delete temp;
            return;
        }

        ListNode* current = head;
        while (current->next && current->next->val != val) {
            current = current->next;
        }

        if (current->next) {
            ListNode* temp = current->next;
            current->next = current->next->next;
            delete temp;
        }
    }

    // 查找节点
    bool search(int val) {
        ListNode* current = head;
        while (current) {
            if (current->val == val) {
                return true;
            }
            current = current->next;
        }
        return false;
    }

    // 打印链表
    void print() {
        ListNode* current = head;
        while (current) {
            cout << current->val << " ";
            current = current->next;
        }
        cout << endl;
    }
};

栈 (Stack)

// 使用数组实现栈
class Stack {
private:
    vector<int> data;

public:
    // 入栈
    void push(int val) {
        data.push_back(val);
    }

    // 出栈
    int pop() {
        if (empty()) {
            throw runtime_error("Stack is empty");
        }
        int val = data.back();
        data.pop_back();
        return val;
    }

    // 获取栈顶元素
    int top() {
        if (empty()) {
            throw runtime_error("Stack is empty");
        }
        return data.back();
    }

    // 判断是否为空
    bool empty() {
        return data.empty();
    }

    // 获取大小
    int size() {
        return data.size();
    }
};

// 栈的应用 - 括号匹配
bool isValidParentheses(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return st.empty();
}

队列 (Queue)

// 使用数组实现队列
class Queue {
private:
    vector<int> data;
    int front;
    int rear;

public:
    Queue() : front(0), rear(0) {}

    // 入队
    void enqueue(int val) {
        data.push_back(val);
        rear++;
    }

    // 出队
    int dequeue() {
        if (empty()) {
            throw runtime_error("Queue is empty");
        }
        int val = data[front];
        front++;
        return val;
    }

    // 获取队首元素
    int getFront() {
        if (empty()) {
            throw runtime_error("Queue is empty");
        }
        return data[front];
    }

    // 判断是否为空
    bool empty() {
        return front == rear;
    }

    // 获取大小
    int size() {
        return rear - front;
    }
};

树结构

二叉树

// 二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 二叉树遍历
class BinaryTree {
public:
    // 前序遍历 (根-左-右)
    void preorder(TreeNode* root) {
        if (!root) return;
        cout << root->val << " ";
        preorder(root->left);
        preorder(root->right);
    }

    // 中序遍历 (左-根-右)
    void inorder(TreeNode* root) {
        if (!root) return;
        inorder(root->left);
        cout << root->val << " ";
        inorder(root->right);
    }

    // 后序遍历 (左-右-根)
    void postorder(TreeNode* root) {
        if (!root) return;
        postorder(root->left);
        postorder(root->right);
        cout << root->val << " ";
    }

    // 层序遍历
    void levelorder(TreeNode* root) {
        if (!root) return;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            cout << node->val << " ";

            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }

    // 计算树的高度
    int height(TreeNode* root) {
        if (!root) return 0;
        return 1 + max(height(root->left), height(root->right));
    }
};

二叉搜索树

class BST {
private:
    TreeNode* root;

    TreeNode* insert(TreeNode* node, int val) {
        if (!node) return new TreeNode(val);

        if (val < node->val) {
            node->left = insert(node->left, val);
        } else if (val > node->val) {
            node->right = insert(node->right, val);
        }

        return node;
    }

    TreeNode* search(TreeNode* node, int val) {
        if (!node || node->val == val) return node;

        if (val < node->val) {
            return search(node->left, val);
        } else {
            return search(node->right, val);
        }
    }

    TreeNode* findMin(TreeNode* node) {
        while (node->left) {
            node = node->left;
        }
        return node;
    }

    TreeNode* deleteNode(TreeNode* node, int val) {
        if (!node) return node;

        if (val < node->val) {
            node->left = deleteNode(node->left, val);
        } else if (val > node->val) {
            node->right = deleteNode(node->right, val);
        } else {
            // 节点有一个子节点或没有子节点
            if (!node->left) {
                TreeNode* temp = node->right;
                delete node;
                return temp;
            } else if (!node->right) {
                TreeNode* temp = node->left;
                delete node;
                return temp;
            }

            // 节点有两个子节点
            TreeNode* temp = findMin(node->right);
            node->val = temp->val;
            node->right = deleteNode(node->right, temp->val);
        }

        return node;
    }

public:
    BST() : root(nullptr) {}

    void insert(int val) {
        root = insert(root, val);
    }

    bool search(int val) {
        return search(root, val) != nullptr;
    }

    void remove(int val) {
        root = deleteNode(root, val);
    }
};

排序算法

冒泡排序

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}
// 时间复杂度: O(n²)
// 空间复杂度: O(1)

选择排序

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
    }
}
// 时间复杂度: O(n²)
// 空间复杂度: O(1)

插入排序

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
// 时间复杂度: O(n²)
// 空间复杂度: O(1)

快速排序

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
// 时间复杂度: 平均 O(n log n), 最坏 O(n²)
// 空间复杂度: O(log n)

归并排序

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    vector<int> leftArr(n1), rightArr(n2);

    for (int i = 0; i < n1; i++) {
        leftArr[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        rightArr[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}
// 时间复杂度: O(n log n)
// 空间复杂度: O(n)

查找算法

线性查找

int linearSearch(vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}
// 时间复杂度: O(n)

二分查找

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}
// 时间复杂度: O(log n)
// 前提: 数组必须是有序的

图算法

图的表示

// 邻接矩阵
class GraphMatrix {
private:
    vector<vector<int>> adj;
    int vertices;

public:
    GraphMatrix(int v) : vertices(v) {
        adj.resize(v, vector<int>(v, 0));
    }

    void addEdge(int u, int v) {
        adj[u][v] = 1;
        adj[v][u] = 1;  // 无向图
    }

    void printGraph() {
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
                cout << adj[i][j] << " ";
            }
            cout << endl;
        }
    }
};

// 邻接表
class GraphList {
private:
    vector<vector<int>> adj;
    int vertices;

public:
    GraphList(int v) : vertices(v) {
        adj.resize(v);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);  // 无向图
    }

    void printGraph() {
        for (int i = 0; i < vertices; i++) {
            cout << i << ": ";
            for (int neighbor : adj[i]) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
};

深度优先搜索 (DFS)

void dfs(vector<vector<int>>& adj, int start, vector<bool>& visited) {
    visited[start] = true;
    cout << start << " ";

    for (int neighbor : adj[start]) {
        if (!visited[neighbor]) {
            dfs(adj, neighbor, visited);
        }
    }
}

广度优先搜索 (BFS)

void bfs(vector<vector<int>>& adj, int start) {
    vector<bool> visited(adj.size(), false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        cout << current << " ";

        for (int neighbor : adj[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

动态规划

斐波那契数列

// 递归版本 (效率低)
int fibRecursive(int n) {
    if (n <= 1) return n;
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}

// 动态规划版本
int fibDP(int n) {
    if (n <= 1) return n;

    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

// 空间优化版本
int fibOptimized(int n) {
    if (n <= 1) return n;

    int prev2 = 0, prev1 = 1, current;

    for (int i = 2; i <= n; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return current;
}

背包问题

// 0-1背包问题
int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = max(
                    dp[i - 1][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][capacity];
}

实际应用

游戏开发中的应用

  • A* 寻路算法 - 游戏AI路径规划
  • 四叉树/八叉树 - 空间分割和碰撞检测
  • 状态机 - 游戏状态管理
  • 图算法 - 关卡设计和社交网络

性能优化

  • 缓存友好 - 数据局部性原理
  • 并行算法 - 多线程优化
  • 内存管理 - 对象池和内存对齐

学习资源

在线平台

推荐书籍

  • 《算法导论》- 经典教材
  • 《数据结构与算法分析》- 实用指南
  • 《编程珠玑》- 编程技巧

可视化工具

实践项目

项目建议

  1. 实现基础数据结构 - 手写链表、栈、队列
  2. 排序算法比较 - 性能测试和分析
  3. 图算法应用 - 社交网络分析
  4. 动态规划问题 - 解决实际优化问题

想要更多练习？参与我们的 项目开发 或查看 编程基础