技术博客
首页 所有文章 标签 分类 关于
技术博客

目录

笔记六单链表链表介绍与模拟实现

 收录于 未分类
   约 3230 字   预计阅读 7 分钟 
https://bing.ee123.net/img/rand?artid=146102148

笔记六：单链表链表介绍与模拟实现

在他一生中，从来没有人能够像你们这样，以他的视角看待这个世界。

———《寻找天堂》

一、什么是链表？

链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。链表由一系列节点（链表中每一个元素称为节点）组成，节点在运行时动态生成 （malloc），每个节点包括两个部分：

  • 一个是存储数据元素的 数据域
  • 另一个是存储下一个节点地址的 指针域

二、为什么要使用链表？

使用链表用于 解决动态数量的数据存储 。比如说，我们要管理一 票据，可能有一张，但也可能有一亿张。怎么办呢？申请一个几十G的大数组存储着吗？万一用户只有一百张票据要处理呢？内存较小拒绝运行？可申请少了又不够用啊……

而且，用数组的话，删除然后添加票据，是每次删除让后面五百万张往前移一格呢、还是每次添加从头搜索空闲格子？如何区分空闲格子和值为0的数据？要进行区分的话是多占用空间呢还是占用数据值域？占用了值域会不会使得数据处理变得格外复杂？会不会一不小心就和正常数据混淆？万一拿来区分的字段在某个版本后废弃不用、或者扩充值域了呢？

那么，链表这种东西就是个很有效的数据结构，可以很有效的管理这类不定量的数据。

三、 单链表介绍与使用

3.1 单链表

单链表的每个节点除了存放数据元素外，还要存储指向下一个节点的指针。与顺序表进行对比：

优点缺点
顺序表可随机存储，存储密度较高要求大片连续空间，改变容量不方便
单链表不要求大片连续空间，改变容量方便不可随机存取，要耗费一定空间存放指针

https://i-blog.csdnimg.cn/direct/34a55a6586f04d7b943bd9f7bb751812.png

3.1.1 创建单链表节点

typedef int SLTDataType;
//链表是由节点构成
//逻辑结构：一定连续；物理结构：不一定连续
//不会造成空间的浪费，由独立的节点构成
typedef struct SListNode {  //SList : single linked list 单链表
	SLTDataType data;  //  一个是存储数据元素的数据域
	struct SListNode* next;  //   另一个是存储下一个节点地址的指针域
}SLTNode;

https://i-blog.csdnimg.cn/direct/bc04b1522b284ceaa7563d03bc8516f8.png

上面的结构体仅是单链表节点的定义，要创建一新的节点需要对里面的数据进行初始化：插入数值，节点指向的下一个节点为空

//创建一个节点
struct SListNode* SLTBuyNode(SLTDataType x) {
	SLTNode* newnode = (struct SListNode*)malloc(sizeof(struct SListNode));
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

https://i-blog.csdnimg.cn/direct/fb2ed4ffd09e40988226e0cd44a2d60f.png

3.1.2 单链表的头插、尾插

单链表的尾插

https://i-blog.csdnimg.cn/direct/d816730ca923467bb0a4891989809002.png

这里传递的链表节点的参数，为什么是二级指针呢？

在初始化过程中，需要 修改头指针 ，因此要用到二级指针传递头指针的地址，这样才能修改头指针。这与普通变量类似，当需要修改普通变量的值，需传递其地址。使用二级指针，很方便就修改了传入的结点一级指针的值。 如果用一级指针，则只能通过指针修改指针所指内容，却无法修改指针的值，也就是指针所指的内存块。

//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) { //一级指针传递的为结构体变量地址的值，二级指针接收的是指向结构体变量的指针的地址
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//链表为空，新节点作为pphead
	if (*pphead == NULL) {
		*pphead = newnode;
		return;
	}
	//链表不为空，链表的尾指向新节点
	SLTNode* ptail = *pphead;
	while (ptail->next) {
		ptail = ptail->next;
	}
	ptail->next = newnode;
}
单链表的头插

https://i-blog.csdnimg.cn/direct/4cceb7a7453c41d3b4b80056d289dacd.png

void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	//链表为空，新节点指向pphead，pphead再指向新节点；链表不为空，新节点指向pphead，pphead再指向新节点
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

插入完数据后，想要打印以一下链表的数据，通过从头开始一个一个节点地访问数据，并打印，便实现了链表数据的打印。然后看看插入的情况；

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

尾插部分数据，观察打印的结果是否符合预期结果；发现运行结果与预期相符，所以链表的插入操作是没什么大问题的

https://i-blog.csdnimg.cn/direct/953e5bd1183a4c13982295d4cf56c9bb.png

3.1.3  单链表的头删、尾删

如果链表为空，不需要删除；如果删除的是第一个结点，则需要将保存链表首地址的指针保存第一个结点的下一个结点的 地址 如果删除的是中间结点，则找到中间结点的前一个结点，让前一个结点的指针域保存这个结 点的后一个结点的地址即可

单链表的尾删
void SLTPopBack(SLTNode** pphead) {
	assert(pphead);
	//链表为空，不删除
	assert(*pphead); //指向第一个节点的地址
	//链表不为空，只有一个节点
	if ((*pphead)->next = NULL) {
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//多个节点，释放最后一个节点，其前驱节点指向空
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next) {
		prev = ptail;
		ptail = ptail->next;
	}
	prev->next = NULL;
	free(ptail);
	ptail = NULL;
}
单链表的头删

https://i-blog.csdnimg.cn/direct/e7b76fe84c1d4391afc7e848e0aece77.png

