数据结构--单链表

前言

上一章，我们讲了数据结构--动态顺序表，我们会发现有以下问题：

1.当我们要头部或者插入或删除时，都需要进行位置挪动，腾出某一个位置，时间复杂度为0(N)；

2.增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3.增容会有一定的浪费空间；例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

下面我们来看看单链表这种线性结构；

链表

概念与结构

链表是一种常见的数据结构，用于存储和组织数据。它由一系列节点组成，每个节点包含两部分：数据和指向下一个节点的指针。

链表中的节点在内存中可以分布在任意位置，不像数组那样需要连续的存储空间。每个节点都包含了存储的数据以及指向下一个节点的指针。通过这种方式，链表可以灵活地分配和管理内存空间。就像一节节连动的火车车厢；

 在数据结构中，呈现：

 逻辑图中，呈现：

 在逻辑图中，链式结构是连续性的，但实际上不一样连续；从数据结构中看出，链表是通过地址来联系在一起的，不需要地址的连续性；在我们要解决链表相关问题时，只需要画出逻辑图即可；

 注意：

结点的空间在堆区中开辟；堆区中申请出的空间，会按照一定的策略进行分配，两次申请的空间可能连续，可能不连续；

链表的分类

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

1. 单向或者双向

2. 带头或者不带头
 

3. 循环或者非循环
 

可以通过一定的组合达成不同种类的链表；

这里我们比较常用的是有两种结构：

 

 在这里，我们将先实现无头单向非循环链表，这是链表中结构最为简单的；简称单链表。

单链表的接口实现

先写一下它的结构：

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

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

结构体中放入一个数据存储类型和一个结构体指针；结构体指针存放下一个结点的地址；

单链表打印

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

将链表从头到尾遍历一遍，用一个cur指针来进行移动，在while循环中不断遍历打印出结果；打印完就进入下一个结点；

增加链表结点

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

	return newnode;
}

用动态内存分配进行扩容，同时对data和next进行初始化；最后返回结点；

 

尾插

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

		tail->next = newnode;
	}
	
}

这里要注意，我们的形参用到了二级指针，因为当结构体指针为空时，我们就需要对结构体指针进行改变，用二级指针接收结构体指针的地址，能够有效的访问，否则将会报错；当结构体指针不为空时，就利用结构体指针通过循环访问到尾结点，然后在尾结点进行连接；

 

验证：

void Test3()
{
	SLTNode* plist = NULL;
	SLPushBack(&plist, 1);
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);
	SLTrint(plist);
	
}
int main()
{
	Test3();
	return 0;
}

 尾删

void SLPopBack(SLTNode** pphead)
{
	assert(pphead);
	//判空
	assert(*pphead);
	//一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//其他
	else
	{
		SLTNode* tailPrev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tailPrev = tail;
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;

	}
}

当删除的是第一个结点，将会改变结构体指针的地址，所以形参要引用二级指针；其他情况就先找到尾结点，然后进行删除；

 

验证：

void Test3()
{
	SLTNode* plist = NULL;
	SLPushBack(&plist, 1);
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);
	SLTrint(plist);
	SLPopBack(&plist);
	SLTrint(plist);
	
}
int main()
{
	Test3();
	return 0;
}

 头插头删

void SLPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySListNode(x);
	
	newnode->next = *pphead;
	*pphead = newnode;

}

void SLPopFront(SLTNode** pphead)
{	
	assert(pphead);
	//判空
	assert(*pphead);
	//其他
	SLTNode* newhead = (*pphead)->next;
	free(*pphead);
	*pphead = newhead;
}

头插相对尾插来说比较容易，因为有头指针，所以不用遍历循环来找到尾结点；并且无论头节点是否为空，操作程序都保持一致；

头删只要找到头结点的下一个结点，那么就可以删除了；

 

验证：

void Test2()
{
	SLTNode* plist = NULL;
	SLPushBack(&plist, 1);
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);
	SLPushBack(&plist, 5);
	SLTrint(plist);
	SLPushFront(&plist, 6);
	SLPushFront(&plist, 7);
	SLPushFront(&plist, 8);
	SLPushFront(&plist, 9);
	SLTrint(plist);
	SLPopFront(&plist);
	SLTrint(plist);

}


int main()
{
	Test2();
	return 0;
}

 查找与插入

