【数据结构实战】从零开始打造你的专属链表

    

🏝️专栏：【数据结构实战篇】

🌅主页：f狐o狸x

目录

一、链表的概念及结构

二、链表的分类

        2.1 单向的或双向的

        2.2 带头的或不带头的

        2.3 循环或非循环

        三、链表的实现

        3.1 打印和动态申请一个结点

        3.2 尾插一个数

        3.3 头插一个数

        3.4 尾删一个数

 3.5 头删一个数

        3.6 查找数据

        3.7 pos位置插入数据

        3.8 pos位置删除数据

         3.9 销毁链表

四、链表代码

        本期我们接着上期的来，开始我们的链表环节

一、链表的概念及结构

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

        我们可以看出：

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

        2. 现实中 ，每一个节点都需要用malloc向堆栈申请

        3. 申请出来的空间可能连续，也有可能是不连续的

二、链表的分类

        实际中链表的结构非常多样，这里介绍几种类别

        2.1 单向的或双向的

        

        2.2 带头的或不带头的

        带头的链表也被称为哨兵位

        2.3 循环或非循环

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

        三、链表的实现

        我们先实现单链表

typedef int SLDataType;

typedef struct SListNode
{
	SLDataType data;
	struct SList* next;
}SListNode;

        先在头文件中声明好单链表

        3.1 打印和动态申请一个结点

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

// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newcode = (SListNode*)malloc(sizeof(SListNode));
	if (newcode == NULL)
	{
		perror("SListPushBack::malloc");
		return NULL;
	}
	newcode->next = NULL;
	newcode->data = x;
	return newcode;
}

        3.2 尾插一个数

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{
	SListNode* newcode = BuySListNode(x);
	//检查单链表是否为空
	if (*pplist == NULL)
	{
		*pplist = newcode;
	}
	else
	{
		SListNode* tail = *pplist;
		//找尾
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newcode;
	}
}

        3.3 头插一个数

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
	SListNode* NewCode = BuySListNode(x);
	NewCode->next = *pplist;
	*pplist = NewCode;
}

        3.4 尾删一个数

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(*pplist);
	//只有一个节点
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		//找尾	
		SListNode* tail = *pplist;
		SListNode* prev = NULL;;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		//删除节点
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}

}

        也可以这样尾删

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(*pplist);
	//只有一个节点
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		找尾	
		//SListNode* tail = *pplist;
		//SListNode* prev = NULL;;
		//while (tail->next)
		//{
		//	prev = tail;
		//	tail = tail->next;
		//}
		删除节点
		//free(tail);
		//tail = NULL;
		//prev->next = NULL;

		SListNode* tail = *pplist;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		//删除节点
		free(tail->next);
		tail->next = NULL;

		
	}

}

 3.5 头删一个数

// 单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(*pplist);
	SListNode* del = *pplist;
	*pplist = (*pplist)->next;
	free(del);
	del = NULL;
}

        3.6 查找数据

        找到数据返回该节点的地址，找不到则返回null

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

        3.7 pos位置插入数据

        利用查找函数找到数据的地址之后，在该节点前面插入数据

// pos之前插入
void SListInsert(SListNode** pplist, SListNode* pos, SLTDataType x)
{
	assert(pplist);
	assert(pos);
	//申请一个节点
	SListNode* NewNode = BuySListNode(x);
	//找到pos前的位置
	SListNode* prev = NULL;
	SListNode* cur = *pplist;
	//第一个位置插入
	if (pos == *pplist)
	{
		//直接头插
		SListPushFront(pplist, x);
	}
	//其他位置插入
	else
	{
		while (cur)
		{
			if (cur == pos)
			{
				prev->next = NewNode;
				NewNode->next = cur;
			}
			prev = cur;
			cur = cur->next;
		}
	}
}

        3.8 pos位置删除数据

        同理，先找到数据节点的位置，再删除

// pos位置删除
void SLTErase(SListNode** pplist, SListNode* pos)
{
	assert(pplist);
	assert(pos);
	//pos是第一个节点
	if (pos == *pplist)
	{
		//直接头删
		SListPopFront(pplist);
	}
	//其他位置删除
	else
	{
		//找到pos前的位置
		SListNode* prev = *pplist;
		SListNode* cur = *pplist;
		while (cur != pos)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = cur->next;
		free(cur);
		cur = NULL;
	}
}

         3.9 销毁链表

        每次申请一个节点我们都用到了malloc开辟了一块空间，记得归还，有借有还，再借不难~

