暴力数据结构之单链表专题

1. 单链表的初始化

首先定义节点的结构，然后动态内存申请一部分空间，每一个节点都有一个值以及指向下一个节点的指针，称作值域和指针域。 

//定义节点的结构
//数据 + 指向下一个节点的指针

typedef int SLTDataType;

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

初始化需要为链表节点动态申请一块空间，然后对值域和指针域初始化。

//初始化函数
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;
}

2. 单链表的相关函数

2.1 头插和头删

首先断言头结点不能为空，然后直接从表头插入节点。

//头插函数
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//newnode *pphead
	//将链表依次后移,从头插入
	newnode->next = *pphead;
	*pphead = newnode;
}

断言判断头结点及其地址都不为空，然后将原头结点的下一个节点保存起来，释放原来的头结点，则原头结点的下一个节点成为新的头结点。

//头删函数
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
2.2 尾插和尾删

断言头结点不能为空，同样插入，但是要判断原链表是否为空链表，是空链表则直接插入，反之遍历链表找到尾节点再插入。

//尾插函数
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//*pphead 就是指向第一个节点的指针
	//空链表和非空链表
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		//ptail指向的是尾节点
		ptail->next = newnode;
	}
}

断言判断头结点及其地址均不为空，同样的原链表如果只有一个节点则直接释放，反之找到尾节点后释放尾节点。

//尾删函数
void SLTPopBack(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;
	}
}
2.3 在指定位置的前后插入数据

断言待插入节点位置、头结点及其地址均不为空，如果pos为头结点就直接头插，反之遍历链表找到pos的上一个节点，然后在二者中间插入。

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	assert(pphead && *pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//判断是否为头节点
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}

断言待插入节点位置、头结点及其地址均不为空，找到pos的上一个节点，然后在二者中间插入。 

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
2.4 删除当前节点或后面节点

 断言待插入节点位置、头结点及其地址均不为空，如果pos为头结点直接头删，反之遍历链表找     到pos节点后保存相邻节点，释放pos节点，将相邻节点连接起来形成新链表。

//删除pos当前指向的节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	//pos是头结点/不是头结点
	if (pos == *pphead)
	{
		//头删
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

断言待插入节点位置及其下一个节点均不为空，保存pos下一个节点即待删除节点，释放pos节点，将相邻节点连接起来形成新链表。

//删除pos之后的节点
void SLTErase(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos = del->next;
	free(del);
	del = NULL;
}
2.5 销毁和查找 

遍历链表找符合的节点，然后直接返回该节点。

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur != NULL)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//pcur == NULL;
	return NULL;
}

由于前面有动态内存申请，所以要进行释放free掉，就有了销毁函数。 

//销毁链表
void SLTDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

3. 代码展示（可自行复制调试）

3.1 test.c
#include"SList.h"

void SListTest01()
{
	//链表是由一个一个的节点组成
	//创建几个节点
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;

	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;

	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;

	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;

	//将四个节点连接起来
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;

	//调用链表的打印
	SLTNode* plist = node1;
	SLTPrint(plist);
}

void SListTest02()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	//SLTPushBack(NULL, 5);
	//
	//测试头插
	//SLTPushFront(&plist, 6);
	//SLTPrint(plist);
	//SLTPushFront(&plist, 7);
	//SLTPrint(plist);
	//SLTPushFront(&plist, 8);
	//SLTPrint(plist);

	//测试尾删
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);

}

int main()
{
	//SListTest01();
	SListTest02();
	return 0;
}
3.2 SList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>


//定义节点的结构
//数据 + 指向下一个节点的指针

typedef int SLTDataType;

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

//打印函数
void SLTPrint(SLTNode* phead);

//初始化函数
SLTNode* SLTBuyNode(SLTDataType x);

//头插函数
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//尾插函数
void SLTPushBack(SLTNode** pphead, SLTDataType x);

//头删函数
void SLTPopFront(SLTNode** pphead);

//尾删函数
void SLTPopBack(SLTNode** pphead);


//删除pos之后的节点
void SLTErase(SLTNode* pos);


//销毁链表
void SLTDesTroy(SLTNode** pphead);
3.3 SList.c 
#include"SList.h"


//打印函数
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("->%d", pcur->data);
		pcur = pcur->next;
	}
	printf("->NULL\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 SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//newnode *pphead
	//将链表依次后移,从头插入
	newnode->next = *pphead;
	*pphead = newnode;
}


//尾插函数
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//*pphead 就是指向第一个节点的指针
	//空链表和非空链表
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		//ptail指向的是尾节点
		ptail->next = newnode;
	}
}



//尾删函数
void SLTPopBack(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 SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}



//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur != NULL)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//pcur == NULL;
	return NULL;
}

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	assert(pphead && *pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//判断是否为头节点
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}



//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}


