大家好我是沐曦希💕

链表

1.链表的概念及结构
2.链表的分类
3.单链表的实现
- SList.h
- SList.c
- test.c
4.单链表改进
- 4.1 替换法删除pos
- 4.2 替换法pos之前插入节点
5.写在最后

1.链表的概念及结构

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

2.链表的分类

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

单向或者双向

带头或者不带头

循环或者非循环

虽然有这么多的链表的结构，但是实际中最常用还是两种结构：

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

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);

要更改头结构体指针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.在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("NULLn");
}
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.因为头插数据，尾插数据和任意位置插入数据都需要创建一个新节点，那么就可以分装一个函数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;
}

在这里插入图片描述

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("NULLn");
	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;
}

在这里插入图片描述

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;
}

5.写在最后

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

网络知识

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

链表

1.链表的概念及结构

2.链表的分类

3.单链表的实现

SList.h

SList.c

test.c

4.单链表改进

4.1 替换法删除pos

4.2 替换法pos之前插入节点

5.写在最后

链表

1.链表的概念及结构

2.链表的分类

3.单链表的实现

SList.h

SList.c

test.c

4.单链表改进

4.1 替换法删除pos

4.2 替换法pos之前插入节点

5.写在最后

相关文章

央媒谈“文盲演员”引发饭圈甩锅大战

野生大熊猫深夜遛达 镜头前呆萌打卡

张萌谈演员到底需不需要有文化

情人节多地迎领证高峰

婚房烂尾10年业主住进毛坯房

多地首套房贷利率降至4%以下 为什么急于提前还贷

野生大熊猫深夜遛达镜头前呆萌打卡

多地首套房贷利率降至4%以下为什么急于提前还贷