C语言实现链表--数据结构

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

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

    在这里插入图片描述

    • 魔王的介绍‍️一名双非本科大一小白。
    • 魔王的目标努力赶上周围卷王的脚步。
    • 魔王的主页大魔王.
      请添加图片描述
      ❤️‍大魔王与你分享很喜欢宫崎骏说的一句话:“不要轻易去依赖一个人,它会成为你的习惯当分别来临,你失去的不是某个人而是你精神的支柱,无论何时何地,都要学会独立行走,它会让你走得更坦然些。”

    文章目录

    一、前言

    本篇讲述的是八种链表中面试和刷题中最容易出现的链表–无头单向不循环链表过几天也会出一个性能最好的链表–有头双向循环链表希望能够帮助你。

    • 下面的链表都是针对无头单向不循环这钟来说的。

    链表是线性表的一种它与顺序表不同的是它在内存中并不是连续存储而是一个节点对应一个位置前一个结点存着下一个结点的地址从而产生了联系。如图

    在这里插入图片描述

    二、链表实现

    1、创建结构体类型

    如图所示链表和顺序表的不同之处链表每个元素都是一个结点是一个整体既包含该位置的数值又包含下一个位置的地址但它不用像顺序表一样去记住有几个元素因为它不是连续存放的所以这样做根本没有任何意义。因此虽然顺序表和链表都用到了结构体但他们是完全不同的意思。

    代码

    typedef int SListDateType;

typedef struct SeqListNode
{
	SListDateType date;
	struct SeqListNode* next;
}SListNode;

    2、创建结点

    每次增加数据我们都需要调用创建新结点这个函数它的目的是在堆区开辟一个结点的内存空间然后把我们新建数据的值赋上去至于地址我们在创建时并不知道赋什么所以先置空最后返回新建的结构体指针。

    代码

    //创建新结点。
SListNode* BuyNewnode(SListDateType x)
{
	SListNode* newnode = malloc(sizeof(SListNode));
	assert(newnode);
	newnode->date = x;
	newnode->next = NULL;
	return newnode;
}

    3、打印单链表

    单链表的打印就是从第一个打印直到最后一个怎么判断是否结束那就是最后一个结点指向的是NULL。

    代码

    //打印单链表。
void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	while (cur)
	{
		printf("%d->",cur->date);
		cur = cur->next;
	}
	printf("NULL\n");
}

    4、单链表尾插

    单链表尾插挺简单的就是先创建出来这个新节点然后让原链表最后结点指向新节点就ok了。

    //单链表尾插。
void SListPushBack(SListNode** pphead,SListDateType x)
{
	assert(pphead);

	SListNode* newnode = BuyNewnode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SListNode* cur = *pphead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

    5、单链表头插

    单链表头插意味着要改变传过来的结构体指针头指针我们知道形参只是实参的临时拷贝那么如何实现改变实参呢那就需要指针但是实参本来就是一级指针所以我们需要传二级指针也就是实参一级指针的地址这样才能实现修改。
    知道了上面这些那么剩下的就是让新节点地址赋给实参然后让新结点指向原来的头结点就好。

    代码

    //单链表头插。
void SListPushFront(SListNode** pphead, SListDateType x)
{
	assert(pphead);
	SListNode* newnode=BuyNewnode(x);
	newnode->next = *pphead;//先指向这个如果先弄下面一步就找不到原头节点的位置了。
	*pphead = newnode;//pphead是二级指针解引用后就是一级指针newnode也是一级指针然后让newnode赋给pphead这样就改变了实参。
}

    6、单链表尾删

    单链表尾删很简单就是把最后的结点释放倒数第二个结点便成了尾结点此时它指向的是已经释放的结点是野指针我们要让它置空他也应该置空因为尾结点要指向空不然之后用的时候程序不知道什么时候结束。
    我们需要首先判断是否只有一个因为只有一个的话那就要改变实参了释放这仅有的结点让实参的值置空。

    代码

    //单链表尾删。
void SListPopBack(SListNode** pphead)
{
	assert(pphead);

	assert(*pphead);//指针指向的内容不能是空的
	SListNode* cur = *pphead;
	SListNode* cur_ = NULL;//存倒数第二个结点的位置
	if (cur->next == NULL)
	{
		free(cur);
		*pphead = NULL;
		return;
	}
	while (cur->next)
	{
			cur_ = cur;//保留要释放结点的前一个位置然后当下面用完cur释放后让cur_释放后的最后结点位置指向空
			cur = cur->next;
	}
	free(cur);
	cur_->next = NULL;
}

    7、单链表头删

    单链表头删要让实参变为第二个结点的地址也就是说要改变实参所以还是要用二级指针。

    代码

    //单链表头删。
void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SListNode* first = *pphead;
	*pphead = (*pphead)->next;
	free(first);
}

    8、单链表查找

    当我们想在某个值后面插入元素时我们首先需要直到这个地方的地址我们才能进行操作。所以便有了查找函数实现原理就是逐个遍历出现就返回这个结点地址如果没出现就返回空指针。

    代码

    //单链表查找。
