用C++构建链表及实现功能 |21xrx.com

用C++构建链表及实现功能

2023-06-28 05:39:41 深夜i 14 0

C++ 链表构建实现功能

链表是一种常见的数据结构，它由一个节点序列组成，每个节点包含两个部分，一部分是数据，一部分是指向下一个节点的指针。链表相较于数组而言，具有动态性和灵活性，因此非常适合在需要频繁插入、删除、修改元素的场景下使用。在本文中，将介绍如何使用C++构建链表，并实现常用的功能。

1. 构建链表

以下是链表节点的定义：

struct Node {
  int data; // 数据
  Node* next; // 指向下一个节点的指针
};

链表的头节点可以用一个指针来表示：

Node* head = nullptr;

当链表为空时，头节点指向nullptr。链表中的节点可以通过new运算符动态地创建：

Node* node = new Node;

为了方便起见，这里我们提供一个可以根据输入数据创建链表的函数：

void CreateList(Node*& head) {
  head = new Node;
  int data;
  std::cout << "请输入链表中的数据，输入 -1 结束：" << std::endl;
  std::cin >> data;
  Node* p = head;
  while (data != -1) {
    Node* node = new Node;
    node->data = data;
    node->next = nullptr;
    p->next = node;
    p = p->next;
    std::cin >> data;
  }
}

2. 遍历链表

遍历链表即访问链表中的每个节点并对其进行操作。可以通过while循环实现。以下是遍历链表的代码：

void TraverseList(Node* head) {
  if (head == nullptr)
    std::cout << "链表为空" << std::endl;
    return;
  
  Node* p = head->next;
  while (p != nullptr)
    std::cout << p->data << " ";
    p = p->next;
  
  std::cout << std::endl;
}

其中，head为链表的头节点。

3. 插入节点

在链表中插入一个节点，需要先找到要插入节点的前驱节点。然后，将前驱节点的指针指向新节点，新节点的指针指向后继节点。以下是代码：

void InsertNode(Node*& head, int data, int pos) {
  Node* node = new Node;
  node->data = data;
  node->next = nullptr;
  if (head == nullptr)
    head = node;
    return;
  
  Node* p = head;
  int i = 1;
  while (p->next != nullptr && i < pos) {
    p = p->next;
    i++;
  }
  if (i == pos)
    node->next = p->next;
    p->next = node;
   else
    std::cout << "插入失败
}

其中，head为链表的头节点，data为要插入的数据，pos为要插入的位置。

4. 删除节点

在链表中删除一个节点，需要先找到要删除节点的前驱节点，并将前驱节点的指针指向后继节点。以下是代码：

void DeleteNode(Node*& head, int pos) {
  if (head == nullptr) 无法删除" << std::endl;
    return;
  
  Node* p = head;
  int i = 1;
  while (p->next != nullptr && i < pos) {
    p = p->next;
    i++;
  }
  if (i == pos && p->next != nullptr) {
    Node* q = p->next;
    p->next = p->next->next;
    delete q;
  } else 位置超出范围" << std::endl;
  
}

其中，head为链表的头节点，pos为要删除节点的位置。

5. 修改节点

在链表中修改一个节点，需要先找到要修改节点的位置，并将其数据改为指定的值。以下是代码：

void ModifyNode(Node* head, int data, int pos) {
  if (head == nullptr)
    std::cout << "链表为空" << std::endl;
    return;
  
  Node* p = head->next;
  int i = 1;
  while (p != nullptr && i < pos) {
    p = p->next;
    i++;
  }
  if (i == pos)
    p->data = data;
   else 位置超出范围" << std::endl;
  
}

其中，head为链表的头节点，data为要修改的数据，pos为要修改节点的位置。

综上所述，C++语言中的链表是一种非常有用的数据结构。通过上述方法，我们可以轻松地构建链表，并实现链表的各种功能。既可以用于学习，也可以用于实际开发。

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

下一篇: 如何使用VC++编写程序

评论区

相似文章