当前位置： 首页 > news >正文

单链表——简单的增删查改

news 来源：原创 2024/4/19 16:57:22

前言：上次介绍了顺序表，这次我要分享对单链表的一些简单理解，主要框架与上次大致相同，内容主要是单链表的增删查改，适用于初学者，之后会继续更新一些更深入的内容。同时，这也仅仅是我个人对所学知识的一些总结，有错误还望各位能够指正，谢谢各位。

目录

一：链表的简单介绍

(1) 概述

(2) 图示

二：单链表实现简单的增删查改

(1) 大致框架

1. 程序的基本框架

2. 三大基本功能函数的实现(打印，节点创建，链表销毁)

(2) 尾插尾删的实现

1. 尾插

2. 尾删

3. 测试样例结果展示

(3) 头插头删的实现

1. 头插

2. 头删

3. 测试样例结果展示

(4) 指定位置的插入与删除

1. 坐标的查找

2. 指定节点的插入

3. 锁定节点的删除

三：完整代码的展示及测试结果的呈现

(1) Test.c

(2) SList.h

(3) SList.c

(4) 测试结果

一：链表的简单介绍

(1) 概述

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。同时要特别说明的是：链表与数组最本质的区别就是链表由两部分组成，即数据域和指针域，这样的结构使其既能够存储数据，又可以比较灵活的对数据进行插入删除。当然，其相较于数组而言不仅只有优点，还有一些不可避免的缺陷，后续会专门对二者进行一个比较。

(2) 图示

单链表的逻辑结构与现实生活中的火车十分相似，由车头与多节车厢组成。但是我们要清楚，单链表实际是以物理结构存在的，没有所谓的连接关系，只是一个一个节点之间可以依靠着各个节点的指针域进行链接，而形成一种链式结构。

二：单链表实现简单的增删查改

(1) 大致框架

1. 程序的基本框架

Test.c——用于各个接口函数功能的测试

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"

void Test1()//尾插尾删的测试样例
{
	SLNode* phead = NULL;//定义一个指向链表起始位置的指针phead

	//尾插需要改变phead的指向,所以传参时要传递二级指针!!!!!
	SListPushBack(&phead, 1);
	SListPushBack(&phead, 2);
	SListPushBack(&phead, 3);
	SListPushBack(&phead, 4);
	SListPushBack(&phead, 5);
	SListPrint(phead);

	SListPopBack(&phead);
	SListPopBack(&phead);
	SListPopBack(&phead);
	SListPrint(phead);

	SListDestroy(&phead);
}

//完成接口函数功能的测试
int main()
{
 	Test1();//测试尾插尾删

	//Test2();//测试头插头删
	
	//Test3();//测试锁定位置的插入与删除
	return 0;
}

 SList.h——用于各个头文件的包含,单链表结构的定义以及各个接口函数的定义

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

typedef int SLNDataType;//单链表数据域数据类型的定义

//单链表结构的定义
typedef struct SListNode
{
	struct SListNode* next;//指针域
	SLNDataType data;//数据域
} SLNode;

//单链表增删查改的接口函数定义
void SListPrint(SLNode* phead);//打印
SLNode* BuySListNode(SLNDataType x);//开辟新节点
void SListDestroy(SLNode** pphead);//销毁单链表,防止内存泄漏问题

void SListPushBack(SLNode** pphead, SLNDataType x);//尾插
void SListPopBack(SLNode** pphead);//尾删
void SListPushFront(SLNode** pphead, SLNDataType x);//头插
void SListPopFront(SLNode** pphead);//头删

SLNode* SListFind(SLNode* phead,SLNDataType x);//查找某个节点
void SListInsertAfter(SLNode* pos, SLNDataType x);//在pos节点后进行节点的插入
void SListEraseAfter(SLNode* pos);//删除pos节点后的节点
void SListEraseNode(SLNode** pphead, SLNode* pos);//删除pos节点

SList.c——用于各个接口函数功能的实现

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"

void SListPrint(SLNode* phead)//打印
{
	
}

SLNode* BuySListNode(SLNDataType x)//开辟节点,并且需要返回开辟的节点
{
	
}

void SListPushBack(SLNode** pphead, SLNDataType x)//尾插的两种情况
{
	
}

void SListPopBack(SLNode** pphead)//尾删要考虑三种情况(要考虑周到)！！！
{
	
}

void SListPushFront(SLNode** pphead, SLNDataType x)//头插直接插入即可
{
	
}

void SListPopFront(SLNode** pphead)//头删
{
	
}

SLNode* SListFind(SLNode* phead,SLNDataType x)//查找
{
	
}

