C++类模板实现单链表 |21xrx.com

C++类模板实现单链表

2023-07-09 04:07:26 深夜i 8 0

C++ 类模板单链表实现

单链表是一种常见的数据结构，可以实现对数据的快速插入和删除。在C++中，可以使用类模板来实现单链表的定义和操作。

1. 定义链表节点

链表节点是链表的基本单位，它可以包含任何类型的数据。定义一个链表节点的类模板如下：

template <typename T>
class ListNode {
public:
  T data; // 节点数据
  ListNode* next; // 下一个节点指针
  ListNode(T data) : data(data), next(nullptr) {} // 构造函数
};

这里使用了模板类型参数T，表示节点数据的类型。节点包含数据成员data和指向下一个节点的指针成员next。构造函数用于初始化节点的数据和指针值。

2. 定义链表类

链表类可以包含头节点指针和一些操作函数，如插入节点、删除节点和查找节点。定义链表类的类模板如下：

template <typename T>
class LinkedList {
private:
  ListNode<T>* head; // 链表头指针
public:
  LinkedList() : head(nullptr) {} // 构造函数
  ~LinkedList(); // 析构函数
  void insert(T data); // 插入节点
  void remove(T data); // 删除节点
  bool search(T data); // 查找节点
};

链表类中包含了一个私有成员head，表示链表的头节点指针。构造函数用于初始化头节点指针。析构函数用于释放链表中所有节点的内存。

3. 实现链表类

链表的插入节点、删除节点和查找节点操作可以通过遍历链表来实现。具体实现如下：

template <typename T>
LinkedList<T>::~LinkedList() {
  ListNode<T>* p = head;
  while (p != nullptr) {
    ListNode<T>* q = p;
    p = p->next;
    delete q;
  }
}
template <typename T>
void LinkedList<T>::insert(T data) {
  ListNode<T>* node = new ListNode<T>(data);
  if (head == nullptr)
    head = node;
   else {
    ListNode<T>* p = head;
    while (p->next != nullptr)
      p = p->next;
    
    p->next = node;
  }
}
template <typename T>
void LinkedList<T>::remove(T data) {
  if (head == nullptr)
    return;
  
  if (head->data == data) {
    ListNode<T>* p = head;
    head = head->next;
    delete p;
    return;
  }
  ListNode<T>* p = head;
  while (p->next != nullptr && p->next->data != data)
    p = p->next;
  
  if (p->next != nullptr) {
    ListNode<T>* q = p->next;
    p->next = q->next;
    delete q;
  }
}
template <typename T>
bool LinkedList<T>::search(T data) {
  ListNode<T>* p = head;
  while (p != nullptr) {
    if (p->data == data)
      return true;
    
    p = p->next;
  }
  return false;
}

这里使用了C++的动态内存分配和释放，需要注意避免内存泄漏。插入节点操作需要判断链表是否为空，删除节点操作需要判断要删除的节点是否为头节点，查找节点操作需要遍历整个链表进行查找。

4. 使用链表类

使用链表类需要先实例化一个对象，然后调用需要的函数进行操作。例如：

LinkedList<int> list;
list.insert(1);
list.insert(2);
list.insert(3);
list.remove(2);
bool found = list.search(3);

这里使用int作为节点数据类型，插入了三个节点，删除了值为2的节点，并查找值为3的节点。

总结

C++类模板是实现单链表的一种有效方式。通过定义链表节点和链表类，可以方便地实现对数据的插入、删除和查找操作。在使用时需要注意避免内存泄漏等问题。

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

下一篇: C++：一个好的数据库开发语言选择？

评论区

相似文章