【C++ 数据结构与算法一站式备考指南】一文掌握数据结构与算法课程知识点（一）-阿里云开发者社区

前言

1. 背景：为什么数据结构和算法在C++课程中重要

数据结构和算法（Data Structures and Algorithms）是计算机科学和编程中的核心概念，它们不仅是C++课程的重要组成部分，而且对于软件开发和计算机科学的其他领域也有着至关重要的作用。在C++中，熟练掌握数据结构和算法能让你编写出更高效、更可靠、更易维护的代码。这也是为什么许多大学和在线课程将其作为核心课程来教授。

数据结构提供了一种组织和存储数据的方法，而算法则定义了如何有效地操作这些数据。理解这两者之间的关系，并能在实际编程中灵活运用，是每一位C++程序员必须掌握的基础技能。

2. 博客目标：备考重点与学习方法

这篇博客的主要目标是为即将参加C++课程考试的学生提供一个全面、深入的学习指南。我们将按照考试大纲的主要内容来组织材料，包括线性表（Linear Lists）、栈和队列（Stacks and Queues）、二叉树（Binary Trees）、图（Graphs）、数据查找（Data Search）以及排序（Sorting）等。

为了确保你能全面理解和掌握这些主题，我们不仅会介绍相关的理论知识，还会提供大量的实例代码和练习题。这些代码和练习题将使用C++编程语言来实现，因此，除了帮助你理解数据结构和算法的基本概念外，还可以提高你的C++编程能力。

3. 预览：本文将覆盖的主要主题

以下是本博客将深入探讨的主题：

线性表操作：我们将讨论顺序表（Sequential Lists）和单链表（Singly Linked Lists），以及如何进行初始化、查找、插入和删除等基本操作。
栈和队列基本操作：通过一些简单的应用问题，比如进制转换和字符串输入，我们将展示如何使用栈（Stack）和队列（Queue）。
二叉树操作：使用二叉链表（Binary Linked Lists）作为存储结构，我们将介绍如何建立二叉树、进行先序、中序和后序以及按层次遍历，并求出所有叶子和节点个数。
图的遍历操作：我们将使用邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）作为存储结构，完成有向图（Directed Graphs）和无向图（Undirected Graphs）的深度优先搜索（DFS）和广度优先搜索（BFS）。
数据查找：本部分将介绍顺序查找（Sequential Search）、折半查找（Binary Search）和二叉排序查找（Binary Sort Search）算法，并比较它们的查找速度。
排序：我们将实现并比较多种排序算法，包括直接插入排序（Insertion Sort）、冒泡排序（Bubble Sort）、直接选择排序（Selection Sort）、快速排序（Quick Sort）、堆排序（Heap Sort）和归并排序（Merge Sort）。

通过这些主题的详细讲解和实例，你将能够全面掌握C++中的数据结构和算法，为即将到来的考试做好充分的准备。希望这篇博客能为你的学习之旅提供有力的支持！

第一部分：线性表操作

1.1 顺序表（Sequential Lists）

顺序表是一种最基础的数据结构，在C++中，它通常可以通过数组（Array）或动态数组（Dynamic Array，例如STL中的std::vector）来实现。顺序表具有连续的内存空间和高效的随机访问特性，但插入和删除操作可能会涉及数据的移动。接下来，我们将详细讨论顺序表的几个基本操作。

1.1.1 初始化

初始化一个顺序表是非常直接的。如果你使用数组，你需要在编译时确定数组的大小。而如果你使用std::vector，你可以在运行时动态地改变其大小。

使用数组初始化

int arr[10]; // 初始化一个大小为10的整数数组

使用std::vector初始化

#include <vector>
std::vector<int> vec;  // 初始化一个空的整数动态数组
std::vector<int> vec(10);  // 初始化一个大小为10的整数动态数组

1.1.2 查找

在顺序表中查找一个元素通常是非常快速的，时间复杂度为 (O(1))。你只需要知道元素的索引（Index）即可直接访问。

示例代码

int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int element = arr[5];  // 直接通过索引查找，element现在是6
std::vector<int> vec = {1, 2, 3, 4, 5};
int another_element = vec[2];  // another_element现在是3

1.1.3 插入

插入元素可能是一个相对缓慢的操作，因为你可能需要移动多个元素来为新元素腾出空间。时间复杂度可能达到 (O(n))。

在数组中插入元素

在数组中插入元素通常不是一个好主意，因为数组的大小是固定的。但是，如果你有一个足够大的数组，并且知道最大可能的元素数量，你可以通过手动移动元素来实现。

在std::vector中插入元素

