数据结构-链表

🗡CSDN主页：d1ff1cult.🗡

🗡代码云仓库：d1ff1cult.🗡

🗡文章栏目：数据结构专栏🗡

目录

目录

代码总览：

接口slist.h：

slist.c:

1.什么是链表

1.1链表的概念

 1.2链表的分类

2.链表与顺序表

顺序表的优点与缺陷

3链表

3.1链表实现

总结

代码总览：

slist.h：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef int SLTDataType;

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

void SLTPrint(SLTNode* phead);

SLTNode* BuySListNode(SLTDataType x);
//开辟新的节点

void SLTPushBack(SLTNode** pphead, SLTDataType x);
//尾插
void SLTPushFront(SLTNode* phead, SLTDataType x);
//头插
void SLTPopBack(SLTNode** pphead);
//尾删
void SLTPopFront(SLTNode**  pphead);
//头删
void SLTInsert(SLTNode**phead,SLTNode* pos, SLTDataType x);
//在pos之前插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//在pos之后插入x
void SLTErase(SLTNode** pphead, SLTNode*pos);
//删除pos位置
void SLTEraseAfter(SLTNode* pos);
//删除pos后一个位置
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//查找

slist.c:

#define _CRT_SECURE_NO_WARNINGS
#include"slist.h"
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x) 
{
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}//头插
void SLTPopBack(SLTNode** pphead, SLTDataType x)
{
	//1.空
	assert(*pphead);
	//2.一个节点
	//3.一个以上节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		/*SLTNode* tailPrev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tailPrev = tail;
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;*/
		SLTNode* tail = *pphead;
		while(tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}
void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead);//空
	//非空
	SLTNode* newhead = (*pphead)->next;
	free(*pphead);
	*pphead = newhead;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data== x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x)
{
	assert(pos);
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
		assert(pos);
		SLTNode* newnode = BuySListNode(x);
		newnode->next = pos->next;
		pos->next = newnode;
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* posNext = pos->next;
	pos->next = posNext->next;
	free(posNext);
	posNext = NULL;
}

1.什么是链表

1.1链表的概念

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

96cd35bb14c440be979abea5657c77fe.png

 2fe2c859e4054c178d5ede5c3ae66ce3.png

 从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续现实中的结点一般都是从堆上申请出来的从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

22587d64336a4323b7a0a51a0da775bf.png

 1.2链表的分类

1.带头或不带头

2.循环或不循环

3.双向或单向

67297e973b054a16a8cddcafe624fc59.png

2.链表与顺序表

顺序表的优点与缺陷

顺序表的数据在物理空间上是连续存放的，使得我们用数组下标访问变的十分简单，尾插尾删的效率比较高，但同时想要在中间删除数据时，需要将数据一个个挪动，效率比较低，但同时他的数据在物理空间上连续存放也有了以下的问题

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

详细了解请移步：

3链表

链表是一块一块独立的空间，通过结构体指针来连接，删除/插入数据比较方便，空间使用malloc函数开辟，浪费的空间比较少，而且在物理上不是连续存放的，不会出现异地扩容之类的行为，对空间懂得利用较高，空间都是按需申请的

3.1链表实现

1.定义一个结构体

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

同时为了方便改变数据的类型，我们定义typedef int SLTDataType;结构体中的内容有存储的数据还有指向下一块内容的结构体指针 next

2.链表的遍历

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

 这其中有一句非常关键的代码：cur=cur->next;这个时候又得拿出这张图了：

385cc3a008a04895a3ed6817e0e61fb0.png

将头指针phead赋值给cur，让cur不断向后遍历，直到遇到NULL指针停下来

那么cur=cur->next;首先cur=phead，此时cur指向了第一个结构体，打印data

然后再将结构体中next指向的地址赋值给cur，此时cur就指向了下一个结构体，

如此遍历直到cur遇到了NULL；

3.创建新节点

定义一个结构体指针newnode用来创建新的节点，使用malloc手动开辟所需的空间，需要注意的是newnode是结构体指针，类型是SLTNode而不是SLTDataType，如果定义成了SLTDataType类型，后续的free操作就会报错

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

 4.尾插