//删除pos当前指向的节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	//pos是头结点/不是头结点
	if (pos == *pphead)
	{
		//头删
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}


//删除pos之后的节点
void SLTErase(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos = del->next;
	free(del);
	del = NULL;
}

//销毁链表
void SLTDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

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

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

相关文章

微博评论爬取

微博评论爬取

import requests import csv# 打开CSV文件以写入数据 f open(data.csv, modea, encodingutf-8-sig, newline) csv_writer csv.DictWriter(f, fieldnames[昵称, 性别, 归属地, 内容]) csv_writer.writeheader()# 定义一个函数用于获取评论内容 def GetContent(max_id):# 设置请…
阅读更多...
SRS服务接入华为云CDN

SRS服务接入华为云CDN

CDN简介: CDN的全称是Content Delivery Network&#xff0c;即内容分发网络。其基本思路是尽可能避开互联网上有可能影响数据传输速度和稳定性的瓶颈和环节&#xff0c;使内容传输得更快、更稳定。通过在网络各处放置节点服务器所构成的在现有的互联网基础之上的一层智能虚拟网…
阅读更多...
为何3C电子精密件测量首选闪测仪？

为何3C电子精密件测量首选闪测仪？

在工业生产中&#xff0c;精密件的测量是至关重要的环节&#xff0c;它直接关系到产品的质量和性能。大部分3c电子工厂以及精密五金加工厂中&#xff0c;产品质检环节中大部分测量仪器都采用闪测仪。为什么呢&#xff1f; 测量精度与稳定性 闪测仪能够提供更高的测量精度和稳定…
阅读更多...
window11上修改字符编码方式

window11上修改字符编码方式

windos11字符编码方式为gbk。我们有时候要用cmd命令行检测中文的代码里面含有中文的时候就会出现乱码&#xff0c;将gbk更改为utf-8后便可以解决这一情况。 步骤&#xff1a; 1、windows上【设置】-【时间和语言】【语言与区域】-【管理语言设置】 打开区域界面&#xff0c;点…
阅读更多...
Linux 终端中的目录切换

Linux 终端中的目录切换

目录 ⛳️推荐 前言 理解 Linux 中的路径 利用 cd 命令变更目录 故障解决 文件或目录不存在 非目录错误 特殊目录符号 测试你的知识 ⛳️推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击…
阅读更多...
PCB走线宽度、PCB走线宽度计算、PCB走线宽度和电流

PCB走线宽度、PCB走线宽度计算、PCB走线宽度和电流

目录 一、什么是PCB走线宽度&#xff1f; 二、什么是走线&#xff1f; 三、哪些因素对走线宽度至关重要&#xff1f; 1、信号走线 2、电源走线 3、直线宽度和信号反射 四、怎么计算PCB走线宽度&#xff1f; 1、使用PCB走线宽度计算器 2、使用方程式 五、怎么计算PCB 走…
阅读更多...
Java 【数据结构】 二叉树（Binary_Tree）【神装】

Java 【数据结构】 二叉树（Binary_Tree）【神装】

登神长阶 第五神装 二叉树 Binary-Tree 目录 &#x1f3b7;一.树形结构 &#x1fa97;1.概念 &#x1f3b8;2.具体应用 &#x1f3b9; 二.二叉树&#xff08;Binary Tree&#xff09; &#x1f3ba;1.概念 &#x1f3bb;2.表现形式 &#x1fa95;3.特殊类型 &#x1f941…
阅读更多...
【C语言__基础概念__复习篇8】

【C语言__基础概念__复习篇8】

目录 前言 一、C语言是什么 二、C语言的发展历史 三、编译器的选择 3.1 编译和链接 3.2 编译器的对比 3.3 VS如何使用 四、main函数 五、关键字 六、字符和ASCII编码 七、字符串和\0 八、转义字符 九、注释 十、数据类型 10.1 数据类型的介绍 10.2 数据类型大小的计…
阅读更多...
互联网大佬座位排排坐：马化腾第一，雷军第二

互联网大佬座位排排坐：马化腾第一，雷军第二

关注卢松松&#xff0c;会经常给你分享一些我的经验和观点。 这是马化腾、雷军、张朝阳、周鸿祎的座位&#xff0c;我觉得是按照互联网地位排序的。 马化腾坐头把交椅&#xff0c;这个没毛病&#xff0c;有他在的地方&#xff0c;其他几位都得喊声“大哥”。雷军坐第二把交椅…
阅读更多...
Linux进程详解二：创建、状态、进程排队

Linux进程详解二：创建、状态、进程排队

文章目录 进程创建进程状态进程排队 进程创建 pid_t fork(void) 创建一个子进程成功将子进程的pid返回给父进程&#xff0c;0返回给新创建的子进程 fork之后有两个执行分支&#xff08;父和子&#xff09;&#xff0c;fork之后代码共享 bash -> 父 -> 子 创建一个进…
阅读更多...
上汽大通：依托电子签网络，升级产业供应链协同

