当前位置： 首页 > article >正文

【数据结构】链表链表

article 2025/1/7 13:33:18

一、链表的基本知识

链表是什么？

C语言中的数据结构链表是一种动态数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针

链表的优点

链表相对于数组等静态结构具有以下的特点：

  • 动态内存分配： 链表的节点可以在程序运行时动态地创建和删除，不需要在编译时确定大小。
  • 灵活的内存使用： 链表可以根据需要分配内存，不会浪费内存空间。
  • 插入和删除操作： 在链表中插入和删除节点通常只需要改变指针，不需要移动其他元素，因此操作效率较高。
  • 无序性： 链表中的元素没有固定的顺序，可以通过指针访问任意位置的元素。

链表的类别

其实链表的形式是有多种的，它们的基础属性是由：带头、循环、方向构成，也就是说他们有三个基本属性，所以可以构成八种不同的链表，下面我会详细地讲解不带头、单向、不循环链表(单链表) 与 带头、双向、循环链表(双链表) ，只要了解了这两个链表是如何实现的，我们就可以十分轻松地将这三个不同的基础属性组合在一起，创造出自己想要的链表

二、单链表

什么是单链表

单链表(Singly Linked List)

  • 每个节点包含一个指向下一个节点的指针
  • 只能从表头向表尾遍历
    在这里插入图片描述

链表的实现

每个链表都具有增删查改的功能，我们接下来会完善这几个功能

首先呢，我们需要创建两个文件一个是SList.c源文件另一个是SList.h头文件，分别在存放单链表的方法实现代码，与方法声明

在这里插入图片描述
这里的test.c用于功能测试

1. 单链表的本体实现

链表是由结构体作为节点，再将节点链接而成的，所以我们需要在SList.h的头文件中将链表的节点定义好，如代码如下：

SList.h

#include <stdio.h> //写上需要用到的头文件
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType; //定义节点里的数据的类型

typedef struct SListNode { //定义结构体
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

这里我在SList.h的头文件中包含了需要的头文件，并且将int重名为了SLTDataType，这是为了便于当链表想要存储其他数据时方便修改；同时定义了一个名为SListNode的结构体，并将其重命名为SLTNode，这就是单链表的节点，存放着节点的数据与下一个节点的地址，这样，我们的单个节点就写好了

2. 单链表的节点创建

链表节点的创建其实是作为一个子函数使用，这个子函数会用在链表的头插、尾插、指定位置后插入函数中

SList.h

//节点创建
SLTNode* SLTBuyNode(SLTDataType x);

SList.c

//节点创建
SLTNode* SLTBuyNode(SLTDataType x) {
	SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));
	if (NewNode == NULL) {
		perror("SLTBuyNode()::malloc()");
		exit(1);
	}
	NewNode->data = x;
	NewNode->next = NULL;
	return NewNode;
}

3. 单链表的尾插

链表的尾插指的是在链表的最后一个节点插入一个节点作为新的尾节点，所以我们必须先找到尾节点再进行插入，请看下面的代码实现

SList.h

//链表的尾插
void SLTPushBack(SLTNode* phead, SLTDataType x);

SList.c

//链表的尾插
void SLTPushBack(SLTNode* phead, SLTDataType x) {
	assert(phead);
	
	SLTNode* pcur = phead;//创建临时节点
	SLTNode* NewNode = SLTBuyNode(x);//创建新节点

	while (pcur->next) {//找到尾节点
		pcur = pcur->next;
	}

	pcur->next = NewNode;
}

4. 单链表的头插

链表的头插与链表的尾插大差不差，但是头插是在链表的头部插入节点，所以我们插入的新节点是我们的新头节点，头插后需要改变原来指向头节点的指针

SList.h

//链表的头插
void SLTPushFornt(SLTNode** pphead, SLTDataType x);

SList.c

