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

C++实现单向链表

2023-07-05 10:43:13 深夜i -- --

C++ 单向链表实现

C++是一种高效的编程语言，其具有优秀的在数据结构上实现的能力。实现数据结构中的链表，可以使用C++的各种特性，在内存管理、抽象数据类型定义、指针使用等方面都能得到很好的体现。

链表是一种重要的数据结构，其中的节点是分离的、非顺序的，由指针相连接而得到互相关联。链表有多种实现方式，例如单向链表、双向链表和循环链表等。

其中单向链表的实现最为基础，它由一个节点的数据部分和下一个节点指针部分构成，可以用来存储大量的数据，并且由于其动态的增删操作，使其更加灵活和适应各种数据处理需求。

下面以单向链表的实现为例，来介绍如何使用C++的特性，来实现链表的创建、插入、删除、查找等操作。

链表节点的定义

因为链表节点由数据部分和指针部分组成，因此在C++中可以使用结构体来定义链表节点：


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

接下来需要编写创建和删除链表节点的函数：


Node* CreateNode(int data) {
 Node* new_node = new Node;
 new_node->data = data;
 new_node->next = nullptr;
 return new_node;
}
void DeleteNode(Node* node)
 delete node;

创建节点时使用了C++的new关键字，这可以在堆上分配内存并返回一个指向该内存区域的指针。删除节点时使用了C++的delete关键字，这可以释放由new分配的内存区域。

链表的创建

链表的创建可以通过循环读入数据，并且通过指针逐个链接数据形成。在具体实现中，可以使用一个头指针表示链表的起始位置，当链表为空时，头指针为nullptr；当链表不为空时，头指针指向链表的第一个节点。


Node* CreateList() {
 Node *head = nullptr, *tail = nullptr;
 int data;
 do {
  std::cin >> data;
  if (data == -1) break;
  Node* node = CreateNode(data);
  if (!head)
   head = node;
   tail = node;
   else
   tail->next = node;
   tail = node;
  
 } while (true);
 return head;
}

在读入数据后，需要通过CreateNode函数分配节点内存，并将新的节点加入到链表末尾。由于链表是单向的，因此仅需用一个尾指针记录最后一个节点。

链表的插入

链表的插入是指在链表中插入新节点，可以实现在链表开头、结尾或是特定节点之前或之后进行插入。以下代码演示如何在链表的开头插入新节点：


void InsertNode(Node** head, int data) {  // 传入头指针的地址
 Node* new_node = CreateNode(data);
 new_node->next = *head;
 *head = new_node;
}

补充说明一下，由于C++是按值传递参数，即使传入了指针的地址，但函数传入头指针后并不会直接改变原指针的指向，因此需要使用二级指针来间接改变指针的地址，保证传出函数后指针已经被正确修改。

链表的删除

链表的删除是指从链表中删除特定节点或链表中的所有节点。以下代码演示如何删除链表中的某个节点：


void DeleteNode(Node** head, Node* node_to_delete) {
 if (*head == node_to_delete) {
  *head = node_to_delete->next;
  DeleteNode(node_to_delete);
  return;
 }
 Node* cur_node = *head;
 while (cur_node->next && cur_node->next != node_to_delete)
  cur_node = cur_node->next;
 
 if (cur_node->next == node_to_delete) {
  cur_node->next = node_to_delete->next;
  DeleteNode(node_to_delete);
 }
}

该代码首先判断需要删除的节点是否为头指针所指，如果是，则修改头指针为下一个节点，并释放该节点内存；否则，通过遍历整个链表找到该节点并删除。在代码中使用了递归的方式来释放节点内存。

链表的查找

链表的查找是指在链表中查找是否存在指定数据或节点，并返回该节点的指针。以下代码演示如何在链表中查找指定值的数据：


Node* FindNode(Node* head, int data) {
 while (head && head->data != data)
  head = head->next;
 
 return head;
}

该函数使用了while循环，查找到指定数据后停止，并返回该节点的指针。如果查找失败则返回nullptr。

总结

链表是一种重要的数据结构，在C++中具有优秀的实现能力，通过使用结构体、堆分配内存、指针调用等特性，可以高效地实现链表的创建、插入、删除、查找等操作。当需要处理大量动态数据或需要在中途频繁插入、删除数据时，链表的实现将更加灵活和高效。

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

下一篇: C++和C语言的应用范围和差别：哪个更广泛使用？

评论区

()

相似文章