【数据结构与算法】单链表的增删查改（附源码）

news/2025/2/22 14:35:20

 

这么可爱的猫猫不值得点个赞吗😽😻

目录

一.链表的概念和结构

二.单链表的逻辑结构和物理结构

1.逻辑结构

 2.物理结构

三.结构体的定义

四.增加

1.尾插   SListpushback

2.头插  SListpushfront

五.删除

1.尾删  SListpopback

2.头删  SListpopfront

六.查找  插入  释放   打印

1.查找   SListfind

2.插入  SListinsert

3.释放  SListerase

4.打印  SListprint

七.源码

1.SList.h

2.SList.c

3.test.c

一.链表的概念和结构

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

链表其实有很多种类：

1.单向  双向

2.带头  不带头

3.循环  不循环

其中共能组合出8种形式的链表；

这篇文章讲的是结构最简单的链表，也就是单向不带头不循环链表，即单链表。

单链表中的元素称为节点，节点有一个数据data，还有一个结构体指针next 存储下一个节点的地址，最后一个节点的next是NULL。

二.单链表的逻辑结构和物理结构

1.逻辑结构

 2.物理结构

三.结构体的定义

typedef int SLdatatype;  //对数据类型重定义，方便后续更改

typedef struct SListNode
{
	SLdatatype data;
	struct SListNode* next;
}SLNode;

四.增加

1.尾插   SListpushback

想要实现尾插，就要先找到尾节点，但要注意，当链表是空时，就没有尾节点，这个时候直接插入就行了；

我们可以申请一个新的节点newnode，然后插入链表中，由于尾插和头插都需要申请新的节点，所以我们可以将这封装成一个函数；

注意，不管是尾插还是头插，最后都会使链表发生改变，所以我们要传二级指针进去。

找尾节点时，while里的循环条件要写成 tail->next !=NULL  

请看逻辑结构：

申请新节点 BuySListNode

SLNode* BuySListNode(SLdatatype x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	assert(newnode);
	newnode->data = x;  //x是要插入的数据
	newnode->next = NULL;
	return newnode;
}

尾插 SListpushback

 

void SListpushback(SLNode** pphead,SLdatatype x)  //注意传的是二级指针
{
	SLNode* newnode = BuySListNode(x);
	if (*pphead == NULL)   //判断链表是否为空
	{
		*pphead = newnode;
	}
	else
	{
		SLNode* tail = *pphead;  //寻找尾节点
		while (tail->next != NULL)   //注意这里不能写成 while(tail!=NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

2.头插  SListpushfront

头插时只需让新节点的 next 指向旧的头节点，然后再把 newnode 赋给头节点，使之成为新的头节点，即使是空表也没关系，newnode 会直接成为头节点。

 

void SListpushfront(SLNode** pphead, SLdatatype x)
{
	SLNode* newnode = BuySListNode(x);
		newnode->next = *pphead;
		*pphead = newnode;
}

五.删除

1.尾删  SListpopback

尾删前，我们需要判断：

1.若为空表，则直接结束函数；

2.若链表中只有一个节点，则直接 free 头节点，然后置为NULL；

3.寻找尾节点 tail 和尾节点的前一个节点 pre ,因为我们释放掉尾节点后，pre就成为了新的尾节点，而尾节点的 next 是 NULL ，所以我们需要找到尾节点的前一个节点。

找尾的方法和之前的一样。

void SListpopback(SLNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->next == NULL)  //注意这里因为优先级的问题，*pphead 要打括号
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* pre = NULL;
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			pre = tail;   //记录 tail 的前一个节点
			tail = tail->next;
		}
		pre->next = NULL;  //next 置为NULL
	}
}

2.头删  SListpopfront

在头删前：

1.判断是否为空表；

2.定义一个 next 用来保存头节点中的 next  ，释放完后，这个 next 就成为了新的头节点。

void SListpopfront(SLNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		SLNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}

六.查找  插入  释放   打印

1.查找   SListfind

在插入和释放前，都需要调用 find 函数，来找到希望插入或是释放的位置。

SLNode* SListfind(SLNode* phead, SLdatatype x)
{
	SLNode* pos = phead;
	while (pos)
	{
		if (pos->data == x)
		{
			return pos;
		}
		pos = pos->next;
	}
}

2.插入  SListinsert

如果是链表中只有一个节点，就变成了头插，只需要调用头插函数就行了，如果是空表也不用担心，可以设置成不调用函数；

在插入前，需要找到指定位置 pos 的前驱 pre，

使pre->next=newnode  , newnode->next=pos

如图所示，假设在3的前一个位置插入数据：

 