//链表的头插
void SLTPushFornt(SLTNode** pphead, SLTDataType x) {
	assert(*pphead && pphead);
	
	SLTNode* NewNode = SLTBuyNode(x);//创建新节点
	NewNode->next = *pphead;
	*pphead = NewNode;
}

因为我们头插需要更换我们头节点指针的指向位置，所以这里我们通过传入二级指针来修改指向头节点的指针

5. 单链表的打印

链表的打印十分简单，直接遍历即可，因为我们最后一个节点的next肯定是NULL，所以可以通过判断每个节点的最后一个节点从而结束往下遍历

SList.h

//链表的打印
void SLTPrint(SLTNode* phead);

SList.c

//链表的打印
void SLTPrint(SLTNode* phead) {
	assert(phead);
	
	while (phead) {
		printf("%d->", phead->data);
		phead = phead->next;
	}
	printf("NULL\n");
}

6. 单链表的尾删

单链表的尾删就是找到尾节点再删除即可，再将上一节点的nenxt置为空

SList.h

//链表的尾删
void SLTPopBack(SLTNode** pphead);

SList.h

//链表的尾删
void SLTPopBack(SLTNode** pphead) {
	assert(*pphead);

	SLTNode* prev = NULL;
	SLTNode* pcur = *pphead;

	if (pcur->next == NULL) {//如果只有一个节点
		free(pcur);
		(*pphead) = NULL;
	}
	else {
		while (pcur->next) {
			prev = pcur;//保存上一个节点
			pcur = pcur->next;//找到尾节点
		}
		free(pcur);
		prev->next = NULL;
	}
}

使用二级指针是因为我们需要堤防链表中只有一个节点的情况

7. 单链表的头删

单链表的头删与尾删也是大差不差的，头删需要考虑指向头指针节点的变化

SList.h

//链表的头删
void SLTPopFront(SLTNode** pphead);

SList.c

//链表的头删
void SLTPopFront(SLTNode** pphead) {
	assert(pphead && *pphead);

	SLTNode* pcur = (*pphead)->next;
	free(*pphead);
	*pphead = pcur;
}

8. 单链表的查找

查找链表中的某个节点，我们可以遍历整个链表，并且返回找到的节点，若是没有找到则返回NULL

SList.h

//链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

SList.c

//链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
	assert(phead);
	
	SLTNode* pcur = phead;
	while (pcur) {
		if (pcur->data == x) {
			return pcur;
		}
	}
	return NULL;
}

9. 单链表的修改

如果我们需要改掉链表中的某个节点的值，我们需要先找到这个节点的地址，所以我们需要配合单链表的查找链表中的节点

SList.h

//链表的修改
void SLTModify(SLTNode* pcur, SLTDataType x);

SList.c

//链表的修改
void SLTModify(SLTNode* pcur, SLTDataType x) {
	assert(pcur);
	
	pcur->data = x;
}

10. 单链表的销毁

单链表的销毁我们需要将链表的所有节点逐一释放，并且将指向头节点的指针指向NULL

SList.h

//销毁链表
void SLTDestory(SLTNode** pphead);

SList.c

//链表的销毁
void SLTDestroy(SLTNode** pphead) {
	assert(pphead && *pphead);
	
	SLTNode* pcur = *pphead;
	SLTNode* pnext = NULL;
	while (pcur) {
		pnext = pcur->next;
		free(pcur);
		pcur = pnext;
	}
	*pphead = NULL;
}

11. 单链表的总测试

Test.c

#include "SList.h"

void Test() {
	SLTNode* phead = SLTBuyNode(1);
	SLTPrint(phead);
	SLTPushBack(phead, 2);
	SLTPrint(phead);
	SLTPushFront(&phead, 0);
	SLTPrint(phead);

	SLTPopBack(&phead);
	SLTPrint(phead);
	SLTPopFront(&phead);
	SLTPrint(phead);

	SLTNode* NodeFind = SLTFind(phead, 1);
	SLTModify(NodeFind, 10);
	SLTPrint(phead);

	SLTDestroy(&phead);
}

