讨论详情 - Online Judge

C++
C++单链表、双链表、循环链表教程
admin SU @ 2025-3-13 21:35:23

什么是单链表

在编程里，单链表属于一种基础的数据结构，由一连串的节点构成。每个节点都包含两部分内容：一是数据域，用于存放具体的数据；二是指针域，其作用是指向链表中的下一个节点。链表的首个节点称作头节点，而最后一个节点的指针域则指向空（nullptr）。

单链表节点的定义

借助 C++ 的结构体，我们能够定义单链表的节点。下面是一个简单的例子：

#include <iostream>

// 定义单链表节点结构
struct ListNode {
    int data; // 数据域，这里假设存储整数
    ListNode* next; // 指针域，指向下一个节点

    // 构造函数，方便初始化节点
    ListNode(int val) : data(val), next(nullptr) {}
};

在这个结构体中，data 是用来存放数据的，next 则是指向下一个节点的指针。构造函数 ListNode(int val) 可以让我们在创建节点时直接为其赋值。

创建单链表

下面我们来创建一个简单的单链表，并且向其中添加节点。

int main() {
    // 创建头节点
    ListNode* head = new ListNode(1);

    // 创建第二个节点
    ListNode* second = new ListNode(2);
    // 将头节点的 next 指针指向第二个节点
    head->next = second;

    // 创建第三个节点
    ListNode* third = new ListNode(3);
    // 将第二个节点的 next 指针指向第三个节点
    second->next = third;

    return 0;
}

在上述代码中，我们创建了三个节点，并且让每个节点的 next 指针指向下一个节点，从而形成了一个简单的单链表。

遍历单链表

要查看链表中的所有元素，我们需要对链表进行遍历。以下是实现遍历的代码：

void printList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

在这个函数里，我们使用 while 循环从链表的头节点开始，逐个访问每个节点，直到到达链表的末尾（即 current 为 nullptr）。

在链表末尾插入节点

下面的代码展示了如何在链表的末尾插入一个新节点：

void insertAtEnd(ListNode*& head, int val) {
    ListNode* newNode = new ListNode(val);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    ListNode* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
}

这个函数首先检查链表是否为空，如果为空，新节点就成为头节点；否则，它会遍历到链表的末尾，然后将新节点插入。

删除链表中的节点

假设我们要删除链表中第一个值等于给定值的节点，以下是实现代码：

void deleteNode(ListNode*& head, int val) {
    if (head == nullptr) return;
    if (head->data == val) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    ListNode* current = head;
    while (current->next != nullptr && current->next->data != val) {
        current = current->next;
    }
    if (current->next != nullptr) {
        ListNode* temp = current->next;
        current->next = current->next->next;
        delete temp;
    }
}

这个函数会先检查头节点是否是要删除的节点，如果是，就更新头节点；否则，它会遍历链表，找到要删除的节点并将其从链表中移除。

完整示例代码

下面是将上述功能整合在一起的完整示例代码：

#include <iostream>

// 定义单链表节点结构
struct ListNode {
    int data; // 数据域，这里假设存储整数
    ListNode* next; // 指针域，指向下一个节点

    // 构造函数，方便初始化节点
    ListNode(int val) : data(val), next(nullptr) {}
};

// 遍历链表并打印节点值
void printList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

// 在链表末尾插入节点
void insertAtEnd(ListNode*& head, int val) {
    ListNode* newNode = new ListNode(val);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    ListNode* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
}

// 删除链表中第一个值等于给定值的节点
void deleteNode(ListNode*& head, int val) {
    if (head == nullptr) return;
    if (head->data == val) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    ListNode* current = head;
    while (current->next != nullptr && current->next->data != val) {
        current = current->next;
    }
    if (current->next != nullptr) {
        ListNode* temp = current->next;
        current->next = current->next->next;
        delete temp;
    }
}

int main() {
    ListNode* head = nullptr;

    // 插入节点
    insertAtEnd(head, 1);
    insertAtEnd(head, 2);
    insertAtEnd(head, 3);

    // 打印链表
    std::cout << "插入节点后的链表: ";
    printList(head);

    // 删除节点
    deleteNode(head, 2);

    // 再次打印链表
    std::cout << "删除节点 2 后的链表: ";
    printList(head);

    return 0;
}

总结

通过上述内容，你已经了解了单链表的基本操作，包括节点的定义、链表的创建、遍历、插入和删除。单链表在很多场景下都有应用，例如实现栈、队列等数据结构。随着不断学习和实践，你会对单链表有更深入的理解。

admin SU @ 2025-3-13 21:53:00
在 C++ 中，动态申请二维数组有多种方式，下面为你详细介绍不同的实现方法。

方法一：使用指针数组

