您的位置：首页 > 财经 > 金融 > 数据结构——链表

数据结构——链表

2024/12/23 12:35:02 来源：https://blog.csdn.net/qixi_ao/article/details/141612920  浏览:  次   关键词：数据结构——链表

单链表

基本概念

  • 顺序表：顺序存储的线性表。
  • 链式表：链式存储的线性表，简称链表。

既然顺序存储中的数据因为挤在一起而导致需要成片移动，那很容易想到的解决方案是将数据离散地存储在不同内存块中，然后在用来指针将它们串起来。这种朴素的思路所形成的链式线性表，就是所

谓的链表。

顺序表和链表在内存在的基本样态如下图所示：

请添加图片描述

链表的分类

根据链表中各个节点之间使用指针的个数，以及首尾节点是否相连，可以将链表细分为如下种类：

  1. 单向链表
  2. 单向循环链表
  3. 双向循环链表

这些不同链表的操作都是差不多的，只是指针数目的异同。以最简单的单向链表为例，其基本示意图

如下所示：

请添加图片描述

上图中，所有的节点均保存一个指针，指向其逻辑上相邻的下一个节点（末尾节点指向空）。另外注

意到，整条链表用一个所谓的头指针 head 来指向，由 head 开始可以找到链表中的任意一个节点。

head 通常被称为头指针。

链表的基本操作，一般包括：

  1. 节点设计
  2. 初始化空链表
  3. 增删节点
  4. 链表遍历
  5. 销毁链表

下面着重针对这几项常见操作，讲解单向链表的处理。

单链表节点设计

单向链表的节点非常简单，节点中除了要保存用户数据之外（这里以整型数据为例），只需要增加一

个指向本类节点的指针即可，如下所示：

typedef int DATA;
typedef struct Node
{DATA data; // 存储数据---数据域struct Node *next; // 存储下一个节点的地址---指针域
} NODE;

单链表初始化

首先，空链表有两种常见的形式。一种是带所谓的头结点的，一种是不带头结点的。所谓的头结点是

不存放有效数据的节点，仅仅用来方便操作，如下：

请添加图片描述

而不带头结点的空链表如下所示：

请添加图片描述

注意：

  • 头指针 head 是必须的，是链表的入口
  • 头节点是可选的，为了方便某些操作

由于头结点是不存放有效数据的，因此如果空链表中带有头结点，那么头指针 head 将永远不变，这会给以后的链表操作带来些许便捷。

下面以带头结点的链表为例，展示单向链表的初始化的示例代码：

int slist_create(NODE** head,DATA data)
{NODE* p = (NODE*)malloc(sizeof(NODE));if(!p){return -1;}p -> data = data;p -> next = NULL;*head = p;return 0;
}

单链表增删节点

相对于顺序表需要整片移动数据，链表增删节点只需要修改几个相关指针的指向，动作非常快速。与顺序表类似，可以对一条链表中的任意节点进行增删操作，示例代码是：

int slist_addHead(NODE **head, DATA data)
{NODE *p = (NODE *)malloc(sizeof(NODE));if (!p){return -1;}p->data = data;p->next = *head;*head = p;return 0;
}
int slist_addTail(NODE **head, DATA data)
{NODE *pNew = (NODE *)malloc(sizeof(NODE));if (!pNew){return -1;}pNew->data = data;pNew->next = NULL;NODE *p = *head, *q = NULL;if (!p){*head = pNew;return 0;}while (p){q = p;p = p->next;}q->next = pNew;return 0;
}
int slist_insert(NODE **head, DATA pos, DATA data)
{NODE *pNew = (NODE *)malloc(sizeof(NODE));if (!pNew)return -1;pNew->data = data;pNew->next = NULL;NODE *p = *head, *q = NULL;if (!p){*head = pNew;return 0;}if (memcmp(&(p->data), &pos, sizeof(DATA)) == 0){pNew->next = *head;*head = pNew;return 0;}while (p){if (memcmp(&(p->data), &pos, sizeof(DATA)) == 0){pNew->next = p;q->next = pNew;return 0;}q = p;p = p->next;}q->next = pNew;return 0;
}
int slist_update(const NODE *head, DATA old, DATA newdata)
{NODE *p = NULL;if (!(p = slist_find(head, old)))return -1;p->data = newdata;return 0;
}
int slist_delete(NODE **head, DATA data)
{NODE *p = *head, *q = NULL;if (!p)return -1;if (memcmp(&(p->data), &data, sizeof(DATA)) == 0){*head = p->next;free(p);return 0;}while (p){if (memcmp(&(p->data), &data, sizeof(DATA)) == 0){q->next = p->next;free(p);return 0;}q = p;p = p->next;}return -1;
}

注意:

删除链表的节点并不意味着释放其内存，而是将其剔除出链表

单链表的遍历

遍历的意思就是逐个访问每一个节点，对于线性表而言，由于路径唯一的选择就是从头走到尾。因此相当而言比较简单。

