C++ 链表的实现

2024-11-11 20:37:05

为了动态和灵活地增加、删除数据，可以通过指针动态地管理元素。链表的每个元素成为一个节点，每个节点的结构内都包含一个指向下一个节点的指针。通过这些节点的指针，最终可以将这些节点元素链接在一起，因此这种数据形式称为链表。

链表的一般定义形式：

struct film{
    char title[20];
    int rating;
    struct film * next;
};

next指针就是实现链接功能并且指向下一个节点的指针。在ADT的表述中，链表结构的功能函数包括创建链表、添加节点、删除节点、遍历节点等。

1.创建节点问题

template<class type>
struct Node{
    int data;
    Node<type>* next;

//成员初始化列表的方式写构造函数
    Node() :next(nullptr){} 
    Node(type data) :data(data), next(nullptr){}//定义一个带参数的构造函数
};

（1）成员变量声明

Node<type>类型的指针：
- Node<type>表示一个模板化的节点类型。其中，type是模板参数，可以在实例化这个结构体时指定节点存储的数据类型。
- Node<type>*就是一个指向这种类型节点的指针。
next成员变量：
- 在链表数据结构中，每个节点通常需要一个指向下一个节点的指针来连接整个链表。
- 这里的next就是这样一个指针，它用于将当前节点与链表中的下一个节点关联起来。

例如，假设有一个链表存储整数，代码可能如下：

Node<int> node1(5);
Node<int> node2(10);
node1.next = &node2;
//或是
node1->next = node2;

创建了两个节点node1和node2，并将node1的next指针指向node2，表示它们在链表中是相邻的节点——或是，将node1所指向的节点的next成员变量设置为指向node2所指向的节点，从而建立了链表中的连接关系。

`（2）next`指针初始化为`nullptr`

一、安全性考虑

避免意外访问：
- 当创建一个新的节点时，如果不明确初始化next指针，它可能会指向一个随机的内存地址。在后续对链表进行操作时，如果不小心使用了未初始化的next指针，可能会导致程序访问非法内存地址，从而引发严重的错误甚至崩溃。
- 通过初始化为nullptr，可以确保在使用next指针之前，明确知道它没有指向任何有效的节点，从而避免意外访问无效内存。

二、明确链表结构

表示链表状态：
- 在链表数据结构中，next指针用于连接各个节点。初始状态下，新创建的节点还没有被插入到链表中，所以它不应该指向任何其他节点。
- 将next初始化为nullptr清晰地表明这个节点目前是孤立的，没有与其他节点形成链表关系。这有助于在构建和操作链表时准确地判断节点的状态和链表的结构。

三、便于后续操作

简化插入和删除操作：
- 在进行链表的插入和删除操作时，需要根据节点的next指针来确定链表的连接关系。如果新节点的next指针初始状态明确为nullptr，在进行插入操作时，可以更容易地确定插入的位置和更新指针的指向。
- 例如，在链表头部插入节点时，可以直接将新节点的next指针指向当前的头节点，然后更新头指针为新节点。如果新节点的next指针没有初始化，可能需要额外的判断和处理来确保操作的正确性。

四、可读性和可维护性

提高代码的清晰度：
- 明确地将next指针初始化为nullptr使得代码更加清晰易读。其他开发人员在阅读代码时，可以立即明白新创建的节点在初始状态下没有与其他节点建立连接，有助于更好地理解链表的操作逻辑。
- 这种明确的初始化方式也有助于提高代码的可维护性。在后续对代码进行修改和扩展时，不容易因为未初始化的指针而引入难以察觉的错误。

（3）构造函数

无参构造函数的作用
- 初始化默认状态：
  - 在模板结构体Node中，无参构造函数Node()主要用于创建一个处于初始默认状态的节点。它将next指针初始化为nullptr，这是非常重要的，因为当创建一个新节点时，它在初始状态下不应该指向任何其他不确定的位置。
  - 例如，在构建链表的过程中，可能会先创建一些节点，然后再将它们逐个连接起来。无参构造函数提供了一种简单的方式来创建这些初始状态下独立的节点，保证了节点在未被连接到链表之前的安全性和确定性。
- 提供默认行为：
  - 它为用户提供了一种创建节点的默认方式。如果用户只需要创建一个节点，而暂时不关心节点的数据部分（例如，数据部分可能会在后续步骤中填充），就可以使用无参构造函数。这增加了代码的灵活性，使得用户可以根据具体的需求选择合适的构造函数来创建节点。