SListNode* SListFind(SListNode* phead, SListDateType x)
{
	assert(phead);//既然查找了那么就不能为空链表否则没有意义这是使用者的问题。
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->date == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;//上面已经判断不能为空链表所以这里返回的空指针指的就是找不到而不是链表为空。
}

    9、单链表插入

    单链表插入如果时从该位置之后插入很方便不需要遍历找上一个结点的位置直接用传过来的结点的位置进行操作。
    但是一般意义上的插入都是在该位置之前那么就需要遍历找到上一个位置的结点因为我们要用这是单链表的弊端。

    ☃️该位置之后插入

    代码

    //单链表插入(pos之后)。
void SListInsertAfter(SListNode* phead,SListNode* pos, SListDateType x)
{
	assert(pos);//插入默认是该链表不为空的如果想要空的时候插入用头插函数。
	SListNode* cur = phead;
	SListNode* newnode = BuyNewnode(x);
	while (cur!=pos)
	{
		cur = cur->next;
	}
	newnode->next = cur->next;
	cur->next = newnode;
}

    ☃️该位置之前插入插入正常理解

    //单链表插入(pos之前)。
void SListInsertBefore(SListNode** pphead, SListNode* pos, SListDateType x)
{
	assert(pphead);

	assert(*pphead);//和刚才同理链表没有元素的时候插入调用头插函数。
	SListNode* cur = *pphead;
	SListNode* newnode = BuyNewnode(x);
	if (cur->next == NULL)
	{
		*pphead = newnode;
		newnode->next = pos;
	}
	else
	{
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = newnode;
		newnode->next = pos;
	}
}

    10、单链表删除

    单链表删除需要找到前一个结点让前一个结点指想删除位置指向的位置然后释放要删除的位置即可。

    代码

    //单链表删除。
void SListEraseAfter(SListNode** pphead, SListNode* pos)
{
	assert(pphead);

	assert(*pphead);
	SListNode* cur = *pphead;
	if (cur == pos)
	{
		*pphead = pos->next;
		free(pos);
	}
	else
	{
		while (cur->next!=pos)
		{
			cur = cur->next;
		}
		cur->next = cur->next->next;//或者写成cur->next = pos->next;
		free(pos);
	}
}
    • 因为传的pos是一级指针所以我们无法在函数里修改pos的值我们只能修改pos指向位置的内容当我们释放pos后实参pos还指向释放后的位置也就变成了野指针所以我们需要在出函数后让pos置空。
      在这里插入图片描述

    11、单链表销毁

    单链表销毁就是释放每个结点的空间一直到最后结点注意别释放前没做准备导致释放后找不到下一个结点的位置。

    //单链表的销毁。
void SListDestroy(SListNode** pphead)
{
	assert(pphead);

	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* pc = cur;
		cur = cur->next;
		free(pc);
	}
}

    三、总代码

    SeqListNode.h

    SeqListNode.h

    #pragma once

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


typedef int SListDateType;

typedef struct SeqListNode
{
	SListDateType date;
	struct SeqListNode* next;
}SListNode;

//创建新结点。
SListNode* BuyNewnode(SListDateType x);

//打印单链表。
void SListPrint(SListNode* phead);

//单链表尾插。
void SListPushBack(SListNode** pphead,SListDateType x);

//单链表头插。
void SListPushFront(SListNode** pphead, SListDateType x);

//单链表尾删。
void SListPopBack(SListNode** pphead);

//单链表头删。
void SListPopFront(SListNode** pphead);

//单链表查找。
SListNode* SListFind(SListNode* phead, SListDateType x);

