链表基础知识（一、单链表）

一、链表表示和实现

顺序表的问题及思考 
问题：
1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到
200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：
如何解决以上问题呢？下面给出了链表的结构来看看。

1.1 链表的概念及结构 

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，用于存储逻辑关系为 “一对一” 的数据。链表中每个数据的存储都由以下两部分组成：
  1.数据元素本身，其所在的区域称为数据域。
  2.指向直接后继元素的指针，所在的区域称为指针域。

   （单链表的节点）

数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

 

  

二、链表的分类：

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

1. 单向、双向
2. 带头、不带头
3. 循环、非循环

  • 头节点：是一个节点，本质上是一个结构体变量，区分数据域和指针域，不存放任何数据，只存放指向链表中真正存放数据的第一个节点的地址，仅用于辅助管理整个链表的结构。

  • 头指针：是一个指针，本质上是一个结构体类型的指针变量，不区分数据域和指针域，它仅存储链表中第一个节点的地址。

  • 带头节点也就意味着不需要传二级指针了

 

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

2.2链表和顺序表的对比

三、单链表

3.1单链表的优劣：

1、查找速度慢

2、 不能从后往前

3、找不到前驱

4、单向链表不能自我删除，需要靠辅助节点 。

无头+单向+非循环链表增删查改实现

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

3.2SList.h 

#pragma once //防止重复包含
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLTDataType;//方便改变数据类型
struct SListNode
{
	SLTDataType data;
	struct SListNode* next;//下一个地址
	//结构体中嵌套指针,但不能嵌套自己,会死循环
}SLTNode;
typedef struct SListNode STLNode;


// 不会改变链表的头指针，传一级指针
void SListPrint(STLNode* phead);

// 可能会改变链表的头指针，传二级指针
void SListPushBack(STLNode** pphead, SLTDataType x);
void SListPushFront(STLNode** pphead, SLTDataType x);//分有节点头插和无节点头插,尾插得分开处理
void SListPopFront(STLNode** pphead);
void SListPopBack(STLNode** pphead);

// 不会改变链表的头指针，传一级指针
STLNode* SListFind(STLNode* pphead, SLTDataType x);
// 在pos的前面插入x
void SListInsert(STLNode** pphead, STLNode* pos, SLTDataType x);
// 删除pos位置的值
void SListErase(STLNode** pphead, STLNode* pos);


有些地方也有这样定义
 在pos的前面插入x
//void SListInsert(STLNode** phead, int i, SLTDataType x);
 删除pos位置的值
//void SListErase(STLNode** phead, int i);

3.3打印链表

第一步：输出第一个节点的数据域，输出完毕后，让指针保存后一个节点的地址

 第二步：输出移动地址对应的节点的数据域，输出完毕后，指针继续后移 

 第三步：以此类推，直到节点的指针域为NULL

void SListPrint(STLNode* phead)
{
	STLNode* cur = phead;
	while (cur != NULL)//第一个地址不为空
	{
		printf("%d->", cur->data);
		cur = cur->next;//令cur下一个地址
	}
	printf("NULL\n");

}

3.4新建一个节点

函数中的 malloc 用于在堆上分配内存。它返回一个指向新分配内存的指针，该指针被转换为 stlNode* 类型并存储在 newnode 变量中。这个新节点被初始化为包含一个 data 字段和一个 next 字段，其中 data 字段被设置为参数 x 的值，而 next 字段被初始化为 NULL。

STLNode* BuySListNode(SLTDataType x)
{
	STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
	newnode->data = x;
	newnode->next = NULL;
}

3.5尾插

void SListPushBack(STLNode** pphead, SLTDataType x)
//void SListPushBack(STLNode*& pphead, SLTDataType x)
//在					C++语法中可以加&,引用,别名
{
	STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
	newnode->data = x;
	newnode->next = NULL;
	
	// 找尾节点的指针
	if (*pphead == NULL)//pphead是plist的地址
	{
		*pphead = newnode;//在尾部创建新节点
	}
	else {
		STLNode* tail = *pphead;//phead在开始时为空
		while (tail->next != NULL)//判断下一个指针是否为空
		{
			tail = tail->next;//指向下一个节点
		}

		// 尾节点，链接新节点
		tail->next = newnode;
	}
}