这种方法是先创建一个指针数组，每个指针再指向一个一维数组，从而模拟出二维数组的效果。
```
#include <iostream>

int main() {
    int rows = 3;
    int cols = 4;

    // 动态分配一个指针数组，每个指针指向一个一维数组
    int** arr = new int*[rows];
    for (int i = 0; i < rows; ++i) {
        arr[i] = new int[cols];
    }

    // 初始化二维数组
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            arr[i][j] = i * cols + j;
        }
    }

    // 输出二维数组
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            std::cout << arr[i][j] << " ";
        }
        std::cout << std::endl;
    }

    // 释放内存
    for (int i = 0; i < rows; ++i) {
        delete[] arr[i];
    }
    delete[] arr;

    return 0;
}
```
代码解释：
1. 动态分配指针数组：int** arr = new int*[rows]; 这行代码创建了一个包含 rows 个元素的指针数组，每个元素都是一个 int* 类型的指针。
2. 为每个指针分配一维数组：通过 for 循环，为指针数组中的每个指针分配一个包含 cols 个元素的一维数组。
3. 初始化和访问二维数组：使用嵌套的 for 循环可以方便地初始化和访问二维数组的元素。
4. 释放内存：先释放每个一维数组的内存，再释放指针数组的内存，避免内存泄漏。
方法二：使用一维数组模拟二维数组

将二维数组的元素存储在一个一维数组中，通过计算索引来模拟二维数组的访问。
```
#include <iostream>

int main() {
    int rows = 3;
    int cols = 4;

    // 动态分配一个一维数组来存储二维数组的元素
    int* arr = new int[rows * cols];

    // 初始化二维数组
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            arr[i * cols + j] = i * cols + j;
        }
    }

    // 输出二维数组
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            std::cout << arr[i * cols + j] << " ";
        }
        std::cout << std::endl;
    }

    // 释放内存
    delete[] arr;

    return 0;
}
```
代码解释：
1. 动态分配一维数组：int* arr = new int[rows * cols]; 这行代码创建了一个包含 rows * cols 个元素的一维数组。
2. 计算索引：通过 i * cols + j 计算二维数组中元素在一维数组中的索引，实现二维数组的访问。
3. 释放内存：使用 delete[] 释放一维数组的内存。
方法三：使用 std::vector

std::vector 是 C++ 标准库中的容器，使用它可以更方便地管理动态内存。
```
#include <iostream>
#include <vector>

int main() {
    int rows = 3;
    int cols = 4;

    // 动态创建二维 vector
    std::vector<std::vector<int>> arr(rows, std::vector<int>(cols));

    // 初始化二维数组
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            arr[i][j] = i * cols + j;
        }
    }

    // 输出二维数组
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            std::cout << arr[i][j] << " ";
        }
        std::cout << std::endl;
    }

    // 不需要手动释放内存，vector 会自动管理

    return 0;
}
```
代码解释：
1. 创建二维 vector：std::vector<std::vector<int>> arr(rows, std::vector<int>(cols)); 这行代码创建了一个包含 rows 个元素的 vector，每个元素又是一个包含 cols 个元素的 vector。
2. 初始化和访问二维数组：使用嵌套的 for 循环可以方便地初始化和访问二维数组的元素。
3. 内存管理：std::vector 会自动管理内存，不需要手动释放。
总结
- 方法一使用指针数组，灵活性较高，但需要手动管理内存，容易出现内存泄漏问题。
- 方法二使用一维数组模拟二维数组，内存连续，访问效率较高，但索引计算相对复杂。
- 方法三使用 std::vector，代码简洁，内存管理方便，推荐在大多数情况下使用。
admin SU @ 2025-3-13 21:51:50
在 C++ 里，动态申请空间能够让程序在运行时依据实际需求来分配和释放内存，这是一项极为关键的特性。下面会详细介绍 C++ 中动态申请空间的方法，包含 new 运算符、delete 运算符以及 C 风格的 malloc 和 free 函数。

1. 为什么需要动态申请空间

在常规的变量定义中，内存的分配是静态的，也就是在编译时就已经确定了内存的大小。不过，在一些情形下，我们在编写程序时并不知道具体需要多少内存，例如要存储用户输入的一组数据，数据的数量是不确定的。这时就需要动态申请空间，在运行时根据实际需求来分配内存。

2. 使用 new 和 delete 运算符

2.1 动态分配单个变量

运用 new 运算符能够在堆上动态分配单个变量的内存空间。以下是示例代码：
```
#include <iostream>

int main() {
    // 使用 new 动态分配一个 int 类型的变量
    int* ptr = new int;

    // 给动态分配的变量赋值
    *ptr = 10;

    // 输出动态分配变量的值
    std::cout << "动态分配的整数的值是: " << *ptr << std::endl;

    // 使用 delete 释放动态分配的内存
    delete ptr;

    return 0;
}
```
代码解释：
- int* ptr = new int;：new int 会在堆上分配一个 int 类型的内存空间，并且返回该内存空间的地址，这个地址会被赋给指针 ptr。
- *ptr = 10;：通过解引用指针 ptr，可以给动态分配的变量赋值。
- delete ptr;：使用 delete 运算符释放之前动态分配的内存，防止出现内存泄漏。
2.2 动态分配数组

使用 new[] 运算符可以动态分配数组的内存空间。示例代码如下：
```
#include <iostream>

int main() {
    // 动态分配一个包含 5 个 int 元素的数组
    int* arr = new int[5];

    // 给数组元素赋值
    for (int i = 0; i < 5; ++i) {
        arr[i] = i;
    }

    // 输出数组元素
    for (int i = 0; i < 5; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    // 使用 delete[] 释放动态分配的数组内存
    delete[] arr;

    return 0;
}
```
代码解释：
- int* arr = new int[5];：new int[5] 会在堆上分配一个包含 5 个 int 元素的数组的内存空间，同时返回数组首元素的地址，该地址会被赋给指针 arr。
- delete[] arr;：使用 delete[] 运算符释放动态分配的数组内存，这里要注意使用 delete[] 而不是 delete，不然会引发未定义行为。
2.3 动态分配自定义类型对象

