C++实现的链表类实例

以下是C++实现的链表类实例的完整攻略。

1. 什么是链表

链表是计算机中常用的一种动态数据结构，它通过节点之间的指针连接，可以比较方便地增、删、改、查数据。链表的节点结构一般包含两部分：数据域和指针域，数据域存储节点所存储的数据，指针域存储下一个节点的位置信息。

2. C++中实现链表类的关键

在C++中，我们可以通过定义一个链表类来实现链表的操作。链表类一般包含以下几个关键部分：

• 节点结构体的定义
• 链表头指针的定义
• 构造函数和析构函数
• 插入节点函数
• 删除节点函数
• 遍历节点函数

下面我们来一个一个讲解。

2.1 节点结构体的定义

我们可以通过定义一个节点结构体来表示链表中的每一个节点。例如，可以定义如下的节点结构体：

struct ListNode {
    int val; // 节点中存储的数据
    ListNode *next; // 下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {} // 构造函数
};

上面的代码定义了一个名为ListNode的结构体，这个结构体中包含了两个成员变量val和next。其中，val表示节点中存储的数据，next表示下一个节点的指针。我们还定义了一个构造函数，用于初始化节点的值。

2.2 链表头指针的定义

由于链表是一个动态的数据结构，每一次操作都可能导致链表的头指针发生变化。因此，我们需要定义一个指向链表头部的指针，以便在对链表进行增、删、改、查操作时能够找到链表的位置。例如，可以定义如下的头指针变量：

ListNode* head;

上面的代码定义了一个名为head的指针，它指向链表的头节点。

2.3 构造函数和析构函数

链表类中的构造函数和析构函数通常用于链表的初始化和销毁。例如，可以定义如下的构造函数和析构函数：

class LinkedList {
public:
    LinkedList() {
        head = new ListNode(0); // 创建一个头节点
    }
    ~LinkedList() {
        ListNode* p = head;
        while (p) {
            ListNode* q = p;
            p = p->next;
            delete q;
        }
        head = NULL;
    }
private:
    ListNode* head; // 头指针
};

上面的代码中，构造函数中创建了一个头节点，并将头指针指向头节点。析构函数中则用while循环遍历链表中的每个节点，并删除它们。最后将头指针置为NULL。注意，在析构函数中一定要释放链表中所有的节点空间，否则可能导致内存泄漏。

2.4 插入节点函数

链表类中的插入节点函数通常有两个参数，一个是要插入的值，另一个是要插入的位置。例如，可以定义如下的插入节点函数：

void insert(int pos, int val) {
    ListNode* p = head;
    int index = 0;
    while (p && index < pos - 1) {
        p = p->next;
        index++;
    }
    if (p) {
        ListNode* q = new ListNode(val);
        q->next = p->next;
        p->next = q;
    }
}

上面的代码中，我们先用一个while循环找到要插入的位置，然后创建一个新节点，并将新节点插入到链表中。插入节点的思路是：先将新节点的next指向插入位置之后的节点，再将插入位置之前的节点的next指向新节点。

2.5 删除节点函数

链表类中的删除节点函数通常有一个参数，表示要删除的节点的位置。例如，可以定义如下的删除节点函数：

void remove(int pos) {
    ListNode* p = head;
    int index = 0;
    while (p && index < pos - 1) {
        p = p->next;
        index++;
    }
    if (p && p->next) {
        ListNode* q = p->next;
        p->next = q->next;
        delete q;
    }
}

上面的代码中，我们先用一个while循环找到要删除的位置之前的节点，然后将要删除的节点从链表中摘除。删除节点的思路是：将删除位置之前的节点的next指向删除位置之后的节点，再将被删除的节点删除。

2.6 遍历节点函数

链表类中的遍历节点函数通常没有参数，它会从链表的第一个节点开始遍历整个链表，并输出每个节点的值。例如，可以定义如下的遍历节点函数：

void traverse() {
    ListNode* p = head->next;
    while (p) {
        cout << p->val << endl;
        p = p->next;
    }
}

上面的代码中，我们用while循环遍历整个链表，并输出每个节点的值。

3. 示例

下面我们用两个示例来说明如何使用链表类。

3.1 示例1

假设我们要存储一个整数序列，并按照从小到大的顺序输出。我们可以使用链表来实现。代码如下：

int main() {
    int a[] = {2, 4, 1, 5, 3};
    int n = sizeof(a) / sizeof(int);

    LinkedList list;
    for (int i = 0; i < n; i++) {
        list.insert(i, a[i]);
    }
    list.remove(2);

    list.traverse();

    return 0;
}

上面的代码中，我们先定义了一个整数数组a，并将它插入到链表中。插入后的链表为：2->4->1->5->3。然后我们删除了位置为2的节点，即删除了值为1的节点。最后我们遍历了整个链表，输出每个节点的值。输出结果为：

2
4
5
3

3.2 示例2

假设我们要存储一些单词，并按照字典序从小到大的顺序输出。我们同样可以使用链表来实现。代码如下：

int main() {
    string a[] = {"dog", "cat", "apple", "car", "boy"};
    int n = sizeof(a) / sizeof(string);

    LinkedList list;
    for (int i = 0; i < n; i++) {
        list.insert(i, a[i]);
    }
    list.remove(2);

    list.traverse();

    return 0;
}

上面的代码中，我们先定义了一个字符串数组a，并将它插入到链表中。插入后的链表为：dog->cat->apple->car->boy。然后我们删除了位置为2的节点，即删除了值为apple的节点。最后我们遍历了整个链表，输出每个节点的值。输出结果为：

cat
car
boy
dog

至此，我们就完成了C++实现的链表类实例的完整攻略。