引入了新的结构体指针tail，不断遍历链表，直到tail->next==NULL的时候说明已经找到了链表的尾部，此时再将创建好的newnode赋值给tail->next将新节点和链表链接起来实现了链表的尾插。  注意，while中tail->next==NULL，不能写成tail==NULL，tail=newnode。

因为phead newnode tail都是形参出了作用域后就会销毁，这样写不仅实现不了尾插，还会导致内存的泄露。

下面这个图就是错误原因

81dd5d1672074efc8e48ccdf4c0bdcbb.png

这一段尾插没有考虑链表为空的情况。

void SLTPushBack(SLTNode* phead, SLTDataType x) 
{
	SLTNode* newnode = BuySListNode(x);
	SLTNode* tail = phead;
	while (tail->next != NULL)
	{
		tail = tail->next;
	}
	tail->next = newnode;
}//尾插

 下面为正确的尾插，参数需要传二级指针

1.改变结构体需要用结构体指针（参数）

2.改变结构体指针需要用结构体指针的指针（tail->next = newnode）

void SLTPushBack(SLTNode** pphead, SLTDataType x) 
{
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

 5.头插

分为三种情况

1.空

2.一个节点

3.一个以上的节点（两种写法）

当找到尾部tail后不能直接将tail   free释放掉然后置空，因为上一个结构体还指向tail，然而tail又是局部变量，出了作用域就会被销毁，所以上一个结构体的next指向了野指针，所以我们就想到了使用tail的前一个 tailPrev，避免了野指针的出现；

链表的头插，，简单而且效率高

void SLTPopBack(SLTNode** pphead, SLTDataType x)
{
	//1.空
	assert(*pphead);
	//2.一个节点
	
	//3.一个以上节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		/*SLTNode* tailPrev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tailPrev = tail;
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;*/
		SLTNode* tail = *pphead;
		while(tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

 6.头删

同样考虑是否为空，较为简单，头删简单效率高。

void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead);//空
	//非空
	SLTNode* newhead = (*pphead)->next;
	free(*pphead);
	*pphead = newhead;
}

7.查

这里的查也同时可以起到修改的作用，查找到数据后，将其内容修改。

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data== x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//修改：
//SLTNode* pos = SLTFind(plist, 1);
	//if (pos)
	//{
	//	pos->data *= 10;
	//}

8.在pos位置前插入

（其实相当于在pos位置插入）在pos位置前插入，需要链表遍历到pos，但是此时不知道pos前一个位置的地址，无法做到在pos位置前插入，所以我们又引进了一个结构体指针prev，指向了pos的前一个位置.

单链表的前插还是具有一定的局限性，前插用双向链表来实现更为便捷。

void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x)
{
	assert(pos);
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}

}

 9.在pos位置后插入

注意

newnode->next = pos->next;
pos->next = newnode;

这两句代码的顺序不能改变，不然就会出现环链表，，从而导致死循环

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
		assert(pos);
		SLTNode* newnode = BuySListNode(x);
		newnode->next = pos->next;
		pos->next = newnode;
}

 10.删除pos位置

首先判断一下pos是不是头指针，如果是就复用之前写的头删，如果不是，就选择引入prev指针指向pos的前一个位置，方便与pos后面的指针链接

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

11.删除pos位置后一个

较为简单不再赘述

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* posNext = pos->next;
	pos->next = posNext->next;
	free(posNext);
	posNext = NULL;
}

 12.销毁