使用std::vector插入元素更为方便，你可以使用push_back或insert方法。

std::vector<int> vec = {1, 2, 3};
vec.push_back(4);  // 在尾部插入元素，现在vector为 {1, 2, 3, 4}
vec.insert(vec.begin() + 1, 0);  // 在索引1的位置插入元素0，现在vector为 {1, 0, 2, 3, 4}

1.1.4 删除

和插入操作类似，删除操作也可能需要移动元素，时间复杂度也可能达到 (O(n))。

在数组中删除元素

与插入类似，删除数组中的元素也是不容易的，因为你需要手动移动其他元素来填补空位。

在std::vector中删除元素

使用std::vector则相对简单，你可以使用erase或pop_back方法。

std::vector<int> vec = {1, 0, 2, 3, 4};
vec.erase(vec.begin() + 1);  // 删除索引1处的元素，现在vector为 {1, 2, 3, 4}
vec.pop_back();  // 删除最后一个元素，现在vector为 {1, 2, 3}

1.1.5 示例代码与注意事项

示例代码

在这一部分，我们将通过一个完整的C++代码示例来展示如何进行顺序表（即数组和std::vector）的初始化、查找、插入和删除操作。

使用数组

#include <iostream>
int main() {
    int arr[5] = {1, 2, 3, 4, 5};  // 初始化
    // 查找
    int element_to_find = 4;
    for (int i = 0; i < 5; ++i) {
        if (arr[i] == element_to_find) {
            std::cout << "Element found at index: " << i << std::endl;
            break;
        }
    }
    // 插入（在索引2插入元素6）
    for (int i = 4; i >= 2; --i) {
        arr[i] = arr[i - 1];
    }
    arr[2] = 6;
    // 删除（删除索引1的元素）
    for (int i = 1; i < 4; ++i) {
        arr[i] = arr[i + 1];
    }
    // 输出数组
    for (int i = 0; i < 5; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

使用std::vector

#include <iostream>
#include <vector>
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};  // 初始化
    // 查找
    int element_to_find = 4;
    for (size_t i = 0; i < vec.size(); ++i) {
        if (vec[i] == element_to_find) {
            std::cout << "Element found at index: " << i << std::endl;
            break;
        }
    }
    // 插入（在索引2插入元素6）
    vec.insert(vec.begin() + 2, 6);
    // 删除（删除索引1的元素）
    vec.erase(vec.begin() + 1);
    // 输出vector
    for (auto elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    return 0;
}

注意事项

数组大小和索引有效性：当使用数组时，需要特别注意数组的大小和索引的有效性。访问超出数组范围的索引会导致未定义行为（Undefined Behavior）。
动态内存和std::vector：与数组不同，std::vector能动态地改变其大小。但这并不意味着你可以无视内存限制，动态数组过大仍然可能导致内存不足（Out of Memory）。
时间复杂度：在进行插入或删除操作时，理解其时间复杂度（Time Complexity）是非常重要的。对于数组和std::vector，这些操作的时间复杂度通常是(O(n))，因为可能需要移动多个元素。
C++ STL的使用：在实际应用中，尽量使用C++标准库（STL）提供的数据结构和算法，如std::vector，除非有特殊需求。这不仅可以简化代码，还能提高程序的可维护性和效率。

掌握了这些基本操作和注意事项，你就可以更加自信地使用C++来操作顺序表了。这些基础知识将为你后续学习更复杂的数据结构和算法打下坚实的基础。

1.2 单链表（Singly Linked Lists）

单链表是另一种常用的线性数据结构，与顺序表不同，单链表的元素在内存中不需要是连续的。每个元素由一个数据节点和一个指向下一个元素的指针（Pointer）组成。因为单链表不需要连续的内存空间，所以在某些情况下插入和删除操作可能更为高效。下面我们将详细讨论单链表的几个基本操作。

1.2.1 初始化

初始化一个单链表通常涉及创建一个头节点（Head Node），这个节点通常不存储任何数据，而仅用作链表的起始点。

示例代码

struct Node {
    int data;
    Node* next;
};
Node* head = new Node();  // 创建一个空的头节点
head->next = nullptr;  // 初始化头节点的next指针为nullptr

1.2.2 查找

在单链表中查找一个元素通常需要从头节点开始，逐一检查每个节点的数据，直到找到所需的元素。因此，查找操作的时间复杂度为 (O(n))。

示例代码

Node* find(int value, Node* head) {
    Node* current = head->next;  // 从第一个数据节点开始
    while (current != nullptr) {
        if (current->data == value) {
            return current;  // 返回找到的节点
        }
        current = current->next;  // 移动到下一个节点
    }
    return nullptr;  // 如果没有找到，返回nullptr
}

1.2.3 插入

单链表的插入操作相对灵活，因为不需要移动多个元素。你只需要更改相邻节点的指针即可。插入操作的时间复杂度为 (O(1))，但这通常需要你已经知道了要插入位置的前一个节点。

示例代码

void insert(int value, Node* prevNode) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

1.2.4 删除

与插入操作类似，删除操作也是相对高效的。你只需要更改被删除节点的前一个节点的指针，然后释放（Free）被删除节点的内存。时间复杂度为 (O(1))，前提是你已经找到了要删除的节点。

示例代码

void deleteNode(Node* prevNode) {
    if (prevNode->next == nullptr) {
        return;  // 没有可删除的节点
    }
    Node* tempNode = prevNode->next;
    prevNode->next = tempNode->next;
    delete tempNode;  // 释放内存
}

这些基本操作构成了单链表这一数据结构的核心，熟练掌握这些操作对于理解和应用单链表是非常重要的。在下一节中，我们还将提供一些实用的示例代码和注意事项，以帮助你更加深入地理解单链表。

1.2.5 示例代码与注意事项

示例代码

在这一部分，我们将通过一个完整的C++代码示例来展示如何进行单链表的初始化、查找、插入和删除操作。

#include <iostream>
struct Node {
    int data;
    Node* next;
};
// 初始化单链表
Node* initialize() {
    Node* head = new Node();
    head->next = nullptr;
    return head;
}
// 查找元素
Node* find(int value, Node* head) {
    Node* current = head->next;
    while (current != nullptr) {
        if (current->data == value) {
            return current;
        }
        current = current->next;
    }
    return nullptr;
}
// 插入元素
void insert(int value, Node* prevNode) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}
// 删除元素
void deleteNode(Node* prevNode) {
    if (prevNode->next == nullptr) {
        return;
    }
    Node* tempNode = prevNode->next;
    prevNode->next = tempNode->next;
    delete tempNode;
}
// 打印链表
void printList(Node* head) {
    Node* current = head->next;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}