有参构造函数的作用
- 方便数据初始化：
  - 有参构造函数Node(type data)用于在创建节点的同时，将数据成员data初始化为指定的值。在链表中，节点通常需要存储一些数据，这个构造函数就提供了一种便捷的方式来完成数据的初始化。
  - 例如，如果链表用于存储整数，用户可以使用Node<int>(5)这样的方式创建一个节点，其中5是要存储在节点中的数据。这种方式使得数据的初始化和节点的创建可以同时进行，符合面向对象编程中对象创建和初始化的一般原则。
- 完整对象创建：
  - 它允许用户在创建节点时就赋予其完整的状态。与无参构造函数不同，有参构造函数创建的节点不仅具有明确的next指针状态（初始化为nullptr），还具有指定的数据值。这对于那些需要立即使用带有特定数据的节点的情况非常有用，比如在初始化链表或者向链表中插入特定数据节点时。
两个构造函数结合的优势
- 满足不同的使用场景：
  - 无参和有参构造函数的存在使得Node结构体能够适应多种不同的使用场景。有时候，用户可能只需要创建一个空节点，等待后续填充数据和连接到链表；而有时候，用户希望在创建节点的同时就确定其数据内容，方便快捷地构建链表。
  - 例如，在从一个数据数组构建链表时，可以使用有参构造函数直接创建带有数组元素数据的节点；而在动态扩展链表或者进行一些复杂的链表操作时，可能会先使用无参构造函数创建节点，然后再进行数据填充和连接操作。

*注：

如果成员变量是常量或者引用类型，就必须使用成员初始化列表进行初始化。

2.链表模板类

template<class type>
class list{
public:
    //无参构造
    list(){
        size = 0; //记录链表中节点的数量
        listEnd = nullptr;
        listHead = nullptr;
    }

一、模板化的优势

通用性：
- 通过使用模板参数class type，可以使链表类能够存储任意类型的数据。这极大地提高了代码的通用性和可复用性。
- 无论是存储基本数据类型（如整数、浮点数、字符等），还是自定义的复杂数据类型（如结构体、类对象等），都可以使用同一个链表模板类，而无需为每种数据类型单独编写一个链表类。
- 例如，可以使用list<int>创建一个存储整数的链表，也可以使用list<MyCustomClass>创建一个存储自定义类对象的链表。

二、无参构造函数的作用

初始化链表状态：
- 在无参构造函数list()中，将链表的大小size初始化为 0，表示初始状态下链表中没有任何元素。
- 将listEnd和listHead分别初始化为nullptr，意味着链表的头指针和尾指针都指向空，即链表为空。
- 当创建一个新的链表对象时，无参构造函数确保链表处于一个明确的初始状态，便于后续对链表进行各种操作。
提供默认创建方式：
- 无参构造函数为用户提供了一种简单的方式来创建一个空的链表对象。在某些情况下，用户可能需要先创建一个空链表，然后再逐步向其中添加元素。
- 例如，在一些数据处理场景中，可能需要根据不同的条件动态地构建链表。无参构造函数提供了一个起点，让用户可以从一个空链表开始，根据具体的需求逐步添加元素，而不需要在创建链表时就指定初始元素。
与其他操作的配合：
- 无参构造函数创建的空链表可以方便地与链表类的其他成员函数配合使用。例如，可以通过添加成员函数来实现向链表中插入元素、删除元素、遍历链表等操作。
- 这些成员函数可以根据链表的初始状态（空链表）进行相应的处理，确保在各种情况下都能正确地操作链表。
- 同时，无参构造函数也为链表类的进一步扩展和定制提供了基础。可以在后续根据需要添加更多的构造函数或成员函数，以满足不同的使用场景。

3. assign成员函数

