19、数据结构与算法基础

厨子大约 8 分钟C++C++基础编程程序厨

数据结构与算法是编程的核心内容，我们一定要掌握，本文主要介绍常见的数据结构与算法。

线性表

概念

线性表是一种逻辑结构，它可以通过顺序存储（顺序表）或链式存储（链表）来实现。

顺序表

顺序表是通过数组实现的线性表，元素在内存中连续存储。

代码示例：

#include <iostream>
#include <stdexcept> // 用于异常处理

class SeqList {
private:
    int* data; // 存储数据的数组
    int size; // 当前元素个数
    int capacity; // 数组容量

public:
    SeqList(int cap = 10) : capacity(cap), size(0) {
        data = new int[capacity];
    }

    ~SeqList() {
        delete[] data;
    }

    // 插入元素
    void insert(int index, int value) {
        if (index < 0 || index > size) {
            throw std::out_of_range("Index out of range");
        }
        if (size == capacity) {
            resize();
        }
        for (int i = size; i > index; --i) {
            data[i] = data[i - 1];
        }
        data[index] = value;
        ++size;
    }

    // 删除元素
    void remove(int index) {
        if (index < 0 || index >= size) {
            throw std::out_of_range("Index out of range");
        }
        for (int i = index; i < size - 1; ++i) {
            data[i] = data[i + 1];
        }
        --size;
    }

    // 获取元素
    int get(int index) {
        if (index < 0 || index >= size) {
            throw std::out_of_range("Index out of range");
        }
        return data[index];
    }

    // 打印顺序表
    void print() {
        for (int i = 0; i < size; ++i) {
            std::cout << data[i] << " ";
        }
        std::cout << std::endl;
    }

private:
    // 扩容
    void resize() {
        capacity *= 2;
        int* newData = new int[capacity];
        for (int i = 0; i < size; ++i) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
    }
};

int main() {
    SeqList list;
    list.insert(0, 1);
    list.insert(1, 2);
    list.insert(2, 3);
    list.print(); // 输出：1 2 3

    list.remove(1);
    list.print(); // 输出：1 3

    return 0;
}

链表

链表是通过指针实现的线性表，元素在内存中不连续存储。

代码示例

#include <iostream>
#include <stdexcept> // 用于异常处理

struct Node {
    int value;
    Node* next;
    Node(int val) : value(val), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;

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

    ~LinkedList() {
        Node* current = head;
        while (current) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }

    // 插入元素
    void insert(int index, int value) {
        if (index < 0) {
            throw std::out_of_range("Index out of range");
        }
        Node* newNode = new Node(value);
        if (index == 0) {
            newNode->next = head;
            head = newNode;
        } else {
            Node* current = head;
            for (int i = 0; i < index - 1; ++i) {
                if (!current) {
                    throw std::out_of_range("Index out of range");
                }
                current = current->next;
            }
            newNode->next = current->next;
            current->next = newNode;
        }
    }

    // 删除元素
    void remove(int index) {
        if (index < 0 || !head) {
            throw std::out_of_range("Index out of range");
        }
        if (index == 0) {
            Node* temp = head;
            head = head->next;
            delete temp;
        } else {
            Node* current = head;
            for (int i = 0; i < index - 1; ++i) {
                if (!current->next) {
                    throw std::out_of_range("Index out of range");
                }
                current = current->next;
            }
            Node* temp = current->next;
            current->next = temp->next;
            delete temp;
        }
    }

    // 获取元素
    int get(int index) {
        if (index < 0 || !head) {
            throw std::out_of_range("Index out of range");
        }
        Node* current = head;
        for (int i = 0; i < index; ++i) {
            if (!current->next) {
                throw std::out_of_range("Index out of range");
            }
            current = current->next;
        }
        return current->value;
    }

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

int main() {
    LinkedList list;
    list.insert(0, 1);
    list.insert(1, 2);
    list.insert(2, 3);
    list.print(); // 输出：1 2 3

    list.remove(1);
    list.print(); // 输出：1 3

    return 0;
}

栈与队列

栈

栈是一种后进先出（LIFO）的数据结构，支持入栈和出栈操作。

代码示例

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);

    while (!s.empty()) {
        std::cout << s.top() << " "; // 输出：3 2 1
        s.pop();
    }
    std::cout << std::endl;

    return 0;
}

