手撕单链表

2023-09-16 16:02:19

> 作者简介:დ旧言~,目前大一,现在学习Java,c,c++,Python等
> 座右铭:松树千年终是朽,槿花一日自为荣。
> 望小伙伴们点赞👍收藏✨加关注哟💕💕 

4909e8cfd8b84e8b92df3a0e69dfff61.jpeg

 🌟前言       

        前面我们已经学习了顺序表,顺序表可以存储动态的数据,但是一旦元素过少,而又要开辟空间,这样就造成空间的浪费,为了解决这类问题,人们发现了单链表,把一个一个元素以链子的形式存储,那单链表如何实现呢,今天咱们就实现一下--《单链表》。

🌙主体

咱们从三个方面实现单链表,动态管理,头插头删尾插尾删,增删查改。

在程序中为了实现顺序表,需要创建头文件Slist.h ,创建源文件Test.c,Slist.c。

 🌠动态管理

💤初始化动态单链表

既然实现单链表,初始化动态的单链表必不可少,从两个方面实现初始化动态的单链表。

1.首先我们在Slist.h定义动态的单链表,省得我们再定义节点(单链表)。

//重匿名方法来定义数据类型
typedef int SLTDataType;

//定义动态的单链表
typedef struct SListNode
{
	//定义数据类型
	SLTDataType data;
	//指向下一个元素
	struct SListNode* next;
}SLTNode;

2.对单链表进行初始化。(这里和顺序表相似)

💦这里采用malloc开辟空间

💦采用预指令判断空间是否开辟完成(没有开辟空间返回-1)

💦之后就是简单的初始数据

💦记得返回值

//初始化
SLTNode* BuySListNode(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 SLTDestory(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	//比cur->next!=NULL更好一些
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

🌠头插头删尾插尾删

💤打印元素

打印元素就太简单了,直接上代码

//打印数据
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		//找到下一个地址
		cur = cur->next;
	}
	printf("NULL\n");
}

 💤头插

💦1.因为需要改变结构体的指针,因此需要二级指针来接收

💦2.因为头插是一个元素,因此需要初始化

💦3.指向开始

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	//初始化
	SLTNode* newnode = BuySListNode(x);
	//改变地址指向
	newnode->next = *pphead;
	//指向开始
	*pphead = newnode;
}

💤尾插(重点)

💦1.因为需要改变结构体的指针,因此需要二级指针来接收

💦2.因为尾插是一个元素,因此需要初始化

💦3.如果单链表没有元素,直接把头赋值给pphead

💦4.如果单链表有元素,就需要找到尾,再把开辟好的newnode赋值给tail->next

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	//初始化
	SLTNode* newnode = BuySListNode(x);
	//判断pphead == NULL
	if (*pphead == NULL)
	{
		//改变的结构体的指针,所以要用二级指针
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			//找到尾
			tail = tail->next;
		}

		//改变的结构体,用结构体的指针即可(指向空指针)
		tail->next = newnode;
	}
}

💤头删(重点)

头删还是比较简单的,这里就需要注意一点(单链表为空时,不为空时)

//头删
void SLTPopFront(SLTNode** pphead)
{
	//空时
	assert(*pphead);
	//非空时 指向下一个
	SLTNode* newhead = (*pphead)->next;
	//释放内存
    free(*pphead);
	*pphead = newhead;
}

💤尾删(重点)

💦1.一个节点(一个元素)直接把头指向空(NULL)

💦2.一个节点以上(一个元素以上),先找到尾,再释放内存,最后尾指向空(NULL)

//尾删
void SLTPopBack(SLTNode** pphead)
{
	//不能为空
	assert(*pphead);

	// 1、一个节点
	if ((*pphead)->next == NULL)
	{
		//释放空间
		free(*pphead);
		//指向空
		*pphead = NULL;
	}
	// 2、一个以上节点
	else
	{
		//找到尾
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}

		//释放空间
		free(tail->next);
		//指向空
		tail->next = NULL;
	}
}

  🌠增删查改