int main() {
    Node* head = initialize();
    insert(1, head);
    insert(2, head);
    insert(3, head);
    std::cout << "Original List: ";
    printList(head);
    Node* node = find(2, head);
    if (node != nullptr) {
        std::cout << "Element found: " << node->data << std::endl;
    } else {
        std::cout << "Element not found." << std::endl;
    }
    deleteNode(head);  // 删除头节点后的第一个元素
    std::cout << "List after deletion: ";
    printList(head);
    return 0;
}

注意事项

内存管理：在使用单链表时，尤其是在插入和删除节点时，必须注意正确地管理内存。忘记释放已删除节点的内存将导致内存泄漏（Memory Leak）。
空指针检查：在进行查找、插入和删除操作时，应始终检查指针是否为nullptr，以防止空指针解引用，这是一种常见的运行时错误。
头节点的使用：在这里，我们使用了一个不存储任何数据的头节点来简化链表操作。这样做使得插入和删除操作更加统一，因为你不需要单独处理在链表开头进行插入或删除的情况。
时间复杂度：虽然单链表的插入和删除操作通常具有较好的时间复杂度 (O(1))，但查找操作通常需要 (O(n)) 的时间。因此，在需要频繁查找操作的场景下，单链表可能不是最佳选择。

掌握了这些基本操作和注意事项，你就可以更加自信地使用C++来操作单链表了。这些基础知识将为你后续学习更复杂的数据结构和算法打下坚实的基础。

第二部分：栈和队列基本操作

2.1 栈 (Stack)

栈（Stack）是一种特殊的线性数据结构，只允许在一个端口进行插入和删除操作。这一端通常被称为“栈顶”（Top），而另一端则称为“栈底”（Bottom）。栈遵循先进后出（FILO，First-In-Last-Out）或后进先出（LIFO，Last-In-First-Out）的原则。栈在编程、算法设计以及计算机科学的其他方面都有广泛的应用。

2.1.1 进制转换

进制转换是栈在计算机科学中一个经典的应用场景。例如，将一个十进制数转换为二进制数。这可以通过不断地将十进制数除以2，并将余数压入栈中，最后再依次弹出栈来实现。

下面是一个C++的示例代码：

#include <iostream>
#include <stack>
using namespace std;
void decimalToBinary(int n) {
    stack<int> s;
    while (n > 0) {
        s.push(n % 2);
        n = n / 2;
    }
    while (!s.empty()) {
        cout << s.top();
        s.pop();
    }
    cout << endl;
}
int main() {
    int n = 10;
    cout << "The binary representation of " << n << " is: ";
    decimalToBinary(n);
    return 0;
}