3.6头插

void SListPushFront(STLNode** pphead, SLTDataType x)
{
	STLNode* newnode = BuySListNode(x);//新建一个节点
	newnode->next = *pphead;//在第一个地址前建立一个新节点
	*pphead = newnode;//使新节点变为第一个地址
}

3.7头删

void SListPopFront(STLNode** pphead)
{
	STLNode* next = (*pphead)->next;//保存下一个地址
	free(*pphead);//释放空间
	*pphead = next;//令其指针指向下一个地址
}

3.8尾删

 尾删的目的是从给定的单链表中删除最后一个节点，所以分三种情况：

1、链表为空        

2、链表只有一个节点        

3、链表有多个节点

链表为空：

如果链表为空（*pphead == NULL），那么就没有什么可以删除的内容，所以函数直接返回。

只有一个节点时：

有多个节点时：

如果链表有多个节点，我们需要找到链表的最后一个节点，并删除它。为了找到最后一个节点，我们设置两个指针 prev 和 tail，开始时都指向链表头。然后我们遍历链表，直到找到最后一个节点。找到后，我们释放最后一个节点的内存，然后把倒数第二个节点的 next 设置为 NULL，表示链表最后一个节点已经被删除。

void SListPopBack(STLNode** pphead)
{
	//1.空
	//2.一个节点
	//3.一个以上节点
	if (*pphead == NULL)//1.空
    //如果为空，说明链表已经为NULL，没有可以删除的内容了
	{
		return;
	}
	else if ((*pphead)->next == NULL)//2.一个节点
	{
		free(*pphead);//1.先释放
		*pphead = NULL;//2.把plist置成空
	}
	else {
        //3.一个以上节点
		STLNode* prev = NULL;
		STLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	
	}
}

3.9查找

其实就是遍历一遍链表，但是只能返回第一次出现的地址。我们查找到节点的地址后就可以通过地址去修改数据域中存储的数据。

TLNode* SListFind(STLNode* phead, SLTDataType x)
{
	STLNode* cur = phead;
	while (cur != NULL)
	//while (cur)
	{
		if (cur->data = x)
		{
			return cur;//找到了
		}
		cur = cur->next;
	}
	return NULL;
}

3.10在pos的前面插入

  • //创建新节点 stlNode* newnode = BuySListNode(x); 

  • // 初始时，prev 指向链表的头节点 pphead。 stlNode* prev = *pphead;

  • while (cur != pos) // 这个 while 循环用于找到 pos 节点。  

  • prev = prev->next; cur = cur->next; //如果 cur 不等于 pos，那么移动 prev 和 cur。prev 移动到 cur 的下一个节点。cur 移动到下一个节点。

  • prev->next = newnode;//现在，prev 指向 pos 的前一个节点，cur 指向 pos 节点本身。我们将新节点插入到 prev 和 cur 之间。

  • prev->next = newnode; // 然后，我们将新节点的 next 指向 pos，这样新节点就位于 pos 之前了。

void SListInsert(STLNode** pphead, STLNode* pos, SLTDataType x)
{
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else {
		STLNode* newnode = BuySListNode(x);
		STLNode* prev = *pphead;
		/*while (prev->next != pos)*/
		STLNode* cur = *pphead;
		while (cur != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	
	}
}

3.11删除pos位置的值

void SListErase(STLNode** pphead, STLNode* pos)
{
	if (pos == *pphead)//如果要删除的是头节点
	{
		SListPopFront(pphead);//头删
	}
	else {
		STLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;//删除指定位置的节点
		free(pos);//释放要删除节点的内存
	}
}

四、SList.c

#include"SeqList.h"

void SListPrint(STLNode* phead)
{
	STLNode* cur = phead;
	while (cur != NULL)//第一个地址不为空
	{
		printf("%d->", cur->data);
		cur = cur->next;//令cur下一个地址
	}
	printf("NULL\n");

}

STLNode* BuySListNode(SLTDataType x)
{
	STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
	newnode->data = x;
	newnode->next = NULL;
}

//尾插
void SListPushBack(STLNode** pphead, SLTDataType x)
//void SListPushBack(STLNode*& pphead, SLTDataType x)
//在					C++语法中可以加&,引用,别名
{
	STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
	newnode->data = x;
	newnode->next = NULL;
	
	// 找尾节点的指针
	if (*pphead == NULL)//pphead是plist的地址
	{
		*pphead = newnode;
	}
	else {
		STLNode* tail = *pphead;//phead在开始时为空
		while (tail->next != NULL)//判断下一个指针是否为空
		{
			tail = tail->next;
		}

		// 尾节点，链接新节点
		tail->next = newnode;
	}
}


void SListPushFront(STLNode** pphead, SLTDataType x)
{
	STLNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}


void SListPopFront(STLNode** pphead)
{
	STLNode* next = (*pphead)->next;//保存下一个地址
	free(*pphead);//释放空间
	*pphead = next;//令其指针指向下一个地址
}

void SListPopBack(STLNode** pphead)
{
	//1.空
	//2.一个节点
	//3.一个以上节点
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);//1.先释放
		*pphead = NULL;//2.把plist置成空
	}
	else {
		STLNode* prev = NULL;
		STLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	
	}
}


