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

这篇具有很好参考价值的文章主要介绍了C语言实现链表--数据结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

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

一、前言

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

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

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

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

二、链表实现

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置空。
    C语言实现链表--数据结构

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

四、总结

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

✨请点击下面进入主页关注大魔王
如果感觉对你有用的话,就点我进入主页关注我吧!文章来源地址https://www.toymoban.com/news/detail-434327.html

到了这里,关于C语言实现链表--数据结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】—C语言实现双向链表(超详细!)

                                          食用指南:本文在有C基础的情况下食用更佳                                       🔥 这就不得不推荐此专栏了:C语言                                     🍀 双向链表 前 置知识 :单链表      

    2024年02月13日
    浏览(50)
  • 【数据结构】C语言实现双向链表(带头结点、循环)

    结点定义: 接口定义: 我们将申请结点的代码封装成函数,方便后续使用 由于是带头结点的双向链表,因此在使用链表前,我们需要对链表进行初始化。 遍历链表,值得说的是,带头结点的双向链表的循环结束条件是 cur != phead 尾插时,需要先找到尾结点,然后将新结点插

    2024年02月03日
    浏览(72)
  • 【数据结构】链表OJ题(顺序表)(C语言实现)

    ✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ 🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿 🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟 🌟🌟 追风赶月莫停留 🌟🌟 🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀 🌟🌟 平芜尽处是春山

    2024年02月05日
    浏览(46)
  • (c语言实现)数据结构链表oj题(2)

    🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨ 🐻推荐专栏: 🍔🍟🌯C语言进阶 🔑个人信条: 🌵知行合一 🍉本篇简介::分析力扣中有关链表的部分题目. 题目来源于:牛客网-题目链接 输入一个链表,输出该链表中倒数第k个结点。 示例: 输入:1,{1,2,3,4,5} 返回值:{5} 创建两个指针: ①

    2024年02月04日
    浏览(55)
  • c语言数据结构——链表的实现及其基本操作

    顺序表的问题及思考 问题: 中间/头部的插入删除,时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有数据插

    2023年04月09日
    浏览(85)
  • [C语言][数据结构][链表] 双链表的从零实现!

    目录 零.必备知识 0.1 一级指针 二级指针 0.2 双链表节点的成员列表         a. 数据         b. 后驱指针         c. 前驱指针 0.3 动态内存空间的开辟 一. 双链表的实现与销毁         1.1 节点的定义         1.2 双向链表的初始化 创建新节点         1.3 尾插       

    2024年04月17日
    浏览(245)
  • [C语言][数据结构][链表] 单链表的从零实现!

    目录 零.必备知识 1.一级指针 二级指针 2. 节点的成员列表     a.数据     b.指向下一个节点的指针. 3. 动态内存空间的开辟 (malloc-calloc-realloc) 一.单链表的实现与销毁          1.1 节点的定义         1.2 单链表的尾插         1.3 单链表的头插         1.4 单链表的尾删  

    2024年04月11日
    浏览(76)
  • c语言数据结构实验:链表实现学生信息的储存

    进入正题 本文作者同为大一新生,写这篇文章的目的是记录自己的学习经历,以及帮助一些稍有困难的同学理解数据结构,能力有限,如有错误请指出。本文基于严蔚敏老师的《数据结构与算法(c语言版 第二版)》创作。(建议学习的时候搭配着书看) 学习前提 : 1.本文

    2024年02月03日
    浏览(42)
  • 【数据结构初阶】四、线性表里的链表(带头+双向+循环 链表 -- C语言实现)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】三、 线性表里的链表(无头+单向+非循环链表 -- C语言实现)-CSDN博客  ====

    2024年02月08日
    浏览(45)
  • 顺序表和链表【数据结构】【基于C语言实现】【一站式速通】

    目录 顺序表 顺序表的优点 顺序表的实现 1.结构体的定义 2.初始化数组  3.插入数据 4.其余接口函数的实现 5.释放内存 顺序表的缺陷 单向链表 单向链表的优点 单向链表的实现 1.链表的定义  2.链表的初始化 3.其余接口函数的实现 5.释放内存 单向链表的缺陷 双向链表 双向链

    2024年01月24日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包