C++ 创造链表类 |21xrx.com

C++ 创造链表类

2023-07-06 13:31:42 深夜i -- --

C++ 链表类创建节点

C++语言中，链表是一种非常常见且重要的数据结构。实现一个链表类可以实现链表的常见操作，比如查找、插入、删除等。下面是使用C++语言实现一个链表类的基本步骤。

1. 定义链表节点类

链表节点类包括两个成员，一个是数据成员，用于存储节点中的数据；另一个是指向下一个节点的指针。


class ListNode {
public:
  int val;
  ListNode* next;
  ListNode(int data) : val(data), next(nullptr) {}
};

2. 定义链表类

定义链表类可以包括链表头节点，也可以不包括链表头节点。在本文中，我们定义一个链表类不包括头节点，且提供了一些基本的链表操作。


class LinkedList {
public:
  LinkedList();
  ~LinkedList();
  void addNode(int val); // 添加节点
  void deleteNode(int val); // 删除节点
  ListNode* findNode(int val); // 查找节点
  void display(); // 输出链表
private:
  ListNode* head; // 链表头
};

3. 实现链表类的成员函数

在链表类的实现中，我们需要实现各种基本操作的具体实现。


// 添加节点
void LinkedList::addNode(int val) {
  ListNode* newNode = new ListNode(val); // 创建新节点
  if (head == nullptr)
    head = newNode; // 链表为空
  
  else {
    ListNode* cur = head;
    while (cur->next != nullptr)
      cur = cur->next;
    
    cur->next = newNode;
  }
}
// 删除节点
void LinkedList::deleteNode(int val) {
  if (head == nullptr)
    return; // 链表为空
  
  if (head->val == val) {
    ListNode* temp = head;
    head = head->next;
    delete temp;
    return;
  }
  ListNode* cur = head->next;
  ListNode* prev = head;
  while (cur != nullptr) {
    if (cur->val == val)
      prev->next = cur->next;
      delete cur;
      break;
    
    prev = cur;
    cur = cur->next;
  }
}
// 查找节点
ListNode* LinkedList::findNode(int val) {
  ListNode* cur = head;
  while (cur != nullptr) {
    if (cur->val == val)
      return cur;
    
    cur = cur->next;
  }
  return nullptr;
}
// 输出链表
void LinkedList::display() {
  ListNode* cur = head;
  while (cur != nullptr)
    cout << cur->val << " ";
    cur = cur->next;
  
  cout << endl;
}
// 构造函数
LinkedList::LinkedList()
  head = nullptr;
// 析构函数
LinkedList::~LinkedList() {
  ListNode* cur = head;
  while (cur != nullptr) {
    ListNode* temp = cur;
    cur = cur->next;
    delete temp;
  }
}

4. 测试链表类

我们可以使用下面的代码测试链表类的各种操作。


int main() {
  LinkedList ll;
  ll.addNode(1);
  ll.addNode(2);
  ll.addNode(3);
  ll.deleteNode(1);
  ll.display();
  ListNode* node = ll.findNode(3);
  if (node != nullptr)
    cout << "find node " << node->val << endl;
  
  return 0;
}

　　通过上面的代码可以看到，实现一个链表类并不是很难，但对于理解链表基本操作和数据结构的意义却非常有帮助。

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

下一篇: 如何定义C++运算符

评论区

()

相似文章