void SLTPopFront(SLTNode** pphead) {
	assert(pphead);
	//链表为空，不删除
	assert(*pphead);
	//链表不为空，释放最后一个节点，其前驱节点指向空
	SLTNode* pcur = *pphead;
	*pphead = pcur->next;
	pcur->next = NULL;
	free(pcur);
	pcur = NULL;
}

3.1.4 链表节点的查找

先对比第一个结点的数据域是否是想要的数据，如果是就直接返回，如果不是则继续查找下 一个结点，如果到达最后一个结点的时候都没有匹配的数据，说明要查找数据不存在

//查找
SLTNode* STLFind(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* pcur = *pphead;
	while (pcur) {
		if (pcur->data == x) {
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

3.1.5 在指定位置插入数据

在指定位置前插入数据
//在指定位置前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	assert(pphead);
	assert(pos);
	//头节点不能为空
	assert(*pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//当pos节点指向 头节点时,进行头插
	if (*pphead == pos) {
		SLTPushFront(pphead, x);
		return;
	}
	//pos pphead不指向同一节点
	SLTNode* prev = *pphead;
	while (prev->next != pos) { //找到pos节点的前驱
		prev = prev->next;
	}
	newnode->next = pos;
	prev->next = newnode;
}
在指定位置之后插入数据
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

3.1.6 删除pos之后的节点

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {
	assert(pos);
	assert(pos->next);//pos后不为空
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}

3.1.7 销毁链表

重新定义一个指针next，保存pcur指向节点的地址，然后next后移保存下一个节点的地址，然后释放pcur对应的节点，以此类推，直到pcur为NULL为止

//销毁链表,由独立的节点构成，需要一个个销毁
void SListDestroy(SLTNode** pphead) {
	assert(pphead);
	assert(*pphead);
	SLTNode* pcur = *pphead;
	while (pcur) {
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

四、完整代码

SList.h

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

//顺序表存在的一定的问题：
//1.顺序表的中间/头部的插入需要挪动数据
//2.扩容存在性能的消耗
//3.会有空间的浪费

typedef int SLTDataType;
//链表是由节点构成
//逻辑结构：一定连续；物理结构：不一定连续
//不会造成空间的浪费，由独立的节点构成
typedef struct SListNode {  //SList : single linked list 单链表
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

//链表的头插、尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(struct SListNode** pphead, SLTDataType x);

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

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

//查找
SLTNode* STLFind(SLTNode** phead, SLTDataType x);

//在指定位置前插入数据
void SLTInsert(SLTNode** phead, SLTNode* pos,SLTDataType x);

//删除pos节点
void SLTErase(SLTNode** phead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDestroy(SLTNode** phead);

SList.c

#include"SList.h"

//创建一个节点
struct SListNode* SLTBuyNode(SLTDataType x) {
	SLTNode* newnode = (struct SListNode*)malloc(sizeof(struct SListNode));
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}


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

//链表的头插、尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) { //一级指针传递的为结构体变量地址的值，二级指针接收的是指向结构体变量的指针的地址
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//链表为空，新节点作为pphead
	if (*pphead == NULL) {
		*pphead = newnode;
		return;
	}
	//链表不为空，链表的尾指向新节点
	SLTNode* ptail = *pphead;
	while (ptail->next) {
		ptail = ptail->next;
	}
	ptail->next = newnode;
}

void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	//链表为空，新节点指向pphead，pphead再指向新节点；链表不为空，新节点指向pphead，pphead再指向新节点
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}


//链表的头删、尾删
void SLTPopBack(SLTNode** pphead) {
	assert(pphead);
	//链表为空，不删除
	assert(*pphead); //指向第一个节点的地址
	//链表不为空，只有一个节点
	if ((*pphead)->next = NULL) {
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//多个节点，释放最后一个节点，其前驱节点指向空
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next) {
		prev = ptail;
		ptail = ptail->next;
	}
	prev->next = NULL;
	free(ptail);
	ptail = NULL;
}
void SLTPopFront(SLTNode** pphead) {
	assert(pphead);
	//链表为空，不删除
	assert(*pphead);
	//链表不为空，释放最后一个节点，其前驱节点指向空
	SLTNode* pcur = *pphead;
	*pphead = pcur->next;
	pcur->next = NULL;
	free(pcur);
	pcur = NULL;
}

//查找
SLTNode* STLFind(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* pcur = *pphead;
	while (pcur) {
		if (pcur->data == x) {
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

//在指定位置前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	assert(pphead);
	assert(pos);
	//头节点不能为空
	assert(*pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//当pos节点指向 头节点时,进行头插
	if (*pphead == pos) {
		SLTPushFront(pphead, x);
		return;
	}
	//pos pphead不指向同一节点
	SLTNode* prev = *pphead;
	while (prev->next != pos) { //找到pos节点的前驱
		prev = prev->next;
	}
	newnode->next = pos;
	prev->next = newnode;
}

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {
	assert(pphead);
	assert(pos);
	//当pos节点指向 头节点时,进行头删
	if (*pphead == pos) {
		SLTPopFront(pphead);
		return;
	}
	//pos pphead不指向同一节点
	SLTNode* prev = *pphead;
	while (prev->next != pos) { //找到pos节点的前驱
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}


//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {
	assert(pos);
	assert(pos->next);//pos后不为空
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	//pos->next = del->next;
	free(del);
	del = NULL;
}

//销毁链表,由独立的节点构成，需要一个个销毁
void SListDestroy(SLTNode** pphead) {
	assert(pphead);
	assert(*pphead);
	SLTNode* pcur = *pphead;
	while (pcur) {
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}
更新于 2025-03-10
 链表, 笔记, 数据结构, C
返回 | 主页