💤查找下标

这个函数是为了增删查改服务的函数,这个函数还是比较好实现的。

//查找下标 需要给尾phead参数
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}
	return NULL;
}

💤在pos之前插入x

💦1.因为需要改变结构体的指针,因此需要二级指针来接收

💦2.先断言(pphead和pos)

💦3.如果只有一个元就头插

💦4.再找到pos之前的地址

💦5.初始化插入的元素

💦6.改变元素的地址

//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	//断言
	assert(pphead);
	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;
	}
}

💤在pos之后插入x

这里和上面的代码相似,这里主函数(Test.c)就会调用查找元素的函数,这里就简单点

//在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	//断言
	assert(pos);
	
	//初始化

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

💤删除pos位置

💦1.因为需要改变结构体的指针,因此需要二级指针来接收

💦2.先断言(pphead和pos)

💦3.如果只有一个元就头删

💦4.再找到pos的地址

💦5.修改pos的地址

💦6.释放内存

//删除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);
	}
}

💤删除pos的后一个位置

 这里和上面的代码相似,这里主函数(Test.c)就会调用查找元素的函数,这里就简单点

//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
	//断言
	assert(pos);
	//检查pos是否是尾节点
	assert(pos->next);
	//改变地址
    SLTNode* posNext = pos->next;
	pos->next = posNext->next;
	//释放内存
    free(posNext);
	posNext = NULL;
}

💤单链表结点修改

       其实这个函数也没啥技术含量, 这里和上面的代码相似,这里主函数(Test.c)就会调用查找元素的函数,这里就简单点

// 单链表结点修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur != pos)
	{
		cur = cur->next;
		assert(cur);
	}
	pos->data = x;
}

🌙代码总结

🌠主函数

//包含头文件
#include"Slist.h"

void TestSList1()
{
	int n;
	printf("请输入链表的长度:");
	scanf("%d", &n);
	printf("\n请依次输入每个节点的值:");
	SLTNode* plist = NULL;

	for (size_t i = 0; i < n; i++)
	{
		int val;
		scanf("%d", &val);
		SLTNode* newnode = BuySListNode(val);

		//头插
		newnode->next = plist;
		//指向头 
		plist = newnode;
	}
	
	//打印数据
	SLTPrint(plist);

	//这里头插本质相似
	//SLTPushBack(&plist, 10000);
	
	//打印数据
	SLTPrint(plist);
}

void TestSList2()
{
	//初始化
	SLTNode* plist = NULL;
	
	//头插
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	
	//打印数据
	SLTPrint(plist);

	SLTPushFront(&plist, 10);
	SLTPushFront(&plist, 20);
	SLTPushFront(&plist, 30);
	SLTPushFront(&plist, 40);
	
	//打印数据
	SLTPrint(plist);
}

void TestSList3()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);


	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);

	//SLTPopBack(&plist);
	//SLTPrint(plist);
}

void TestSList4()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	//SLTPopFront(&plist);
	SLTPrint(plist);
}

void TestSList5()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 40);
	if (pos)
	{
		pos->data *= 10;
	}
	SLTPrint(plist);

	int x;
	scanf("%d", &x);
	pos = SLTFind(plist, x);
	if (pos)
	{
		SLTInsert(&plist, pos, x * 10);
	}
	SLTPrint(plist);
}

void TestSList6()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);

	int x;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	if (pos)
	{
		//SLTInsertAfter(pos, x * 10);
	}
	SLTPrint(plist);
}

void TestSList7()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);

	int x;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	if (pos)
	{
		//SLTErase(&plist, pos);
		//SLTEraseAfter(pos);
		pos = NULL;
	}
	SLTPrint(plist);

	//SLTPopFront(&plist);
	//SLTPrint(plist);

	//SLTPopFront(&plist);
	//SLTPrint(plist);

	//SLTPopFront(&plist);
	//SLTPrint(plist);

	//SLTPopFront(&plist);
	//SLTPrint(plist);

}

