C++如何创建和遍历链表 |21xrx.com

C++如何创建和遍历链表

2023-07-05 05:45:00 深夜i 9 0

C++ 创建遍历链表

C++语言中，链表是一种常用的数据结构。链表可以实现动态的存储和查找数据，常用在操作系统、数据库和网络等方面。本文将详细介绍如何创建和遍历链表。

一、链表的概念

链表是由若干个节点连接而成的线性结构，每个节点包含两部分：数据部分和指针部分。数据部分用于存储用户数据，指针部分用于指向下一个节点的地址，实现链表的连接。

链表有单向链表和双向链表两种形式。单向链表是指链表中每个节点只包含一个指针，指向下一个节点。双向链表是指链表中每个节点包含两个指针，分别指向上一个节点和下一个节点。

二、链表的创建

链表的创建需要先定义节点结构体，然后按照序列把节点连接起来。

结构体定义：

struct Node {
  int val;
  Node* next;
  Node(int x) : val(x), next(nullptr) {}
};

节点的指针类型为 `Node*`，表示指向节点的地址。`next`指针用于指向下一个节点的地址。

单向链表创建：

Node* createLinkedList(vector<int>& nums) {
  Node* head = nullptr;
  Node* tail = nullptr;
  for (int i = 0; i < nums.size(); ++i) {
    if (head == nullptr) {
      head = new Node(nums[i]);
      tail = head;
    } else {
      tail->next = new Node(nums[i]);
      tail = tail->next;
    }
  }
  return head;
}

双向链表创建：

struct DoubleNode {
  int val;
  DoubleNode* prev;
  DoubleNode* next;
  DoubleNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};
DoubleNode* createDoubleLinkedList(vector<int>& nums) {
  DoubleNode* head = nullptr;
  DoubleNode* tail = nullptr;
  for (int i = 0; i < nums.size(); ++i) {
    if (head == nullptr) {
      head = new DoubleNode(nums[i]);
      tail = head;
    } else {
      tail->next = new DoubleNode(nums[i]);
      tail->next->prev = tail;
      tail = tail->next;
    }
  }
  return head;
}

三、链表的遍历

链表遍历是指对链表中每个节点进行访问，输出节点数据。遍历链表有两种方法：迭代和递归。

单向链表迭代遍历：

void traverseLinkedList(Node* head) {
  while (head != nullptr)
    cout << head->val << " ";
    head = head->next;
  
}

单向链表递归遍历：

void traverseLinkedList(Node* head) {
  if (head == nullptr) return;
  cout << head->val << " ";
  traverseLinkedList(head->next);
}

双向链表迭代遍历：

void traverseDoubleLinkedList(DoubleNode* head) {
  while (head != nullptr)
    cout << head->val << " ";
    head = head->next;
  
}

双向链表递归遍历：

void traverseDoubleLinkedList(DoubleNode* head) {
  if (head == nullptr) return;
  cout << head->val << " ";
  traverseDoubleLinkedList(head->next);
}

以上是C++中创建和遍历链表的方法，可以根据需要选择单向链表或双向链表及迭代或递归遍历方式。使用链表可以有效地存储和查找数据，是编程中不可或缺的一部分。

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

下一篇: C++中如何表示10的-5次方？

评论区

相似文章