new 运算符还可以用来动态分配自定义类型的对象。示例代码如下：
```
#include <iostream>

// 定义一个简单的类
class MyClass {
public:
    MyClass() {
        std::cout << "MyClass 构造函数被调用" << std::endl;
    }
    ~MyClass() {
        std::cout << "MyClass 析构函数被调用" << std::endl;
    }
};

int main() {
    // 动态分配一个 MyClass 类型的对象
    MyClass* obj = new MyClass;

    // 使用 delete 释放动态分配的对象内存
    delete obj;

    return 0;
}
```
代码解释：
- MyClass* obj = new MyClass;：new MyClass 会在堆上分配一个 MyClass 类型的对象的内存空间，并且自动调用该类的构造函数。
- delete obj;：使用 delete 运算符释放动态分配的对象内存，同时会自动调用该类的析构函数。
3. 使用 malloc 和 free 函数（C 风格）

在 C++ 里，也能够使用 C 语言的 malloc 和 free 函数来进行动态内存分配。不过，malloc 和 free 不会自动调用构造函数和析构函数。示例代码如下：
```
#include <iostream>
#include <cstdlib>

int main() {
    // 使用 malloc 动态分配一个 int 类型的变量
    int* ptr = (int*)malloc(sizeof(int));

    if (ptr != nullptr) {
        // 给动态分配的变量赋值
        *ptr = 20;

        // 输出动态分配变量的值
        std::cout << "动态分配的整数的值是: " << *ptr << std::endl;

        // 使用 free 释放动态分配的内存
        free(ptr);
    }

    return 0;
}
```
代码解释：
- int* ptr = (int*)malloc(sizeof(int));：malloc(sizeof(int)) 会在堆上分配一个 int 类型大小的内存空间，返回一个 void* 类型的指针，需要将其强制转换为 int* 类型。
- free(ptr);：使用 free 函数释放之前动态分配的内存。
4. 注意事项
- 内存泄漏：动态分配的内存使用完之后必须释放，否则会造成内存泄漏，也就是内存一直被占用，无法被其他程序使用。
- new 和 delete 配对，new[] 和 delete[] 配对：使用 new 分配的内存要用 delete 释放，使用 new[] 分配的数组内存要用 delete[] 释放。
- 空指针检查：使用 malloc 分配内存时，要检查返回的指针是否为 nullptr，以确保内存分配成功。
通过上述内容，你应该对 C++ 中的动态申请空间有了比较清晰的认识。在实际编程中，要根据具体情况选择合适的动态内存分配方式。
admin SU @ 2025-3-13 21:51:16
在 C++ 中，动态申请空间是一项重要的功能，它允许程序在运行时根据实际需求分配和释放内存。下面将详细介绍 C++ 中动态申请空间的两种主要方式：使用 new 运算符和 malloc 函数。

1. 使用 new 运算符

new 是 C++ 专门用于动态内存分配的运算符，它不仅能分配内存，还能自动调用对象的构造函数，使用起来更加方便和安全。

1.1 动态分配单个对象
```
#include <iostream>

int main() {
    // 动态分配一个 int 类型的对象
    int* ptr = new int;
    // 给分配的内存赋值
    *ptr = 10;
    std::cout << "动态分配的整数的值是: " << *ptr << std::endl;
    // 释放动态分配的内存
    delete ptr;
    return 0;
}
```
代码解释：
- new int 表达式在堆上分配了一个 int 类型的内存空间，并返回该内存空间的地址。
- delete ptr 用于释放之前分配的内存，避免内存泄漏。
1.2 动态分配数组
```
#include <iostream>

int main() {
    // 动态分配一个包含 5 个 int 元素的数组
    int* arr = new int[5];
    // 给数组元素赋值
    for (int i = 0; i < 5; ++i) {
        arr[i] = i;
    }
    // 输出数组元素
    for (int i = 0; i < 5; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    // 释放动态分配的数组内存
    delete[] arr;
    return 0;
}
```
代码解释：
- new int[5] 分配了一个包含 5 个 int 元素的数组，并返回数组首元素的地址。
- delete[] arr 用于释放动态分配的数组内存，注意这里使用 delete[] 而不是 delete，否则会导致未定义行为。
1.3 动态分配自定义类型对象
```
#include <iostream>

class MyClass {
public:
    MyClass() {
        std::cout << "MyClass 构造函数被调用" << std::endl;
    }
    ~MyClass() {
        std::cout << "MyClass 析构函数被调用" << std::endl;
    }
};

int main() {
    // 动态分配一个 MyClass 类型的对象
    MyClass* obj = new MyClass;
    // 释放动态分配的对象内存
    delete obj;
    return 0;
}
```
代码解释：
- new MyClass 分配了一个 MyClass 类型的对象，并自动调用其构造函数。
- delete obj 释放对象内存时，会自动调用其析构函数。
2. 使用 malloc 函数（C 风格的内存分配）

