21xrx.com
2024-12-22 23:38:49 Sunday
登录
文章检索 我的文章 写文章
用C++实现链表并动态分配内存
2023-06-29 02:56:35 深夜i     --     --
C++ 链表 动态分配内存 指针 结构体

链表是计算机科学中常见的一种数据结构，它由一个节点集合组成，每个节点包含两个部分：一个数据部分和一个指针部分，用于指向下一个节点。链表可以用来存储和管理一系列数据，而 C++ 是一种支持动态内存分配并提供强大数据处理能力的编程语言。本文将介绍如何使用 C++ 实现链表并动态分配内存。

1. 定义节点结构体

首先需要定义一个节点结构体，该结构体包括两个部分：一个数据部分和一个指针部分。数据部分可以存储任何类型的数据，例如 int、char、string 等。指针部分用于指向下一个节点。在 C++ 中，可以使用结构体或类来定义节点，这里使用结构体。

struct Node

{

  int data;    // 数据部分

  Node* next;   // 指针部分

};

2. 实现链表类

接下来需要实现链表类。链表类需要包含以下成员函数：

（1）构造函数：用于创建链表对象，初始化链表的头节点。

LinkedList::LinkedList()

  head = nullptr;

（2）析构函数：用于释放链表对象占用的内存空间。

LinkedList::~LinkedList()

{

  Node* current = head;

  while (current != nullptr)

  {

    Node* next = current->next;

    delete current;

    current = next;

  }

}

（3）添加节点：用于向链表中添加一个新节点。

void LinkedList::addNode(int data)

{

  Node* newNode = new Node;

  newNode->data = data;

  newNode->next = nullptr;

  if (head == nullptr)  // 如果链表为空，直接设置头节点

    head = newNode;

  else          // 否则在链表尾部添加节点

  {

    Node* current = head;

    while (current->next != nullptr)

      current = current->next;

    current->next = newNode;

  }

}

（4）删除节点：用于删除链表中指定位置的节点。

void LinkedList::deleteNode(int position)

{

  if (head == nullptr)  // 如果链表为空，直接返回

    return;

  if (position == 0)   // 如果要删除头节点，特殊处理

  {

    Node* temp = head->next;

    delete head;

    head = temp;

  }

  else          // 否则寻找要删除节点的前一个节点

  {

    Node* current = head;

    for (int i = 0; i < position - 1 && current != nullptr; i++)

      current = current->next;

    if (current == nullptr || current->next == nullptr)  // 如果要删除的节点不存在，返回

      return;

    Node* temp = current->next;

    current->next = temp->next;

    delete temp;

  }

}

（5）打印链表：用于将链表中存储的数据输出到屏幕上。

void LinkedList::printList()

{

  Node* current = head;

  while (current != nullptr)

    cout << current->data << " ";

    current = current->next;

}

3. 测试链表类

接下来可以编写测试代码来测试链表类：

int main()

{

  LinkedList list;

  list.addNode(1);

  list.addNode(2);

  list.addNode(3);

  list.addNode(4);

  list.printList();  // 输出：1 2 3 4

  list.deleteNode(2);

  list.printList();  // 输出：1 2 4

  return 0;

}

这里创建了一个链表对象，并向其中添加了四个节点。然后通过调用 printList() 函数将链表中存储的数据输出到屏幕上。接着删除了链表中位置为 2 的节点，再次调用 printList() 函数将链表中存储的数据输出到屏幕上。

动态分配内存的好处在于程序运行时可以根据需要分配和释放内存空间，提高了内存的使用效率。当链表的节点数量很大时，使用动态分配内存可以避免内存浪费和堆栈溢出的问题。同时使用 C++ 实现链表的过程也是学习数据结构和算法的过程，能够锻炼编程能力和思考能力。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复