void DestorySList(SListNode** pplist)
{
	SListNode* del = NULL;
	while (*pplist)
	{
		del = *pplist;
		*pplist = (*pplist)->next;
		free(del);
		del = NULL;
	}
	pplist = NULL;
}

四、链表代码

#define  _CRT_SECURE_NO_WARNINGS 1;

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;

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

// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x);
// pos之前插入
void SListInsert(SListNode** pplist, SListNode* pos, SLTDataType x);
// pos位置删除
void SLTErase(SListNode** pplist, SListNode* pos);


#define  _CRT_SECURE_NO_WARNINGS 1;

#include "SList.h"

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

// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newcode = (SListNode*)malloc(sizeof(SListNode));
	if (newcode == NULL)
	{
		perror("SListPushBack::malloc");
		return NULL;
	}
	newcode->next = NULL;
	newcode->data = x;
	return newcode;
}

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{
	SListNode* newcode = BuySListNode(x);
	//检查单链表是否为空
	if (*pplist == NULL)
	{
		*pplist = newcode;
	}
	else
	{
		SListNode* tail = *pplist;
		//找尾
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newcode;
	}
}

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
	SListNode* NewCode = BuySListNode(x);
	NewCode->next = *pplist;
	*pplist = NewCode;
 }

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

	else
	{
		找尾	
		//SListNode* tail = *pplist;
		//SListNode* prev = NULL;;
		//while (tail->next)
		//{
		//	prev = tail;
		//	tail = tail->next;
		//}
		删除节点
		//free(tail);
		//tail = NULL;
		//prev->next = NULL;

		SListNode* tail = *pplist;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		//删除节点
		free(tail->next);
		tail->next = NULL;

		
	}

}

// 单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(*pplist);
	SListNode* del = *pplist;
	*pplist = (*pplist)->next;
	free(del);
	del = NULL;
}

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

// pos之前插入
void SListInsert(SListNode** pplist, SListNode* pos, SLTDataType x)
{
	assert(pplist);
	assert(pos);
	//申请一个节点
	SListNode* NewNode = BuySListNode(x);
	//找到pos前的位置
	SListNode* prev = *pplist;
	SListNode* cur = *pplist;
	//第一个位置插入
	if (pos == *pplist)
	{
		//直接头插
		SListPushFront(pplist, x);
	}
	//其他位置插入
	else
	{
		while (cur!=pos)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = NewNode;
		NewNode->next = cur;
	}
}

// pos位置删除
void SLTErase(SListNode** pplist, SListNode* pos)
{
	assert(pplist);
	assert(pos);
	//pos是第一个节点
	if (pos == *pplist)
	{
		//直接头删
		SListPopFront(pplist);
	}
	//其他位置删除
	else
	{
		//找到pos前的位置
		SListNode* prev = *pplist;
		SListNode* cur = *pplist;
		while (cur != pos)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = cur->next;
		free(cur);
		cur = NULL;
	}
}

// 销毁链表
void DestorySList(SListNode** pplist)
{
	SListNode* del = NULL;
	while (*pplist)
	{
		del = *pplist;
		*pplist = (*pplist)->next;
		free(del);
		del = NULL;
	}
	pplist = NULL;
}

        坚持学习！当你快扛不住的时候，困难也快扛不住了！

        留下你宝贵的三连叭~ QAQ

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

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

相关文章

Axure PR 9 多级下拉选择器 设计交互

Axure PR 9 多级下拉选择器 设计交互

​ 大家好&#xff0c;我是大明同学。 Axure选择器是一种在交互设计中常用的组件&#xff0c;这期内容&#xff0c;我们来探讨Axure中多级下拉选择器设计与交互技巧。 下拉列表选择输入框元件 创建选择输入框所需的元件 1.在元件库中拖出一个矩形元件。 2.选中矩形元件&…
阅读更多...
HiveSQL 中判断字段是否包含某个值的方法

HiveSQL 中判断字段是否包含某个值的方法

HiveSQL 中判断字段是否包含某个值的方法 在 HiveSQL 中&#xff0c;有时我们需要判断一个字段是否包含某个特定的值。下面将介绍几种常用的方法来实现这个功能。 一、创建示例表并插入数据 首先&#xff0c;我们创建一个名为employee的表&#xff0c;并插入一些示例数据&am…
阅读更多...
【日常问题排查小技巧-连载】