在这个示例中，我们使用C++的STL（Standard Template Library，标准模板库）中的stack容器来实现栈。

2.1.2 字符串输入/解析

栈也经常用于解析和验证括号匹配问题，例如，检查一个包含(、)、{、}、[和]的字符串是否是“平衡的”。平衡的意思是每一个开放的括号都有一个相应的闭合括号，并且它们是正确嵌套的。

以下是一个使用栈来检查字符串是否平衡的C++代码示例：

#include <iostream>
#include <stack>
using namespace std;
bool isValid(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();
}
int main() {
    string s = "{[()]}";
    if (isValid(s)) {
        cout << "The string is balanced." << endl;
    } else {
        cout << "The string is not balanced." << endl;
    }
    return 0;
}

这里我们也使用了C++的STL中的stack容器。

2.1.3 示例代码与注意事项

2.1.3.1 栈的基本操作

首先，我们来看看如何使用C++的STL（Standard Template Library，标准模板库）来实现栈的基本操作：push（压入）、pop（弹出）和top（查看栈顶元素）。

#include <iostream>
#include <stack>
using namespace std;
int main() {
    stack<int> s;
    // Push elements into stack
    s.push(10);
    s.push(20);
    s.push(30);
    // Pop elements from stack
    s.pop();
    // Get the top element
    if (!s.empty()) {
        cout << "Top element: " << s.top() << endl;
    }
    return 0;
}

在这个示例中，我们首先创建了一个名为s的整数类型栈。然后，我们使用push函数将10、20和30压入栈中。接着，使用pop函数弹出一个元素（即30）。最后，我们使用top函数查看并打印栈顶元素，这里应该是20。

2.1.3.2 判断字符串是否为回文

栈也可以用于解决一些有趣的问题，比如判断一个字符串是否是回文（Palindrome）。回文是一种从前往后和从后往前读都一样的字符串。

#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool isPalindrome(string str) {
    stack<char> s;
    string reversedStr = "";
    // Push all characters of the string into stack
    for (char c : str) {
        s.push(c);
    }
    // Pop characters from stack to form the reversed string
    while (!s.empty()) {
        reversedStr += s.top();
        s.pop();
    }
    return str == reversedStr;
}
int main() {
    string str = "level";
    if (isPalindrome(str)) {
        cout << str << " is a palindrome." << endl;
    } else {
        cout << str << " is not a palindrome." << endl;
    }
    return 0;
}

在这个示例中，我们使用一个栈来存储输入字符串中的所有字符。然后，我们从栈中弹出这些字符以形成一个新的反转字符串。最后，我们比较原始字符串和反转字符串是否相同，以判断它是否是回文。

在使用栈进行编程时，一定要注意以下几点：

容量限制：某些类型的栈（例如数组实现的栈）可能有容量限制。
异常处理：当尝试从一个空栈中弹出元素或查看栈顶元素时，应该进行适当的异常处理。
复杂度分析：栈操作（push、pop、top）通常是O(1)复杂度，但是某些实现（例如链表实现的栈）可能有不同的性能特性。

2.2 队列 (Queue)

队列（Queue）是另一种基础的线性数据结构，与栈（Stack）相似，但操作限制不同。队列遵循先进先出（FIFO，First-In-First-Out）的原则，通常用于存储按顺序排列的元素，并在两端进行操作：一端添加元素（通常称为“队尾”或 Rear），另一端移除元素（通常称为“队首”或 Front）。

2.2.1 简单应用

队列经常用于实现需要按照先来先服务（First-Come-First-Serve）原则进行的各种算法和模拟。例如，操作系统中的任务调度、网络请求处理等。

2.2.1.1 任务调度模拟

假设我们有一个简单的任务调度器，它按照任务到达的顺序进行处理。下面是一个使用C++和STL中的queue实现的简单示例：

#include <iostream>
#include <queue>
#include <string>
using namespace std;
void taskScheduler(queue<string> &tasks) {
    while (!tasks.empty()) {
        cout << "Processing task: " << tasks.front() << endl;
        tasks.pop();
    }
}
int main() {
    queue<string> tasks;
    // Adding tasks to the queue
    tasks.push("Task 1");
    tasks.push("Task 2");
    tasks.push("Task 3");
    // Process tasks
    taskScheduler(tasks);
    return 0;
}