void SListinsert(SLNode** pphead, SLNode* pos,SLdatatype x)
{
	SLNode* newnode = BuySListNode(x);
	if (pos->next == NULL)
	{
		SListpushfront(pphead, x);
	}
	else
	{
		SLNode* pre = *pphead;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		pre->next = newnode;
		newnode->next = pos;
	}
}

3.释放  SListerase

释放前：

1.如果只有一个节点，则直接释放头节点，再置为空即可；

2.如果不止一个节点，还需找到要释放的位置的前一个节点 pre ，将 pre 的 next 指向 pos 的next，然后再释放;

如图所示，假设要释放掉3这个节点：

 

void SListerase(SLNode** pphead, SLNode* pos, SLdatatype x)
{
	if (pos->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* pre = *pphead;
		while (pre->next !=pos)
		{
			pre = pre->next;
		}
		pre->next = pos->next;
		free(pos);
	}
}

4.打印  SListprint

虽然可以直接用头节点 phead 遍历，但博主还是推荐定义一个新的结构体指针  cur  ，把phead 的值赋给 cur ，会显得更优雅；

注意这里的 while 里的式子要写成  cur  ，如果 写成 cur->next ，那么最终打印出来的结果会少一个节点的数据。

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

七.源码

1.SList.h

#define _CRT_SECURE_NO_WARNINGS


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

typedef int SLdatatype;

typedef struct SListNode
{
	SLdatatype data;
	struct SListNode* next;
}SLNode;


void SListprint(SLNode* phead);   //打印

void SListpushback(SLNode** pphead,SLdatatype x);   //尾插

void SListpushfront(SLNode** pphead, SLdatatype x);   //头插

void SListpopfront(SLNode** pphead);   //头删

void SListpopback(SLNode** pphead);   //尾删

SLNode* SListfind(SLNode* phead,SLdatatype x);   //查找

void SListinsert(SLNode** pphead, SLNode* pos,SLdatatype x);   //插入

void SListerase(SLNode** pphead, SLNode* pos, SLdatatype x);   //释放

2.SList.c

#define _CRT_SECURE_NO_WARNINGS

#include "SList.h"


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


SLNode* BuySListNode(SLdatatype x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

void SListpushback(SLNode** pphead,SLdatatype x)
{
	SLNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLNode* tail = *pphead;  //寻找尾节点
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}


void SListpushfront(SLNode** pphead, SLdatatype x)
{
	SLNode* newnode = BuySListNode(x);
		newnode->next = *pphead;
		*pphead = newnode;
}


void SListpopfront(SLNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		SLNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}


void SListpopback(SLNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* pre = NULL;
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			pre = tail;
			tail = tail->next;
		}
		pre->next = NULL;
	}
}


SLNode* SListfind(SLNode* phead, SLdatatype x)
{
	SLNode* pos = phead;
	while (pos)
	{
		if (pos->data == x)
		{
			return pos;
		}
		pos = pos->next;
	}
}


void SListinsert(SLNode** pphead, SLNode* pos,SLdatatype x)
{
	SLNode* newnode = BuySListNode(x);
	if (pos->next == NULL)
	{
		SListpushfront(pphead, x);
	}
	else
	{
		SLNode* pre = *pphead;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		pre->next = newnode;
		newnode->next = pos;
	}
}



void SListerase(SLNode** pphead, SLNode* pos, SLdatatype x)
{
	if (pos->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* pre = *pphead;
		while (pre->next !=pos)
		{
			pre = pre->next;
		}
		pre->next = pos->next;
		free(pos);
	}
}

3.test.c

博主写的主函数只是用来测试单链表的，写起主函数来也不难，大家可以自行编写。

#include "SList.h"


void testSList1()
{
	SLNode* plist = NULL;
	
	SListpushback(&plist,1);
	SListpushback(&plist,2);
	SListpushback(&plist,3);
	SListpushback(&plist,4);
	SListprint(plist);
	SListpushfront(&plist, 0);
	SListprint(plist);
	SListpopfront(&plist);
	SListpopfront(&plist);
	SListpopfront(&plist);
	SListprint(plist);
	SListpopback(&plist);
	SListpopback(&plist);
	SListpopback(&plist);
	SListprint(plist);
}

void testSList2()
{
	SLNode* plist = NULL;
	SListpushback(&plist, 1);
	SListpushback(&plist, 2);
	SListpushback(&plist, 3);
	SListpushback(&plist, 4);
	SLNode* pos = SListfind(plist, 3);
	if (pos)
	{
		SListinsert(&plist,pos, 20);
		SListprint(plist);
	}
	pos = SListfind(plist, 2);
	if (pos)
	{
		SListerase(&plist,pos,2);
		SListprint(plist);
	}
	
}