STLNode* SListFind(STLNode* phead, SLTDataType x)
{
	STLNode* cur = phead;
	while (cur != NULL)
	//while (cur)
	{
		if (cur->data = x)
		{
			return cur;//找到了
		}
		cur = cur->next;
	}
	return NULL;
}

// 在pos的前面插入x
void SListInsert(STLNode** pphead, STLNode* pos, SLTDataType x)
{
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else {
		STLNode* newnode = BuySListNode(x);
		STLNode* prev = *pphead;
		/*while (prev->next != pos)*/
		STLNode* cur = *pphead;
		while (cur != pos)

		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	
	}
}
// 删除pos位置的值
void SListErase(STLNode** pphead, STLNode* pos)
{
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else {
		STLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

五、Test.c

#include"SeqList.h"

void TestSList1()
{
	STLNode* plist = NULL;//先让plist指向空
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	//插入几个值,用节点存起来
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 0);
	SListPrint(plist);
	
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPrint(plist);
	
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPrint(plist);
}
void TestSList3()
{
	STLNode* plist = NULL;//先让plist指向空
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	//插入几个值,用节点存起来
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);

	/*SListPopBack(&plist);
	SListPopBack(&plist);
	SListPrint(plist);*/
	//想在3的前面插入一个数字
	STLNode* pos = SListFind(plist, 1);
	if (pos)
	{
		SListInsert(&plist, pos, 10);
	}
	SListPrint(plist);

	pos = SListFind(plist, 3);
	if (pos)
	{
		SListInsert(&plist, pos, 30);
	}
	SListPrint(plist);
}

void TestSList4()
{
	STLNode* plist = NULL;//先让plist指向空
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);

	STLNode* pos = SListFind(plist, 3);
	if (pos)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);

	pos = SListFind(plist, 4);
	if (pos)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);
}

int main()
{
	TestSList4();

	return 0;
}

今天就先到这了！！！

看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！

你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信！！!

关注必回！！！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/241760.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【CANoe】CANoe手动发送XCP报文读取观测量

【CANoe】CANoe手动发送XCP报文读取观测量

文章目录 1、硬件连接&#xff1a;配置CANoe的CAN端口&#xff0c;连接到ECU标定对应的CAN口2、配置CAN IG模块报文&#xff1a;连接XCP&#xff0c;读取观测量&#xff0c;断开XCP3、报文解析4、参考资料 1、硬件连接&#xff1a;配置CANoe的CAN端口&#xff0c;连接到ECU标定…
阅读更多...
【JUC】二十七、synchronized锁升级之无锁

【JUC】二十七、synchronized锁升级之无锁

文章目录 1、背景2、Monitor、Java对象、线程如何关联起来的&#xff1f;3、synchronized锁升级4、锁升级之无锁 关于synchronized同步&#xff0c;能用无锁结构就不要用锁&#xff1b;能锁块&#xff0c;就不要锁整个方法&#xff1b;能用对象锁&#xff0c;就不要用类锁。 用…
阅读更多...
探秘机器学习核心逻辑：梯度下降的迭代过程 (图文详解)

探秘机器学习核心逻辑：梯度下降的迭代过程 (图文详解)