int main() {
	Test();

	return 0;
}

在这里插入图片描述
单链表的内容我们就到这里

三、双向链表

双向链表是什么？

这里我们介绍链表的第二种，带头双向循环链表，带头的双向链表多了一个头节点，而这个头节点是不会储存任何值的，同时，每个节点里面包含着上一个节点的地址与下一个节点的地址，与自身的数值，而头节点的前一个节点为尾节点，所以说是循环的，方法的实现与单链表思想差不多，只是需要多思考头节点的存在与指向前节点的地址，请看下面的图片
在这里插入图片描述

链表的实现

每个链表都具有增删查改的功能，我们接下来会完善这几个功能

首先呢，我们需要创建两个文件一个是List.c源文件另一个是List.h头文件，分别在存放单链表的方法实现代码，与方法声明
在这里插入图片描述
这里的test.c用于功能测试

1. 双链表的本体实现

我们说过，双链表是一个带头双向循环链表，所以双链表的每个节点里面都有指向前一个节点、指向后一个节点的指针，还有它本身携带的数据
List.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int LTDataType;

typedef struct ListNode {
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

2. 双链表的初始化函数

我们说过双链表是带头的且头节点不算入链表的个数中，那么初始化函数的作用就是创建一个头节点，我们创建的头节点指针将指向这个头节点
List.h

//双链表的初始化
LTNode* LTInit();

List.c

LTNode* LTInit() {
	LTNode* NewNode = (LTNode*)malloc(sizeof(LTNode));
	if (NewNode == NULL) {
		perror("LTInit()::malloc()");
		return NULL;
	}

	NewNode->prev = NewNode->next = NewNode;
	NewNode->data = -1;

	return NewNode;
}

这里我们在函数中创建了一个头节点，头节点的值为-1，其实为什么都是可以的，并且它的前后指针都为NULL，同时的你也可以将他的前后指针都指向它自己，但不论怎么样，在你添加节点时都要考虑这两个指针的变化

3. 单链表的创建节点函数

List.h

//双链表的创建节点
LTNode* LTBuyNode(LTDataType x);

List.c

//双链表的创建节点
LTNode* LTBuyNode(LTDataType x) {
	LTNode* NewNode = (LTNode*)malloc(sizeof(LTNode));
	if (NewNode == NULL) {
		perror("LTBuyNode()::malloc()");
		return NULL;
	}
	NewNode->prev = NewNode->next = NULL;
	NewNode->data = x;
	return NewNode;
}

4. 双链表的尾插

双链表的尾插与单链表的尾插只有一个区别，就是两链表的尾插必须注意头节点的前指针与尾节点的后指针
List.h

//两链表的尾插
void LTPushBack(LTNode** phead, LTDataType x);

List.c

//两链表的尾插
void LTPushBack(LTNode** phead, LTDataType x) {
	assert(phead && *phead);
	
	LTNode* NewNode = LTBuyNode(x);
	//找到为尾节点
	LTNode* tail = (*phead)->prev;
	//修改指向
	tail->next = NewNode;
	NewNode->next = *phead;
	NewNode->prev = tail;
	(*phead)->prev = NewNode;
}

5. 双链表的头插

List.h

//双链表的头插
void LTPushFront(LTNode** phead, LTDataType x);

List.c

//双链表的头插
void LTPushFront(LTNode** phead, LTDataType x) {
	assert(phead && *phead);

	LTNode* NewNode = LTBuyNode(x);

	//更换指向
	NewNode->next = *phead;
	NewNode->prev = (*phead)->prev;
	(*phead)->prev->next = NewNode;
	*phead = NewNode;
}

6. 双链表的打印(正向)

List.h

//双链表的打印
void LTPrint(LTNode* phead);

List.c

//双链表的打印
void LTPrint(LTNode* phead) {
	assert(phead);

	LTNode* pcur = phead->next;
	printf("head->");
	while (pcur->next != phead) {
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("head\n");
}

7. 双向链表的尾删

双向链表的尾删与单链表的尾删也是异曲同工的，但是还是要处理头节点的指

List.h

//双链表的尾删
void LTPopBack(LTNode** pphead);

List.c

//双链表的尾删
void LTPopBack(LTNode** pphead) {
	assert(pphead && *pphead);

	LTNode* pcur = (*pphead)->next;
	if (pcur == *pphead) {
		printf("没有可删除数据！\n");
		return;
	}

	//找尾部
	while (pcur->next != *pphead) {
		pcur = pcur->next;
	}
	
	LTNode* prev = pcur->prev;

	prev->next = *pphead;
	(*pphead)->prev = prev;
	free(pcur);
}

8. 双向链表的头插

List.h

//双向链表的头删
void LTPopFront(LTNode** pphead);

List.c

//双向链表的头删
void LTPopFront(LTNode** pphead) {
	assert(pphead && *pphead);

	LTNode* pcur = (*pphead)->next;
	if (pcur == *pphead) {
		printf("没有可删除数据！\n");
		return;
	}

	LTNode* pnext = pcur->next;
	(*pphead)->next = pnext;
	pnext->prev = *pphead;
	
	free(pcur);
}

9. 双向链表的查找

List.h

//双向来链表的查找
LTNode* LTFind(LTNode* pphead, LTDataType x);

List.c

//双向来链表的查找
LTNode* LTFind(LTNode* pphead, LTDataType x) {
	assert(pphead);

	LTNode* pcur = pphead->next;
	while (pcur != pphead) {
		if (pcur->data == x) {
			return pcur;
		}
		pcur = pcur->next;
	}

	return NULL;
}

10. 双向链表的销毁

List.h

//双向链表的销毁
void LTDestory(LTNode** pphead);

List.c

//双向链表的销毁
void LTDestory(LTNode** pphead) {
	assert(pphead && *pphead);
	
	LTNode* pcur = (*pphead)->next;
	if (pcur == *pphead) {
		free(pcur);
		*pphead = NULL;
		return;
	}

	LTNode* pnext = pcur;
	while (pcur != *pphead) {
		pnext = pcur->next;
		free(pcur);
		pcur = pnext;
	}
	free(pcur);
	*pphead = NULL;
}

四、End

链表的内容是非常多的，所以我只列举了两种，大家还是要多多看看代码，只要掌握了链表的基本逻辑，我们就可以自己写出属于自己的链表，谢谢大家的阅读！


http://www.kler.cn/a/467886.html

相关文章：

  • 数学建模入门——描述性统计分析
  • Spring AMQP ----注解篇
  • 鸿蒙NEXT使用request模块实现本地文件上传
  • winform中使用panuon开源UI库的问题
  • 苍穹外卖 项目记录 day03
  • http性能测试命令ab
  • 若依修改超级管理员admin的密码
  • 【Leetcode 每日一题】732. 我的日程安排表 III
  • 【阅读笔记】基于FPGA的红外图像二阶牛顿插值算法的实现
  • CSS——1.优缺点
  • 权限管理的方法
  • 微信小程序页面传参传对象
  • 特种作业操作证考试题库及答案（登高架设作业）
  • 功能篇：vue中的vuex使用例子
  • windows11（或centos7）安装nvidia显卡驱动、CUDA、cuDNN
  • Lucas-Kanade光流法详解
  • vue路由模式面试题
  • ffmpeg filter 滤镜命令
  • yolo目标检测之摄像头检测
  • vulkan从小白到专家——VulkanSwapChain
  • 《Rust权威指南》学习笔记（一）
  • Linux一些问题
  • Android 系统 `android.app.Application` 类的深度定制
  • Jellyfin播放卡顿，占CPU的解决方法
  • 数学常用术语作用reminder
  • 供应链系统设计-供应链中台系统设计（七）- 商品中心设计篇