【日常问题排查小技巧-连载】

线上服务CPU飙高排查 先执行 top&#xff0c;找到CPU占用比较高的进程 id&#xff0c;&#xff08;比如 21448&#xff09; jstack 进程 id > show.txt&#xff08;jstack 21448 > show.txt&#xff09; 找到进程中CPU占用比较高的线程&#xff0c;线程 id 转换为 16 进…
阅读更多...
jmeter常用配置元件介绍总结之jsr223执行python脚本

jmeter常用配置元件介绍总结之jsr223执行python脚本

系列文章目录 安装jmeter jmeter常用配置元件介绍总结之jsr223执行python脚本 1.安装jsr223执行python插件2.基础语法介绍2.1.log2.2.parameters向脚本传参与接参2.3.vars2.4.props2.5.prev 3.常用脚本3.1.MD5加密单个参数&#xff1a;3.2.MD5加密多个参数&#xff1a;3.3.URLe…
阅读更多...
【数据结构】插入排序——直接插入排序 和 希尔排序

【数据结构】插入排序——直接插入排序 和 希尔排序

直接插入排序 和 希尔排序 一、直接插入排序二、直接插入排序的弊端三、希尔排序&#xff08;1&#xff09;对插入排序的联想&#xff08;2&#xff09;希尔排序的思路 四、直接插入排序和希尔排序效率对比1>随机生成10000个数2>我们随机生成100000个数3>我们随机生成…
阅读更多...
基于Tkinter的深度学习图像处理界面开发(二)

基于Tkinter的深度学习图像处理界面开发(二)

现在很多搞算法的人&#xff0c;跑跑代码&#xff0c;比如训练和测试代码搞得飞溜&#xff0c;但想把算法代码打包成一个软件&#xff0c;比如给它包装一个界面&#xff0c;就不会了&#xff0c;有些人会推荐用qt做界面&#xff0c;但qt的上手难度还是比较高&#xff0c;如果我…
阅读更多...
【设计模式】结构型模式（四）：组合模式、享元模式

【设计模式】结构型模式（四）：组合模式、享元模式

《设计模式之结构型模式》系列&#xff0c;共包含以下文章&#xff1a; 结构型模式&#xff08;一&#xff09;&#xff1a;适配器模式、装饰器模式结构型模式&#xff08;二&#xff09;&#xff1a;代理模式结构型模式&#xff08;三&#xff09;&#xff1a;桥接模式、外观…
阅读更多...
Scala 中 set 的实战应用 ：图书管理系统

Scala 中 set 的实战应用 ：图书管理系统

1. 创建书籍集合 首先&#xff0c;我们创建一个可变的书籍集合&#xff0c;用于存储图书馆中的书籍信息。在Scala中&#xff0c;mutable.Set可以用来创建一个可变的集合。 val books mutable.Set("朝花惜拾", "活着") 2. 添加书籍 我们可以使用操作符…
阅读更多...
Flink安装和Flink CDC实现数据同步

Flink安装和Flink CDC实现数据同步

一&#xff0c;Flink 和Flink CDC 1&#xff0c; Flink Apache Flink是一个框架和分布式处理引擎&#xff0c;用于对无界和有界数据流进行有状态计算。 中文文档 Apache Flink Documentation | Apache Flink 官方文档 &#xff1a;https://flink.apache.org Flink 中文社区…
阅读更多...
有什么初学算法的书籍推荐？

有什么初学算法的书籍推荐？

对于初学算法的读者&#xff0c;以下是一些值得推荐的书籍&#xff1a; 1、算法超简单&#xff1a;趣味游戏带你轻松入门与实践 作者&#xff1a;童晶 著 推荐理由&#xff1a;本书把趣味游戏应用于算法教学&#xff0c;提升读者的学习兴趣&#xff0c;并通过可视化的图解和动…
阅读更多...
【数据结构】堆和二叉树（2）

【数据结构】堆和二叉树（2）

文章目录 前言一、建堆和堆排序1.堆排序 二、二叉树链式结构的实现1.二叉树的遍历 三、链式二叉树的功能函数1.二叉树结点个数2.二叉树叶子结点个数3.二叉树的高度4.二叉树第k层结点个数5. 二叉树查找值为x的结点6.二叉树销毁 总结 前言 接着上一篇博客&#xff0c;我们继续分…
阅读更多...
Ubuntu24.04网络异常与应对方案记录