队列

队列是一种先进先出（FIFO）的数据结构，支持入队和出队操作。

代码示例

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);

    while (!q.empty()) {
        std::cout << q.front() << " "; // 输出：1 2 3
        q.pop();
    }
    std::cout << std::endl;

    return 0;
}

递归算法与分治策略

递归算法

递归是指函数直接或间接调用自身。它通常用于解决分治问题。

代码示例：计算阶乘

#include <iostream>

int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main() {
    std::cout << "Factorial of 5: " << factorial(5) << std::endl; // 输出：120
    return 0;
}

分治策略

分治策略的主要思想就是将问题分解为若干子问题，分别解决后再合并结果。

代码示例：归并排序

#include <iostream>
#include <vector>

void merge(std::vector<int>& arr, int left, int mid, int right) {
    std::vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    for (i = left, k = 0; i <= right; ++i, ++k) {
        arr[i] = temp[k];
    }
}

void mergeSort(std::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);
    }
}

int main() {
    std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(arr, 0, arr.size() - 1);

    for (int num : arr) {
        std::cout << num << " "; // 输出：3 9 10 27 38 43 82
    }
    std::cout << std::endl;

    return 0;
}

树与二叉树

树的定义

树是一种非线性数据结构，它由节点（Node）和边（Edge）组成，具有以下特点：

  • 每个节点有零个或多个子节点。
  • 没有父节点的节点称为根节点（Root）。
  • 没有子节点的节点称为叶子节点（Leaf）。
  • 除了根节点外，每个节点有且仅有一个父节点。

二叉树

二叉树是树的一种特殊形式，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树的性质

  • 深度：从根节点到某个节点的路径长度。
  • 高度：树中节点的最大深度。
  • 满二叉树：每个节点都有两个子节点，且所有叶子节点都在同一层。
  • 完全二叉树：除了最后一层，其他层都是满的，且最后一层的节点从左到右连续排列。

二叉树的遍历与搜索

二叉树的遍历

二叉树的遍历是指按照某种顺序访问树中的所有节点。常见的遍历方式有：

  • 前序遍历：根节点 -> 左子树 -> 右子树。
  • 中序遍历：左子树 -> 根节点 -> 右子树。
  • 后序遍历：左子树 -> 右子树 -> 根节点。
  • 层序遍历：按层次从上到下、从左到右访问节点。

代码示例：二叉树的定义与遍历

#include <iostream>
#include <queue>

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

// 前序遍历
void preOrder(TreeNode* root) {
    if (root == nullptr) return;
    std::cout << root->value << " ";
    preOrder(root->left);
    preOrder(root->right);
}

// 中序遍历
void inOrder(TreeNode* root) {
    if (root == nullptr) return;
    inOrder(root->left);
    std::cout << root->value << " ";
    inOrder(root->right);
}

// 后序遍历
void postOrder(TreeNode* root) {
    if (root == nullptr) return;
    postOrder(root->left);
    postOrder(root->right);
    std::cout << root->value << " ";
}

// 层序遍历
void levelOrder(TreeNode* root) {
    if (root == nullptr) return;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        std::cout << node->value << " ";
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    std::cout << "PreOrder: ";
    preOrder(root); // 输出：1 2 4 5 3 6 7
    std::cout << std::endl;

    std::cout << "InOrder: ";
    inOrder(root); // 输出：4 2 5 1 6 3 7
    std::cout << std::endl;

    std::cout << "PostOrder: ";
    postOrder(root); // 输出：4 5 2 6 7 3 1
    std::cout << std::endl;

    std::cout << "LevelOrder: ";
    levelOrder(root); // 输出：1 2 3 4 5 6 7
    std::cout << std::endl;

    return 0;
}

二叉搜索树（BST）