//单链表插入。
//pos之后插入。
//不用从头开始查找比较高效
void SListInsertAfter(SListNode* phead,SListNode* pos, SListDateType x);
//pos之前插入。
//还要从头开始查找不合适
void SListInsertBefore(SListNode** pphead, SListNode* pos, SListDateType x);

//单链表删除。
void SListEraseAfter(SListNode** pphead, SListNode* pos);

//单链表的销毁。
void SListDestroy(SListNode** phead);

    SeqListNode.c

    SeqListNode.c

    #define _CRT_SECURE_NO_WARNINGS 1

#include "SeqListNode.h"

//创建新结点。
SListNode* BuyNewnode(SListDateType x)
{
	SListNode* newnode = malloc(sizeof(SListNode));
	assert(newnode);
	newnode->date = x;
	newnode->next = NULL;
	return newnode;
}

//打印单链表。
void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	while (cur)
	{
		printf("%d->",cur->date);
		cur = cur->next;
	}
	printf("NULL\n");
}

//单链表尾插。
void SListPushBack(SListNode** pphead,SListDateType x)
{
	assert(pphead);

	SListNode* newnode = BuyNewnode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SListNode* cur = *pphead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

//单链表头插。
void SListPushFront(SListNode** pphead, SListDateType x)
{
	assert(pphead);

	SListNode* newnode=BuyNewnode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

//单链表尾删。
void SListPopBack(SListNode** pphead)
{
	assert(pphead);

	assert(*pphead);//指针指向的内容不能是空的
	SListNode* cur = *pphead;
	SListNode* cur_ = NULL;//存倒数第二个结点的位置
	if (cur->next == NULL)
	{
		free(cur);
		*pphead = NULL;
		return;
	}
	while (cur->next)
	{
			cur_ = cur;//保留要释放结点的前一个位置然后当下面用完cur释放后让cur_释放后的最后结点位置指向空
			cur = cur->next;
	}
	free(cur);
	cur_->next = NULL;
}

//单链表头删。
void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SListNode* first = *pphead;
	*pphead = (*pphead)->next;
	free(first);
}

//单链表查找。
SListNode* SListFind(SListNode* phead, SListDateType x)
{
	assert(phead);
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->date == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//单链表插入(pos之后)。
void SListInsertAfter(SListNode* phead,SListNode* pos, SListDateType x)
{
	assert(pos);
	SListNode* cur = phead;
	SListNode* newnode = BuyNewnode(x);
	while (cur!=pos)
	{
		cur = cur->next;
	}
	newnode->next = cur->next;
	cur->next = newnode;
}

//单链表插入(pos之前)。
void SListInsertBefore(SListNode** pphead, SListNode* pos, SListDateType x)
{
	assert(pphead);

	assert(*pphead);
	SListNode* cur = *pphead;
	SListNode* newnode = BuyNewnode(x);
	if (cur->next == NULL)
	{
		*pphead = newnode;
		newnode->next = pos;
	}
	else
	{
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = newnode;
		newnode->next = pos;
	}
}

//单链表删除。
void SListEraseAfter(SListNode** pphead, SListNode* pos)
{
	assert(pphead);

	assert(*pphead);
	SListNode* cur = *pphead;
	if (cur == pos)
	{
		*pphead = pos->next;
		free(pos);
	}
	else
	{
		while (cur->next!=pos)
		{
			cur = cur->next;
		}
		cur->next = cur->next->next;
		free(pos);
	}
}

//单链表的销毁。
void SListDestroy(SListNode** pphead)
{
	assert(pphead);

	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* pc = cur;
		cur = cur->next;
		free(pc);
	}
}

    Test.c

    Test.c

    #define _CRT_SECURE_NO_WARNINGS 1

#include "SeqListNode.h"

void test1()
{
	SListNode* pc = NULL;
	SListPrint(pc);

	SListPushBack(&pc,0);
	SListPrint(pc);

	SListPushBack(&pc, 1);
	SListPrint(pc);

	SListPushBack(&pc, 2);
	SListPrint(pc);

	SListPushBack(&pc, 3);
	SListPrint(pc);

	SListPushBack(&pc, 4);
	SListPrint(pc);

	SListPushBack(&pc, 5);
	SListPrint(pc);

	SListPushBack(&pc, 6);
	SListPrint(pc);

	SListPushBack(&pc, 7);
	SListPrint(pc);
}

void test2()
{
	SListNode* pc = NULL;
	SListPrint(pc);

	SListPushFront(&pc, 0);
	SListPrint(pc);

	SListPushFront(&pc, 1);
	SListPrint(pc);

	SListPushFront(&pc, 2);
	SListPrint(pc);

	SListPushFront(&pc, 3);
	SListPrint(pc);

	SListPushFront(&pc, 4);
	SListPrint(pc);

	SListPushFront(&pc, 5);
	SListPrint(pc);

	SListPushFront(&pc, 6);
	SListPrint(pc);

	SListPushFront(&pc, 7);
	SListPrint(pc);
}
void test3()
{
	SListNode* pc = NULL;
	SListPrint(pc);

	SListPushBack(&pc, 0);
	SListPrint(pc);

	SListPushBack(&pc, 1);
	SListPrint(pc);

	SListPushBack(&pc, 2);
	SListPrint(pc);

	SListPushBack(&pc, 3);
	SListPrint(pc);

	SListPopBack(&pc);
	SListPrint(pc);

	SListPopBack(&pc);
	SListPrint(pc);

	SListPopBack(&pc);
	SListPrint(pc);

	SListPopBack(&pc);
	SListPrint(pc);
}
void test4()
{
	SListNode* pc = NULL;
	SListPrint(pc);

	SListPushBack(&pc,0);
	SListPrint(pc);

	SListPushBack(&pc, 1);
	SListPrint(pc);

	SListPushBack(&pc, 2);
	SListPrint(pc);

	SListPushBack(&pc, 3);
	SListPrint(pc);

	SListPushBack(&pc, 4);
	SListPrint(pc);

	SListPushBack(&pc, 5);
	SListPrint(pc);

	SListPushBack(&pc, 6);
	SListPrint(pc);

	SListPopFront(&pc);
	SListPrint(pc);

	SListPopFront(&pc);
	SListPrint(pc);

	SListPopFront(&pc);
	SListPrint(pc);

	SListPopFront(&pc);
	SListPrint(pc);

	SListPopFront(&pc);
	SListPrint(pc);

	SListPopFront(&pc);
	SListPrint(pc);
}
void test5()
{
	SListNode* pc = NULL;
	SListPushBack(&pc,0);
	//SListPushBack(&pc,1);
	//SListPushBack(&pc,2);
	SListPrint(pc);
	SListNode* pos = SListFind(pc,0);
	assert(pos);
	//SListInsertAfter(*pc, pos, 9);//pos之后插入。
	SListInsertBefore(&pc, pos, 5);//pos之前插入。
	SListPrint(pc);
	pos = SListFind(pc, 5);
	SListEraseAfter(&pc, pos);//删除后要置空
	pos = NULL;//这块被释放了所以置空
	SListPrint(pc);
	SListDestroy(&pc);
}

int main()
{
	//test1();//测试尾插。
	//test2();//测试头插。
	test3();//测试尾删。
	//test4();//测试头删。
	//test5();//测试查找,插入,销毁。
	return 0;
}

    四、总结

    在这里插入图片描述

    ✨请点击下面进入主页关注大魔王
    如果感觉对你有用的话就点我进入主页关注我吧

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

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

    上一篇：多元线性回归的系数及其标准差估计

    下一篇：DETR详解

    “C语言实现链表--数据结构” 的相关文章

    Leetcode：343. 整数拆分（C++）2年前 (2023-02-02)
    初识Python2年前 (2023-02-02)
    kubernetes核心概念 Service2年前 (2023-02-02)
    共享模型之内存(一)2年前 (2023-02-02)
    PowerCLi 批量多esxi主机创建登陆用户2年前 (2023-02-02)
    dotnet 警惕使用 StackTrace 加获取方法标记 Attribute 特性在 Release 下被内联2年前 (2023-02-02)
    京东云开发者｜关于“React 和 Vue 该用哪个”我真的栓Q2年前 (2023-02-02)
    数字化“乡村小道”跑得不舒服,试试低代码“高速公路”2年前 (2023-02-02)
    【Dubbo3终极特性】「云原生三中心架构」带你探索Dubbo3体系下的配置中心和元数据中心、注册中心的原理及开发实战（上）2年前 (2023-02-02)
    洛谷 P1208混合牛奶 题解2年前 (2023-02-02)

    阿里云国际版