我要评论
文章目录
🎯引言
欢迎来到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）来定义。一个典型的单链表节点结构如下：
struct node {
int data; // 数据域，用于存储节点的数据
struct node* next; // 指针域，用于存储指向下一个节点的指针
};
节点的组成
- 数据域（data）：
- 数据域存储链表中实际的数据。
- 数据类型可以根据需求变化，例如int、float、char，甚至是复杂的结构体。
- 在上述例子中，数据域的类型是int。
- 指针域（next）：
- 指针域存储指向下一个节点的指针。
- 如果这是链表中的最后一个节点，则指针域存储null，表示链表的结束。
- 在双向链表中，节点会包含两个指针域，一个指向下一个节点，一个指向前一个节点。
结构图示:
链表是由一个个节点所构成的,通过指针将每个节点联系起来。
2.2单链表的实现
slist.h源代码:
//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源代码:
//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. 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博客，期待在下一篇文章中继续与您探讨更多有趣的数据结构和算法。
发表评论