SLTNode* SLFind(SLTNode* phead, SLTDataType x)
{
	//判空
	assert(phead);
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

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

查找：在循环里面通过结点的data与x进行匹配，找到就返回该结点，找不到返回空；如果有多个结点的data与x一致，返回链表最接近头指针的；

插入：是在pos后面进行插入，这样插入比较方便，不用考虑头指针是否为空的问题；

 

验证：

void Test3()
{
	SLTNode* plist = NULL;
	SLPushBack(&plist, 1);
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);
	SLTrint(plist);
	SLTNode* pos = SLFind(plist, 3);
	SLTInsertAfter(pos, 88);
	SLTrint(plist);

}
int main()
{
	Test3();
	return 0;
}

删除pos结点

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

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	//检查尾节点
	assert(pos->next);

	SLTNode* posNext = pos->next;

	pos->next = posNext->next;
	free(posNext);

}

第一种删除是删除pos结点，但需要判断该结点是否为首结点；而且需要遍历找到pos结点的前一个结点；比较麻烦；

第二种删除是删除pos结点后一个结点，只需要通过pos结点连接到下下一个结点即可，最后free掉pos的下一个结点；

验证：

void Test3()
{
	SLTNode* plist = NULL;
	SLPushBack(&plist, 1);
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);
	SLTrint(plist);
	SLTNode* pos = SLFind(plist, 3);
	SLTInsertAfter(pos, 88);
	SLTrint(plist);
	SLTErase(&plist, pos);
	SLTrint(plist);
	
}
int main()
{
	Test3();
	return 0;
}

 

void Test3()
{
	SLTNode* plist = NULL;
	SLPushBack(&plist, 1);
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);
	SLTrint(plist);
	SLTNode* pos = SLFind(plist, 3);
	SLTInsertAfter(pos, 88);
	SLTrint(plist);
	SLTEraseAfter(pos);
	SLTrint(plist);
	
}
int main()
{
	Test3();
	return 0;
}

 摧毁

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

通过记住头结点的下一个结点，free掉头节点，然后头节点的下一个结点成为新的头节点；

验证：

void Test3()
{
	SLTNode* plist = NULL;
	SLPushBack(&plist, 1);
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);
	SLTrint(plist);
	SLTNode* pos = SLFind(plist, 3);
	SLTInsertAfter(pos, 88);
	SLTrint(plist);
	SLTDestroy(&plist);
	SLTrint(plist);
}
int main()
{
	Test3();
	return 0;
}

 完整代码

slist.h

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

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


void SLTrint(SLTNode* phead);
SLTNode* BuySListNode(SLTDataType x);
void SLPushBack(SLTNode** pphead, SLTDataType x);
void SLPushFront(SLTNode** pphead, SLTDataType x);
void SLPopBack(SLTNode** pphead);
void SLPopFront(SLTNode** pphead);
SLTNode* SLFind(SLTNode* phead, SLTDataType x);
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTEraseAfter(SLTNode* pos);
void SLTDestroy(SLTNode** phead);

slist.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Slist.h"

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

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

	return newnode;
}


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

		tail->next = newnode;
	}
	
}

void SLPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySListNode(x);
	
	newnode->next = *pphead;
	*pphead = newnode;

}

void SLPopBack(SLTNode** pphead)
{
	assert(pphead);
	//判空
	assert(*pphead);
	//一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//其他
	else
	{
		SLTNode* tailPrev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tailPrev = tail;
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;

	}
}
void SLPopFront(SLTNode** pphead)
{	
	assert(pphead);
	//判空
	assert(*pphead);
	//其他
	SLTNode* newhead = (*pphead)->next;
	free(*pphead);
	*pphead = newhead;
}

SLTNode* SLFind(SLTNode* phead, SLTDataType x)
{
	//判空
	assert(phead);
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

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(pos);
	if (pos == *pphead)
	{
		SLPopFront(pphead);
	}
	else
	{
		SLTNode* perv = *pphead;
		while (perv->next != pos)
		{
			perv = perv->next;
		}
		perv->next = pos->next;
		free(pos);
	}
}

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	//检查尾节点
	assert(pos->next);

	SLTNode* posNext = pos->next;

	pos->next = posNext->next;
	free(posNext);

}

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

test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Slist.h"

void Test1()
{
	int n;
	SLTNode* plist = NULL;
	printf("请输入链表长度");
	scanf("%d", &n);
	printf("请输入值");
	for (int i = 0; i < n; i++)
	{
		int val;
		scanf("%d", &val);
		SLTNode* newnode = BuySListNode(val);

		newnode->next = plist;
		plist = newnode;
	}
	SLTrint(plist);
}

void Test2()
{
	SLTNode* plist = NULL;
	SLPushBack(&plist, 1);
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);
	SLPushBack(&plist, 5);
	SLTrint(plist);
	SLPushFront(&plist, 6);
	SLPushFront(&plist, 7);
	SLPushFront(&plist, 8);
	SLPushFront(&plist, 9);
	SLTrint(plist);
	SLPopFront(&plist);
	SLTrint(plist);

}