malloc 是 C 语言中用于动态内存分配的函数，C++ 也支持使用它。不过，malloc 只分配内存，不会调用对象的构造函数，使用时需要手动进行类型转换。

2.1 动态分配单个对象
```
#include <iostream>
#include <cstdlib>

int main() {
    // 动态分配一个 int 类型的对象
    int* ptr = static_cast<int*>(malloc(sizeof(int)));
    if (ptr != nullptr) {
        // 给分配的内存赋值
        *ptr = 20;
        std::cout << "动态分配的整数的值是: " << *ptr << std::endl;
        // 释放动态分配的内存
        free(ptr);
    }
    return 0;
}
```
代码解释：
- malloc(sizeof(int)) 分配了一个 int 类型大小的内存空间，并返回一个 void* 类型的指针。
- static_cast<int*>(...) 将 void* 类型的指针转换为 int* 类型。
- free(ptr) 用于释放动态分配的内存。
2.2 动态分配数组
```
#include <iostream>
#include <cstdlib>

int main() {
    // 动态分配一个包含 3 个 int 元素的数组
    int* arr = static_cast<int*>(malloc(3 * sizeof(int)));
    if (arr != nullptr) {
        // 给数组元素赋值
        for (int i = 0; i < 3; ++i) {
            arr[i] = i * 2;
        }
        // 输出数组元素
        for (int i = 0; i < 3; ++i) {
            std::cout << arr[i] << " ";
        }
        std::cout << std::endl;
        // 释放动态分配的数组内存
        free(arr);
    }
    return 0;
}
```
代码解释：
- malloc(3 * sizeof(int)) 分配了一个包含 3 个 int 元素的数组所需的内存空间。
- free(arr) 释放动态分配的数组内存。
3. new 与 malloc 的比较
- 类型安全：new 是类型安全的，它会自动处理类型，而 malloc 返回的是 void* 类型，需要手动进行类型转换。
- 构造和析构：new 会自动调用对象的构造函数，delete 会自动调用对象的析构函数；而 malloc 和 free 不会调用构造和析构函数。
- 异常处理：new 在内存分配失败时会抛出 std::bad_alloc 异常，而 malloc 在内存分配失败时返回 nullptr。
综上所述，在 C++ 中推荐使用 new 和 delete 进行动态内存分配，因为它们更符合 C++ 的面向对象特性，使用起来更加安全和方便。但在一些需要与 C 代码兼容的场景中，malloc 和 free 仍然是可用的选择。

admin SU @ 2025-3-13 21:45:46

1. 什么是单链表

单链表是一种线性数据结构，由一系列节点组成。每个节点包含两部分：

数据域：用于存储具体的数据。
指针域：存储指向下一个节点的指针，通过这个指针将各个节点连接起来。

链表的第一个节点称为头节点，如果链表为空，头节点为空指针。链表的最后一个节点的指针域指向 nullptr，表示链表的结束。

2. 单链表节点的定义

在 C++ 中，我们可以使用结构体来定义单链表的节点，示例代码如下：

#include <iostream>

// 定义单链表节点结构
struct ListNode {
    int data;  // 数据域，这里假设存储整数
    ListNode* next;  // 指针域，指向下一个节点

    // 构造函数，方便初始化节点
    ListNode(int value) : data(value), next(nullptr) {}
};

在上述代码中，ListNode 结构体定义了单链表的节点。data 成员用于存储节点的数据，next 成员是一个指向 ListNode 类型的指针，用于指向下一个节点。构造函数 ListNode(int value) 允许我们在创建节点时直接为节点的数据域赋值，并将 next 指针初始化为 nullptr。

3. 单链表的基本操作

3.1 创建单链表

下面的代码展示了如何创建一个简单的单链表，包含几个节点并连接起来：

int main() {
    // 创建头节点
    ListNode* head = new ListNode(1);

    // 创建第二个节点
    ListNode* second = new ListNode(2);
    // 将头节点的 next 指针指向第二个节点
    head->next = second;

    // 创建第三个节点
    ListNode* third = new ListNode(3);
    // 将第二个节点的 next 指针指向第三个节点
    second->next = third;

    return 0;
}

在这个示例中，我们依次创建了三个节点，然后通过设置 next 指针将它们连接成一个单链表。

3.2 遍历单链表

要查看链表中的所有元素，需要对链表进行遍历。以下是实现遍历的代码：

// 遍历单链表并打印节点数据
void printList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

printList 函数使用 while 循环从链表的头节点开始，逐个访问每个节点并打印其数据，直到到达链表的末尾（current 为 nullptr）。

3.3 在链表头部插入节点

在链表头部插入节点的步骤如下：

// 在链表头部插入节点
void insertAtHead(ListNode*& head, int value) {
    ListNode* newNode = new ListNode(value);
    newNode->next = head;
    head = newNode;
}

该函数首先创建一个新节点，然后将新节点的 next 指针指向原来的头节点，最后更新头节点为新节点。注意，这里使用引用 ListNode*& head 是为了能够修改头节点的指针。

3.4 在链表尾部插入节点

在链表尾部插入节点的代码如下：

// 在链表尾部插入节点
void insertAtTail(ListNode*& head, int value) {
    ListNode* newNode = new ListNode(value);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    ListNode* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
}