int main()
{
	//testSList1();
	testSList2();
	return 0;
}

八.单链表的一些问题

在单链表中，要想找到某一个数据，就需要从头节点开始，所以单链表是非随机存取的存储结构，且要想对单链表进行一些操作，总是要找到前驱节点，有时还需判断一些特殊情况，有什么办法能解决这些问题呢？

博主将在下篇双向带头循环链表中讲解，敬情期待~

🤩🥰本篇文章到此就结束了，如有错误或是建议，欢迎小伙伴们提出~😍😃

🐲👻希望可以多多支持博主哦~🥰😍

🤖🐯谢谢你的阅读~👻🦁

 


http://www.niftyadmin.cn/n/104603.html

相关文章

多线程之wait和notify

多线程之wait和notify

目录 1.wait()方法 2. notify方法 因为线程之间是抢占式执行的&#xff0c;所以线程之间执行的先后顺序难以预知。但是实际开发中&#xff0c;我们希望线程之间的执行顺序是能被掌控的&#xff0c;比如线程2开始之前&#xff0c;需要线程1的某个任务先被执行。也就是说,很多时…
阅读更多...
Pytorch中FLOPs和Params计算

Pytorch中FLOPs和Params计算

文章目录一. 含义二. 使用thop库计算FLOPs和Params三. 注意四. 相关链接一. 含义 FLOPs&#xff08;计算量&#xff09;&#xff1a;注意s小写&#xff0c;是floating point operations的缩写&#xff08;这里的小s则表示复数&#xff09;&#xff0c;表示浮点运算数&#xff…
阅读更多...
Rust语言的基本介绍

Rust语言的基本介绍

rust缘起和目标 rust的英文是锈菌&#xff0c;是一种真菌&#xff0c;这种真菌的生命力非常顽强&#xff0c;其 在生命周期内可以产生多达5种孢子类型&#xff0c;这5种生命形态还可以相互转 化。“Rust”也有“铁锈”的意思&#xff0c;暗合“裸金属”之意&#xff0c;代表了R…
阅读更多...
MySQL-视图、存储过程、触发器

MySQL-视图、存储过程、触发器

目录视图创建视图查询视图修改视图删除视图视图检查选项视图更新作用存储过程特点基本语法创建调用查看删除变量系统变量查看系统变量设置系统变量注意点用户自定义变量复制使用注意局部变量声明赋值IF语句参数用法&#xff1a;IN 案例&#xff1a;OUT案例&#xff1a;INOUTCAS…
阅读更多...
《MySQL学习》 索引失效的三种特殊情况

《MySQL学习》 索引失效的三种特殊情况

一.条件字段使用函数 explain select * from bpm_proc_instance bpi where CREATED_AT > 2022-06-01 CREATED_AT 字段建立了索引&#xff0c;此时explain分析的结果表明能使用到索引 但如果我们对 CREATED_AT 字段使用函数 explain select * from bpm_proc_instance bpi w…
阅读更多...
【Python】3.3实现多线程

【Python】3.3实现多线程

程序Program进程Process线程Thread为完成特定任务而用计算机语言编写的一组计算机能识别和执行的指令的集合。程序是指令、数据及其组织形式的描述&#xff0c;一段静态代码&#xff0c;静态对象。计算机中的程序关于某数据集合上的一次执行过程。进程是程序的实体&#xff0c;…
阅读更多...
亿级高并发电商项目-- 实战篇 --万达商城项目 十三（编写购物车、优化修改商品、下架商品方法、购物车模块监听修改商品、删除商品消息）

亿级高并发电商项目-- 实战篇 --万达商城项目 十三（编写购物车、优化修改商品、下架商品方法、购物车模块监听修改商品、删除商品消息）

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是小童&#xff0c;Java开发工程师&#xff0c;CSDN博客博主&#xff0c;Java领域新星创作者 &#x1f4d5;系列专栏&#xff1a;前端、Java、Java中间件大全、微信小程序、微信支付、若依框架、Spring全家桶 &#x1f4…
阅读更多...
确定进制

确定进制

题目描述6*9 42 对于十进制来说是错误的&#xff0c;但是对于13进制来说是正确的。即, 6(13) * 9(13) 42(13)&#xff0c; 而 42(13) 4 * 131 2 * 130 54(10)。 你的任务是写一段程序读入三个整数p、q和 r&#xff0c;然后确定一个进制 B(2<B<16) 使得 p * q r. 如果…
阅读更多...
最新文章

Copyright @ 2022~2023