C++单链表的基本操作 |21xrx.com

C++单链表的基本操作

2023-07-07 13:58:26 深夜i -- --

C++ 单链表基本操作

C++单链表是一种非常常见的数据结构，它由多个节点组成，每个节点都包含数据域和指向下一个节点的指针域。在C++中，我们可以通过定义结构体或类来构建单链表。本文将介绍C++单链表的基本操作。

1. 定义节点结构体或类

在C++中定义单链表，首先需要定义节点的结构体或类。结构体可以使用以下代码来定义：

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

如果使用类来定义，则可以使用以下代码：

class ListNode {
public:
  int val; // 存储节点数据
  ListNode *next; // 指向下一个节点的指针
  ListNode(int x) : val(x), next(NULL) {} // 构造函数
};

2. 创建单链表

单链表的创建需要动态申请内存，可以使用new运算符来实现。可以定义一个函数来创建单链表：

ListNode* createLinkedList(vector<int>& nums) {
  ListNode* head = new ListNode(0); // 创建头节点
  ListNode* cur = head; // 指向当前节点
  for(int i = 0; i < nums.size(); i++) {
    ListNode* node = new ListNode(nums[i]); // 创建新节点
    cur->next = node; // 当前节点指向新节点
    cur = cur->next; // 当前节点移动到新节点
  }
  return head->next; // 返回头节点的下一个节点
}

其中，vector & nums为传入的整数数组，可以根据需要改变参数类型。

3. 遍历单链表

单链表遍历需要使用循环操作，可以定义一个函数来实现：

void traverseLinkedList(ListNode* head) {
  while(head != NULL)
    cout << head->val << " "; // 输出节点的值
    head = head->next; // 指向下一个节点
  
}

4. 插入节点

单链表插入节点需要注意插入位置和节点的指针指向，可以定义一个函数来实现：

void insertLinkedList(ListNode* head, int pos, int val) {
  ListNode* cur = head; // 指向当前节点
  for(int i = 0; i < pos - 1; i++)
    cur = cur->next; // 移动到插入位置的前一个节点
  
  ListNode* node = new ListNode(val); // 创建新节点
  node->next = cur->next; // 新节点指向下一个节点
  cur->next = node; // 前一个节点指向新节点
}

其中，pos为插入的位置，可以根据需要改变参数类型。

5. 删除节点

单链表删除节点需要注意删除位置和节点的指针指向，可以定义一个函数来实现：

void deleteLinkedList(ListNode* head, int pos) {
  ListNode* cur = head; // 指向当前节点
  for(int i = 0; i < pos - 1; i++)
    cur = cur->next; // 移动到删除位置的前一个节点
  
  ListNode* temp = cur->next; // 记录当前节点的下一个节点
  cur->next = temp->next; // 当前节点指向下一个节点的下一个节点
  delete temp; // 释放内存
}

其中，pos为删除的位置，可以根据需要改变参数类型。

通过上述基本操作，C++单链表的构建和管理得以实现，灵活运用可以为程序的设计提供更多便利和可扩展性。

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

下一篇: 微软推出 C++ 2022！

评论区

相似文章