• 【数据结构初阶】线性表——单链表（手撕单链表）

    大家好我是沐曦希💕

    链表

    1.链表的概念及结构

    概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
    链表逻辑的结构（形象化）：在这里插入图片描述
    物理结构（在内存中时间存储结构）:
    在这里插入图片描述

    2.链表的分类

    实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

    1. 单向或者双向
      在这里插入图片描述
    2. 带头或者不带头
      在这里插入图片描述
    3. 循环或者非循环
      在这里插入图片描述
      虽然有这么多的链表的结构，但是实际中最常用还是两种结构：
      1.无头的
    1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
    2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

    3.单链表的实现

    SList.h

    #pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
//打印单链表
void SListPrint(SLTNode* phead);
//销毁单链表
void SListDestory(SLTNode** pphead);
//动态申请一个节点
SLTNode* BuyListNode(SLTDataType x);
//单链表的尾插数据
void SListPushBack(SLTNode** pphead, SLTDataType x);
//单链表的头插数据
void SListPushFront(SLTNode** pphead, SLTDataType x);
//单链表的尾删数据
void SListPopBack(SLTNode** pphead);
//单链表的头删数据
void SListPopFront(SLTNode** pphead);
//单链表的查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
// 单链表在pos位置之前插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 单链表删除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos);
// 单链表在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SLTNode* pos);

    • 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

    要更改头结构体指针plist时，应该进行传址调用，所以用二级指针来接受。
    改谁用谁的指针。
    在很多库里面都会分别有在pos前后插入x的函数和分别有删除pos位置和删除pos位置之后的值的。

    // 单链表在pos位置之前插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 单链表删除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos);
// 单链表在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SLTNode* pos);

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

    区别在于：
    1.在pos前插入x和删除pos位置的函数声明要传单链表的头结构体指针。
    在pos前插入x时，当pos为第一个节点时，要改变头结构体指针的指向新的节点，就要传头结构体指针的地址。头结构体指针指向新的节点，新的节点的next指针指向第一个节点或者NULL。
    在这里插入图片描述
    删除pos位置的值时，当pos为第一个节点时，要改变头结构体指针的指向新的节点，就要传头结构体指针的地址。头结构体指针应该指向第二个节点或者NULL。
    在这里插入图片描述
    2.在pos前插入x和删除pos位置的实现要进行分情况讨论，
    即第一种情况为pos为第一个节点和第二种情况pos不为第一个节点，代码更为复杂。

    SList.c

    要更改头结构体指针plist时，应该进行传址调用，所以用二级指针来接受。
    改谁用谁的指针，并且传的是头节点指针的地址。

    #include"SList.h"
