C语言-链表
HanLop 2024-07-22 09:35:01 阅读 68
文章目录
🎯引言👓链表1.链表的概念与分类1.1链表的概念 :1.2链表的分类:
2.单链表(不带头节点的单向非循环链表)2.1概念与结构2.2单链表的实现
3.双向链表(带头节点的双向循环链表)3.1结构3.2双向链表的实现
4.顺序表和链表的对比4.1 存储结构4.2 内存管理4.3 适用场景
🥇结语
🎯引言
欢迎来到HanLop博客的C语言数据结构初阶系列。在这个系列中,我们将深入探讨各种基本的数据结构和算法,帮助您打下坚实的编程基础。本次我将为你讲解链表。链表是一种线性数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。由于其灵活的内存分配方式,链表在动态数据存储和处理方面有着独特的优势。在本篇文章中,我们将介绍链表的基本概念、链表的创建和操作方法,以及其优缺点。通过一些实际的代码示例,您将更好地掌握链表在C语言中的应用,从而为后续学习其他数据结构打下坚实的基础。
👓链表
1.链表的概念与分类
1.1链表的概念 :
链表是一种动态数据结构,由一系列节点(Node)组成。每个节点包含两部分:数据域(存储数据)和指针域(存储下一个节点的地址)。根据指针域的数量和方向
1.2链表的分类:
链表结构有很多种,如下图(2*2*2种):
1. 带头节点的单向非循环链表
带头节点的单向非循环链表在链表的开头有一个特殊的头节点,该头节点不存储实际数据,只用于指向第一个真正存储数据的节点。
特点:
增加了对链表操作的统一性,尤其是在链表为空或者操作第一个节点时更为方便。尾节点指针为NULL,表示链表的结束。
2. 带头节点的单向循环链表
带头节点的单向循环链表在链表的开头有一个头节点,尾节点的指针指向头节点,形成一个环。
特点:
可以从链表的任何一个节点回到头节点,形成一个闭环。常用于需要循环遍历的场景。
3. 带头节点的双向非循环链表
带头节点的双向非循环链表在链表的开头有一个头节点,每个节点有两个指针,分别指向前一个节点和后一个节点。
特点:
可以从链表的任何一个节点向前或向后遍历。尾节点的后指针为NULL,表示链表的结束。
4.带头节点的双向循环链表
带头节点的双向循环链表在链表的开头有一个头节点,每个节点有两个指针,尾节点的后指针指向头节点,头节点的前指针指向尾节点,形成一个环。
特点:
形成一个双向闭环,可以从链表的任何一个节点双向遍历回到头节点。常用于需要双向循环遍历的场景。
5. 不带头节点的单向非循环链表
不带头节点的单向非循环链表没有特殊的头节点,链表的第一个节点就是存储实际数据的节点。
特点:
节省了一个节点的内存,但在操作第一个节点时需要特殊处理。尾节点指针为NULL,表示链表的结束。
6. 不带头节点的单向循环链表
不带头节点的单向循环链表没有头节点,尾节点的指针指向第一个节点,形成一个环。
特点:
可以从链表的任何一个节点回到第一个节点,形成一个闭环。常用于需要循环遍历的场景。
7. 不带头节点的双向非循环链表
不带头节点的双向非循环链表没有头节点,每个节点有两个指针,分别指向前一个节点和后一个节点。
特点:
可以从链表的任何一个节点向前或向后遍历。尾节点的后指针为NULL,表示链表的结束。
8. 不带头节点的双向循环链表
不带头节点的双向循环链表没有头节点,每个节点有两个指针,尾节点的后指针指向第一个节点,第一个节点的前指针指向尾节点,形成一个环。
特点:
形成一个双向闭环,可以从链表的任何一个节点双向遍历回到第一个节点。常用于需要双向循环遍历的场景。
如此多的种类,我们下面只实现两种,单向链表(不带头节点的单向非循环链表)和双向链表(带头节点的双向循环链表)学会这两种之后其他种类的链表也可以自己去实现
2.单链表(不带头节点的单向非循环链表)
2.1概念与结构
概念:
不带头节点的单链表没有特殊的头节点,链表的第一个节点就是存储实际数据的节点。所有操作均直接作用于链表的第一个节点。
节点:
在链表(特别是单链表)中,节点是链表的基本组成单位。每个节点包含两个主要部分:数据域和指针域。下面是对节点的详细解释。
节点的定义
在C语言中,节点通常使用结构体(struct)来定义。一个典型的单链表节点结构如下:
<code>struct Node {
int data; // 数据域,用于存储节点的数据
struct Node* next; // 指针域,用于存储指向下一个节点的指针
};
节点的组成
数据域(data):
数据域存储链表中实际的数据。数据类型可以根据需求变化,例如int、float、char,甚至是复杂的结构体。在上述例子中,数据域的类型是int。 指针域(next):
指针域存储指向下一个节点的指针。如果这是链表中的最后一个节点,则指针域存储NULL,表示链表的结束。在双向链表中,节点会包含两个指针域,一个指向下一个节点,一个指向前一个节点。
结构图示:
链表是由一个个节点所构成的,通过指针将每个节点联系起来。
2.2单链表的实现
SList.h源代码:
<code>//SList.h文件中
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataTyped;
typedef struct SListNode
{
SLDataTyped val;
struct SListNode* next;
}SListNode;
//链表的打印
void SListPrint(SListNode* phead);
//创建新节点
SListNode* SLBuyNode(SLDataTyped x);
//头部插入删除/尾部插入删除
void SListPushFront(SListNode** pphead, SLDataTyped x);
void SListPushBack(SListNode** pphead, SLDataTyped x);
void SListPopBack(SListNode** pphead);
void SListPopFront(SListNode** pphead);
//查找
SListNode* SListFind(SListNode** pphead, SLDataTyped x);
//在指定位置之前插入数据
void SListInsert(SListNode** pphead, SListNode* pos, SLDataTyped x);
//在指定位置之后插入数据
void SListInsertAfter(SListNode* pos, SLDataTyped x);
//删除pos节点
void SListErase(SListNode** pphead, SListNode* pos);
//删除pos之后的节点
void SListEraseAfter(SListNode* pos);
//销毁链表
void SListDestory(SListNode** pphead);
解析:
数据结构定义
typedef int SLDataTyped;
typedef struct SListNode {
SLDataTyped val;
struct SListNode* next;
} SListNode;
SLDataTyped
:定义链表中存储的数据类型,可以根据需要修改。SListNode
:定义链表节点结构,包括数据域val
和指针域next
。
函数声明及其作用
创建新节点
SListNode* SLBuyNode(SLDataTyped x);
功能:创建一个新节点,并将其值设置为x
。参数:节点的值。返回值:指向新创建节点的指针。
打印链表
void SListPrint(SListNode* phead);
功能:遍历并打印整个链表。参数:链表的头指针。返回值:无。
头部插入节点
void SListPushFront(SListNode** pphead, SLDataTyped x);
功能:在链表头部插入一个新节点。参数:链表的头指针的指针,插入节点的值。返回值:无。
尾部插入节点
void SListPushBack(SListNode** pphead, SLDataTyped x);
功能:在链表尾部插入一个新节点。参数:链表的头指针的指针,插入节点的值。返回值:无。
尾部删除节点
void SListPopBack(SListNode** pphead);
功能:删除链表尾部的节点。参数:链表的头指针的指针。返回值:无。
头部删除节点
void SListPopFront(SListNode** pphead);
功能:删除链表头部的节点。参数:链表的头指针的指针。返回值:无。
查找节点
SListNode* SListFind(SListNode** pphead, SLDataTyped x);
功能:在链表中查找值为x
的节点。参数:链表的头指针的指针,查找的值。返回值:指向找到节点的指针,找不到返回NULL。
在指定位置之前插入节点
void SListInsert(SListNode** pphead, SListNode* pos, SLDataTyped x);
功能:在指定位置pos
之前插入一个值为x
的节点。参数:链表的头指针的指针,插入位置的节点指针,插入节点的值。返回值:无。
在指定位置之后插入节点
void SListInsertAfter(SListNode* pos, SLDataTyped x);
功能:在指定位置pos
之后插入一个值为x
的节点。参数:插入位置的节点指针,插入节点的值。返回值:无。
删除指定位置的节点
void SListErase(SListNode** pphead, SListNode* pos);
功能:删除链表中指定位置pos
的节点。参数:链表的头指针的指针,要删除的节点指针。返回值:无。
删除指定位置之后的节点
void SListEraseAfter(SListNode* pos);
功能:删除链表中指定位置pos
之后的节点。参数:要删除其后节点的节点指针。返回值:无。
销毁链表
void SListDestory(SListNode** pphead);
功能:销毁整个链表,释放所有节点的内存。参数:链表的头指针的指针。返回值:无。
SList.c源代码:
//SList.c文件中
#include "SList.h"
void SListPrint(SListNode* phead)
{
//assert(phead);
SListNode* pcur = phead;
while (pcur)
{
printf("%d->", pcur->val);
pcur = pcur->next;
}
printf("NULL\n");
}
SListNode* SLBuyNode(SLDataTyped x)
{
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
newNode->val = x;
newNode->next = NULL;
return newNode;
}
void SListPushBack(SListNode** pphead, SLDataTyped x)
{
assert(pphead);
SListNode* newNode = SLBuyNode(x);
SListNode* pcur = *pphead;
if (*pphead == NULL)
{
*pphead = newNode;
}
else
{
while (pcur->next)
{
pcur = pcur->next;
}
pcur->next = newNode;
}
}
void SListPushFront(SListNode** pphead, SLDataTyped x)
{
assert(pphead);
SListNode* newNode = SLBuyNode(x);
SListNode* pcur = *pphead;
if (*pphead == NULL)
{
*pphead = newNode;
}
else
{
newNode->next = *pphead;
*pphead = newNode;
}
}
void SListPopBack(SListNode** pphead)
{
assert(pphead&&*pphead);
SListNode* pcur = *pphead;
SListNode* prev = *pphead;
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
while (pcur->next)
{
prev = pcur;
pcur = pcur->next;
}
free(pcur);
pcur = NULL;
prev->next = NULL;
}
}
void SListPopFront(SListNode** pphead)
{
assert(pphead && *pphead);
SListNode* del = *pphead;
*pphead = (*pphead)->next;
free(del);
del = NULL;
}
SListNode* SListFind(SListNode** pphead, SLDataTyped x)
{
assert(pphead && *pphead);
SListNode* pcur = *pphead;
while (pcur)
{
if (pcur->val == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
void SListInsert(SListNode** pphead, SListNode* pos, SLDataTyped x)
{
assert(pphead&&*pphead);
assert(pos);
SListNode* pcur = *pphead;
SListNode* prev = *pphead;
//pos是头节点
if (pos == *pphead)
{
SListPushFront(pphead, x);
}
else
{
SListNode* newNode = SLBuyNode(x);
while (pcur != pos)
{
prev = pcur;
pcur = pcur->next;
}
prev->next = newNode;
newNode->next = pos;
}
}
void SListInsertAfter(SListNode* pos, SLDataTyped x)
{
assert(pos);
SListNode* next = pos->next;
SListNode* newNode = SLBuyNode(x);
newNode->next = pos->next;
pos->next = newNode;
}
void SListErase(SListNode** pphead, SListNode* pos, SLDataTyped x)
{
assert(pphead && *pphead);
assert(pos);
SListNode* prev = *pphead;
SListNode* pcur = *pphead;
//头删
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
while (pcur != pos)
{
prev = pcur;
pcur = pcur->next;
}
prev->next = pcur->next;
free(pos);
pos = NULL;
pcur = NULL;
}
}
void SListEraseAfter(SListNode* pos)
{
assert(pos&&pos->next);
SListNode* next = pos->next;
SListNode* Dnext = pos->next->next;
pos->next = Dnext;
free(next);
next = NULL;
}
void SListDestory(SListNode** pphead)
{
assert(pphead && *pphead);
SListNode* pcur = *pphead;
SListNode* next = NULL;
while (next)
{
next = pcur->next;
free(pcur);
pcur = NULL;
}
*pphead = NULL;
}
代码解析:
打印链表 SListPrint
void SListPrint(SListNode* phead) {
SListNode* pcur = phead;
while (pcur) {
printf("%d -> ", pcur->val);
pcur = pcur->next;
}
printf("NULL\n");
}
功能:遍历链表并打印每个节点的值,以箭头形式连接每个节点。实现细节:
使用一个指针 pcur
初始化为链表的头节点 phead
。循环遍历链表直到 pcur
为空(即到达链表末尾)。打印当前节点的值 pcur->val
,并移动到下一个节点 pcur = pcur->next
。最后打印 "NULL"
表示链表结束。
创建新节点 SLBuyNode
SListNode* SLBuyNode(SLDataTyped x) {
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->val = x;
newNode->next = NULL;
return newNode;
}
功能:创建一个新的链表节点并初始化其值和 next
指针。实现细节:
使用 malloc
分配内存以存储新节点。检查内存分配是否成功,若失败则输出错误信息并退出程序。将新节点的 val
设置为参数 x
,next
设置为 NULL
,表示该节点为链表的末尾节点。返回指向新创建节点的指针。
头部插入节点 SListPushFront
void SListPushFront(SListNode** pphead, SLDataTyped x) {
SListNode* newNode = SLBuyNode(x); // 创建一个新节点
newNode->next = *pphead; // 新节点的 next 指向当前头节点
*pphead = newNode; // 更新头节点指针,使其指向新节点
}
功能:在链表的头部插入一个新节点。实现细节:
创建一个新的节点 newNode
并将其值初始化为 x
。将新节点的 next
指向当前的头节点 *pphead
。更新头节点指针 *pphead
,使其指向新节点 newNode
。
尾部插入节点 SListPushBack
void SListPushBack(SListNode** pphead, SLDataTyped x) {
SListNode* newNode = SLBuyNode(x); // 创建一个新节点
if (*pphead == NULL) {
*pphead = newNode; // 若链表为空,直接将新节点设为头节点
} else {
SListNode* pcur = *pphead;
while (pcur->next) {
pcur = pcur->next; // 找到链表的最后一个节点
}
pcur->next = newNode; // 将新节点连接到链表的最后
}
}
功能:在链表的尾部插入一个新节点。实现细节:
创建一个新的节点 newNode
并将其值初始化为 x
。检查链表是否为空(即 *pphead == NULL
),如果是,直接将新节点设为头节点。如果链表不为空,使用 pcur
指针遍历链表直到找到最后一个节点。将最后一个节点的 next
指针指向新节点 newNode
,完成插入操作。
头部删除节点 SListPopFront
void SListPopFront(SListNode** pphead) {
assert(pphead && *pphead); // 断言链表和头节点都存在
SListNode* del = *pphead; // 记录要删除的节点
*pphead = (*pphead)->next; // 更新头节点指针,使其指向下一个节点
free(del); // 释放被删除的节点的内存
}
功能:删除链表的头部节点。实现细节:
使用断言 assert
确保链表和头节点 *pphead
存在。创建一个临时指针 del
,指向要删除的节点 *pphead
。更新头节点指针 *pphead
,使其指向下一个节点 (*pphead)->next
。释放被删除节点 del
的内存,防止内存泄漏。
尾部删除节点 SListPopBack
void SListPopBack(SListNode** pphead) {
assert(pphead && *pphead); // 断言链表和头节点都存在
if (*pphead == NULL) {
return; // 如果链表为空,直接返回
}
SListNode* pcur = *pphead;
SListNode* prev = NULL;
while (pcur->next) {
prev = pcur;
pcur = pcur->next; // 找到链表的倒数第二个节点
}
if (prev == NULL) {
free(*pphead); // 若链表只有一个节点,直接释放头节点
*pphead = NULL;
} else {
free(pcur); // 释放最后一个节点的内存
prev->next = NULL; // 断开倒数第二个节点与最后一个节点的连接
}
}
功能:删除链表的尾部节点。实现细节:
使用断言 assert
确保链表和头节点 *pphead
存在。如果链表为空(即 *pphead == NULL
),直接返回,不进行删除操作。使用 pcur
指针和 prev
指针找到链表的倒数第二个节点 prev
和最后一个节点 pcur
。如果 prev
为 NULL
,表示链表只有一个节点,直接释放头节点 *pphead
。否则,释放最后一个节点 pcur
的内存,并断开 prev->next
指针与 pcur
的连接,完成删除操作。
查找节点 SListFind
SListNode* SListFind(SListNode** pphead, SLDataTyped x) {
assert(pphead && *pphead); // 断言链表和头节点都存在
SListNode* pcur = *pphead;
while (pcur) {
if (pcur->val == x) {
return pcur; // 找到值为 x 的节点,返回该节点指针
}
pcur = pcur->next; // 继续遍历下一个节点
}
return NULL; // 遍历完链表未找到,返回 NULL
}
功能:在链表中查找值为 x
的节点。实现细节:
使用断言 assert
确保链表和头节点 *pphead
存在。使用 pcur
指针遍历整个链表。如果找到节点值等于 x
的节点,返回该节点的指针 pcur
。如果遍历完整个链表都没有找到值为 x
的节点,返回 NULL
。
在指定位置之前插入节点 SListInsert
void SListInsert(SListNode** pphead, SListNode* pos, SLDataTyped x) {
assert(pphead && *pphead); // 断言链表和头节点都存在
assert(pos); // 断言插入位置 pos 存在
SListNode* pcur = *pphead;
SListNode* prev = NULL;
if (pos == *pphead) {
SListPushFront(pphead, x); // 如果插入位置是头节点,则调用头部插入函数
} else {
SListNode* newNode = SLBuyNode(x); // 创建新节点
while (pcur != pos) {
prev = pcur;
pcur = pcur->next; // 找到插入位置的前一个节点 prev 和插入位置节点 pos
}
prev->next = newNode; // 将新节点插入到 prev 和 pos 之间
newNode->next = pos;
}
}
功能:在链表中指定位置 pos
之前插入一个新节点。实现细节:
使用断言 assert
确保链表和头节点 *pphead
存在,以及插入位置 pos
存在。创建 pcur
和 prev
指针,用于遍历链表和记录插入位置的前一个节点。如果插入位置 pos
是头节点 *pphead
,则调用 SListPushFront
函数在头部插入节点。否则,创建新节点 newNode
并找到 pos
的前一个节点 prev
。将新节点 newNode
插入到 prev
和 pos
之间,完成插入操作。
在指定位置之后插入节点 SListInsertAfter
void SListInsertAfter(SListNode* pos, SLDataTyped x) {
assert(pos); // 断言插入位置 pos 存在
SListNode* newNode = SLBuyNode(x); // 创建新节点
newNode->next = pos->next; // 将新节点的 next 指向 pos 的下一个节点
pos->next = newNode; // 将 pos 的 next 指向新节点,完成插入操作
}
功能:在链表中指定位置 pos
之后插入一个新节点。实现细节:
使用断言 assert
确保插入位置 pos
存在。创建新节点 newNode
并将其值初始化为 x
。将新节点 newNode
的 next
指针指向 pos
的下一个节点 pos->next
。将 pos
的 next
指针指向新节点 newNode
,完成插入操作。
删除指定节点 SListErase
void SListErase(SListNode** pphead, SListNode* pos) {
assert(pphead && *pphead); // 断言链表和头节点都存在
assert(pos); // 断言要删除的位置 pos 存在
SListNode* prev = *pphead;
SListNode* pcur = *pphead;
if (pos == *pphead) {
SListPopFront(pphead); // 如果要删除的位置是头节点,则调用头部删除函数
} else {
while (pcur != pos) {
prev = pcur;
pcur = pcur->next; // 找到要删除位置的前一个节点 prev 和要删除的节点 pos
}
prev->next = pcur->next; // 将 prev 的 next 指向 pos 的下一个节点,跳过 pos
free(pos); // 释放 pos 节点的内存
}
}
功能:删除链表中指定位置 pos
的节点。实现细节:
使用断言 assert
确保链表和头节点 *pphead
存在,以及要删除的位置 pos
存在。创建 prev
和 pcur
指针,用于遍历链表和记录要删除的位置 pos
。如果要删除的位置 pos
是头节点 *pphead
,则调用 SListPopFront
函数删除头部节点。否则,找到 pos
的前一个节点 prev
和要删除的节点 pos
。将 prev
的 next
指针指向 pos
的下一个节点 pcur->next
,跳过要删除的节点 pos
。释放要删除节点 pos
的内存,完成删除操作。
删除指定节点之后的节点 SListEraseAfter
void SListEraseAfter(SListNode* pos) {
assert(pos && pos->next); // 断言插入位置 pos 和 pos 的下一个节点存在
SListNode* next = pos->next;
pos->next = next->next; // 将 pos 的 next 指向 pos 的下下一个节点
free(next); // 释放 pos 的下一个节点的内存
}
功能:删除链表中指定位置 pos
的下一个节点。实现细节:
使用断言 assert
确保插入位置 pos
存在,且 pos
的下一个节点 pos->next
存在。创建 next
指针指向 pos
的下一个节点。将 pos
的 next
指针指向 next
的下一个节点 next->next
,跳过 next
节点。释放 next
节点的内存,完成删除操作。
销毁链表 SListDestory
void SListDestory(SListNode** pphead) {
assert(pphead && *pphead); // 断言链表和头节点都存在
SListNode* pcur = *pphead;
while (pcur) {
SListNode* next = pcur->next; // 记录下一个节点的指针
free(pcur); // 释放当前节点的内存
pcur = next; // 移动到下一个节点
}
*pphead = NULL; // 将头节点指针设为 NULL,完成销毁操作
}
功能:销毁整个链表并释放所有节点的内存。实现细节:
使用断言 assert
确保链表和头节点 *pphead
存在。使用 pcur
指针遍历整个链表,依次释放每个节点的内存。在释放当前节点 pcur
内存之前,记录下一个节点的指针 next
。将 pcur
移动到下一个节点 next
,继续循环直到链表所有节点都被释放。最后将头节点指针 *pphead
设为 NULL
,完成销毁链表的操作。
3.双向链表(带头节点的双向循环链表)
3.1结构
图示:
3.2双向链表的实现
List.h源代码:
<code>//List.h文件
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTDataType;
typedef struct ListNode
{
LTDataType x;
struct ListNode* prev;
struct ListNode* next;
}ListNode;
void ListInit(ListNode** phead);
//申请新的节点
ListNode* BuyListNode(LTDataType x);
//打印节点
void ListPrint(ListNode* phead);
//尾插尾删/头插头删
void ListPushBack(ListNode* phead, LTDataType x);
void ListPushFront(ListNode* phead, LTDataType x);
void ListPopBack(ListNode* phead);
void ListPopFront(ListNode* phead);
//查找
ListNode* ListFind(ListNode* phead,LTDataType x);
//在pos位置之后插入数据
void ListInsert(ListNode* pos, LTDataType x);
//删除pos位置的数据
void ListErase(ListNode* pos);
//链表的销毁
void ListDestory(ListNode** pphead);
源码解析:
头文件保护和包含的头文件
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
功能:使用 #pragma once
实现头文件的单次包含保护,避免多重包含问题。头文件:包含了 stdio.h
(标准输入输出)、stdlib.h
(标准库函数)、assert.h
(断言)。
定义节点结构体和数据类型
typedef int LTDataType;
typedef struct ListNode
{
LTDataType x;
struct ListNode* prev;
struct ListNode* next;
} ListNode;
功能:定义了双向链表的节点结构体 ListNode
和节点值的数据类型 LTDataType
。结构体成员:
x
:节点的数据成员。prev
:指向前一个节点的指针。next
:指向后一个节点的指针。
1. void ListInit(ListNode** phead);
功能:初始化双向链表。参数:指向链表头节点指针的指针 phead
。通过修改 phead
的值来更新链表头指针。
2. ListNode* BuyListNode(LTDataType x);
功能:申请并返回一个新的链表节点。参数:节点的数据成员的值 x
。返回值:指向新节点的指针。
3. void ListPrint(ListNode* phead);
功能:打印双向链表的所有节点值。参数:指向链表头节点的指针 phead
。
4. void ListPushBack(ListNode* phead, LTDataType x);
功能:在链表尾部插入一个新节点。参数:指向链表头节点的指针 phead
,新节点的数据成员的值 x
。
5. void ListPushFront(ListNode* phead, LTDataType x);
功能:在链表头部插入一个新节点。参数:指向链表头节点的指针 phead
,新节点的数据成员的值 x
。
6. void ListPopBack(ListNode* phead);
功能:删除链表尾部的节点。参数:指向链表头节点的指针 phead
。
7. void ListPopFront(ListNode* phead);
功能:删除链表头部的节点。参数:指向链表头节点的指针 phead
。
8. ListNode* ListFind(ListNode* phead, LTDataType x);
功能:查找链表中第一个值为 x
的节点。参数:指向链表头节点的指针 phead
,要查找的值 x
。返回值:指向找到的节点的指针,若未找到则返回 NULL
。
9. void ListInsert(ListNode* pos, LTDataType x);
功能:在指定节点 pos
后插入一个新节点。参数:指定位置节点的指针 pos
,新节点的数据成员的值 x
。
10. void ListErase(ListNode* pos);
功能:删除指定节点 pos
。参数:指向链表中待删除节点的指针 pos
。
11. void ListDestory(ListNode** pphead);
功能:销毁整个链表及其所有节点。参数:指向链表头节点指针的指针 pphead
。通过将所有节点释放,并将 *pphead
设置为 NULL
来实现。
List.c源码
//List.c文件
#include "List.h"
void ListInit(ListNode** phead)
{
assert(phead);
*phead = (ListNode*)malloc(sizeof(ListNode));
(*phead)->x = -1;
(*phead)->next = *phead;
(*phead)->prev = *phead;
}
ListNode* BuyListNode(LTDataType x)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->x = x;
newNode->next = newNode;
newNode->prev = newNode;
return newNode;
}
void ListPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* tail = phead->prev;
ListNode* newNode = BuyListNode(x);
newNode->next = phead;
newNode->prev = tail;
tail->next = newNode;
phead->prev = newNode;
}
void ListPrint(ListNode* phead)
{
assert(phead);
ListNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->x);
pcur = pcur->next;
}
printf("\n");
}
void ListPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newNode = BuyListNode(x);
phead->next->prev = newNode;
newNode->next = phead->next;
newNode->prev = phead;
phead->next = newNode;
}
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}
ListNode* ListFind(ListNode* phead, LTDataType x)
{
assert(phead);
assert(phead->next != phead);
ListNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->x == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newNode = BuyListNode(x);
pos->next->prev = newNode;
newNode->next = pos->next;
newNode->prev = pos;
pos->next = newNode;
}
void ListErase(ListNode* pos)
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos == NULL;
}
void ListDestory(ListNode** pphead)
{
assert(pphead);
assert(*pphead != NULL);
ListNode* pcur = (*pphead)->next;
ListNode* next = pcur->next;
while (pcur != *pphead)
{
free(pcur);
pcur = next;
next = pcur->next;
}
free(*pphead);
*pphead = NULL;
}
源码解析:
1. void ListInit(ListNode** phead)
void ListInit(ListNode** phead)
{
assert(phead);
*phead = (ListNode*)malloc(sizeof(ListNode));
(*phead)->x = -1;
(*phead)->next = *phead;
(*phead)->prev = *phead;
}
功能:初始化双向循环链表。
实现过程:
使用 malloc
分配内存以存储头节点。将头节点的数据域 x
初始化为 -1
,表示头节点。将头节点的 next
和 prev
指针都指向自身,形成一个空链表的循环结构。
2. ListNode* BuyListNode(LTDataType x)
ListNode* BuyListNode(LTDataType x)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->x = x;
newNode->next = newNode;
newNode->prev = newNode;
return newNode;
}
功能:申请并返回一个新的链表节点。
实现过程:
使用 malloc
分配内存以存储新节点。将新节点的数据域 x
初始化为参数 x
。将新节点的 next
和 prev
指针都指向自身,表示新节点单独存在时的循环结构。
3. void ListPrint(ListNode* phead)
void ListPrint(ListNode* phead)
{
assert(phead);
ListNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->x);
pcur = pcur->next;
}
printf("\n");
}
功能:打印双向循环链表的所有节点值。
实现过程:
从链表的第一个节点开始遍历,直到回到头节点 phead
。使用 printf
打印每个节点的数据域 x
的值,并在末尾输出换行符。
4. void ListPushBack(ListNode* phead, LTDataType x)
void ListPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* tail = phead->prev;
ListNode* newNode = BuyListNode(x);
newNode->next = phead;
newNode->prev = tail;
tail->next = newNode;
phead->prev = newNode;
}
功能:在链表尾部插入一个新节点。
实现过程(在实现这些函数时我们都需要画图辅组我们写代码.):
找到链表尾部节点 tail
,即 phead->prev
。创建一个新节点 newNode
,并将其 next
指向头节点 phead
,将其 prev
指向 tail
。更新 tail
和 phead
的 next
和 prev
指针,使新节点插入到尾部。
图示:
5. <code>void ListPushFront(ListNode* phead, LTDataType x)
void ListPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newNode = BuyListNode(x);
phead->next->prev = newNode;
newNode->next = phead->next;
newNode->prev = phead;
phead->next = newNode;
}
功能:在链表头部插入一个新节点。
实现过程:
创建一个新节点 newNode
。将新节点的 next
指向头节点的 next
,将新节点的 prev
指向头节点 phead
。更新头节点 phead
和原头节点的 next
节点的 prev
指针,使新节点插入到头部。
6. void ListPopBack(ListNode* phead)
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}
功能:删除链表尾部的节点。
实现过程:
找到链表尾部节点 del
,即 phead->prev
。更新 del
节点前后节点的 next
和 prev
指针,使尾部节点从链表中删除。释放 del
节点的内存。
7. void ListPopFront(ListNode* phead)
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}
功能:删除链表头部的节点。
实现过程:
找到头部节点 del
,即 phead->next
。更新头节点 phead
和原头节点的 next
节点的 prev
指针,使头部节点从链表中删除。释放 del
节点的内存。
8. ListNode* ListFind(ListNode* phead, LTDataType x)
ListNode* ListFind(ListNode* phead, LTDataType x)
{
assert(phead);
assert(phead->next != phead);
ListNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->x == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
功能:查找链表中第一个值为 x
的节点。
实现过程:
从链表的第一个节点开始遍历,直到回到头节点 phead
。比较每个节点的数据域 x
和参数 x
,找到匹配的节点则返回其指针,否则返回 NULL
。
9. void ListInsert(ListNode* pos, LTDataType x)
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newNode = BuyListNode(x);
pos->next->prev = newNode;
newNode->next = pos->next;
newNode->prev = pos;
pos->next = newNode;
}
功能:在指定节点 pos
后插入一个新节点。
实现过程:
创建一个新节点 newNode
。将新节点的 next
指向 pos
节点的 next
,将新节点的 prev
指向 pos
节点。更新 pos
节点和 pos
后面节点的 prev
指针,使新节点插入到指定位置。
10. void ListErase(ListNode* pos)
void ListErase(ListNode* pos)
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}
功能:删除指定节点 pos
。
实现过程:
更新 pos
节点前后节点的 next
和 prev
指针,使节点 pos
从链表中删除。释放 pos
节点的内存。
11. void ListDestory(ListNode** pphead)
void ListDestory(ListNode** pphead)
{
assert(pphead);
assert(*pphead != NULL);
ListNode* pcur = (*pphead)->next;
ListNode* next = pcur->next;
while (pcur != *pphead)
{
free(pcur);
pcur = next;
next = pcur->next;
}
free(*pphead);
*pphead = NULL;
}
功能:销毁整个链表及其所有节点。
实现过程:
从链表的第一个节点开始,逐个释放每个节点的内存,直到回到头节点。最后释放头节点的内存,并将 *pphead
置为 NULL
。
4.顺序表和链表的对比
4.1 存储结构
顺序表(数组):
存储方式:使用一段连续的内存空间存储元素,通过索引访问元素。特点:随机访问速度快,时间复杂度为 O(1);插入和删除元素时,需要移动大量元素,时间复杂度为 O(n)。 链表:
存储方式:使用不连续的内存空间,每个节点存储数据和指向下一个节点的指针。特点:插入和删除元素方便,时间复杂度为 O(1),只需修改指针;随机访问效率较低,需从头节点遍历到目标节点,时间复杂度为 O(n)。
4.2 内存管理
顺序表:
内存管理:动态顺序表在实现时通常会预留一定的空间,当元素数量超过当前容量时,会动态扩展内存空间。这通常涉及到重新分配更大的内存块,并将原有数据复制到新的内存中,然后释放旧内存。优点:在元素数量不断增加时,仍然可以保持高效的随机访问性能,而且相比静态顺序表更加灵活。缺点:动态扩展和内存重新分配可能会导致性能开销,特别是在频繁操作大量数据时。 链表:
内存分配:节点动态分配,每个节点独立管理内存。优点:插入和删除效率高,不会造成内存碎片。缺点:每个节点额外需要存储指针信息,占用更多内存空间;随机访问效率低下。
4.3 适用场景
顺序表:
当需要高效的随机访问 链表:
当需要频繁插入和删除操作,而不关心随机访问效率时。
🥇结语
通过本篇文章的学习,您应该已经掌握了链表的基本概念、创建和操作方法,以及链表在C语言中的应用。链表作为一种灵活且高效的线性数据结构,在许多编程场景中都有广泛的应用。希望通过这些知识,您能够更好地理解和运用链表,从而为进一步学习和掌握更复杂的数据结构打下坚实的基础。感谢您阅读HanLop博客,期待在下一篇文章中继续与您探讨更多有趣的数据结构和算法。
声明
本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。