下面是单向链表的遍历示例代码，假设遍历每个节点并将其整数数据输出：

NODE* slist_find(const NODE* head,DATA data)
{const NODE* p = head;while(p){if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0){return (NODE*)p;}p = p -> next;}return NULL;
}
void slist_showAll(const NODE* head)
{const NODE* p = head;while(p){printf("%d ",p -> data);p = p -> next;}printf("\n");
}

单链表的销毁

由于链表中的各个节点被离散地分布在各个随机的内存空间，因此销毁链表必须遍历每一个节点，释放每一个节点。

注意：

销毁链表时，遍历节点要注意不能弄丢相邻节点的指针

void slist_destroy(NODE** head)
{NODE* p = *head, *q = NULL;while(p){q = p;p = p -> next;free(q);}*head = NULL;
}

完整代码

  • singList.h
#ifndef __SEQLIST_H
#define __SEQLIST_H#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>// 定义顺序表的结构体
typedef struct
{int capacity;// 顺序表的容量（顺序表本质上是数组）int last;    // 末元素的下标int *data;   // 数据，其实是一个存放多个int的容器
} seqList;// 创建顺序表（顺序表的初始化）
seqList *initList(int cap);// 向顺序表的表头插入一个新数据
bool insert(seqList *list,int data);// 判断顺序表是否满了
bool isFull(seqList *list);// 遍历顺序表中的元素
void show(seqList *list);// 将顺序表中指定的某个元素删除
bool removeNode(seqList *list,int data);// 销毁顺序表
void destroy(seqList *s);
#endif

slist.c

