21xrx.com
2024-11-05 17:33:08 Tuesday
登录
文章检索 我的文章 写文章
C++类模板实现单链表
2023-07-09 04:07:26 深夜i     --     --
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++类模板是实现单链表的一种有效方式。通过定义链表节点和链表类,可以方便地实现对数据的插入、删除和查找操作。在使用时需要注意避免内存泄漏等问题。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复