在这个示例中，我们创建了一个名为tasks的队列来存储任务。然后，我们使用push方法将三个任务添加到队列中。接着，我们调用taskScheduler函数来处理这些任务，它会按照任务到达的顺序（先进先出）进行处理。

2.2.1.2 数据流平均值计算

队列也可以用于解决流式数据的问题，例如计算一个滑动窗口内的数字平均值。以下是一个简单的C++示例：

#include <iostream>
#include <queue>
using namespace std;
double calculateAverage(queue<int> &data, int windowSize) {
    double sum = 0;
    if (data.size() < windowSize) return 0;
    queue<int> windowData;
    for (int i = 0; i < windowSize; ++i) {
        int value = data.front();
        sum += value;
        windowData.push(value);
        data.pop();
    }
    return sum / windowSize;
}
int main() {
    queue<int> data;
    data.push(1);
    data.push(2);
    data.push(3);
    data.push(4);
    data.push(5);
    int windowSize = 3;
    double average = calculateAverage(data, windowSize);
    cout << "The average of the last " << windowSize << " elements is: " << average << endl;
    return 0;
}

在这个示例中，我们用一个队列data来模拟流式数据，并用另一个队列windowData来存储滑动窗口内的数据。然后，我们计算这个窗口内数据的平均值。

2.2.2 示例代码与注意事项

在本小节中，我们将提供更多关于如何在C++中使用队列（Queue）的示例代码。

2.2.2.1 双端队列（Deque）

双端队列（Deque, Double-Ended Queue）是一种特殊的队列，允许在两端进行插入和删除操作。C++ STL（Standard Template Library，标准模板库）提供了deque容器来实现这一数据结构。

下面是一个简单的使用deque的C++示例：

#include <iostream>
#include <deque>
using namespace std;
int main() {
    deque<int> dq;
    // Insert elements at the end
    dq.push_back(10);
    dq.push_back(20);
    // Insert elements at the beginning
    dq.push_front(30);
    dq.push_front(40);
    // Remove elements from the end
    dq.pop_back();
    // Remove elements from the beginning
    dq.pop_front();
    // Display elements
    for (int elem : dq) {
        cout << elem << " ";
    }
    cout << endl;
    return 0;
}

在这个示例中，我们展示了如何使用push_back和push_front方法在双端队列的两端插入元素，以及如何使用pop_back和pop_front方法从两端删除元素。

2.2.2.2 优先队列（Priority Queue）

优先队列（Priority Queue）是一种特殊的队列，其中的元素不是按照到达的顺序排列，而是根据某种优先级进行排序。C++ STL提供了priority_queue容器来实现这一数据结构。

以下是一个使用优先队列的C++示例：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq;
    // Insert elements
    pq.push(10);
    pq.push(30);
    pq.push(20);
    // Remove and display elements
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    return 0;
}

在这个示例中，我们使用priority_queue容器来创建一个优先队列，并使用push方法插入元素。这些元素会自动按照降序排列。然后，我们使用top方法查看优先队列中的最大元素，并使用pop方法进行删除。

【C++ 数据结构与算法一站式备考指南】一文掌握数据结构与算法课程知识点（二）https://developer.aliyun.com/article/1467832

【C++ 数据结构与算法 一站式备考指南】一文掌握 数据结构与算法课程 知识点（一）

前言

1. 背景：为什么数据结构和算法在C++课程中重要

2. 博客目标：备考重点与学习方法

3. 预览：本文将覆盖的主要主题

第一部分：线性表操作

1.1 顺序表（Sequential Lists）

1.1.1 初始化

1.1.2 查找

1.1.3 插入

1.1.4 删除

1.1.5 示例代码与注意事项

示例代码

注意事项

1.2 单链表（Singly Linked Lists）

1.2.1 初始化

1.2.2 查找

1.2.3 插入

1.2.4 删除

1.2.5 示例代码与注意事项

示例代码

注意事项

第二部分：栈和队列基本操作

2.1 栈 (Stack)

2.1.1 进制转换

2.1.2 字符串输入/解析

2.1.3 示例代码与注意事项

2.1.3.1 栈的基本操作

2.1.3.2 判断字符串是否为回文

2.2 队列 (Queue)

2.2.1 简单应用

2.2.1.1 任务调度模拟

2.2.1.2 数据流平均值计算

2.2.2 示例代码与注意事项

2.2.2.1 双端队列（Deque）

2.2.2.2 优先队列（Priority Queue）

热门文章

最新文章

相关课程

相关电子书

相关实验场景

【C++ 数据结构与算法一站式备考指南】一文掌握数据结构与算法课程知识点（一）