int main()
{
	TestSList7();

	return 0;
}

🌠SqList.h头文件

//使用一些头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//重匿名方法来定义数据类型
typedef int SLTDataType;

//定义动态的单链表
typedef struct SListNode
{
	//定义数据类型
	SLTDataType data;
	//指向下一个元素
	struct SListNode* next;
}SLTNode;

//初始化
SLTNode* BuySListNode(SLTDataType x);
//打印数据
void SLTPrint(SLTNode* phead);

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);

//查找下标
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos的后一个位置
void SLTInsertAfter(SLTNode* pos);

//销毁链表
void SLTDestory(SLTNode** pphead);

// 单链表结点修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x);

🌠SqList.c源文件

#define _CRT_SECURE_NO_WARNINGS 1

//包含头文件
#include"Slist.h"

//初始化
SLTNode* BuySListNode(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 SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		//找到下一个地址
		cur = cur->next;
	}
	printf("NULL\n");
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	//初始化
	SLTNode* newnode = BuySListNode(x);
	//改变地址指向
	newnode->next = *pphead;
	//指向开始
	*pphead = newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	//初始化
	SLTNode* newnode = BuySListNode(x);
	//判断pphead == NULL
	if (*pphead == NULL)
	{
		//改变的结构体的指针,所以要用二级指针
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			//找到尾
			tail = tail->next;
		}

		//改变的结构体,用结构体的指针即可(指向空指针)
		tail->next = newnode;
	}
}

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

//尾删
void SLTPopBack(SLTNode** pphead)
{
	//不能为空
	assert(*pphead);

	// 1、一个节点
	if ((*pphead)->next == NULL)
	{
		//释放空间
		free(*pphead);
		//指向空
		*pphead = NULL;
	}
	// 2、一个以上节点
	else
	{
		//找到尾
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}

		//释放空间
		free(tail->next);
		//指向空
		tail->next = NULL;
	}
}

//查找下标 需要给尾phead参数
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}
	return NULL;
}

//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	//断言
	assert(pphead);
	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;
	}
}

//在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	//断言
	assert(pos);
	
	//初始化

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

//删除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);
	}
}

//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
	//断言
	assert(pos);
	//检查pos是否是尾节点
	assert(pos->next);
	SLTNode* posNext = pos->next;
	pos->next = posNext->next;
	free(posNext);
	posNext = NULL;
}


// 单链表结点修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur != pos)
	{
		cur = cur->next;
		assert(cur);
	}
	pos->data = x;
}


