c++实现单链表源代码

在C++编程中，单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和指向下一个节点的指针。本教程将详细解释如何使用C++实现单链表，包括链表的基本操作，如插入、删除、遍历等。 我们需要定义一个链表节点的结构体或类。在C++中，由于模板的强大功能，我们可以创建一个泛型链表节点，可以存储任何类型的数据。模板声明如下： ```cpp template <typename T> struct ListNode { T data; // 存储数据 ListNode<T>* next; // 指向下一个节点的指针 }; ``` 接下来，我们需要创建一个表示链表的类，包含一些基本操作。这个类通常包含头节点和链表的大小： ```cpp template <typename T> class LinkedList { private: ListNode<T>* head; // 链表的头节点 int size; // 链表的大小 public: // 构造函数和析构函数 LinkedList() : head(nullptr), size(0) {} ~LinkedList() { clear(); } // 链表操作 void insertAtFront(T value); // 在链表前端插入元素 void insertAtEnd(T value); // 在链表尾部插入元素 void deleteNode(T value); // 删除具有特定值的节点 void display(); // 显示链表中的所有元素 void clear(); // 清空链表 }; ``` 这些成员函数的实现如下： 1. `insertAtFront`：在链表开头插入新节点。 ```cpp void LinkedList<T>::insertAtFront(T value) { ListNode<T>* newNode = new ListNode<T>{value, head}; head = newNode; size++; } ``` 2. `insertAtEnd`：在链表尾部插入新节点，需要遍历链表找到最后一个节点。 ```cpp void LinkedList<T>::insertAtEnd(T value) { ListNode<T>* newNode = new ListNode<T>{value, nullptr}; if (head == nullptr) { head = newNode; } else { ListNode<T>* current = head; while (current->next != nullptr) { current = current->next; } current->next = newNode; } size++; } ``` 3. `deleteNode`：删除具有特定值的节点。此操作可能需要遍历链表并更新指针。 ```cpp void LinkedList<T>::deleteNode(T value) { ListNode<T>* current = head; ListNode<T>* previous = nullptr; while (current != nullptr && current->data != value) { previous = current; current = current->next; } if (current == nullptr) return; // 如果找不到要删除的节点 if (previous == nullptr) { head = current->next; // 删除头节点 } else { previous->next = current->next; } delete current; size--; } ``` 4. `display`：打印链表中的所有元素。 ```cpp void LinkedList<T>::display() { ListNode<T>* temp = head; while (temp != nullptr) { std::cout << temp->data << " -> "; temp = temp->next; } std::cout << "nullptr" << std::endl; } ``` 5. `clear`：释放链表中的所有节点内存并设置链表为空。 ```cpp void LinkedList<T>::clear() { ListNode<T>* current = head; while (current != nullptr) { ListNode<T>* toDelete = current; current = current->next; delete toDelete; } head = nullptr; size = 0; } ``` 以上就是使用C++实现单链表的基本步骤。通过这个实现，我们可以创建和操作包含各种类型数据的链表。在实际项目中，还可以添加更多的功能，如查找节点、反转链表、合并两个已排序的链表等。通过理解和熟练掌握单链表，可以为更复杂的数据结构和算法打下坚实的基础。