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

C++语言实现链表数据结构

2023-07-04 19:20:21 深夜i -- --

C++ 链表数据结构实现

链表是一种非常重要的数据结构，在C++语言中，实现链表同样也是非常重要的知识点。链表是一种动态数据结构，它可以随着程序的运行动态地增删节点。相比于数组，链表的灵活性更高，但是在访问节点时会牺牲一点效率。

链表的实现方法有很多种，最常用的是单向链表和双向链表。这里我们重点介绍一下单向链表的实现方法。一个单向链表由若干个节点组成，每个节点包括两个部分：一个数据域和一个指向下一个节点的指针。

在C++语言中，我们可以通过定义一个结构体来表示一个节点。代码如下所示：


struct ListNode {
  int val;
  ListNode* next;
  ListNode(int x) : val(x), next(NULL) {}
};

其中，val表示节点存储的数据，next表示指向下一个节点的指针。构造函数中的初始化列表可以用来完成节点的初始化操作。

接下来，我们需要定义链表类。链表类包含若干个操作函数，比如添加节点、删除节点、查找节点等。下面是一个简单的链表类实现：


class LinkedList {
public:
  LinkedList()
    head = NULL;
  
  void addNode(int val) {
    ListNode* node = new ListNode(val);
    if (head == NULL)
      head = node;
     else {
      ListNode* cur = head;
      while (cur->next != NULL)
        cur = cur->next;
      
      cur->next = node;
    }
  }
  void 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;
        
        delete cur;
        return;
      }
      prev = cur;
      cur = cur->next;
    }
  }
  ListNode* findNode(int val) {
    ListNode* cur = head;
    while (cur != NULL) {
      if (cur->val == val)
        return cur;
      
      cur = cur->next;
    }
    return NULL;
  }
private:
  ListNode* head;
};

在这个链表类中，我们实现了添加节点、删除节点、查找节点等操作。其中，节点的添加和查找都是遍历节点，删除节点时需要进行指针的重新连接。

最后，我们可以通过下面的代码来测试我们的链表类：


int main() {
  LinkedList list;
  list.addNode(1);
  list.addNode(2);
  list.addNode(3);
  list.deleteNode(2);
  ListNode* node = list.findNode(3);
  return 0;
}

通过上述代码，我们可以清晰地看到链表的各种操作是如何实现的。

综上所述，链表是一种非常重要的数据结构，C++语言对链表的实现同样也是非常重要的知识点。通过本文的介绍，我们可以了解到链表的基本概念，以及如何使用C++语言来实现链表数据结构。

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

下一篇: C++大数据处理技术

评论区

()

相似文章