C++实现单向动态链表 |21xrx.com

C++实现单向动态链表

2023-07-06 18:05:28 深夜i -- --

C++ 单向链表动态链表

C++是一种高级编程语言，可以用来实现各种数据结构和算法。其中，单向动态链表是一种常见的数据结构，可以存储不同类型的数据，并且可以进行快速的插入、删除和查询操作。本文将介绍如何使用C++语言实现单向动态链表。

基本概念

在开始实现单向动态链表之前，我们需要了解一些基本概念。首先，链表由节点(node)组成，每个节点包括两个部分：存储数据的元素(data)和指向下一个节点的指针(next)。指针是一种特殊的数据类型，可以指向内存中的某个地址。

链表的另一个重要概念是头结点。头结点是链表中的一个特殊节点，它不存储数据，只用于指向链表第一个节点。使用头结点的目的是方便链表的操作，例如插入、删除和查询。

创建链表

创建链表的基本步骤是：

1. 定义头结点和当前节点指针。

2. 输入要插入的数据，创建新节点。

3. 将新节点插入到链表中。

4. 输出链表的所有节点。

下面是用C++语言实现创建链表的代码：


#include <iostream>
using namespace std;
struct Node {
  int data;
  Node* next;
};
int main() {
  Node* head = new Node;
  head->next = NULL;
  Node* p = head;
  for (int i = 0; i < 5; i++) {
    int num;
    cin >> num;
    Node* newNode = new Node;
    newNode->data = num;
    newNode->next = NULL;
    p->next = newNode;
    p = p->next;
  }
  p = head->next;
  while (p != NULL)
    cout << p->data << " ";
    p = p->next;
  
  return 0;
}

该代码中，首先定义了两个节点：头结点head和当前节点指针p，它们都是指向Node类型的指针。头结点的next成员初始化为NULL，表示链表为空。

在输入要插入的数据之后，创建新节点newNode，并将其插入到链表中。在每次插入新节点时，将当前节点指针p后移。

最后，通过遍历链表的所有节点，输出链表的元素值。

插入节点

插入节点是链表中的一个基本操作，可以在任意位置插入新的节点。其基本步骤是：

1. 找到要插入的位置，即前一个节点。

2. 创建新节点，将其指针指向原来的节点。

3. 将前一个节点的指针指向新节点。

下面是用C++语言实现插入节点的代码：


void insertNode(Node* head, int pos, int elem) {
  Node* p = head;
  for (int i = 0; i < pos - 1; i++)
    p = p->next;
  
  Node* newNode = new Node;
  newNode->data = elem;
  newNode->next = p->next;
  p->next = newNode;
}

该代码中，插入节点的函数insertNode包含三个参数：头结点head、要插入的位置pos和要插入的元素值elem。

在找到要插入的位置之后，创建新节点newNode，并将其指针指向原来的节点。然后将前一个节点的指针指向新节点。

删除节点

删除节点也是链表中的一个基本操作，可以删除任意位置的节点。其基本步骤是：

1. 找到要删除的位置，即前一个节点。

2. 保存要删除的节点的指针。

3. 将前一个节点的指针指向要删除的节点的下一个节点。

4. 释放要删除的节点的内存空间。

下面是用C++语言实现删除节点的代码：


void deleteNode(Node* head, int pos) {
  Node* p = head;
  for (int i = 0; i < pos - 1; i++)
    p = p->next;
  
  Node* q = p->next;
  p->next = q->next;
  delete q;
}

该代码中，删除节点的函数deleteNode也包含两个参数：头结点head和要删除的位置pos。

在找到要删除的位置之后，保存要删除的节点的指针q，并将前一个节点的指针指向要删除的节点的下一个节点。最后，释放要删除的节点的内存空间。

总结

本文介绍了用C++语言实现单向动态链表的基本概念和操作。创建链表的基本步骤是定义头结点和当前节点指针，输入要插入的数据并插入新节点，最后输出链表的所有节点。插入节点的基本步骤是找到要插入的位置，创建新节点并将其指针指向原来的节点，然后将前一个节点的指针指向新节点。删除节点的基本步骤是找到要删除的位置，保存要删除的节点的指针，将前一个节点的指针指向要删除的节点的下一个节点，最后释放要删除的节点的内存空间。在使用链表时，要注意内存泄漏和空指针错误的问题。

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

下一篇: C语言中的malloc和C++中的new有何不同？

评论区

()

相似文章