Ubuntu24.04网络异常与应对方案记录

PS: 参加过408改卷的ZJU ghsongzju.edu.cn 开启嘲讽: 你们知道408有多简单吗&#xff0c;操作系统真实水平自己知道就行&#xff5e;&#xff5e; Requested credits of master in UWSC30&#xff0c;in ZJU24&#xff0c;domestic master is too simple dmesg dmesg 是一个用…
阅读更多...
就是这个样的粗爆，手搓一个计算器：弧长计算器

就是这个样的粗爆，手搓一个计算器：弧长计算器

作为程序员&#xff0c;没有合适的工具&#xff0c;就得手搓一个&#xff0c;PC端&#xff0c;移动端均可适用。废话不多说&#xff0c;直接上代码。 HTML: <div class"calculator"><label for"radius">圆的半径 (r)&#xff1a;</label&…
阅读更多...
ServletContext介绍

ServletContext介绍

文章目录 1、ServletContext对象介绍1_方法介绍2_用例分析 2、ServletContainerInitializer1_整体结构2_工作原理3_使用案例 3、Spring案例源码分析1_注册DispatcherServlet2_注册配置类3_SpringServletContainerInitializer 4_总结 ServletContext 表示上下文对象&#xff0c;…
阅读更多...
【论文复现】MSA+抑郁症模型总结（三）

【论文复现】MSA+抑郁症模型总结（三）

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀MSA抑郁症模型 热门研究领域&#xff1a;情感计算的横向发展1. 概述2. 论文地址3. 研究背景4. 主要贡献5. 模型结构和代码6. 数据集介绍7. 性…
阅读更多...
使用 Umami 部署博客分析工具

使用 Umami 部署博客分析工具

Umami 简介 Umami 是一款开源且注重隐私的网站分析工具&#xff0c;可替代 Google Analytics。它提供网站流量和用户行为等见解&#xff0c;但不使用 Cookie 或收集个人数据&#xff0c;符合隐私法规。Umami 轻巧易用&#xff0c;可自行托管。 如果你有自己的博客&#xff0c;…
阅读更多...
JAVA笔记 | ResponseBodyEmitter等异步流式接口快速学习

JAVA笔记 | ResponseBodyEmitter等异步流式接口快速学习

先简单记录下简单使用跟测试&#xff0c;后续再补充具体&#xff0c;最近有用到&#xff0c;简单来说就是后端(服务端)编写个发射器&#xff0c;实现一次请求&#xff0c;一直向前端客户端发射数据&#xff0c;直到发射器执行完毕&#xff0c;模拟ai一句一句回复的效果 Respon…
阅读更多...
在IntelliJ IDEA中创建带子模块的SpringBoot工程

在IntelliJ IDEA中创建带子模块的SpringBoot工程

前言 在项目开发中&#xff0c;一个工程往往有若干子工程或模块&#xff0c;所以主工程一般是一个容器&#xff0c;本文介绍在IntelliJ IDEA中创建带多模块的SpringBoot工程的详细步骤。 1、首先打开IntellJ IDEA&#xff08;以下简称IDEA&#xff09;,创建一个新项目。假定新…
阅读更多...
【LeetCode】每日一题 2024_11_9 设计相邻元素求和服务（构造，哈希）

【LeetCode】每日一题 2024_11_9 设计相邻元素求和服务（构造，哈希）

前言 每天和你一起刷 LeetCode 每日一题~ LeetCode 启动&#xff01; 题目&#xff1a;设计相邻元素求和服务 近几天不知道力扣发什么疯&#xff0c;每日一题出的太抽象了&#xff0c;我题解是写不了一点了 . . . 今天稍微正常了些&#xff0c;就又来更新了~ 代码与解题思路…
阅读更多...
如何搭建企业内部知识库？：打造专属智能体，为企业提供高效智能的知识管理

如何搭建企业内部知识库？：打造专属智能体，为企业提供高效智能的知识管理

在当今数据爆炸的时代&#xff0c;虽然AI强大&#xff0c;但常规的AI工具或搜索引擎在面对复杂、专业领域的问题时&#xff0c;可能给出模棱两可的回应&#xff0c;无法满足企业精细化的需求。这就是为什么&#xff0c;企业需要一个专属的AI知识库 —— 它不仅能存储你的数据&a…
阅读更多...
最新文章

Copyright @ 2022~2023