二叉搜索树是一种特殊的二叉树，满足以下性质：

  • 左子树的所有节点值小于根节点值。
  • 右子树的所有节点值大于根节点值。
  • 左右子树也分别是二叉搜索树。

代码示例：二叉搜索树的插入与搜索

#include <iostream>

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

// 插入节点
TreeNode* insert(TreeNode* root, int value) {
    if (root == nullptr) {
        return new TreeNode(value);
    }
    if (value < root->value) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }
    return root;
}

// 搜索节点
bool search(TreeNode* root, int value) {
    if (root == nullptr) return false;
    if (root->value == value) return true;
    if (value < root->value) {
        return search(root->left, value);
    } else {
        return search(root->right, value);
    }
}

int main() {
    TreeNode* root = nullptr;
    root = insert(root, 5);
    insert(root, 3);
    insert(root, 7);
    insert(root, 2);
    insert(root, 4);
    insert(root, 6);
    insert(root, 8);

    std::cout << "Search 4: " << (search(root, 4) ? "Found" : "Not Found") << std::endl; // 输出：Found
    std::cout << "Search 9: " << (search(root, 9) ? "Found" : "Not Found") << std::endl; // 输出：Not Found

    return 0;
}

图

图的定义

图是由顶点（Vertex）和边（Edge）组成的一种数据结构，用于表示多对多的关系。图可以分为有向图和无向图。

图的表示方法

常见的图的表示方法有：

  • 邻接矩阵：用二维数组表示顶点之间的连接关系。
  • 邻接表：用链表或数组表示每个顶点的邻接顶点。

代码示例：邻接矩阵表示图

#include <iostream>
#include <vector>

class Graph {
private:
    int numVertices;
    std::vector<std::vector<int>> adjMatrix;

public:
    Graph(int n) : numVertices(n), adjMatrix(n, std::vector<int>(n, 0)) {}

    // 添加边
    void addEdge(int src, int dest) {
        adjMatrix[src][dest] = 1;
        adjMatrix[dest][src] = 1; // 无向图需要双向设置
    }

    // 打印图
    void print() {
        for (int i = 0; i < numVertices; ++i) {
            for (int j = 0; j < numVertices; ++j) {
                std::cout << adjMatrix[i][j] << " ";
            }
            std::cout << std::endl;
        }
    }
};

int main() {
    Graph graph(4);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);

    graph.print();
    // 输出：
    // 0 1 1 0
    // 1 0 1 0
    // 1 1 0 1
    // 0 0 1 0

    return 0;
}

代码示例：邻接表表示图

#include <iostream>
#include <vector>
#include <list>

class Graph {
private:
    int numVertices;
    std::vector<std::list<int>> adjList;

public:
    Graph(int n) : numVertices(n), adjList(n) {}

    // 添加边
    void addEdge(int src, int dest) {
        adjList[src].push_back(dest);
        adjList[dest].push_back(src); // 无向图需要双向设置
    }

    // 打印图
    void print() {
        for (int i = 0; i < numVertices; ++i) {
            std::cout << "Vertex " << i << ": ";
            for (int neighbor : adjList[i]) {
                std::cout << neighbor << " ";
            }
            std::cout << std::endl;
        }
    }
};

int main() {
    Graph graph(4);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);

    graph.print();
    // 输出：
    // Vertex 0: 1 2
    // Vertex 1: 0 2
    // Vertex 2: 0 1 3
    // Vertex 3: 2

    return 0;
}

练习

  1. 实现一个双向链表，并支持插入、删除和查找操作。
  2. 使用栈实现一个简单的表达式求值程序。
  3. 使用递归算法实现汉诺塔问题的求解。
  4. 使用分治策略实现快速排序算法。
  5. 实现一个二叉树，并编写函数计算其高度。
  6. 实现一个二叉搜索树，并编写函数删除指定节点。
  7. 使用邻接表表示图，并实现深度优先搜索（DFS）算法。
  8. 使用邻接矩阵表示图，并实现广度优先搜索（BFS）算法。