C++中的链表实现 |21xrx.com

C++中的链表实现

2023-07-04 20:18:04 深夜i 10 0

C++ 链表实现

C++是一门面向对象编程语言，其数据结构方面的支持非常强大。其中，链表也是一种常见的数据结构，它可以用于在程序中存储和组织大量的数据。下面，本文将介绍如何在C++中使用链表实现数据的存储和操作。

链表是由一组节点组成的数据结构，每个节点都包含了一个存储的数据和一个指向下一个节点的指针。在C++中，我们可以使用class或struct来定义一个链表节点。例如：

struct ListNode {
  int val; // 存储的数据
  ListNode *next; // 指向下一个节点
  ListNode(int x) : val(x), next(NULL) {}
};

上面的代码定义了一个名为ListNode的结构体，其包含了一个整型变量val和一个指向下一个节点的指针next。

接下来，我们可以定义一个链表类，用于存储和操作链表。因为链表是一种动态的数据结构，所以我们需要维护链表的头节点和尾节点，并提供一些基本的操作方法，如添加节点、删除节点和遍历节点。以下是一个简单的链表类的定义：

class LinkedList {
public:
  LinkedList();
  ~LinkedList();
  void addNode(int val); // 添加节点
  void deleteNode(int val); // 删除值为val的节点
  void traverse(); // 遍历链表
private:
  ListNode *head; // 链表头节点
  ListNode *tail; // 链表尾节点
};

在上面的代码中，我们定义了一个名为LinkedList的类，并声明了三个公共方法：addNode、deleteNode和traverse。其中，addNode方法用于向链表中添加一个节点，deleteNode方法用于删除值为val的节点，traverse方法用于遍历链表。另外，我们还声明了两个私有成员变量：head和tail，用于保存链表的头节点和尾节点。

接下来，我们可以实现这些方法。首先是addNode方法：

void LinkedList::addNode(int val) {
  ListNode *node = new ListNode(val);
  if (head == NULL)
    head = node;
    tail = node;
   else
    tail->next = node;
    tail = node;
  
}

在这个方法中，我们首先创建一个新的节点，并将其赋值给变量node。接着，我们判断链表是否为空，如果是，则将头节点和尾节点都设置为当前节点；否则，将当前节点添加到链表的尾部，并将尾节点更新为当前节点。

接着是deleteNode方法：

void LinkedList::deleteNode(int val) {
  ListNode *cur = head;
  ListNode *prev = NULL;
  while (cur != NULL) {
    if (cur->val == val) {
      if (prev == NULL)
        head = cur->next;
       else
        prev->next = cur->next;
      
      if (tail == cur)
        tail = prev;
      
      delete cur;
      return;
    }
    prev = cur;
    cur = cur->next;
  }
}

在这个方法中，我们首先遍历整个链表，查找要删除的节点。如果找到了目标节点，则将其从链表中删除，并释放其空间。在删除过程中，还需要维护头节点和尾节点的指针。

最后是traverse方法：

void LinkedList::traverse() {
  ListNode *cur = head;
  while (cur != NULL)
    cout << cur->val << " ";
    cur = cur->next;
  
  cout << endl;
}

在这个方法中，我们遍历整个链表，并打印每个节点的值。当遍历完所有节点后，我们输出一个换行符，方便下一次输出。

到这里，我们已经可以使用C++中的链表实现数据的存储和操作了。以下是一个使用示例：

LinkedList list;
list.addNode(1);
list.addNode(2);
list.addNode(3);
list.addNode(4);
list.addNode(5);
list.traverse(); // 输出：1 2 3 4 5
list.deleteNode(3);
list.traverse(); // 输出：1 2 4 5

上面的代码创建了一个名为list的LinkedList对象，并往其中添加了五个节点。接着，我们遍历了整个链表，并输出了它的值。然后，我们删除了值为3的节点，再次遍历链表，可以发现值为3的节点已经被成功删除。

总结来说，C++中的链表是一种非常灵活和实用的数据结构，它可以用于数据的存储和组织，还可以用于算法和数据结构的练习。在使用链表时，需要注意指针的使用和空指针的处理，以免出现运行时错误。

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

下一篇: Java的颜文字表情大全

评论区

相似文章