 void assign(int* begin, int* end){ //begin、end函数模板的参数
        while(begin != end){
            Node<type>* node = new Node<type>(*begin);
            if(size == 0){
                listHead = node;
                listEnd = node->next;
            }
            else{
                node->next = listHead;
                listHead = node; 
            }
            size++;
            begin++;指向下一个数组元素的位置
        }

正序构建链表：

else{
            listEnd->next = node;  // 将新节点加到链表的末尾
                    //让当前链表的尾节点 listEnd 的 next 指针指向新的节点 node，将新节点连接到链表的末尾。
            listEnd = node;        // 更新 listEnd 为新的末尾
        }

函数整体功能：
- assign是list类的一个成员函数，其目的是从一个整数数组（由指针begin和end界定范围）初始化链表。它通过遍历给定的整数数组，将数组中的元素逐个转换为链表中的节点，并构建链表。
- begin是一个指向整数数组的指针，这个指针在assign函数中用于遍历传入的整数数组
循环部分：
- while(begin!= end)：这个循环条件确保只要指针begin没有到达数组的末尾（与end相等），就会继续执行循环体。在每次循环中，从数组中取出一个元素来创建链表节点。
- Node<type>* node = new Node<type>(*begin)：创建一个新的链表节点，使用当前指针begin所指向的整数值作为节点的数据进行初始化。这里使用了Node模板结构体的有参构造函数，传入一个type类型的数据，在这个上下文中，type被实例化为int类型。
- begin++：将指针begin向后移动一位，以便在下一次循环中处理数组中的下一个元素。
链表为空时的处理：
- if(size == 0)：当链表的大小为 0 时，说明链表为空。在这种情况下，新创建的节点既是链表的头节点也是尾节点。
  - listHead = node：将链表的头指针指向新创建的节点，这样就确定了链表的起始位置。
  - listEnd = node：将链表的尾指针也指向新创建的节点，因为此时链表中只有一个节点。
链表不为空时的处理：
- else：当链表不为空时，新创建的节点将被插入到链表的头部，形成一个逆序的链表。
  - node->next = listHead：将新创建的node节点的next指针指向当前的头节点，即将新节点插入到链表的头部，实现链表的逆序插入操作。
  - listEnd = node：更新链表的尾指针为新创建的节点。这是因为在每次插入节点后，新节点成为了链表的最后一个节点。
  - 构建逆序链表的意图：在这段代码中，assign函数的实现方式是构建一个逆序的链表。当从数组中逐个取出元素创建节点并插入链表时，新节点会被插入到链表头部，所以新节点的next指针需要指向当前的头节点。
  - 例如，假设有数组元素[1, 2, 3]，第一次插入节点（值为 1）时，因为链表为空，该节点既是头节点也是尾节点。第二次插入节点（值为 2）时，新节点（值为 2）成为新的头节点，其next指针指向之前的头节点（值为 1），这样就构建了一个逆序的链表结构，新插入的节点总是在头部，原来的头节点就变成了新头节点的下一个节点。
  - 方便操作的考虑：这种方式在某些情况下是比较方便的。比如在频繁地从头部插入节点时，不需要遍历链表找到最后一个节点来插入新节点，只需要简单地更新头节点和新节点的next指针就可以完成插入操作。
  - 另外，在实现一些特定的算法或者功能时，逆序链表可能会更符合逻辑。例如，如果要实现一个后进先出（LIFO）的数据结构（类似于栈），这种逆序链表的构建方式就很合适，新插入的元素（新节点）总是最先被访问（因为在头部）。
更新链表状态：
- size++：每次创建一个新节点并插入到链表中后，增加链表的大小，表示链表中的节点数量增加了一个。
- “begin++” 是指针递增操作，它使得指针begin指向下一个数组元素的位置

总结来说，这个assign函数通过遍历整数数组，逐步构建链表，并且在链表为空和不为空的情况下分别进行了不同的处理，最终实现了从数组初始化链表的功能。同时，由于它是list类的成员函数，所以可以直接访问和修改list类的成员变量，如listHead、listEnd和size。

关于Node<type>* node = new Node<type>(*begin);说明：

整体结构：
- 这是一个声明并初始化指针的语句。它创建了一个指向Node<type>类型对象的指针，并使用动态内存分配（new关键字）为一个新的Node<type>对象分配内存空间，然后将该指针指向这个新创建的对象。
类型分析：
- Node<type>表示一个模板化的节点类型。这里的type是一个模板参数（在这里就是数据类型），可以在实例化这个链表类时指定节点存储的数据类型。
- Node<type>*是一个指向这种模板化节点类型的指针。通过使用指针，可以在运行时动态地分配和管理链表节点的内存。
动态内存分配：
- new Node<type>(*begin)使用new关键字进行动态内存分配，创建一个新的Node<type>对象。括号中的部分(*begin)是调用Node模板结构体的有参构造函数，将指针begin所指向的值作为参数传递给构造函数。
- 这个构造函数会使用传入的值来初始化新创建的节点的数据成员，并将节点的 next指针 初始化为nullptr。
赋值给指针：
- 最后，将新创建的Node<type>对象的地址赋给指针node（当使用new关键字进行动态内存分配时，它会返回所分配内存的地址）。这样，node就可以用来访问和操作这个新创建的链表节点。

例如，假设正在处理一个存储整数的链表，并且指针begin指向一个整数数组的第一个元素。如果这个数组的第一个元素是 5，那么这行代码会创建一个新的链表节点，节点的数据成员被初始化为 5，并且next指针初始化为nullptr。然后，指针node就指向这个新创建的节点。

总结来说，这行代码在链表的初始化过程中起着关键作用，它动态地创建新的链表节点，并使用数组中的值来初始化节点的数据成员，为构建链表提供了基础。

4.保护成员

protected:
    Node<type>* listHead;//指向头的指针
    Node<type>* listEnd;
    int size;
}

为什么写保护成员：

封装性和数据隐藏
- 信息隐藏原则：
  - 把listHead、listEnd和size定义为保护成员遵循了面向对象编程中的信息隐藏原则。这些成员变量存储了链表的关键信息（头节点、尾节点和节点数量），是链表内部状态的重要组成部分。将它们隐藏在protected访问控制级别之下，可以防止外部代码随意访问和修改这些成员，避免了因为外部不恰当的操作而导致链表状态的混乱。
- 提供统一接口：
  - 通过隐藏这些内部数据结构细节，类可以提供一套统一的公共成员函数（如assign、可能还有插入、删除、遍历等函数）来操作链表。外部代码只需要通过这些公共接口来与链表进行交互，而不需要了解链表内部是如何实现的。例如，外部代码可以调用assign函数来初始化链表，而不用关心链表内部是如何存储节点以及如何更新头节点、尾节点和节点数量的。
可继承性和扩展性
- 便于派生类使用：
  - protected访问权限允许派生类访问这些成员。这为类的继承和扩展提供了方便。如果想要创建一个派生类来扩展链表的功能，比如创建一个有序链表类或者带有特殊节点类型的链表类，派生类就可以访问这些保护成员来实现自己的功能。
  - 例如，派生类可能需要根据listHead来实现自己的遍历算法，或者根据size来实现更复杂的插入和删除策略。保护成员使得这些操作在派生类中能够方便地进行，同时又保证了这些关键数据结构不会被外部随意修改。
- 实现多态性和定制化：
  - 可以通过继承和重写成员函数来定制链表的行为。在派生类中，利用这些保护成员，可以在不改变链表基本结构的基础上，对链表的操作进行定制。比如，重写插入函数，根据特定的规则（如按照节点数据大小排序插入）来插入节点，而这个过程可能需要访问listHead和size等保护成员来正确地操作链表。
Node<type>* listHead：头节点
- 这是一个指向Node<type>类型对象的指针，用于表示链表的头节点。
- 通过这个指针，可以方便地访问链表的第一个节点，从而实现对整个链表的遍历和操作。
- 例如，要遍历链表，可以从listHead开始，依次跟随每个节点的next指针，直到到达链表的末尾（即next指针为nullptr）。
Node<type>* listEnd：尾节点
- 同样是一个指向Node<type>类型对象的指针，它指向链表的最后一个节点。
- 维护这个指针可以在一些操作中提供便利，例如在链表尾部进行插入操作时，可以直接通过listEnd快速找到链表的末尾，而无需遍历整个链表。
- 此外，在某些情况下，需要知道链表的最后一个节点，例如在一些算法中需要从链表的末尾开始处理数据。
int size：节点数量
- 这是一个整数变量，用于记录链表中节点的数量。
- 维护链表的大小信息可以在很多情况下提高效率。例如，当需要判断链表是否为空时，可以直接检查size是否为 0，而不需要检查listHead是否为nullptr。
- 在一些操作中，可能需要知道链表的长度，如在某些循环中根据链表的大小进行特定次数的操作。

这些保护成员共同构成了链表的核心数据结构，通过合理地使用和管理这些成员，可以实现高效的链表操作和管理。

码农公寓