void Test3()
{
	SLTNode* plist = NULL;
	SLPushBack(&plist, 1);
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);
	SLTrint(plist);
	SLTNode* pos = SLFind(plist, 3);
	SLTInsertAfter(pos, 88);
	SLTrint(plist);
	SLTDestroy(&plist);
	SLTrint(plist);
}
int main()
{
	Test3();
	return 0;
}

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

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

相关文章

个人可搭建在线商城系统，支持docker一键部署

个人可搭建在线商城系统，支持docker一键部署

Hmart 给大家推荐一个简约自适应电子商城系统&#xff0c;针对虚拟商品在线发货&#xff0c;支持企业微信通知&#xff0c;支持docker一键部署&#xff0c;个人资质也可搭建。 前端 后端 H2 console 运行命令 docker run -d --name mall --restartalways -p 8080:8080 -e co…
阅读更多...
全志F1C200S嵌入式驱动开发（从DDR中截取内存）

全志F1C200S嵌入式驱动开发（从DDR中截取内存）

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】 linux内核起来的时候，不一定所有的内存都是分配给linux使用的。有的时候，我们是希望能够截留一部分内存的。为什么保留这部分内存呢？这里面可以有很多的用途。比如说，第一，如果…
阅读更多...
Spring MVC应用的开发步骤

Spring MVC应用的开发步骤

Spring MVC应用的开发步骤 Spring MVC应用的开发步骤如果以异步方式提交请求利用XML配置文件配置控制器类 Spring MVC应用的开发步骤 下面简单介绍Spring MVC应用的开发步骤。 ① 在web.xml文件中配置核心控制器DispatcherServlet处理所有的HTTP请求。 由于Web应用是基于请求/…
阅读更多...
3个命令定位CPU飙高

3个命令定位CPU飙高

top 指令找出消耗CPU最厉害的那个进程的pid top -H -p 进程pid 找出耗用CPU资源最多的线程pid printf ‘0x%x\n’ 线程pid 将线程pid转换为16进制 结合jstack 找出哪个代码有问题 jstack 进程pid | grep 16进制的线程pid -A 多少行日志 jstack 进程pid | grep 16进制的线程…
阅读更多...
第一章-JavaScript基础进阶part2：事件

第一章-JavaScript基础进阶part2：事件

文章目录 概念一、注册事件&#xff08;绑定事件&#xff09;1.1 addEventListener事件监听 二、删除事件&#xff08;解绑&#xff09;三、DOM事件流四、事件对象event4.1 e.target与this与e.currentTarget的区别4.2 事件对象的常见属性 五、阻止事件默认行为及冒泡六、事件委…
阅读更多...
Apache Kafka Learning

Apache Kafka Learning

目录 一、Kafka 1、Message Queue是什么&#xff1f; 2、Kafka 基础架构 3、Kafka安装 4、Offset自动控制 5、Acks & Retries 6、幂等性 7、事务控制 8、数据同步机制 9、Kafka-Eagle 二、Maven项目测试 1、Topic API 2、生产者&消费者 一、Kafka Kafka是…
阅读更多...
express学习笔记5 - 自定义路由异常处理中间件

express学习笔记5 - 自定义路由异常处理中间件

修改router/index.js&#xff0c;添加异常处理中间件 *** 自定义路由异常处理中间件* 注意两点&#xff1a;* 第一&#xff0c;方法的参数不能减少* 第二&#xff0c;方法的必须放在路由最后*/ router.use((err, req, res, next) > {console.log(err);const msg (err &…
阅读更多...
GD32F103VE睡眠与唤醒

GD32F103VE睡眠与唤醒

GD32F103VE睡眠与唤醒&#xff0c;兆易官网给的程序没有测试。等测试后&#xff0c;才发现有问题。 现修改&#xff0c;测试如下&#xff1a; #include "SleepMode.h" #include "delay.h"u8 WFE_CMD_EnterSleepModeFlag;void Enter_DeepSleepMode(void);…
阅读更多...
vue2-diff算法

vue2-diff算法

1、diff算法是什么&#xff1f; diff算法是一种通过同层的树节点进行比较的高效算法。 其有两个特点&#xff1a; 比较只会在同层级进行&#xff0c;不会跨层级进行。 在diff比较的过程中&#xff0c;循环从两边向中间比较。 diff算法在很多场景中都有应用&#xff0c;在vue中&…
阅读更多...
telnet检验网络能不能通

telnet检验网络能不能通