//销毁链表
void SLTDestory(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	//比cur->next!=NULL更好一些
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

🌟结束语

       今天内容就到这里啦,时间过得很快,大家沉下心来好好学习,会有一定的收获的,大家多多坚持,嘻嘻,成功路上注定孤独,因为坚持的人不多。那请大家举起自己的小说手给博主一键三连,有你们的支持是我最大的动力💞💞💞,回见。

更多推荐

基于Java个性化美食推荐系统设计实现(源码+lw+部署文档+讲解等)

博主介绍:✌全网粉丝30W+,csdn特邀作者、博客专家、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌🍅文末获取源码联系🍅👇🏻精彩专栏推荐订阅👇🏻不然下次找不到哟2022-2024年最全的计算机软件毕业设计选题

基于香橙派和SU-03T 使用Linux实现语音控制刷抖音

硬件介绍SU-03T之前在小车的时候使用过,详见:语音小车---6+最终整合_mjmmm的博客-CSDN博客按照下图进行接线:项目需求通过语音指令来控制安卓手机刷抖音,可以实现视频切换和点赞等功能:1.开机播报“你好,我是你的刷抖音助手”1.当说出“你好抖音助手"可以唤醒模块,模块回复“抖音助手在”2.当超过10s没有

七天学会C语言-第一天(C语言基本语句)

一、固定格式这个是C程序的基本框架,需要记住!!!#include<stdio.h>intmain(){return0;}二、printf语句简单输出一句C程序:#include<stdio.h>intmain(){printf("大家好,");printf("我是");printf("沐尘而生!");return0;

9月15日、9月18日上课内容 Zookeeper集群 + Kafka集群

Zookeeper本章结构Zookeeper概述Zookeeper定义*(了解)Zookeeper是一个开源的分布式的,为分布式框架提供协调服务的Apache项目。Zookeeper工作机制*****(非常重要,需要掌握)Zookeeper从设计模式角度来理解:是一个基于观察者模式设计的分布式服务管理框架,它负责存储和

Cobol学习笔记(整理中80%)

1.数据类型1.1变量定义序号数据名PIC数据类型[VALUE值].例:03MY-IDPIC999[VALUE123].数据类型写几个长度就是几。1.2数据类型1.2.1数值型9:数值型,99999缩写9(5),不满位前补0,0有(+)符号。S:正负数值,S9999缩写S9(4),不满位前补0,值有正负符号。V:小数,

【大数据毕设】基于Hadoop的音乐推荐系统论文(三)

博主介绍:✌全网粉丝6W+,csdn特邀作者、博客专家、大数据领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于大数据技术领域和毕业项目实战✌🍅文末获取项目联系🍅摘要本文基于Hadoop技术,设计并实现了一个名为“酷酷音乐网站”的系统,用于音乐资源的存储、管理和推荐。该系统采用Hado

MySQL 面试题——MySQL 基础

目录1.什么是MySQL?有什么优点?2.MySQL中的DDL与DML是分别指什么?3.✨数据类型varchar与char有什么区别?4.数据类型BLOB与TEXT有什么区别?5.DATETIME和TIMESTAMP的异同?6.✨MySQL中IN和EXISTS的区别是什么?7.MySQL中记录货币用什么字段类型比较好?

java微服务 Dubbo面试题/SpringCloud面试题

java微服务面试题Q:为什么要用微服务?微服务有哪些优势?单体应用把所有功能都堆放在一起,改动影响大,风险高。微服务具有以下优势:针对特定服务发布,影响小,风险小,成本低。频繁发布版本,快速交付需求。低成本扩容,弹性伸缩,适应云环境。Q:怎么解决服务调用闭环(循环依赖)?服务分层,设定groupId。比如分为上层服务

QQ邮箱怎么设置SMTP接口服务器?

在现如今信息快速传递的时代,邮件已成为我们工作、学习和生活中必不可少的一部分。而作为每位用户必备的一款邮箱,QQ邮箱一直以其稳定、高效、安全的特点深受大家的青睐。但是你是否觉得每次发邮件都需要打开QQ邮箱网页,进行繁琐的操作很是麻烦呢?其实,QQ邮箱也提供了SMTP接口服务器,使得我们可以直接调用SMTP接口,让发信更

如何通过bat批处理实现快速生成文件目录,一键生成文件名和文件夹名目录

碰对了情人,相思一辈子。具体方法步骤:一、创建一个执行bat文件(使用记事本即可);1、新建一个txt文本空白记事本文件2、复制以下内容进记事本内dir/a/s/b>LIST.TXT(其中LIST.TXT文件名是提取后将要自动新建的文本文件)二、记事本保存,文件名可以任意写三、把保存的文件名后缀.txt改为.bat,这

网络路径监控分析

不间断的连接应该是任何企业的首要任务。然而,确保网络中的源和目标之间持续、不间断的联系一直是网络通信中一个劳动密集型的过程。了解网络路径中的障碍、识别它们并迅速解决它们以维护健康、不间断的网络至关重要。为什么要监控网络路径维护网络运行状况是任何LAN或WAN网络中最重要的因素。在数据传输期间,无法查明和排查网络路径中跃

热文推荐