C++ 链表初学者教程 |21xrx.com

C++ 链表初学者教程

2023-07-11 08:03:20 深夜i -- --

C++ 链表初学者教程数据结构

链表是一种数据结构，它由一个个节点（node）组成，每个节点保存了一个数据元素和指向下一个节点的指针。链表可以高效地实现插入、删除等操作，是算法和数据结构的重要基础之一。本文将介绍 C++ 中链表的基本概念和操作，适合初学者入门。

1. 定义链表节点

链表节点包含两个元素，一个是数据元素，通常是一个类型为 int、char、double 等的变量；另一个是指向下一个节点的指针。在 C++ 中，可以用 struct 或 class 定义节点。

struct Node {

int val;

Node* next;

};

2. 创建链表

链表由排列有序的节点组成，可以采用头插法或尾插法创建。头插法指的是将新节点插入到链表的头部，即链表的第一个节点；尾插法则是将新节点插入到链表的尾部，即链表的最后一个节点。下面是头插法和尾插法的示例代码：

//头插法

Node* head = nullptr;

for (int i = 0; i < n; i++) {

int val = GetInput(); //获取输入数据

Node* node = new Node nullptr; //创建新节点

node->next = head; //将新节点插入到链表头部

head = node; //更新链表头指针

}

//尾插法

Node* head = nullptr, * tail = nullptr;

for (int i = 0; i < n; i++) {

int val = GetInput(); //获取输入数据

Node* node = new Nodeval; //创建新节点

if (tail != nullptr) tail->next = node; //将新节点插入到链表尾部

else head = node; //第一个节点

tail = node; //更新链表尾指针

}

3. 访问链表节点

链表节点通常通过指针进行访问或操作。要访问链表的第 k 个节点，需要从头节点开始顺着 next 指针向后遍历 k - 1 次，得到第 k 个节点的指针。下面是遍历链表的示例代码：

Node* p = head;

while (p != nullptr)

//访问节点 p

cout << p->val << " ";

p = p->next; //移动指针到下一个节点

4. 插入和删除节点

链表插入或删除节点的操作通常需要修改前后节点的指针，以维护链表结构。插入节点操作可以分为在某个节点之前插入或在尾部插入。删除节点操作通常需要先定位到要删除的节点，然后修改前后节点的指针，最后释放被删除节点的内存。下面是插入和删除节点的示例代码：

//在某个节点之前插入

void insertBefore(Node* node, int val) {

Node* newNode = new Nodeval; //新节点插入到 node 后面

node->next = newNode;

}

//在尾部插入

void insertTail(Node** head, int val) {

Node* newNode = new Nodeval; //新节点

if (*head == nullptr) *head = newNode; //空链表

else {

Node* p = *head;

while (p->next != nullptr) p = p->next; //移动指针到链表的最后一个节点

p->next = newNode;

}

//删除节点

void deleteNode(Node** head, int val) {

Node* p = *head, *prev = nullptr;

while (p != nullptr && p->val != val) //定位要删除的节点

prev = p;

p = p->next;

if (p != nullptr) { //找到节点

if (prev == nullptr) *head = p->next; //删除头节点

else prev->next = p->next; //修改前后节点的指针

delete p; //释放内存

}

总结

本文介绍了 C++ 中链表的基本概念和操作，包括定义节点、创建链表、访问节点、插入和删除节点等。链表是一种常用的数据结构，是算法和数据结构的基础之一，希望本文能提供初学者入门的帮助。

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

下一篇: C++考试题目与答案

评论区

()

相似文章