void SListInsertAfter(SLNode* pos, SLNDataType x)//pos后插入
{
	
}

void SListEraseAfter(SLNode* pos)//删除pos节点后的节点
{
	
}

//删除pos节点有两种情况:1.pos位于首节点————直接头删即可  2.pos不位于首节点————需要先找到pos的前一个结点
void SListEraseNode(SLNode** pphead, SLNode* pos)
{
	
}

//销毁链表
void SListDestroy(SLNode** pphead)
{
	
}

2. 三大基本功能函数的实现(打印，节点创建，链表销毁)

(i) 单链表的打印

void SListPrint(SLNode* phead)//打印
{
	SLNode* cur = phead;
	while (cur)//遍历单链表进行打印
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	if (cur == NULL)//将NULL也打印出来
	{
		printf("NULL\n");
	}
}

(ii) 单链表节点的创建

单链表在插入的过程中,可以实现单个节点的增加,这也是其相较于数组的一项优势,即不存在空间的浪费,而节点的增加必然离不开节点的开辟,因此需要运用到动态开辟空间的知识,即利用malloc函数开辟节点。

SLNode* BuySListNode(SLNDataType x)//开辟节点,并且需要返回开辟的节点
{
	SLNode* tmp = (SLNode*)malloc(sizeof(SLNode));
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);//直接退出程序
	}
	SLNode* newnode = tmp;
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

(iii) 单链表的销毁

在以前学习动态内存管理的知识后就知道,动态开辟的空间在使用完后都要进行释放,否则就会产生内存泄漏的严重后果,因此我们需要将单链表中动态开辟的节点进行释放：

void SListDestroy(SLNode** pphead)
{
	assert(pphead);
	SLNode* cur = *pphead;
	while (cur)//遍历节点进行释放
	{
		SLNode* tmp = cur->next;//保存节点
		free(cur);
		cur = tmp;
	}
	*pphead = NULL;
}

(2) 尾插尾删的实现

1. 尾插

单链表的尾插过程会涉及两种情况：

(1) 链表初始无节点———开辟节点后直接插入即可

(2) 链表初始有节点———先找尾,再将开辟的节点插入尾部