此函数先创建新节点。如果链表为空，新节点就是头节点；否则，遍历到链表尾部，将尾部节点的 next 指针指向新节点。

3.5 删除链表中的节点

下面的代码实现了删除链表中第一个值等于给定值的节点：

// 删除链表中第一个值等于给定值的节点
void deleteNode(ListNode*& head, int value) {
    if (head == nullptr) return;
    if (head->data == value) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    ListNode* current = head;
    while (current->next != nullptr && current->next->data != value) {
        current = current->next;
    }
    if (current->next != nullptr) {
        ListNode* temp = current->next;
        current->next = current->next->next;
        delete temp;
    }
}

该函数首先检查链表是否为空。如果要删除的是头节点，更新头节点并释放原头节点的内存。如果要删除的不是头节点，遍历链表找到该节点并删除。

4. 完整示例代码

以下是将上述操作整合在一起的完整示例代码：

#include <iostream>

// 定义单链表节点结构
struct ListNode {
    int data;  // 数据域，这里假设存储整数
    ListNode* next;  // 指针域，指向下一个节点

    // 构造函数，方便初始化节点
    ListNode(int value) : data(value), next(nullptr) {}
};

// 遍历单链表并打印节点数据
void printList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

// 在链表头部插入节点
void insertAtHead(ListNode*& head, int value) {
    ListNode* newNode = new ListNode(value);
    newNode->next = head;
    head = newNode;
}

// 在链表尾部插入节点
void insertAtTail(ListNode*& head, int value) {
    ListNode* newNode = new ListNode(value);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    ListNode* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
}

// 删除链表中第一个值等于给定值的节点
void deleteNode(ListNode*& head, int value) {
    if (head == nullptr) return;
    if (head->data == value) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    ListNode* current = head;
    while (current->next != nullptr && current->next->data != value) {
        current = current->next;
    }
    if (current->next != nullptr) {
        ListNode* temp = current->next;
        current->next = current->next->next;
        delete temp;
    }
}

int main() {
    ListNode* head = nullptr;

    // 在尾部插入节点
    insertAtTail(head, 1);
    insertAtTail(head, 2);
    insertAtTail(head, 3);

    std::cout << "插入节点后的链表: ";
    printList(head);

    // 在头部插入节点
    insertAtHead(head, 0);
    std::cout << "在头部插入节点 0 后的链表: ";
    printList(head);

    // 删除节点
    deleteNode(head, 2);
    std::cout << "删除节点 2 后的链表: ";
    printList(head);

    return 0;
}

5. 总结

通过以上内容，你已经了解了单链表的基本概念、节点定义以及常见操作，包括创建、遍历、插入和删除节点。单链表在很多场景下都有应用，例如实现栈、队列等数据结构。在使用单链表时，要注意指针的操作，避免出现内存泄漏等问题。随着进一步的学习和实践，你可以将单链表应用到更复杂的程序中。

admin SU @ 2025-3-13 21:45:04

1. 什么是循环链表

循环链表是一种特殊的链表结构，它和普通链表类似，都是由一系列节点组成，每个节点包含数据域和指针域。不过，循环链表的特别之处在于其尾节点的指针不再指向 nullptr，而是指向链表的头节点，形成了一个闭环结构。这样的设计使得我们可以从链表的任意节点开始，沿着指针一直遍历，最终回到起始节点。

循环链表分为单循环链表和双循环链表。单循环链表中每个节点只有一个指向下一个节点的指针；双循环链表中每个节点除了有指向下一个节点的指针，还有一个指向前一个节点的指针，并且头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点。这里我们主要介绍单循环链表。

2. 单循环链表节点的定义

使用 C++ 的结构体来定义单循环链表的节点，代码如下：

#include <iostream>

// 定义单循环链表节点结构
struct Node {
    int data;  // 数据域，这里假设存储整数
    Node* next;  // 指针域，指向下一个节点

    // 构造函数，方便创建节点时初始化数据
    Node(int value) : data(value), next(nullptr) {}
};

在上述代码中，Node 结构体表示单循环链表的节点。data 用于存储节点的数据，next 是一个指针，指向链表中的下一个节点。构造函数 Node(int value) 可以在创建节点时直接为节点的数据域赋值，并将 next 指针初始化为 nullptr。

3. 单循环链表的基本操作

3.1 创建单循环链表

以下代码展示了如何创建一个简单的单循环链表，包含几个节点并连接成环：

int main() {
    // 创建第一个节点
    Node* head = new Node(1);
    // 创建第二个节点
    Node* second = new Node(2);
    // 创建第三个节点
    Node* third = new Node(3);

    // 连接节点
    head->next = second;
    second->next = third;
    // 形成循环，尾节点指向头节点
    third->next = head;

    return 0;
}

在这个例子中，我们依次创建了三个节点，然后通过设置 next 指针将它们连接起来，最后让尾节点的 next 指针指向头节点，形成一个单循环链表。

3.2 遍历单循环链表

遍历单循环链表和普通链表有所不同，因为它没有一个明确的结束标志（nullptr）。我们可以使用一个 do-while 循环来实现遍历，代码如下：

// 遍历单循环链表并打印节点数据
void printCircularList(Node* head) {
    if (head == nullptr) return;
    Node* current = head;
    do {
        std::cout << current->data << " ";
        current = current->next;
    } while (current != head);
    std::cout << std::endl;
}