#include "slist.h"/*
@function:   int slist_create(NODE** head,DATA data);
@berif:      创建单项链表
@argument:   head: 指向头指针变量的地址，用来接收首节点地址data: 存储在节点中的数据
@return :    成功返回 0失败返回 -1
*/
int slist_create(NODE **head, DATA data)
{// 申请内存NODE *p = (NODE *)malloc(sizeof(NODE));// 校验if (!p){return -1;}// 赋值操作p->data = data;p->next = NULL;*head = p;return 0;
}/*
@function:   int slist_addHead(NODE** head,DATA data);
@berif:      向链表头部插入一个节点数据（头插法）
@argument:   head: 指向头指针变量的地址，用来接收首节点地址data: 存储在新节点中的数据
@return :    成功返回 0失败返回 -1
*/
int slist_addHead(NODE **head, DATA data)
{// 创建一个新节点（申请内存）NODE *p = (NODE *)malloc(sizeof(NODE));// 校验if (!p){return -1;}// 给节点添加新数据（创建节点的目的是存储数据）p->data = data;// 新节点指向原本的head节点p->next = *head;// 我们要让p作为我们新的head*head = p;return 0;
}/*
@function:   int slist_addTail(NODE** head,DATA data);
@berif:      向链表尾部插入一个节点数据（尾插法）
@argument:   head: 指向头指针变量的地址，用来接收首节点地址data: 存储在新节点中的数据
@return :    成功返回 0失败返回 -1
*/
int slist_addTail(NODE **head, DATA data)
{// 创建一个新节点（申请内存）NODE *pNew = (NODE *)malloc(sizeof(NODE));// 校验if (!pNew){return -1;}// 赋值操作pNew->data = data; // 存数据pNew->next = NULL; // 因为是最后一个节点，所有没有指向// 获取尾部节点，默认head头结点就是尾结点，p用来保存真实的尾结点NODE *p = *head, *q = NULL;if (!p){// 如果说头节点不存在，我们直接将新节点作为头结点，一般不会发生*head = pNew;return 0;}// 通过一个循环，找尾结点while (p){// 为什么要定义q，因为p是在变化的q = p;p = p->next;// 指针向下指}// 让原本的尾结点指向新插入的的节点，此时新插入的节点变成了尾结点q->next = pNew;return 0;
}/*
@function:   int slist_insert(NODE** head,DATA pos ,DATA data);
@berif:      向链表节点值为pos的位置插入一个节点数据data
@argument:   head: 指向头指针变量的地址pos:  插入节点位置的节点数据data: 存储在新节点中的数据
@return :    成功返回 0失败返回 -1
*/
int slist_insert(NODE** head,DATA pos,DATA data)
{// 创建一个新节点，并申请内存NODE *pNew = (NODE*)malloc(sizeof(NODE));if(!pNew){perror("内存申请失败！");return -1;}// 给新节点赋初值pNew->data = data;pNew->next = NULL;// 声明变量，p是pos对应位置的节点，默认是头结点，q是pos对应节点的上一个节点NODE *p = *head,*q = NULL;// 第一种情况：头结点不存在if(!p){// 新节点pNew作为头结点*head = pNew;return 0;}// 第二种情况：只有头结点if(memcmp(&(p->data),&pos,sizeof(DATA)) == 0){// 头插法// 新节点的next指向head节点pNew->next = *head;// 改变指向，将pNew作为新的头结点*head = pNew;return 0;}// 第三种情况：既有头结点，也有普通节点while (p){// 找pos对应位置的节点if(memcmp(&(p->data),&pos,sizeof(DATA)) == 0){// pNew在p前pNew->next = p;// pNew在q后q->next = pNew;return 0;}q = p;// q在p的前一位，一前（q）一后（p）p = p ->next;}// 尾插法q->next = pNew;return 0;
}/*
@function:   NODE* slist_find(const NODE* head,DATA data);
@berif:      查找链表数据data
@argument:   head: 指向头指针变量data: 待查找的数据
@return :    成功返回节点的地址失败返回NULL
*/
NODE* slist_find(const NODE *head,DATA data)
{// 创建一个变量，用来接收链表const NODE* p = head;while(p){if(memcmp(&(p->data),&data,sizeof(DATA))==0){return (NODE*)p;}// 移动节点p = p->next;}return NULL;
}/*
@function:   int slist_update(const NODE* head,DATA old_data,DATA new_data);
@berif:      更新链表数据old_data 为 new_data
@argument:   head: 指向头指针变量old_data:  待更新的节点数据new_data: 更新后的节点数据
@return :    成功返回  0失败返回  -1
*/
int slist_update(const NODE* head,DATA old_data,DATA new_data)
{NODE* p = NULL;if(!(p = slist_find(head,old_data))){return -1;}p->data = new_data;return 0;}/*
@function:   void slist_showAll(const NODE* head);
@berif:      遍历链表数据
@argument:   head: 指向头指针变量
@return :    无
*/
void slist_showAll(const NODE* head)
{// 创建一个变量用来接收链表const NODE* p = head;// 遍历链表while (p){printf("%d ",p->data);p = p->next;}printf("\n");
}/*
@function:   int slist_delete(NODE** head,DATA data);
@berif:      删除链表中节点值为data的节点
@argument:   head: 指向头指针变量的地址data: 删除节点中的数据
@return :    成功返回 0失败返回 -1
*/
int slist_delete(NODE** head,DATA data)
{// 指针尾随NODE *p = *head,*q = NULL;// 第一种情况：头结点不存在（链表本身不存在），无法操作if(!p){return -1; }// 第二种情况：只有一个节点if(memcmp(&(p->data),&data,sizeof(DATA)) == 0){*head = p -> next;free(p);return 0;}// 第三种情况：有多个节点while (p){if(memcmp(&(p->data),&data,sizeof(DATA)) == 0){q->next = p->next;// p的上一个节点的next指向p的下一个节点// 这个回收不会影响到链表的删除free(p);return 0;}q = p;p = p->next;// p->next代表的是p的下一个节点，将p的下一个节点赋值给p，相当于p移动了一位}return -1;
}/*
@function:   void slist_destroy(NODE** head);
@berif:      回收链表
@argument:   head: 指向头指针变量的地址
@return :    无
*/
void slist_destroy(NODE** head)
{// 指针尾随NODE *p = *head,*q = NULL;while(p){q = p;// 12p = p->next;// 13// 回收前一个节点free(q);}*head = NULL;}

链表优缺点

链式存储中，所有节点的存储位置是随机的，他们之间的逻辑关系用指针来确定，跟物理存储位置无

关，因此从上述示例代码可以很清楚看到，增删数据都非常迅速，不需要移动任何数据。另外，又由

于位置与逻辑关系无关，因此也无法直接访问某一个指定的节点，只能从头到尾按遍历的方式一个个

找到想要的节点。简单讲，链式存储的优缺点跟顺序存储几乎是相对的。

总结其特点如下：

  • 优点

    1. 插入、删除时只需要调整几个指针，无需移动任何数据

    2. 当数据节点数量较多时，无需一整片较大的连续内存空间，可以灵活利用离散的内存

    3. 当数据节点数量变化剧烈时，内存的释放和分配灵活，速度快

  • 缺点

    1. 在节点中，需要多余的指针来记录节点之间的关联。

    2. 所有数据都是随机存储的，不支持立即访问任意一个随机数据。

循环单向链表

所谓的循环，指得是将链表末尾节点循环地指向链表表头。比如，单向链表变成循环链表的示意图如下所示：

请添加图片描述

循环链表的操作跟普通链表操作基本上是一致的，只要针对循环特性稍作修改即可

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

最新新闻

热搜词

AIGC-------AI生成内容如何赋能AR和VR体验? 2025省选集训Day1 略解 音视频入门基础：AAC专题（13）——FFmpeg源码中，获取ADTS格式的AAC裸流音频信息的实现 Linux驱动编程 - procfs创建接口 服务器不稳定，如何提高稳定性？ 656

声明：本站所有新闻及新闻图片来源于其他网站，如有侵权，请及时联系我们！

客户服务 | 关于我们 | 版权声明

版权所有：

Copyright 2024 尧图网 All Rights Reserved.QQ:809451989