C++链表操作指南 |21xrx.com

C++链表操作指南

2023-07-14 04:19:04 深夜i -- --

C++ 链表操作指南

链表是一种常用的数据结构，具有动态性和灵活性，在 C++ 中操作链表可以帮助我们更加高效地处理数据。本指南将向您介绍 C++ 中链表的基本原理及其各种操作方法。

链表的定义

首先要了解链表的结构。链表由许多节点（Node）构成，每个节点都包括两个部分，一个是数据（Data），另一个是指针（Pointer），指向下一个节点。可以使用 C++ 中的类（Class）来定义节点，例如：


class Node {
public:
  int data;
  Node* next;
  Node(int d) : data(d), next(nullptr) {}
};

上述代码中，定义了一个名为 Node 的类，该类包含了两个成员变量 data 和 next，前者可以存储该节点所代表的数据，后者是一个指针，指向下一个节点。

链表的基本操作

在 C++ 中定义好链表的结构之后，我们可以通过各种方法来操作链表，以下是一些基本操作：

1. 插入操作

插入操作可分为三种情况：

（1）在链表头部插入节点；

（2）在链表中间插入节点；

（3）在链表尾部插入节点。


// 在链表头部插入节点
void insertAtHead(Node*& head, int val) {
  Node* new_node = new Node(val);
  new_node->next = head;
  head = new_node;
}
// 在链表中间插入节点
void insertAfter(Node* prev_node, int val) {
  if (prev_node == nullptr) return;
  Node* new_node = new Node(val);
  new_node->next = prev_node->next;
  prev_node->next = new_node;
}
// 在链表尾部插入节点
void insertAtTail(Node*& head, int val) {
  Node* new_node = new Node(val);
  if (head == nullptr)
    head = new_node;
    return;
  
  Node* curr_node = head;
  while (curr_node->next != nullptr)
    curr_node = curr_node->next;
  
  curr_node->next = new_node;
}

2. 删除操作

在链表中删除一个特定的节点需要了解该节点的前一个节点（prev_node），通过 prev_node 操作实现删除。


void deleteNode(Node*& head, int val) {
  Node* curr_node = head;
  if (curr_node != nullptr && curr_node->data == val)
    head = head->next;
    delete curr_node;
    return;
  
  while (curr_node != nullptr && curr_node->data != val)
    curr_node = curr_node->next;
  
  if (curr_node == nullptr) return;
  Node* prev_node = head;
  while (prev_node->next != curr_node)
    prev_node = prev_node->next;
  
  prev_node->next = curr_node->next;
  delete curr_node;
}

3. 查找操作

查找链表中是否存在某个特定值，或查找链表中某个元素的位置。


// 查找链表中是否存在值为 val 的节点
bool searchNode(Node* head, int val) {
  while (head != nullptr) {
    if (head->data == val) return true;
    head = head->next;
  }
  return false;
}
// 查找链表中值为 val 的节点的位置，若不存在返回 -1
int searchIndex(Node* head, int val) {
  int index = 0;
  while (head != nullptr) {
    if (head->data == val) return index;
    head = head->next;
    ++index;
  }
  return -1;
}

4. 反转链表

将链表倒转。


void reverseList(Node*& head) {
  Node* prev_node = nullptr;
  Node* curr_node = head;
  Node* next_node = nullptr;
  while (curr_node != nullptr)
    next_node = curr_node->next;
    curr_node->next = prev_node;
    prev_node = curr_node;
    curr_node = next_node;
  
  head = prev_node;
}

以上为常用的链表操作，这些操作可以满足大部分例子的需求。在实际使用中，也可以根据具体情况设计自定义的操作方法。

总结

通过上述介绍，相信您已经对 C++ 中链表的操作有了基本的了解。链表虽然相对于数组在一些特定场合下存在劣势，但是在其它一些情况下却显得灵活和便捷，为程序员开发提供更多的选择。

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

下一篇: C++数据结构课程设计：简单易懂

评论区

()

相似文章