C++实现单链表数据结构 |21xrx.com

C++实现单链表数据结构

2023-07-05 12:30:47 深夜i -- --

C++ 单链表数据结构链表节点链表操作

单链表是一种常用的数据结构，可以用来存储和管理一系列数据。C++作为一种面向对象的编程语言，在实现单链表时也可以利用其面向对象的特性，使得代码更加清晰、易于理解。下面我们将介绍如何用C++实现单链表数据结构。

1. 定义节点类

在单链表中，每个元素都是一个节点，每个节点中包含两个部分：一个数据部分和一个指向下一个节点的指针。因此，我们可以定义一个节点类来表示每一个节点。


template<typename T>
class Node {
public:
  T data;      // 数据域
  Node<T>* next;   // 指针域
  
  Node(): next(nullptr) {};   // 构造函数
  Node(T value): data(value), next(nullptr) {};
};

在上述代码中，我们使用了模板类，这样在实例化节点时可以传入不同类型的值。例如，我们可以使用`Node `来表示一个整数类型的节点，使用`Node `来表示一个字符串类型的节点。

另外，我们还定义了一个空的构造函数和一个只包含数据初始化的构造函数，方便创建节点实例时使用。

2. 定义链表类

在定义完节点类之后，我们需要定义一个链表类来实现单链表。链表类中包含一个头节点作为链表的起始节点，以及一些对链表进行操作的函数。


template<typename T>
class LinkedList {
private:
  Node<T>* head;  // 头节点指针
  int size;     // 链表大小
public:
  LinkedList(): head(nullptr), size(0) {};  // 构造函数
  ~LinkedList();               // 析构函数
  
  void insert(T value);   // 在链表头插入元素
  void append(T value);   // 在链表尾插入元素
  void remove(T value);   // 删除一个元素
  void traverse();      // 遍历链表
};

除了头节点指针和链表大小外，我们还定义了构造函数和析构函数，以及插入、删除、遍历等操作的函数。

3. 插入操作

链表插入操作分为两种，一种是在头部插入元素，另一种是在尾部插入元素。两者实现方式略有不同。

在头部插入元素时，只需要将头节点指针指向新的节点，然后将新的节点指向原本的头节点即可。


template<typename T>
void LinkedList<T>::insert(T value) {
  Node<T>* node = new Node<T>(value);
  node->next = head;
  head = node;
  size++;
}

在尾部插入元素时，需要遍历整个链表找到最后一个节点，然后将最后一个节点的指针指向新的节点。


template<typename T>
void LinkedList<T>::append(T value) {
  Node<T>* node = new Node<T>(value);
  if (head == nullptr)
    head = node;
   else {
    Node<T>* tail = head;
    while (tail->next != nullptr)
      tail = tail->next;
    
    tail->next = node;
  }
  size++;
}

4. 删除操作

链表删除操作是通过遍历整个链表找到需要删除的节点，然后将指向该节点的指针指向该节点的下一个节点即可。


template<typename T>
void LinkedList<T>::remove(T value) { 
  Node<T>* current = head;
  Node<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--;
}

5. 遍历操作

链表遍历操作是遍历整个链表并输出各个节点的数据。


template<typename T>
void LinkedList<T>::traverse() {
  Node<T>* current = head;
  while (current != nullptr)
    cout << current->data << " ";
    current = current->next;
  
  cout << endl;
}

6. 析构函数

链表在销毁时需要将链表中所有节点都进行释放。


template<typename T>
LinkedList<T>::~LinkedList() {
  Node<T>* current = head;
  while (current != nullptr) {
    Node<T>* next = current->next;
    delete current;
    current = next;
  }
  head = nullptr;
  size = 0;
}

以上就是用C++实现单链表数据结构的所有内容。通过使用模板类，我们可以定义不同类型的节点来满足各种需求，在每个节点中包含数据和指针，方便进行各种操作。相信通过这篇文章的介绍，你也能够理解和掌握单链表的原理和实现方法了。

上一篇: idea打包java可执行jar包

下一篇: 如何用C++判断操作系统类型

评论区

()

相似文章