printCircularList 函数首先检查链表是否为空。如果不为空，使用 do-while 循环从头节点开始，依次访问每个节点并打印其数据，直到再次回到头节点为止。

3.3 在单循环链表头部插入节点

在单循环链表头部插入节点的步骤如下：

// 在单循环链表头部插入节点
void insertAtHead(Node*& head, int value) {
    Node* newNode = new Node(value);
    if (head == nullptr) {
        head = newNode;
        head->next = head;  // 只有一个节点时，自己指向自己形成循环
        return;
    }
    Node* tail = head;
    while (tail->next != head) {
        tail = tail->next;
    }
    newNode->next = head;
    tail->next = newNode;
    head = newNode;
}

该函数首先创建一个新节点。如果链表为空，新节点就是头节点，并且它的 next 指针指向自己形成循环。如果链表不为空，先找到尾节点，然后将新节点的 next 指针指向原来的头节点，尾节点的 next 指针指向新节点，最后更新头节点为新节点。

3.4 在单循环链表尾部插入节点

在单循环链表尾部插入节点的代码如下：

// 在单循环链表尾部插入节点
void insertAtTail(Node*& head, int value) {
    Node* newNode = new Node(value);
    if (head == nullptr) {
        head = newNode;
        head->next = head;  // 只有一个节点时，自己指向自己形成循环
        return;
    }
    Node* tail = head;
    while (tail->next != head) {
        tail = tail->next;
    }
    tail->next = newNode;
    newNode->next = head;
}

此函数同样先创建新节点。若链表为空，新节点成为头节点并形成循环。若链表不为空，找到尾节点，将尾节点的 next 指针指向新节点，新节点的 next 指针指向头节点。

3.5 删除单循环链表中的节点

下面的代码实现了删除单循环链表中第一个值等于给定值的节点：

// 删除单循环链表中第一个值等于给定值的节点
void deleteNode(Node*& head, int value) {
    if (head == nullptr) return;
    if (head->data == value) {
        if (head->next == head) {
            delete head;
            head = nullptr;
        } else {
            Node* tail = head;
            while (tail->next != head) {
                tail = tail->next;
            }
            Node* temp = head;
            head = head->next;
            tail->next = head;
            delete temp;
        }
        return;
    }
    Node* current = head;
    while (current->next != head && current->next->data != value) {
        current = current->next;
    }
    if (current->next != head) {
        Node* temp = current->next;
        current->next = temp->next;
        delete temp;
    }
}

该函数首先检查链表是否为空。如果要删除的是头节点，再分两种情况：若链表只有一个节点，直接删除并将头节点置为 nullptr；若链表有多个节点，找到尾节点，更新尾节点的 next 指针，然后删除头节点。如果要删除的不是头节点，遍历链表找到该节点并删除。

4. 完整示例代码

以下是将上述操作整合在一起的完整示例代码：

#include <iostream>

// 定义单循环链表节点结构
struct Node {
    int data;  // 数据域，这里假设存储整数
    Node* next;  // 指针域，指向下一个节点

    // 构造函数，方便创建节点时初始化数据
    Node(int value) : data(value), next(nullptr) {}
};

// 遍历单循环链表并打印节点数据
void printCircularList(Node* head) {
    if (head == nullptr) return;
    Node* current = head;
    do {
        std::cout << current->data << " ";
        current = current->next;
    } while (current != head);
    std::cout << std::endl;
}

// 在单循环链表头部插入节点
void insertAtHead(Node*& head, int value) {
    Node* newNode = new Node(value);
    if (head == nullptr) {
        head = newNode;
        head->next = head;  // 只有一个节点时，自己指向自己形成循环
        return;
    }
    Node* tail = head;
    while (tail->next != head) {
        tail = tail->next;
    }
    newNode->next = head;
    tail->next = newNode;
    head = newNode;
}

// 在单循环链表尾部插入节点
void insertAtTail(Node*& head, int value) {
    Node* newNode = new Node(value);
    if (head == nullptr) {
        head = newNode;
        head->next = head;  // 只有一个节点时，自己指向自己形成循环
        return;
    }
    Node* tail = head;
    while (tail->next != head) {
        tail = tail->next;
    }
    tail->next = newNode;
    newNode->next = head;
}

// 删除单循环链表中第一个值等于给定值的节点
void deleteNode(Node*& head, int value) {
    if (head == nullptr) return;
    if (head->data == value) {
        if (head->next == head) {
            delete head;
            head = nullptr;
        } else {
            Node* tail = head;
            while (tail->next != head) {
                tail = tail->next;
            }
            Node* temp = head;
            head = head->next;
            tail->next = head;
            delete temp;
        }
        return;
    }
    Node* current = head;
    while (current->next != head && current->next->data != value) {
        current = current->next;
    }
    if (current->next != head) {
        Node* temp = current->next;
        current->next = temp->next;
        delete temp;
    }
}