void SListPushBack(SLNode** pphead, SLNDataType x)//两种情况
{
	SLNode* newnode = BuySListNode(x);//插入数据要先开辟节点
	
	if (*pphead == NULL)//1.初始无节点
	{
		*pphead = newnode;
	}
	else//2.初始有节点时:尾插先找尾
	{
		SLNode* tail = *pphead;
		while (tail->next)//遍历找尾
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

2. 尾删

单链表尾节点的删除比插入复杂些,一共要考虑三种情况：

(1) 链表为空——使用assert函数进行断言直接报错警告操作者即可

(2) 只有一个节点——将唯一的节点释放再置空(这里需要强调一点的是:要直接释放传递过来的参数所代表的首节点,不可只释放用其定义的变量！！！)

(3) 有多个节点——利用遍历链表找尾节点的思路即可

void SListPopBack(SLNode** pphead)//要考虑三种情况(要考虑周到)！！！
{
	//1.链表为空————使用assert函数进行断言直接报错警告操作者
	assert(*pphead);
	SLNode* tail = *pphead;//定义一个用来找尾节点的变量

	//2.只有一个节点————将唯一的节点释放,再置空
	/*if (tail->next == NULL)    (当只有一个节点时,要free掉(*pphead)才达到了释放的效果！！！)
	{
		free(tail); //err!!!
		tail = NULL;
	}*/
	if ((*pphead)->next == NULL)//当只有一个节点时,要free掉(*pphead)才达到了释放的效果
	{
		free(*pphead);
		*pphead = NULL;
	}
	//3.有多个节点——利用遍历链表找尾节点的思路(有两种解决方法)
	
	//else  //方法一
	//{
	//	SLNode* tailPrev = NULL;//用来保存tail的前一个节点,以保证链表能够链接起来
	//	while (tail->next)
	//	{
	//		tailPrev = tail;
	//		tail = tail->next;
	//	}
	//	free(tail);
	//	tail = NULL;
	//	tailPrev->next = NULL;
	//}
	else //简易一点 （方法二）
	{
		while (tail->next->next)//这里找尾并未找到尾节点,找到的是其前一个节点
		{
			tail = tail->next;
		}
		free(tail->next);//此时的tail->next才是真正的尾节点
		tail->next = NULL;
	}
}

3. 测试样例结果展示

(3) 头插头删的实现

1. 头插

相较于尾插,头插简单了一些,不需要进行找尾操作,直接将创建的节点插入即可：

void SListPushFront(SLNode** pphead, SLNDataType x)//头插直接插入即可
{
	assert(pphead);
	SLNode* newnode = BuySListNode(x);//创建节点
	newnode->next = *pphead;//开始链接
	*pphead = newnode;//链表首节点的移动
}

2. 头删

相较于尾删,头删同样简单了一些,不需要进行找尾操作,并且只用考虑链表有无节点两种情况就行，直接将首节点删除,再改变首节点即可：

void SListPopFront(SLNode** pphead)//头删
{
	assert(pphead);
	assert(*pphead);//判空
	SLNode* next = (*pphead)->next;//记录,以方便改变首节点位置
	free(*pphead);
	*pphead = next;
}

3. 测试样例结果展示

(4) 指定位置的插入与删除

1. 坐标的查找

要想进行某个位置的插入删除,那就必须先获取该位置的坐标位置,使用以下函数接口就可以实现单链表中某个坐标的查找：

SLNode* SListFind(SLNode* phead,SLNDataType x)
{
	SLNode* cur = phead;
	while (cur && cur->data != x)//停止寻找的两种情况:1.cur遍历了整个链表  2.找到了目标坐标
	{
		cur = cur->next;//遍历寻找数据域为x的节点
	}
	return cur;//找到了就返回该节点,否则会返回NULL
}

2. 指定节点的插入

使用函数SListFind锁定坐标后,可以对其进行后置插入或前置插入,下面展示后置插入：

void SListInsertAfter(SLNode* pos, SLNDataType x)//pos表示被锁定的节点
{
	SLNode* newnode = BuySListNode(x);//创建要插入的新节点
	SLNode* next = pos->next;//记录被锁定节点的后一节点
	pos->next = newnode;
	newnode->next = next;//两步进行链接
}

3. 锁定节点的删除

对锁定节点进行删除一共有两种情况：

(1)  pos位于首节点———直接头删即可

(2)  pos不位于首节点———需要先找到pos的前一个结点，再执行删除及链接

//删除pos节点有两种情况:1.pos位于首节点————直接头删即可 
// 2.pos不位于首节点————需要先找到pos的前一个结点
void SListEraseNode(SLNode** pphead, SLNode* pos)
{
	assert(pphead && *pphead);
	SLNode* posPrev = *pphead;

	if (pos == *pphead)//头节点,直接头删即可
	{
		SListPopFront(pphead);
	}
	else
	{
		while (posPrev->next != pos)//遍历找到pos的前一个节点
		{
			posPrev = posPrev->next;
		}
		posPrev->next = pos->next;
		free(pos);
	}
}

三：完整代码的展示及测试结果的呈现

(1) Test.c

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"

void Test1()//尾插尾删的测试
{
	SLNode* phead = NULL;//定义一个指向链表起始位置的指针phead

	//尾插需要改变phead的指向,所以传参时要传递二级指针!!!!!
	SListPushBack(&phead, 1);
	SListPushBack(&phead, 2);
	SListPushBack(&phead, 3);
	SListPushBack(&phead, 4);
	SListPushBack(&phead, 5);
	SListPrint(phead);

	SListPopBack(&phead);
	SListPopBack(&phead);
	SListPopBack(&phead);
	SListPrint(phead);

	SListDestroy(&phead);
}

void Test2()//头插头删的测试
{
	SLNode* phead = NULL;

	SListPushFront(&phead, 1);
	SListPushFront(&phead, 2);
	SListPushFront(&phead, 3);
	SListPushFront(&phead, 4);
	SListPushFront(&phead, 5);
	SListPrint(phead);

	SListPopFront(&phead);
	SListPopFront(&phead);
	SListPopFront(&phead);
	SListPrint(phead);

	SListDestroy(&phead);
}

void Test3()//锁定位置的插入与删除的测试
{
	//先构建一小段单链表
	SLNode* phead = NULL;
	SListPushBack(&phead, 1);
	SListPushBack(&phead, 2);
	SListPushFront(&phead, 3);
	SListPushFront(&phead, 4);
	SListPushFront(&phead, 5);
	SListPrint(phead);

	//测试在pos节点后进行节点的插入
	SLNode* node = SListFind(phead,3);
	if (node != NULL)
	{
		SListInsertAfter(node, 6);
	}
	SListPrint(phead);

	node = SListFind(phead, 5);
	if (node != NULL)
	{
		SListInsertAfter(node, 8);
	}
	SListPrint(phead);

	//测试删除pos节点
	node = SListFind(phead, 5);
	if (node != NULL)
	{
		SListEraseNode(&phead,node);
	}
	SListPrint(phead);
	node = SListFind(phead, 1);
	if (node != NULL)
	{
		SListEraseNode(&phead, node);
	}
	SListPrint(phead);

	SListDestroy(&phead);
}

//完成接口函数功能的测试
int main()
{
 	//Test1();//测试尾插尾删

	//Test2();//测试头插头删
	
	Test3();//测试锁定位置的插入与删除
	return 0;
}

(2) SList.h

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

typedef int SLNDataType;//单链表数据域数据类型的定义

//单链表结构的定义
typedef struct SListNode
{
	struct SListNode* next;//指针域
	SLNDataType data;//数据域
} SLNode;

//单链表增删查改的接口函数定义
void SListPrint(SLNode* phead);//打印
SLNode* BuySListNode(SLNDataType x);//开辟新节点
void SListDestroy(SLNode** pphead);//销毁单链表,防止内存泄漏问题

void SListPushBack(SLNode** pphead, SLNDataType x);//尾插
void SListPopBack(SLNode** pphead);//尾删
void SListPushFront(SLNode** pphead, SLNDataType x);//头插
void SListPopFront(SLNode** pphead);//头删

SLNode* SListFind(SLNode* phead,SLNDataType x);//查找某个节点
void SListInsertAfter(SLNode* pos, SLNDataType x);//在pos节点后进行节点的插入
void SListEraseNode(SLNode** pphead, SLNode* pos);//删除pos节点

(3) SList.c

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"

void SListPrint(SLNode* phead)//打印
{
	SLNode* cur = phead;
	while (cur)//遍历单链表进行打印
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	if (cur == NULL)//将NULL也打印出来
	{
		printf("NULL\n");
	}
}

SLNode* BuySListNode(SLNDataType x)//开辟节点,并且需要返回开辟的节点
{
	SLNode* tmp = (SLNode*)malloc(sizeof(SLNode));
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);//直接退出程序
	}
	SLNode* newnode = tmp;
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

void SListPushBack(SLNode** pphead, SLNDataType x)//尾插的两种情况
{
	SLNode* newnode = BuySListNode(x);//插入数据要先开辟节点
	
	if (*pphead == NULL)//1.初始无节点
	{
		*pphead = newnode;
	}
	else//2.初始有节点时:尾插先找尾
	{
		SLNode* tail = *pphead;
		while (tail->next)//遍历找尾
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

void SListPopBack(SLNode** pphead)//尾删要考虑三种情况(要考虑周到)！！！
{
	//1.链表为空————使用assert函数进行断言直接报错警告操作者
	assert(*pphead);
	SLNode* tail = *pphead;//定义一个用来找尾节点的指针变量

	//2.只有一个节点————将唯一的节点释放,再置空

 //(当只有一个节点时,要free掉(*pphead)才达到了释放的效果！！！)
	/*if (tail->next == NULL)   err 
	{
		free(tail);
		tail = NULL;
	}*/
	if ((*pphead)->next == NULL)//当只有一个节点时,要free掉*pphead才达到了释放的效果
	{
		free(*pphead);
		*pphead = NULL;
	}
	//3.有多个节点——利用遍历链表找尾节点的思路(有两种解决方法)
	
	//else  //方法一
	//{
	//	SLNode* tailPrev = NULL;//用来保存tail的前一个节点,以保证链表能够链接起来
	//	while (tail->next)
	//	{
	//		tailPrev = tail;
	//		tail = tail->next;
	//	}
	//	free(tail);
	//	tail = NULL;
	//	tailPrev->next = NULL;
	//}
	else //简易一点 （方法二）
	{
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

void SListPushFront(SLNode** pphead, SLNDataType x)//头插直接插入即可
{
	assert(pphead);
	SLNode* newnode = BuySListNode(x);//创建节点
	newnode->next = *pphead;//开始链接
	*pphead = newnode;//链表首节点的移动
}

void SListPopFront(SLNode** pphead)//头删
{
	assert(pphead);
	assert(*pphead);//判空
	SLNode* next = (*pphead)->next;//记录,以方便改变首节点位置
	free(*pphead);
	*pphead = next;
}

SLNode* SListFind(SLNode* phead,SLNDataType x)//查找
{
	SLNode* cur = phead;
	while (cur && cur->data != x)//停止寻找的两种情况:1.cur遍历了整个链表  2.找到了目标坐标
	{
		cur = cur->next;//遍历寻找数据域为x的节点
	}
	return cur;//找到了就返回该节点,否则会返回NULL
}

void SListInsertAfter(SLNode* pos, SLNDataType x)//pos后插入
{
	SLNode* newnode = BuySListNode(x);//创建要插入的新节点
	SLNode* next = pos->next;//记录被锁定节点的后一节点
	pos->next = newnode;
	newnode->next = next;//两步进行链接
}

//删除pos节点有两种情况:1.pos位于首节点————直接头删即可  
//2.pos不位于首节点————需要先找到pos的前一个结点
void SListEraseNode(SLNode** pphead, SLNode* pos)
{
	assert(pphead && *pphead);
	SLNode* posPrev = *pphead;

	if (pos == *pphead)//头节点,直接头删即可
	{
		SListPopFront(pphead);
	}
	else
	{
		while (posPrev->next != pos)//遍历找到pos的前一个节点
		{
			posPrev = posPrev->next;
		}
		posPrev->next = pos->next;
		free(pos);
	}
}

void SListDestroy(SLNode** pphead)//销毁单链表
{
	assert(pphead);
	SLNode* cur = *pphead;
	while (cur)//遍历节点进行释放
	{
		SLNode* tmp = cur->next;//保存节点
		free(cur);
		cur = tmp;
	}
	*pphead = NULL;
}

(4) 测试结果

总结：

这里仅仅是单链表简单的增删查改功能的实现,大家掌握了后最好还可以去找到一些对应的习题进行练习,这里就不再多说。如果文章有错误还望各位多多指正，万分感谢，再见。

相关文章：

  • 电子技术——MOS放大器基础
  • 嵌入式 学习
  • 【Linux】vim编辑器的使用
  • 强化学习笔记：基于策略的学习之策略迭代(python实现)
  • 1. Spring 基础入门
  • springboot 分布式全局唯一id的生成-雪花算法snowflake
  • 如何使用VMware虚拟机（带你快速了解）
  • Python---学生管理系统(pyinstaller)
  • 客快物流大数据项目（一百零八）：Spring Cloud 技术栈
  • ZYNQ IP核之RAM
  • Day10 C++STL入门基础知识七——案例1【评委打分】
  • 计算机相关专业混体制的解决方案（考公务员）
  • OpenCV-PyQT项目实战（1）安装与环境配置
  • 【HTML | CSS】春节将至，为网页挂上精美的灯笼吧（附源码）程序员的浪漫
  • 字节青训前端笔记 | Next.js 入门
  • 【399天】跃迁之路——程序员高效学习方法论探索系列（实验阶段156-2018.03.11）...
  • 【译】理解JavaScript：new 关键字
  • CODING 缺陷管理功能正式开始公测
  • extjs4学习之配置
  • Golang-长连接-状态推送
  • JDK 6和JDK 7中的substring（）方法
  • Linux快速配置 VIM 实现语法高亮 补全 缩进等功能
  • Redis提升并发能力 | 从0开始构建SpringCloud微服务(2)
  • vue从入门到进阶：计算属性computed与侦听器watch（三）
  • windows下使用nginx调试简介
  • Xmanager 远程桌面 CentOS 7
  • 基于 Babel 的 npm 包最小化设置
  • 简单易用的leetcode开发测试工具（npm）
  • 今年的LC3大会没了？
  • 如何使用 OAuth 2.0 将 LinkedIn 集成入 iOS 应用
  • 使用 5W1H 写出高可读的 Git Commit Message
  • 为物联网而生：高性能时间序列数据库HiTSDB商业化首发！
  • 进程与线程（三）——进程/线程间通信
  • #{}和${}的区别是什么 -- java面试
  • （博弈 sg入门）kiki's game -- hdu -- 2147
  • (生成器)yield与(迭代器)generator
  • (十三)Maven插件解析运行机制
  • （心得）获取一个数二进制序列中所有的偶数位和奇数位， 分别输出二进制序列。
  • （转）linux 命令大全
  • （转）visual stdio 书签功能介绍
  • .Net 6.0 处理跨域的方式
  • .net core使用ef 6
  • .NET 除了用 Task 之外，如何自己写一个可以 await 的对象？
  • .NET 读取 JSON格式的数据
  • .NET 设计模式—简单工厂（Simple Factory Pattern）
  • [BeginCTF]真龙之力
  • [mysql] mysqldump 导出数据库表
  • [NOIP2004] 提高组 洛谷P1090 合并果子
  • [NOIP2013]华容道
  • [one_demo_5]命令行输入输出
  • [PHP]关联和操作MySQL数据库然后将数据库部署到ECS
  • [RK3568 Android11] Input UI 使用流程
  • [SRM603] WinterAndSnowmen
  • [Valkyrie网络测试仪-软件使用技巧] - Scheduler动作录制，定制打流过程（中途启停/调整带宽/使能部分流量）
  • [VisualStudioCode]_[VSCODE]_[C/C++开发环境配置-问题解决和补充]