一 需求解函数 f() 和 g()函数分别为求y值和求导数的函数。 目的&#xff1a;求该函数的最小值&#xff1a; 代码&#xff1a; import numpy as np import matplotlib.pyplot as plt f lambda x : (x - 3.5) ** 2 - 4.5 * x 10 g lambda x : 2 * (x - 3.5) - 4.5x np.l…
阅读更多...
1.3 什么是接口？什么是接口测试？

1.3 什么是接口？什么是接口测试？

上一小节我们认识了C/S和B/S架构，那在B/S架构中，我们测试最常接触的，就是接口。本课程的重点是接口自动化测试，那同学们真的了解什么是接口吗？首先，我们从通俗的角度来看什么是接口。在计算机中，接口是计算机系统中两个独立的部件进行信息交换的共享边界。这种交换可以发…
阅读更多...
ARM day8

ARM day8

1.题目&#xff1a;主机获取从机里面的温湿度数据&#xff0c;并打印出来 结果&#xff1a; 代码&#xff1a; main.c #include "iic.h"#include "si7006.h"void delay(int ms){int i,j;for(i0;i<ms;i){for(j0;j<2000;j);}}int main(){short tem;…
阅读更多...
ThingsBoard 前端项目轮播图部件开发

ThingsBoard 前端项目轮播图部件开发

前言 ThingsBoard 是目前 Github 上最流行的开源物联网平台&#xff08;14.6k Star&#xff09;&#xff0c;可以实现物联网项目的快速开发、管理和扩展, 是中小微企业物联网平台的不二之选。 本文介绍如何在 ThingsBoard 前端项目中开发轮播图部件。 产品需求 最近接到产品…
阅读更多...
自动化测试、压力测试、持续集成

自动化测试、压力测试、持续集成

因为项目的原因&#xff0c;前段时间研究并使用了 SoapUI 测试工具进行自测开发的 api。下面将研究的成果展示给大家&#xff0c;希望对需要的人有所帮助。 SoapUI 是什么&#xff1f; SoapUI 是一个开源测试工具&#xff0c;通过 soap/http 来检查、调用、实现 Web Service …
阅读更多...
python笔记（1）安装环境

python笔记（1）安装环境

1&#xff0c;官网下载自己电脑位数的安装包 https://www.python.org/downloads/windows/ install时勾选中add to path&#xff0c;把路径自动添加到环境变量 安装pycharm就不讲了 安装后选中自己的python安装包 file-> setting->project:yourprojectname ->pyt…
阅读更多...
k8s-8 ingress

k8s-8 ingress

ExternalName类型 当集群外的资源往集群内迁移时&#xff0c;地址并不稳定&#xff0c;访问域名或者访问方式等会产生变化&#xff1b; 使用svc的方式来做可以保证不会改变&#xff1a;内部直接访问svc&#xff1b;外部会在dns上加上解析&#xff0c;以确保访问到外部地址。 …
阅读更多...
CleanMyMac X2024(Mac优化清理工具)v4.14.5中文版

CleanMyMac X2024(Mac优化清理工具)v4.14.5中文版

CleanMyMac X是一款颇受欢迎的专业清理软件&#xff0c;拥有十多项强大的功能&#xff0c;可以进行系统清理、清空废纸篓、清除大旧型文件、程序卸载、除恶意软件、系统维护等等&#xff0c;并且这款清理软件操作简易&#xff0c;非常好上手&#xff0c;特别适用于那些刚入手苹…
阅读更多...
数字中台建设指南（大数据平台）

数字中台建设指南（大数据平台）

制定数字中台战略规划&#xff1a;制定符合企业实际情况的数字中台战略规划&#xff0c;明确建设目标、重点任务和时间表。确定数字中台架构&#xff1a;根据企业业务需求和特点&#xff0c;确定数字中台的架构&#xff0c;包括技术架构、应用架构和数据架构。搭建数字中台基础…
阅读更多...
java设计模式学习之【享元模式】

java设计模式学习之【享元模式】

文章目录 引言享元模式简介定义与用途实现方式 使用场景优势与劣势在Java中的应用享元模式在Spring中的应用画图示例代码地址 引言 想象一下&#xff0c;您正在开发一个游戏&#xff0c;游戏中有成千上万的树木和建筑。如果每个对象都独立存储它的所有数据&#xff0c;将会占用…
阅读更多...
postman接口测试系列： 时间戳和加密

