如何在C++中实现链表的初始化、增加、删除、查询和修改功能？ |21xrx.com

如何在C++中实现链表的初始化、增加、删除、查询和修改功能？

2023-06-24 19:02:01 深夜i -- --

链表初始化增加删除查询修改 C++

在C++中，链表是一种非常基础且常见的数据结构，被广泛应用于各种算法和程序设计中。下面将介绍如何在C++中实现链表的初始化、增加、删除、查询和修改功能。

1. 链表的初始化

链表的初始化通常需要定义一个链表的头结点和一个指向头结点的指针。首先使用new关键字动态分配内存空间，然后将头结点的值设置为0或者NULL，最后将指向头结点的指针指向链表的头结点即可。


struct ListNode{
  int val;
  ListNode* next;
  ListNode(int x): val(x), next(nullptr){};
};
class LinkedList{
public:
  ListNode* head;
  LinkedList(){
    head = new ListNode(0);
    head->next = nullptr;
  }
};

2. 链表的增加

链表的增加操作通常包括在链表的末尾添加一个新节点、在链表的开头添加一个新节点、在链表的中间添加一个新节点等。在下面的示例中，我们将演示如何在链表的末尾添加一个新节点。

首先，我们需要遍历整个链表，找到链表的末尾节点。然后，使用new关键字动态分配内存空间，创建一个新节点，并将该节点的值设置为需要添加的值。最后，将链表的末尾节点的next指针指向新节点即可完成链表的添加操作。


void addNode(ListNode* head, int val){
  ListNode* newNode = new ListNode(val);
  ListNode* p = head;
  while(p->next != nullptr)
    p = p->next;
  p->next = newNode;
}

3. 链表的删除

链表的删除操作通常包括删除指定位置的节点、删除链表中某个特定值的节点等。在下面的示例中，我们将演示如何删除链表中某个特定值的节点。

首先，我们需要遍历整个链表，找到需要删除的节点的前一个节点。然后，将需要删除的节点的next指针保存到一个临时变量中，以便最后将链表重新连接起来。最后，释放需要删除的节点的内存空间，重新连接链表即可完成链表的删除操作。


void deleteNode(ListNode* head, int val) {
  ListNode* p = head;
  while(p->next != nullptr){
    if(p->next->val == val){
      ListNode* temp = p->next;
      p->next = p->next->next;
      delete temp;
      return;
    }
    p = p->next;
  }
}

4. 链表的查询

链表的查询操作通常包括根据节点位置查询节点的值、查询链表中是否存在某个特定值的节点等。在下面的示例中，我们将演示如何查询链表中是否存在某个特定值的节点。

首先，我们需要遍历整个链表，查找指定值的节点。如果找到了需要查找的节点，则返回该节点的值；否则，返回特定的错误码（例如-1）。


int searchNode(ListNode* head, int val){
  ListNode* p = head;
  while(p->next != nullptr){
    if(p->next->val == val)
      return p->next->val;
    p = p->next;
  }
  return -1;
}

5. 链表的修改

链表的修改操作通常包括根据节点位置修改节点的值。在下面的示例中，我们将演示如何根据节点位置修改节点的值。

首先，我们需要遍历整个链表，找到需要修改的节点。然后，将该节点的值修改为需要修改的值即可完成链表的修改操作。


void modifyNode(ListNode* head, int pos, int val){
  ListNode* p = head->next;
  for(int i = 1; i < pos; i++)
    p = p->next;
  
  p->val = val;
}

到此为止，我们已经了解了如何在C++中实现链表的初始化、增加、删除、查询和修改功能。不过需要注意的是，链表内存分配和释放的问题比较敏感，建议使用动态分配内存空间，确保内存分配和释放的正确性。

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

下一篇: 如何在C++中将数组传递给函数？

评论区

()

相似文章