void SLTDestory(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

总结

以上便是不带哨兵 单链表的实现。

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

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

相关文章

消息触达平台 - 基础理论

消息触达平台 - 基础理论

目录 消息触达平台 背景 业务流程 触达配置 服务处理 表现展示 效果统计 触达信息结构 对象 内容 渠道 场景 机制 消息触达平台 背景 在产品生命周期的不同阶段&#xff0c;用户触达体系可以用来对不同用户群体进行定制化运营。结合咱们的日常场景&#xff0c;公司的运营同学或…
阅读更多...
【前端知识】React 基础巩固(四十一)——手动路由跳转、参数传递及路由配置

【前端知识】React 基础巩固(四十一)——手动路由跳转、参数传递及路由配置

React 基础巩固(四十一)——手动路由跳转、参数传递及路由配置 一、实现手动跳转路由 利用 useNavigate 封装一个 withRouter&#xff08;hoc/with_router.js&#xff09; import { useNavigate } from "react-router-dom"; // 封装一个高阶组件 function withRou…
阅读更多...
vue + element UI Table 表格 利用插槽是 最后一行 操作 的边框线 不显示

vue + element UI Table 表格 利用插槽是 最后一行 操作 的边框线 不显示

在屏幕比例100%时 el-table添加border属性 使用作用域插槽 会不显示某侧的边框线&#xff0c;屏幕比例缩小或放大都展示 // 修复列的 边框线消失的bug thead th:not(.is-hidden):last-child {right:-1px;// 或者//border-left: 1px solid #ebeef5; } .el-table__row{td:not(.i…
阅读更多...
常用的CSS渐变样式

常用的CSS渐变样式

边框渐变 方案1&#xff1a; 边框渐变( 支持圆角) width: 726px;height: 144px;border-radius: 24px;border: 5px solid transparent;background-clip: padding-box, border-box; background-origin: padding-box, border-box; background-image: linear-gradient(to right, #f…
阅读更多...
RabbitMQ 教程 | 第4章 RabbitMQ 进阶

RabbitMQ 教程 | 第4章 RabbitMQ 进阶

&#x1f468;&#x1f3fb;‍&#x1f4bb; 热爱摄影的程序员 &#x1f468;&#x1f3fb;‍&#x1f3a8; 喜欢编码的设计师 &#x1f9d5;&#x1f3fb; 擅长设计的剪辑师 &#x1f9d1;&#x1f3fb;‍&#x1f3eb; 一位高冷无情的编码爱好者 大家好&#xff0c;我是 DevO…
阅读更多...
基于多线程实现服务器并发

基于多线程实现服务器并发

看大丙老师的B站视频总结的笔记19-基于多线程实现服务器并发分析_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1F64y1U7A2/?p19&spm_id_frompageDriver&vd_sourcea934d7fc6f47698a29dac90a922ba5a3 思路&#xff1a;首先accept是有一个线程的&#xff0c;另外…
阅读更多...
【C++】 哈希

【C++】 哈希

一、哈希的概念及其性质 1.哈希概念 在顺序结构以及平衡树中&#xff0c;元素关键码与其存储位置之间没有对应的关系&#xff0c;因此在查找一个元素时&#xff0c;必须要经过关键码的多次比较。比如顺序表需要从第一个元素依次向后进行查找&#xff0c;顺序查找时间复杂度为…
阅读更多...
从零开始学Docker（二）：启动第一个Docker容器

从零开始学Docker（二）：启动第一个Docker容器

宿主机环境&#xff1a;RockyLinux 9 这个章节不小心搞成命令学习了&#xff0c;后面在整理成原理吧 Docker生命周期 拉取并启动Nginx容器 # 查找镜像 例如&#xff1a;nginx [root192 ~]# docker search nginx 我们可以看到&#xff0c;第一个时官方认证构建的nginx # 拉…
阅读更多...
Java源码规则引擎：jvs-rules决策流的自定义权限控制

Java源码规则引擎：jvs-rules决策流的自定义权限控制

规则引擎用于管理和执行业务规则。它提供了一个中央化的机制来定义、管理和执行业务规则&#xff0c;以便根据特定条件自动化决策和行为。规则引擎的核心概念是规则。规则由条件和动作组成。条件定义了规则适用的特定情况或规则触发的条件&#xff0c;而动作定义了规则满足时要…
阅读更多...
深度学习之用PyTorch实现线性回归

深度学习之用PyTorch实现线性回归

代码 # 调用库 import torch# 数据准备 x_data torch.Tensor([[1.0], [2.0], [3.0]]) # 训练集输入值 y_data torch.Tensor([[2.0], [4.0], [6.0]]) # 训练集输出值# 定义线性回归模型 class LinearModel(torch.nn.Module):def __init__(self):super(LinearModel, self)._…
阅读更多...
时间复杂度为O(nlogn)的两种排序算法

时间复杂度为O(nlogn)的两种排序算法

1.归并排序 归并排序的核心思想&#xff1a;如果要排序一个数组&#xff0c;我们先把数组从中间分成前后两部分&#xff0c;然后对前后两部分分别排序&#xff0c;再将排好序的两部分合并在一起&#xff0c;这样整个数组就都有序了。 归并排序使用的就是分治思想。分治&#x…
阅读更多...
用Delphi编写一个通用视频转换工具，让视频格式转换变得更简单

用Delphi编写一个通用视频转换工具，让视频格式转换变得更简单

用Delphi编写的简单视频格式转换程序&#xff0c;它使用TComboBox、TOpenDialog和TSaveDialog组件来选择转换格式、选择源视频文件和选择目标视频文件。程序还使用TEdit组件允许用户输入参数&#xff0c;然后将这些组件中的信息拼接成转换命令并在DOS窗口中运行它。 procedure…
阅读更多...
JavaEE——SpringMVC中的常用注解

JavaEE——SpringMVC中的常用注解

目录 1、RestController &#xff08;1&#xff09;、Controller &#xff08;2&#xff09;、ResponseBody 2、RequestMappping &#xff08;1&#xff09;、定义 &#xff08;2&#xff09;、使用 【1】、修饰方法 【2】、修饰类 【3】、指定方法类型 【4】、简化版…
阅读更多...
基于内核链表和JSON的MQTT的使用

基于内核链表和JSON的MQTT的使用

一、内核链表 1.回顾单链表的插入和遍历 假设学生结构体信息如下&#xff0c;封装一个单链表的插入接口和遍历输出的接口&#xff0c;在主函数中利用封装的接口生成一个学生链表&#xff0c;并遍历输出链表的学生信息。 #include <stdio.h> #include <string.h>…
阅读更多...
java设计模式-建造者（Builder）设计模式

java设计模式-建造者（Builder）设计模式

介绍 Java的建造者&#xff08;Builder&#xff09;设计模式可以将产品的内部表现和产品的构建过程分离开来&#xff0c;这样使用同一个构建过程来构建不同内部表现的产品。 建造者设计模式涉及如下角色&#xff1a; 产品&#xff08;Product&#xff09;角色&#xff1a;被…
阅读更多...
【论文精读】基于历史抽取信息的摘要抽取方法

【论文精读】基于历史抽取信息的摘要抽取方法

前言 论文分享 今天分享的是来自2018ACL的长文本抽取式摘要方法论文&#xff0c;作者来自哈尔滨工业大学和微软&#xff0c;引用数369 Neural Document Summarization by Jointly Learning to Score and Select Sentences 摘要抽取通常分为两个部分&#xff0c;句子打分和句子…
阅读更多...
交换机VLAN技术和实验（eNSP）

交换机VLAN技术和实验（eNSP）

目录 一&#xff0c;交换机的演变 1.1&#xff0c;最小网络单元 1.2&#xff0c;中继器&#xff08;物理层&#xff09; 1.3&#xff0c;集线器&#xff08;物理层&#xff09; 1.4&#xff0c;网桥&#xff08;数据链路层&#xff09; 二&#xff0c;交换机的工作行为 2.…
阅读更多...
使用 AntV X6 + vue 实现单线流程图

使用 AntV X6 + vue 实现单线流程图

使用 AntV X6 vue 实现单线流程图 X6 是 AntV 旗下的图编辑引擎&#xff0c;提供了一系列开箱即用的交互组件和简单易用的节点定制能力&#xff0c;方便我们快速搭建 DAG 图、ER 图、流程图等应用。 官方文档 安装 yarn add antv/x61.34.6Tips&#xff1a; 目前 X6 有 1.x…
阅读更多...
无涯教程-Lua - 环境安装

无涯教程-Lua - 环境安装

在Windows上安装 为Windows环境开发了一个单独的名为" SciTE"的IDE,可以从https://code.google.com/p/luaforwindows/下载部分。 运行下载的可执行文件以安装Lua IDE。 由于它是一个IDE&#xff0c;因此您可以使用它来创建和构建Lua代码。 如果您有兴趣在命令行模…
阅读更多...
flutter minio

flutter minio

背景 前端 经常需要上传文件 图片 视频等等 到后端服务器&#xff0c; 如果到自己服务器 一般会有安全隐患。也不方便管理这些文件。如果要想使用一些骚操作 比如 按照前端请求生成不同分辨率的图片&#xff0c;那就有点不太方便了。 这里介绍以下 minio&#xff0c;&#xff0…
阅读更多...
最新文章

Copyright @ 2022~2023