postman接口测试系列： 时间戳和加密

在使用postman进行接口测试的时候&#xff0c;对于有些接口字段需要时间戳加密&#xff0c;这个时候我们就遇到2个问题&#xff0c;其一是接口中的时间戳如何得到&#xff1f;其二就是对于现在常用的md5加密操作如何在postman中使用代码实现呢&#xff1f; 下面我们以一个具体的…
阅读更多...
蚂蚁SEO实用的网络baidu蜘蛛有哪些

蚂蚁SEO实用的网络baidu蜘蛛有哪些

网络蜘蛛是一种用于从互联网上自动抓取信息的程序。它们根据给定的规则和指令&#xff0c;遍历网站上的页面&#xff0c;收集信息并将其存储在数据库中。网络蜘蛛在搜索引擎、数据挖掘、信息提取等领域有着广泛的应用。本文将介绍一种实用的网络蜘蛛&#xff0c;并探讨其实现原…
阅读更多...
快速二维相位解包算法基于按照非连续路径进行可靠性排序

快速二维相位解包算法基于按照非连续路径进行可靠性排序

Miguel Arevallilo Herra ez, David R. Burton, Michael J. Lalor, and Munther A. Gdeisat 摘要&#xff1a; 据我们所知&#xff0c;我们描述了一种新的相位展开技术。已经提出了几种基于首先展开最可靠像素的算法。这些仅限于连续路径&#xff0c;并且在定义起始像素时会遇…
阅读更多...
结合eNSP实验讲VLAN，让理论生动

结合eNSP实验讲VLAN，让理论生动

目录 一、VLAN的简介 1、定义 2、产生的原因--解决传统以太网的问题 3、VLAN的作用 4、VLAN数据帧格式--插入VLAN标签 5、VLAN的种类 5.1静态VLAN--常用 5.1.1静态vlan的范围 5.2动态VLAN 6、VLAN的三种端口类型 6.1Access接口 6.2Trunk接口 6.3Hybrid接口 二、配置…
阅读更多...
Nodejs 第二十三章（Markdown 转 html）

Nodejs 第二十三章（Markdown 转 html）

Markdown 转换html 是一个非常常见的需求 什么是 Markdown ? Markdown 是一种轻量级标记语言&#xff0c;它允许人们使用易读易写的纯文本格式编写文档。 我们需要用到三个库实现 EJS&#xff1a;一款强大的JavaScript模板引擎&#xff0c;它可以帮助我们在HTML中嵌入动态内…
阅读更多...
linux中堡垒机

linux中堡垒机

堡垒机 堡垒机概念目的 安装Jumpserver使用资产管理资产列表创建需要管理的服务器创建用户权限管理页面进行资产授权操作视频 应用管理应用管理页面创建需要管理的应用&#xff0c;这里用数据库mysql举例进入后点击创建资产管理创建登录应用所需的用户选择创建mysql关系型数据库…
阅读更多...
IP地址在流量管理中的作用

IP地址在流量管理中的作用

随着互联网的快速发展&#xff0c;流量管理已成为各行业面临的重要问题。IP地址作为一种标识网络中设备的重要标识符&#xff0c;在流量管理中发挥着重要作用。本文将介绍IP地址在流量管理中的应用&#xff0c;以帮助读者更好地理解这一领域的发展。 一、IP地址的分类与标识 I…
阅读更多...
【C++】输入输出流 ⑥ ( cout 标准输出流对象 | cout 常用 api 简介 | cout.put(char c) 函数 )

【C++】输入输出流 ⑥ ( cout 标准输出流对象 | cout 常用 api 简介 | cout.put(char c) 函数 )

文章目录 一、cout 标准输出流对象1、cout 标准输出流对象简介2、cout 常用 api 简介 二、cout.put(char c) 函数1、cout.put(char c) 函数 简介2、代码示例 - cout.put(char c) 函数 一、cout 标准输出流对象 1、cout 标准输出流对象简介 cout 是 标准输出流 对象 , 是 ostrea…
阅读更多...
最新文章

Copyright @ 2022~2023