void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
void SListDestory(SLTNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)
	{
		return;
	}
	SLTNode* cur = *pphead;
	SLTNode* prev = *pphead;
	while (cur->next)
	{
		prev = cur;
		cur = cur->next;
		free(prev);
	}
	free(cur);
	cur = NULL;
	prev = NULL;
}
SLTNode* BuyListNode(SLTDataType x)
{
	SLTNode* ret = (SLTNode*)malloc(sizeof(SLTNode));
	if (ret)
	{
		ret->data = x;
		ret->next = NULL;
		return ret;
	}
	return NULL;
}
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* tail = *pphead;
	SLTNode* newnode = BuyListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}
	while (tail->next)
	{
		tail = tail->next;
	}
	tail->next = newnode;
}
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuyListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SListPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* cur = *pphead;
	if (cur->next == NULL)
	{
		free(cur);
		cur = NULL;
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = *pphead;
		while (cur->next)
		{
			prev = cur;
			cur = cur->next;
		}
		free(cur);
		cur = NULL;
		prev->next = NULL;
	}
}
void SListPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* cur = *pphead;
	*pphead = cur->next;
	free(cur);
	cur = NULL;
}
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	SLTNode* prev = *pphead;
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
		return;
	}
	while (prev->next != pos)
	{
		prev = prev->next;
		assert(prev);
	}
	SLTNode* newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->next = pos;
}
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	SLTNode* prev = *pphead;
	if (prev == pos)
	{
		SListPopFront(pphead);
		return;
	}
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	SLTNode* cur = prev->next;
	prev->next = cur->next;
	free(cur);
	cur = NULL;
}
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuyListNode(x);
	SLTNode* cur = pos->next;
	pos->next = newnode;
	newnode->next = cur;
}
void SListEraseAfter(SLTNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	SLTNode* cur = pos->next;
	pos->next = cur->next;
	free(cur);
	cur = 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

    1.因为头插数据，尾插数据和任意位置插入数据都需要创建一个新节点，那么就可以分装一个函数BuyListNode来创建一个新节点，并且将data设为要传的数值。
    2.在头插入数据x时，要改变头结构体指针的指向新的节点，就要传头结构体指针的地址。头结构体指针指向新的节点，新的节点的next指针指向第一个节点或者NULL。
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    3.尾插分为两种情况：
    第一种情况：当链表为空，可以调用头插函数。
    第二种情况：当链表不为空，让最后一个节点的指针next存储新节点的地址，新节点的next指针置为空。
    在这里插入图片描述

    在这里插入图片描述

    4.尾删和头删都要分三种情况讨论：
    第一种情况：链表为空。
    在这里插入图片描述
    第二种情况：链表只有一个节点。
    在这里插入图片描述
    第三种情况：链表不止一个节点，那么此时尾删和头删代码就有区别了。

    头删
    在这里插入图片描述
    尾删
    在这里插入图片描述

    5.链表的销毁：通过快慢指针进行销毁，一一释放慢指针的节点。快指针控制循环是否结束。
    在这里插入图片描述

    test.c

    #include"SList.h"
void TestSList1()
{
	SLTNode* plist = NULL;
	SListPrint(plist);
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListDestory(&plist);
}
void TestSList2()
{
	SLTNode* plist = NULL;
	SListPrint(plist);
	SListPushFront(&plist, 10);
	SListPushFront(&plist, 20);
	SListPushFront(&plist, 30);
	SListPushFront(&plist, 40);
	SListPushFront(&plist, 50);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
	SLTNode* ret = SListFind(plist, 40);
	if (ret != NULL)
	{
		SListInsert(&plist, ret, 100);
	}
	SListPrint(plist);
	ret = SListFind(plist, 100);
	if (ret != NULL)
	{
		SListErase(&plist, ret);
	}
	SListPrint(plist);
	ret = SListFind(plist, 40);
	if (ret != NULL)
	{
		SListInsertAfter(ret, 200);
	}
	SListPrint(plist);
	ret = SListFind(plist, 200);
	if (ret != NULL)
	{
		SListEraseAfter(ret);
	}
	SListPrint(plist);
	SListDestory(&plist);
}
int main()
{
	TestSList1();
	TestSList2();
	return 0;
}

    • 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

    在这里插入图片描述

    4.单链表改进

    4.1 替换法删除pos

    链表只给pos这个参数和插入的值x，要求删除pos位置，并且时间复杂度是O(1)。
    用替换法，将pos和pos->next的值互换，创建一个新指针dele指向pos->next。将pos->next->next赋值给pos->next，然后释放掉dele节点。
    在这里插入图片描述
    可以看出该方法解决这道题的致命缺点：pos不能是尾部节点。

    #include
#include
#include
struct SListNode
{
	int val;
	struct SListNode* next;
};
void SListErase(struct SListNode* pos)
{
	assert(pos);
	struct SListNode* dele = pos;
	dele = dele->next;
	pos->val = dele->val;
	pos->next = dele->next;
	free(dele);
}
int main()
{
	struct SListNode* n1 = (struct SListNode*)malloc(sizeof(struct SListNode));
	assert(n1);
	struct SListNode* n2 = (struct SListNode*)malloc(sizeof(struct SListNode));
	assert(n2);
	struct SListNode* n3 = (struct SListNode*)malloc(sizeof(struct SListNode));
	assert(n3);
	struct SListNode* n4 = (struct SListNode*)malloc(sizeof(struct SListNode));
	assert(n4);
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
	n1->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;
	struct SListNode* cur = n1;
	while (cur != NULL)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
	SListErase(n2);
	cur = n1;
	while (cur != NULL)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL");
	free(n1);
	n1 = NULL;
	free(n2);
	n2 = NULL;
	free(n4);
	n4 = NULL;
	return 0;
}

    • 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

    在这里插入图片描述

    4.2 替换法pos之前插入节点

    链表只给pos这个参数，要求pos之前插入新节点，并且时间复杂度是O(1)。
    用替换法，在pos后面插入一个新节点，并且新节点newcode的val是pos节点的val，pos->next赋值给newcode->next，pos->next指向newcode。
    在这里插入图片描述
    这种方法解决改问题是没有缺陷的。

    void SListInsert(struct SListNode* pos, int x)
{
	assert(pos);
	struct SListNode* newcode = BuyListNode(pos->val);
	pos->val = x;
	newcode->next = pos->next;
	pos->next = newcode;
}

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

    5.写在最后

    单链表只适合头插头删，因为时间时间复杂度为O(1)。双向链表适合任意位置高效的插入和删除。
    那么单链表的学习就到这里了。

  • 相关阅读:
    烟感监控小技巧，这才是最高级的方法！
    开放签电子签章企业版V1.6（紧急更新）
    注解和反射详解以及运用
    LeetCode每日一题 1921. 消灭怪物的最大数量
    js中各种数据类型检测与判定
    Java并发(二十一)----wait notify介绍
    重点来了，具有优质脂肪的坚果居然是减肥的好帮手！
    SSM整合(二)
    34 IDEA 架包,字体...
    温湿度传感器原理介绍
  • 原文地址：https://blog.csdn.net/m0_68931081/article/details/126054091