• 【数据结构】单链表

    在这里插入图片描述
    🔥博客主页： 小羊失眠啦.
    🎥系列专栏：《C语言》 《数据结构》 《Linux》《Cpolar》
    ❤️感谢大家点赞👍收藏⭐评论✍️

    在这里插入图片描述

    文章目录

    • 前言
    • 一、什么是链表
      • 1.1 链表的概念及结构
      • 1.2 链表的分类
      • 1.3 单链表的结构
    • 二、链表的实现
      • 📖2.1 创建节点
      • 📖2.2 头插
      • 📖2.3 头删
      • 📖2.4 尾插
        • 💭链表不为空
        • 💭链表不为空
      • 📖2.5 尾删
      • 📖2.6 查找
      • 📖2.7 在pos位置之前插入
      • 📖2.8 在pos位置之后插入
      • 📖2.9 删除pos位置
      • 📖2.10 删除pos后面位置
      • 📖2.11 销毁
    • 三、总代码

    前言

    在上一期中我们学习了顺序表，顺序表可以通过索引（下标）快速地存、取表中元素，但文章末尾提及它有缺点，例如头插或从中间插入效率低等，而链表可以有效的解决这些问题。那么就让我们走进链表的学习~~

    一、什么是链表

    1.1 链表的概念及结构

    概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

    结构：

    在这里插入图片描述

    注意：

    1.链式结构在逻辑上是连续的，但在物理上不一定连续。

    2.节点都是从堆上申请的。

    3.从堆上申请空间，是按一定策略分配的，申请的空间可能连续，也可能不连续。

    1.2 链表的分类

    • 单向或者双向（单链表或者双链表）
    • 带头或者不带头（带哨兵位和不带哨兵位）
    • 循环或者非循环

    1.3 单链表的结构

    typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    这种链表被称为无头+单向+非循环链表

    二、链表的实现

    📖2.1 创建节点

    我们想使用链表来实现各种功能得先有链表，所以首先使用malloc创建节点。

    SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    在这里插入图片描述

    📖2.2 头插

    要想让链表连起来，就要让newnode->next存放下一个节点的地址，也就是旧链表plist的值，然后将newnode的地址存放在plist中，形成新的链表。无论一开始有没有节点，头插都是相同的。

    在这里插入图片描述

    // 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);

	newnode->next = *pplist;
    //*pplist=plist
	*pplist = newnode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    在这里插入图片描述

    📖2.3 头删

    头删时如果先释放空间，就会找不到下一个节点的地址；如果先把下一个节点的地址赋给*pplist就会导致无法释放空间，所以我们要创建一个临时变量来存放下一个节点的地址。

    // 单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(*pplist);

	SListNode* newnode = (*pplist)->next;
	free(*pplist);
	*pplist = newnode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    在这里插入图片描述

    📖2.4 尾插

    我们在尾插时，会有两种情况，链表为空的插入和有其他节点的尾插。第一种情况会出现一些理解性的错误，接下来就让我们学习学习这两种尾插的情况。

    💭链表不为空

    在这里插入图片描述

    当我们传递的是plist的值，屏幕上并没有打印出我们想要的结果。这是为什么呢？

    形参是实参的一份临时拷贝，形参的改变不会影响实参，pplist的改变不会影响plist。 临时变量出作用域销毁，phead和newnode销毁，找不带开辟的节点，会造成内存泄漏。

    确做法是要将plist的地址传递过去，我们通过解引用就可以改变plist。plist中存放的是指针，我们传递指针的地址要用二级指针接收。

    💭链表不为空

    链表不为空时，我们要找到尾节点。这里我们要注意不能使用 tail!=NULL 判断。这样我们无法把链表连接起来。

    // 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
    assert(pplist);
	SListNode* newnode = BuySListNode(x);
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    📖2.5 尾删

    在尾删时也有两种情况，一种是有很多节点，另一种是只剩一个节点，当删最后一个节点时，要改变plist的值，所以我们要传递plist的指针。我们要使用两个指针，当后面的指针释放后，可以利用前面的指针将最后一个节点的next置为空。

    // 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(*pplist);
    //一个
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
    //多个
	else
	{
		SListNode* tail = *pplist;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    在这里插入图片描述

    📖2.6 查找

    循环判断时不要使用cur->next，这样写最后一个数据要单独处理不方便，找到时就返回此时的地址。

    // 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{

	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    📖2.7 在pos位置之前插入

    在pos位置之前插入有一种特殊的情况就是头插，要改变plist的值，我们要传二级指针进去。同时我们要创建一个指针变量，找到pos之前的位置，才能使链表连接起来。

    void SListInsertAfter(SListNode** pplist,SListNode* pos, SLTDateType x)
{
	assert(pos);
	if (pos == *pplist)
	{
		SListPushFront(pplist, x);
	}
	else
	{
		SListNode* prev = *pplist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SListNode* newnode = BuySListNode(x);
		newnode->next = pos;
		prev->next = newnode;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    📖2.8 在pos位置之后插入

    这里我们要注意地址赋值的顺序，顺序不对会造成内存泄漏。如果先把newnode的地址赋给pos的指针域，就会丢失下一个节点的地址。

    void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    📖2.9 删除pos位置

    有可能删除的是头节点，所以要传递二级指针。

    // 删除pos位置
void SLTErase(SListNode** pplist, SListNode* pos)
{
	assert(pos);
	if (pos == *pplist)
	{
		SListPopFront(pplist);
	}
	else
	{
		SListNode* prev = *pplist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		pos = NULL;
		free(pos);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    📖2.10 删除pos后面位置

    void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SListNode* next = pos->next;
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    📖2.11 销毁

    void SListDestory(SListNode** pplist)
{
	assert(pplist);
	SListNode* cur = *pplist;
	SListNode* next = NULL;
	while (cur->next != NULL)
	{
		next = cur->next;
		free(cur);
		cur = NULL;
	}
	*pplist = NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    三、总代码

    SList.h

    #pragma once
// slist.h
#include
#include
#include

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之前插入x
void SListInsert(SListNode** pplist,SListNode* pos, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos,SLTDateType x);
// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos);
// 删除pos后面位置
void SListEraseAfter(SListNode* pos);
// 销毁
void SListDestory(SListNode** pplist);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    SList.c

    #define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

// 单链表打印
void SListPrint(SListNode* plist)
{
	SListNode* tail = plist;
	while (tail)
	{
		printf("%d->", tail->data);
		tail = tail->next;
	}
	printf("NULL\n");
}

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);

	newnode->next = *pplist;
	*pplist = newnode;
}

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(*pplist);
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

// 单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(*pplist);

	SListNode* newnode = (*pplist)->next;
	free(*pplist);
	*pplist = newnode;

}

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{

	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return 0;
}


void SListInsert(SListNode** pplist,SListNode* pos, SLTDateType x)
{
	assert(pos);
	if (pos == *pplist)
	{
		SListPushFront(pplist, x);
	}
	else
	{
		SListNode* prev = *pplist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SListNode* newnode = BuySListNode(x);
		newnode->next = pos;
		prev->next = newnode;
	}
}
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

// 删除pos位置
void SLTErase(SListNode** pplist, SListNode* pos)
{
	assert(pos);
	if (pos == *pplist)
	{
		SListPopFront(pplist);
	}
	else
	{
		SListNode* prev = *pplist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		pos = NULL;
		free(pos);
	}
}

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SListNode* next = pos->next;
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}


void SListDestory(SListNode** pplist)
{
	assert(pplist);
	SListNode* cur = *pplist;
	SListNode* next = NULL;
	while (cur->next != NULL)
	{
		next = cur->next;
		free(cur);
		cur = NULL;
	}
	*pplist = NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185

    本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，小羊一定认真修改，写出更好的文章~~

    在这里插入图片描述

  • 相关阅读:
    git的基本使用
    暑假leetcode剑指offer每日一题打卡-第二十天-剑指 Offer 49. 丑数（middle）
    css 分割线中间带文字
    c++程序实例
    vulnhub靶场之HARRYPOTTER: ARAGOG (1.0.2)
    在DevExpress的GridView的列中，动态创建列的时候，绑定不同的编辑处理控件
    Duchefa丨P1001植物琼脂中英文说明书
    GCP设置Proxy来连接Cloud SQL
    “全数前进”媒体交流会在京举办
    python,修改数组【第十届】【省赛】【研究生组】
  • 原文地址：https://blog.csdn.net/hsjsiwkwm/article/details/134237707