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

  • 阿里云国际版折扣https://www.yundadi.com

    • 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

     

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

    目录

    一.链表的概念和结构

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

    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;
}

    八.单链表的一些问题

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

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

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

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

    🤖🐯谢谢你的阅读~👻🦁

     

  • 阿里云国际版折扣https://www.yundadi.com

    • 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
    返回列表

    上一篇：【C++】哈希——unordered系列容器|哈希冲突|闭散列|开散列

    下一篇：Spring Cloud Alibaba全家桶（三）——微服务负载均衡器Ribbon与LoadBalancer

    “【数据结构与算法】单链表的增删查改（附源码）” 的相关文章

    spark读取数据写入hive数据表1年前 (2023-02-02)
    [一句话说iOS]dispatch如何造成死锁1年前 (2023-02-02)
    Vue 快速入门(一)1年前 (2023-02-02)
    微信小程序 | 小程序系统API调用_微信小程序api调用1年前 (2023-02-02)
    FreeRTOS(教程非常详细）1年前 (2023-02-02)
    引子1年前 (2023-02-02)
    AX9000安装使用Docker1年前 (2023-02-02)
    微信小程序介绍1年前 (2023-02-02)
    学习ASP.NET Core Blazor编程系列二十三——登录（2） 1年前 (2023-02-02)
    最全车牌识别，支持14种中文车牌类型1年前 (2023-02-02)

    阿里云国际版