int main() {
    Node* head = nullptr;

    // 在尾部插入节点
    insertAtTail(head, 1);
    insertAtTail(head, 2);
    insertAtTail(head, 3);

    std::cout << "插入节点后的链表: ";
    printCircularList(head);

    // 在头部插入节点
    insertAtHead(head, 0);
    std::cout << "在头部插入节点 0 后的链表: ";
    printCircularList(head);

    // 删除节点
    deleteNode(head, 2);
    std::cout << "删除节点 2 后的链表: ";
    printCircularList(head);

    return 0;
}

5. 总结

通过以上内容，你已经了解了单循环链表的基本概念、节点定义以及常见操作，包括创建、遍历、插入和删除节点。循环链表在某些场景下非常有用，例如实现循环队列等。在使用循环链表时，要特别注意指针的操作，避免出现死循环等问题。随着进一步的学习和实践，你可以将循环链表应用到更复杂的程序中。

admin SU @ 2025-3-13 21:43:46

1. 什么是双链表

双链表是一种常见的数据结构，它由一系列节点组成。每个节点包含三个主要部分：

数据域：用于存储实际的数据。
指向前一个节点的指针（prev）：这个指针使得我们可以从当前节点回溯到前一个节点。
指向后一个节点的指针（next）：借助这个指针，我们能从当前节点访问到下一个节点。

与单链表相比，双链表的优势在于可以双向遍历，这在某些操作中会带来便利，但相应地也会增加一些空间开销，因为每个节点需要额外存储一个指向前驱节点的指针。

2. 双链表节点的定义

在 C++ 中，我们可以使用结构体来定义双链表的节点，示例代码如下：

#include <iostream>

// 定义双链表节点结构
struct DoublyNode {
    int data; // 数据域，这里假设存储整数类型的数据
    DoublyNode* prev; // 指向前一个节点的指针
    DoublyNode* next; // 指向后一个节点的指针

    // 构造函数，方便创建节点时初始化数据
    DoublyNode(int value) : data(value), prev(nullptr), next(nullptr) {}
};

在上述代码中，DoublyNode 结构体定义了双链表的节点，data 成员存储具体的数据，prev 指针用于指向前一个节点，next 指针用于指向后一个节点。构造函数 DoublyNode(int value) 可以在创建节点时直接为节点的数据域赋值，并将前后指针初始化为 nullptr。

3. 双链表的基本操作

3.1 创建双链表

下面的代码展示了如何创建一个简单的双链表，包含几个节点并连接起来：

int main() {
    // 创建第一个节点
    DoublyNode* head = new DoublyNode(1);

    // 创建第二个节点
    DoublyNode* second = new DoublyNode(2);
    // 建立第一个节点和第二个节点的连接
    head->next = second;
    second->prev = head;

    // 创建第三个节点
    DoublyNode* third = new DoublyNode(3);
    // 建立第二个节点和第三个节点的连接
    second->next = third;
    third->prev = second;

    return 0;
}

在这个示例中，我们依次创建了三个节点，然后通过设置 next 和 prev 指针将它们连接成一个双链表。

3.2 遍历双链表

双链表可以正向和反向遍历，以下是实现正向和反向遍历的代码：

// 正向遍历双链表并打印节点数据
void printForward(DoublyNode* head) {
    DoublyNode* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

// 反向遍历双链表并打印节点数据
void printBackward(DoublyNode* tail) {
    DoublyNode* current = tail;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->prev;
    }
    std::cout << std::endl;
}

printForward 函数从双链表的头节点开始，沿着 next 指针依次访问每个节点并打印其数据，直到到达链表末尾（current 为 nullptr）。printBackward 函数则从双链表的尾节点开始，沿着 prev 指针反向访问每个节点并打印数据。

3.3 在双链表头部插入节点

要在双链表的头部插入一个新节点，可以按照以下步骤操作：

// 在双链表头部插入节点
void insertAtHead(DoublyNode*& head, int value) {
    DoublyNode* newNode = new DoublyNode(value);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    newNode->next = head;
    head->prev = newNode;
    head = newNode;
}

该函数首先创建一个新节点，然后检查链表是否为空。如果链表为空，新节点就成为头节点；否则，将新节点的 next 指针指向原来的头节点，原来头节点的 prev 指针指向新节点，最后更新头节点为新节点。

3.4 在双链表尾部插入节点

在双链表尾部插入节点的代码如下：

// 在双链表尾部插入节点
void insertAtTail(DoublyNode*& head, int value) {
    DoublyNode* newNode = new DoublyNode(value);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    DoublyNode* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
    newNode->prev = current;
}

此函数先创建新节点，若链表为空，新节点即为头节点；若链表不为空，遍历到链表尾部，将尾部节点的 next 指针指向新节点，新节点的 prev 指针指向尾部节点。

3.5 删除双链表中的节点

下面的代码实现了删除双链表中第一个值等于给定值的节点：

// 删除双链表中第一个值等于给定值的节点
void deleteNode(DoublyNode*& head, int value) {
    if (head == nullptr) return;
    DoublyNode* current = head;
    while (current != nullptr && current->data != value) {
        current = current->next;
    }
    if (current == nullptr) return;

    if (current->prev != nullptr) {
        current->prev->next = current->next;
    } else {
        head = current->next;
    }

    if (current->next != nullptr) {
        current->next->prev = current->prev;
    }

    delete current;
}