上汽大通：依托电子签网络，升级产业供应链协同

2023年12月&#xff0c;法大大发布了中国首部《汽车行业合同数智化白皮书》&#xff08;点击阅读及下载&#xff1a;中国首部&#xff01;《汽车行业合同数智化白皮书》重磅发布 | 附下载&#xff09;。该白皮书中基于法大大自身参与汽车行业合同数智化建设的实践和思考&#x…
阅读更多...
一次Ambari安装记录

一次Ambari安装记录

引言 Ambari是一个开源的Apache项目，它提供了一个直观易用的Web界面，用于管理、监控和配置Apache Hadoop集群。它是一个集群管理工具，可以帮助管理员轻松地部署、管理和监控Hadoop集群的各种组件，如HDFS、YARN、MapReduce、Hive、HBase等。通过Ambari，用户可以在集群中添…
阅读更多...
使用R语言生成频数分布表

使用R语言生成频数分布表

概要 使用R语言生成频数分布表 在R语言中&#xff0c;可以使用freq()函数来生成频数分布表。首先&#xff0c;将需要分组的数据存储在一个向量中。然后&#xff0c;使用freq()函数将这个向量作为参数输入&#xff0c;即可生成频数分布表。以下是一个示例&#xff1a; 示例 …
阅读更多...
力扣-2259移除指定数字得到的最大结果

力扣-2259移除指定数字得到的最大结果

思路&#xff1a; 1. def removeDigit(self, number: str, digit: str) -> str:&#xff1a;这是一个类方法&#xff0c;接受两个参数 number 和 digit&#xff0c;分别表示输入的数字字符串和要移除的数字字符&#xff0c;返回一个字符串。 2. n len(number)&#xff1a…
阅读更多...
【linux】chmod权限开放（整个文件夹）

【linux】chmod权限开放（整个文件夹）

文章目录 起因权限查看权限修改 失败权限修改成功 起因 想要共享conda环境给同事&#xff0c;发现同事没权限。 权限查看 ls #查看当前目录 ls -l # 查看当前目录的东西和权限正常情况下是显示 三个rwx分别属于user&#xff0c;group&#xff0c;others 前面第一个rwx 是针…
阅读更多...
抖店2024现状，嘴上抱怨内卷不好做，做起来就一做一个不吱声

抖店2024现状，嘴上抱怨内卷不好做，做起来就一做一个不吱声

我是王路飞。 身边有朋友在做抖店的&#xff0c;你要是问他现在抖店做着怎么样&#xff1f; 他绝对会说现在的抖店非常内卷&#xff0c;流量不好搞&#xff0c;达人不好对接&#xff0c;很难做...... 但是私底下做起来&#xff0c;一做一个不吱声~ 这也是现在抖店的一个真实…
阅读更多...
【MATLAB源码-第196期】基于matlab的A*融合DWA算法栅格路径规划仿真，画出路径图、姿态角度以及线角速度。

【MATLAB源码-第196期】基于matlab的A*融合DWA算法栅格路径规划仿真，画出路径图、姿态角度以及线角速度。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 A算法与DWA算法的融合是一个高效的路径规划策略&#xff0c;这种策略将A算法的全局路径规划能力与DWA算法的局部避障能力结合起来&#xff0c;以期达到更快、更安全的导航效果。以下是对这种融合策略的详细描述。 一、基本概…
阅读更多...
RISC-V CVA6 在 Linux 下相关环境下载与安装

RISC-V CVA6 在 Linux 下相关环境下载与安装

RISC-V CVA6 在 Linux 下相关环境下载与安装 所需环境与源码下载 CVA6 源码下载 首先&#xff0c;我们可以直接从 GitHub 一次性拉取所有源码&#xff1a; git clone --recursive https://github.com/openhwgroup/cva6.git如果这里遇到网络问题&#xff0c;拉取失败&#x…
阅读更多...
Vue--》深入了解 VueUse 功能性工具集

Vue--》深入了解 VueUse 功能性工具集

今天博主为大家介绍一款实用性的插件名字叫做 VueUse &#xff0c;它是专门为 Vue.js 生态系统设计的功能性工具集合。其提供了许多可重用的功能函数&#xff0c;可以帮助开发者更轻松地构建 Vue.js 应用程序。其提供了大量的功能&#xff0c;包括状态管理、副作用管理、组合式…
阅读更多...
力扣HOT100 - 2. 两数相加

力扣HOT100 - 2. 两数相加

解题思路&#xff1a; 缺位的节点进行补零处理&#xff0c;如97323补充为973023 注意相加的进位问题 class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head null, tail null;int carry 0;while (l1 ! null || l2 ! null) {int n1 l…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站