• 链表（1）

    开篇备忘录： “过我嶙峋 拥我九春”

    目录

    正文开始

    1. 前言

    问题与思考

    前面我们了解了顺序表

    1. 中间/头部的插⼊删除，时间复杂度为O(N)
    2. 增容需要申请新空间，拷⻉数据，释放旧空间。会有不⼩的消耗。
    3. 增容⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插⼊了5个数据，后⾯没有数据插⼊了，那么就浪费了95个数据空间。

    链表就可以很好解决以上的问题

    首先定义链表类型，和顺序表一样， 定义一个头文件，两个源文件，在头文件中进行链表的定义和函数的声明，以及包含需要的库函数文件

    在这里插入图片描述

    在头文件中定义链表结构体

    typedef int SLTDatatype;
//定义结点的结构
typedef struct SListNode
{
	SLTDatatype data;
	struct SListNode* next;
}SLTNode;

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

    2. 链表的打印

    void SLPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur != NULL)
	{
		printf("%d ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

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

    传入一个形参， 这个形参指向了链表首地址，定义临时变量pcur指向phead, 这是一种良好的习惯， 不直接改变phead, 只要pcur->next不为NULL,就打印pcur->data 的值，然后让pcur指向下一个结点。

    这里先手动创建一些结点, 后面实现了插入函数, 就不需要手动创建了

    	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	node2->data = 2;
	node3->data = 3;
	node4->data = 4;
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
	SLTNode* plist = node1;
	SLPrint(plist);

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

    打印结果

    在这里插入图片描述

    3. 链表的插入与删除

    头插与尾插

    尾插

    首先这里需要进行传实参, 因为phead的值我可能会改变, 而不是去改变一个临时拷贝的变量, 比如说开始phead所指向的为NULL, 我需要插入一个结点而让phead指向这个结点, 这里需要断言你给我传递的链表首结点地址的地址不可以为NULL, 分为两种情况, 一开始就是空链表和非空链表, 再插入之前都需要开辟一个结点, 直接可以封装成函数.

    SLTNode* SLTBuyNode(SLTDatatype x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

//尾插
void SLPushBack(SLTNode** pphead, SLTDatatype x)
{
	assert(pphead);
	//空链表和非空链表
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)//如果链表为空
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* ptail = *pphead;//寻找最后一个节点
		while (ptail->next)//分为两种情况,否则这里会对NULL解引用
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;//找到之后让它的指针指向新的结点
	}
}

    • 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

    头插

    这里会相对简单, 因为头插无论是否为空链表, 代码都可以插入, 让新节点的指针指向头结点, 再让头指针指向新的结点,此时头结点就是新节点

    void SLPushFront(SLTNode** pphead, SLTDatatype x)
{                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

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

    测试一下

    	SLTNode* plist = NULL;
	SLPushBack(&plist, 1);
	SLPrint(plist);
	SLPushFront(&plist, 2);
	SLPrint(plist);
	SLPushFront(&plist, 3);
	SLPrint(plist);

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

    运行结果:

    在这里插入图片描述

    头删与尾删

    尾删

    这里还是分两种情况, 看代码注释

    void SLPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);//这里链表的地址不能为空,链表也不能为空,否则无结点删除
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = *pphead;//寻找尾结点的前一个结点
		SLTNode* ptail = *pphead;
		while (ptail->next)//如果删除头结点,这里终止循环
		{
			prev = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;//让尾节点的前一个结点指针指向NULL
		//这里就会非法访问
	}
}

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

    头删

    这里只需要先保存头结点的下一个结点的位置,然后释放掉头结点, 让保存的结点成为新的头结点

    void SLPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

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

    代码测试:

    	SLTNode* plist = NULL;
	SLPushBack(&plist, 1);
	SLPrint(plist);
	SLPushFront(&plist, 2);
	SLPrint(plist);
	SLPushFront(&plist, 3);
	SLPrint(plist);
	SLPopBack(&plist);
	SLPrint(plist);
	SLPopFront(&plist);
	SLPrint(plist);

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

    在这里插入图片描述

    4. 完整代码

    下面附上完整代码:

    头文件:

    #pragma once
#include
#include
#include


typedef int SLTDatatype;
//定义结点的结构
typedef struct SListNode
{
	SLTDatatype data;
	struct SListNode* next;
}SLTNode;

//打印
void SLPrint(SLTNode* phead);

//尾插
void SLPushBack(SLTNode** pphead, SLTDatatype x);
//头插
void SLPushFront(SLTNode** pphead, SLTDatatype x);

//尾删
void SLPopBack(SLTNode** pphead);
//头删
void SLPopFront(SLTNode** pphead);

    • 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

    函数的实现文件:

    #define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"

void SLPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur != NULL)
	{
		printf("%d ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

SLTNode* SLTBuyNode(SLTDatatype x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

//尾插
void SLPushBack(SLTNode** pphead, SLTDatatype x)
{
	assert(pphead);
	//空链表和非空链表
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}

//头插
void SLPushFront(SLTNode** pphead, SLTDatatype x)
{                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

//尾删
void SLPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = *pphead;
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}

//头删
void SLPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

    • 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

    5. 总结与思路

    链表是一种数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的插入、删除操作相对于数组来说更为灵活。

    头插法和尾插法是链表的两种常见插入操作。头插法是将新节点插入到链表的头部，即新节点的next指针指向原来的头节点，然后更新头节点指针；而尾插法是将新节点插入到链表的尾部，即原来的尾节点的next指针指向新节点，然后更新尾节点指针。

    头删和尾删是链表的两种常见删除操作。头删是将链表的头节点删除，即更新头节点指针为原头节点的next指针；尾删是将链表的尾节点删除，即更新尾节点指针为倒数第二个节点，并将倒数第二个节点的next指针置为空。

    本文分享先到这, 如果认为文章有帮助的话,感谢点赞收藏关注! ! !

    完

  • 相关阅读:
    录制线上课程，有哪些形式，到底使用什么软件好？
    Vue-01-前端背景介绍
    聚观早报 | 微博个人主页将展示评论；京东PLUS会员突破 3000 万
    如何通过cpolar内网穿透工具实现远程访问本地postgreSQL
    金仓数据库 KingbaseES 异构数据库移植指南 (4. 应用迁移流程）
    【报错解决】java:错误：无效的源发行版：15
    在Vue中使用腾讯云COS(建议正式环境使用)
    王道计算机考研 操作系统学习笔记 + 完整思维导图篇章二: 进程管理
    JavaScript的基本数据类型如何使用？
    2020年最全Java面试汇总整理（含答案），再也不用担心面试被挂了
  • 原文地址：https://blog.csdn.net/2201_75644377/article/details/138168931