telnet检测网络能不能通&#xff08;ip地址端口号&#xff09;
阅读更多...
牵着她——表白不成功算我输（Python实现）

牵着她——表白不成功算我输（Python实现）

目录 1 牵着她的手一直走下去 2 一首小情诗送给甜甜的她 3 历史总结的哲学想法 4 表白不成功算我输&#xff08;Python代码&#xff09; 1 牵着她的手一直走下去 今天牵着她的手&#xff0c;她很贴心。一起并肩赏樱花&#x1f338;。骑着快车&#xff0c;清风抚摸着我俩的…
阅读更多...
【Spring】bean的生命周期

【Spring】bean的生命周期

1.具体的生命周期过程 bean对象创建&#xff08;调用无参构造器&#xff09; 给bean对象设置属性 bean对象初始化之前操作&#xff08;由bean的后置处理器负责&#xff09; bean对象初始化&#xff08;需在配置bean时指定初始化方法&#xff09; bean对象初始化之后操作&am…
阅读更多...
STM32F103——基础篇

STM32F103——基础篇

目录 1、寄存器基础知识 2、STM32F103系统架构 2.1 Cortex M3 内核&芯片 2.2 STM32F103系统架构 3、存储器映射 4、寄存器映射 4.1 寄存器描述解读 4.2 寄存器映射举例 4.3 寄存器地址计算 4.4 stm32f103xe.h 寄存器映射 1、寄存器基础知识 概念&#xff1a;寄存…
阅读更多...
pandas read excel 更改string列为时间类型

pandas read excel 更改string列为时间类型

设想我们有如下一个excel文件 我们都知道上面那个时间列其实是string类型&#xff0c;因此在用pandas做时间校验的时候会不通过&#xff0c;我们可以在read_excel的时候&#xff0c;指定这一列做转换 import pandas as pd from datetime import datetime, timedelta import n…
阅读更多...
MySQL — 存储引擎

MySQL — 存储引擎

文章目录 存储引擎存储引擎类型InnoDBMyISAMMEMORY 存储引擎是数据库的核心&#xff0c;对于mysql来说&#xff0c;存储引擎是以插件的形式运行的。虽然mysql支持种类繁多的存储引擎&#xff0c;但是常用的就那么几种。这篇文章主要是对其进行简单的介绍。 存储引擎 MySQL可插…
阅读更多...
项目实战 — 消息队列（3）{数据库操作}

项目实战 — 消息队列（3）{数据库操作}

目录 一、SQLite &#x1f345; 1、添加依赖 &#x1f345; 2、修改配置文件后缀&#xff08;properties -> yaml&#xff09; &#x1f345; 3、编写配置文件 二、建立数据表 三、添加插入和删除方法 四、整合数据库操作&#xff08;DataBaseManger类&#xff09; &a…
阅读更多...
go Channel

go Channel

channel 单纯地将函数并发执行是没有意义的。函数与函数之间需要交换数据才能体现出并发执行函数的意义。 虽然可以使用共享内存进行数据交换&#xff0c;但是共享内存在不同的goroutine中很容易发生竞态问题。为了保证数据交换的准确性&#xff0c;必须使用互斥量对内存进行…
阅读更多...
STM32基础入门学习笔记：开发板 电路原理与驱动编程

STM32基础入门学习笔记：开发板 电路原理与驱动编程

文章目录&#xff1a; 一&#xff1a;触摸按键 1.触摸按键驱动程序&#xff08;点击&#xff09; touch_key.h touch_key.c main.c 2.按键双击和长按程序 touch_key.h touch_key.c main.c 3.触摸按键滑动程序 main.c 二&#xff1a;数码管显示 1.数码管RTC时钟LE…
阅读更多...
MCUXpresso for VS Code -- 基于VSCode开发RT1176

MCUXpresso for VS Code -- 基于VSCode开发RT1176

MCUXpresso for VS Code 是nxp推出插件&#xff0c;旗下MCX LPC, Kinetis和i.MX rt等MCU&#xff0c;都能在VS Code平台进行嵌入式开发。功能框图如下&#xff1a; 前期准备&#xff1a; 软件环境: windows(实际可以跨系统&#xff0c;linux和mac没有测试) VS Code ninja CMa…
阅读更多...
git之reflog分析

git之reflog分析

写在前面 本文一起看下reflog命令。 1&#xff1a;场景描述 在开发的过程中&#xff0c;因为修改错误&#xff0c;想要通过git reset命令恢复到之前的某个版本&#xff0c;但是选择提交ID错误&#xff0c;导致多恢复了一个版本&#xff0c;假定&#xff0c;该版本对应的内容…
阅读更多...
最新文章

Copyright @ 2022~2023