该函数先遍历双链表找到值等于给定值的节点，若未找到则直接返回。若找到节点，分情况处理：如果该节点不是头节点，将其前一个节点的 next 指针指向该节点的下一个节点；如果是头节点，更新头节点为该节点的下一个节点。同时，如果该节点不是尾节点，将其后一个节点的 prev 指针指向该节点的前一个节点。最后，释放该节点的内存。

4. 完整示例代码

以下是将上述操作整合在一起的完整示例代码：

#include <iostream>

// 定义双链表节点结构
struct DoublyNode {
    int data; // 数据域，这里假设存储整数类型的数据
    DoublyNode* prev; // 指向前一个节点的指针
    DoublyNode* next; // 指向后一个节点的指针

    // 构造函数，方便创建节点时初始化数据
    DoublyNode(int value) : data(value), prev(nullptr), next(nullptr) {}
};

// 正向遍历双链表并打印节点数据
void printForward(DoublyNode* head) {
    DoublyNode* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

// 反向遍历双链表并打印节点数据
void printBackward(DoublyNode* tail) {
    DoublyNode* current = tail;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->prev;
    }
    std::cout << std::endl;
}

// 在双链表头部插入节点
void insertAtHead(DoublyNode*& head, int value) {
    DoublyNode* newNode = new DoublyNode(value);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    newNode->next = head;
    head->prev = newNode;
    head = newNode;
}

// 在双链表尾部插入节点
void insertAtTail(DoublyNode*& head, int value) {
    DoublyNode* newNode = new DoublyNode(value);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    DoublyNode* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
    newNode->prev = current;
}

// 删除双链表中第一个值等于给定值的节点
void deleteNode(DoublyNode*& head, int value) {
    if (head == nullptr) return;
    DoublyNode* current = head;
    while (current != nullptr && current->data != value) {
        current = current->next;
    }
    if (current == nullptr) return;

    if (current->prev != nullptr) {
        current->prev->next = current->next;
    } else {
        head = current->next;
    }

    if (current->next != nullptr) {
        current->next->prev = current->prev;
    }

    delete current;
}

int main() {
    DoublyNode* head = nullptr;

    // 在尾部插入节点
    insertAtTail(head, 1);
    insertAtTail(head, 2);
    insertAtTail(head, 3);

    std::cout << "正向遍历链表: ";
    printForward(head);

    // 找到尾节点
    DoublyNode* tail = head;
    while (tail->next != nullptr) {
        tail = tail->next;
    }
    std::cout << "反向遍历链表: ";
    printBackward(tail);

    // 在头部插入节点
    insertAtHead(head, 0);
    std::cout << "在头部插入节点 0 后，正向遍历链表: ";
    printForward(head);

    // 删除节点
    deleteNode(head, 2);
    std::cout << "删除节点 2 后，正向遍历链表: ";
    printForward(head);

    return 0;
}

5. 总结

通过以上内容，你已经了解了双链表的基本概念、节点定义以及常见操作，包括创建、遍历、插入和删除节点。双链表的双向遍历特性使其在某些场景下比单链表更具优势，但在使用时也需要注意指针的正确操作，避免出现内存泄漏等问题。随着进一步的学习和实践，你可以将双链表应用到更复杂的程序中。

C++单链表、双链表、循环链表教程

什么是单链表

单链表节点的定义

创建单链表

遍历单链表

在链表末尾插入节点

删除链表中的节点

完整示例代码

总结

6 条评论

方法一：使用指针数组

代码解释：

方法二：使用一维数组模拟二维数组

代码解释：

方法三：使用 std::vector

代码解释：

总结

1. 为什么需要动态申请空间

2. 使用 new 和 delete 运算符

2.1 动态分配单个变量

2.2 动态分配数组

2.3 动态分配自定义类型对象

3. 使用 malloc 和 free 函数（C 风格）

4. 注意事项

1. 使用 new 运算符

1.1 动态分配单个对象

1.2 动态分配数组

1.3 动态分配自定义类型对象

2. 使用 malloc 函数（C 风格的内存分配）

2.1 动态分配单个对象

2.2 动态分配数组

3. new 与 malloc 的比较

1. 什么是单链表

2. 单链表节点的定义

3. 单链表的基本操作

3.1 创建单链表

3.2 遍历单链表

3.3 在链表头部插入节点

3.4 在链表尾部插入节点

3.5 删除链表中的节点

4. 完整示例代码

5. 总结

1. 什么是循环链表

2. 单循环链表节点的定义

3. 单循环链表的基本操作

3.1 创建单循环链表

3.2 遍历单循环链表

3.3 在单循环链表头部插入节点

3.4 在单循环链表尾部插入节点

3.5 删除单循环链表中的节点

4. 完整示例代码

5. 总结

1. 什么是双链表

2. 双链表节点的定义

3. 双链表的基本操作

3.1 创建双链表

3.2 遍历双链表

3.3 在双链表头部插入节点

3.4 在双链表尾部插入节点

3.5 删除双链表中的节点

4. 完整示例代码

5. 总结

状态

开发

支持

还没有账户？

登录

方法三：使用 `std::vector`

2. 使用 `new` 和 `delete` 运算符

3. 使用 `malloc` 和 `free` 函数（C 风格）

1. 使用 `new` 运算符

2. 使用 `malloc` 函数（C 风格的内存分配）

3. `new` 与 `malloc` 的比较