单链表—C语言实现数据结构

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

本期带大家一起用C语言实现单链表🌈🌈🌈

单链表—C语言实现数据结构

一、链表的概念🌎

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的;简单来说,线性表的链式存储结构生成的表,称作“链表”。

二、链表中数据元素的构成🌎 🌍

每个元素本身由两部分组成:

1、本身的信息,称为“数据域”

2、指向直接后继的指针,称为“指针域”

三、链表的结构🌎 🌍 🌏

1、带哨兵位或者不带哨兵位 🦴

单链表—C语言实现数据结构

2、循环或者不循环 🦴 🦴

单链表—C语言实现数据结构

3、单向或者双向 🦴 🦴 🦴
单链表—C语言实现数据结构

单链表—C语言实现数据结构

但是我们常用的链表主要是单链表带头双向循环链表,一个结构最简单,一个结构最复杂。

下面简单介绍一下两个链表的特性(补充说明)

无头单向非循环链表:也就是我们俗称的单链表。其结构简单,一般不会单独用来存储数据。实际上更多是作为其他数据结构的子结构,如哈希桶、栈的链式结构等。因为单链表本身有缺陷,所以为常见的考核点之一。

带头双向循环链表:结构最复杂,一般用来单独存储数据。实际使用的链表,大多都是带头双向循环链表。虽然这种链表结构最复杂,但是其实有很多优势,并且在一定程度上对单链表的缺陷做出了一定的纠正。

而我们本篇博客就是对结构最简单的 单链表 进行讲解并实现
也是为了和带头双向循环链表做个对比

对于带头双向循环链表的话,之前以前我们已经总结过了,感兴趣的小伙伴可以在下面的链接当中查看
带头双向循环链表

四、 单链表的实现✅✅

单链表的结构为
存储的有效数据data
指向后一个数据地址的指针next

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

这里我们使用typedef对我们所存储的数据,以及单链表结构体重命名,方便我们后续修改 🍊 🍋 🍒

链表的一开始是空的。所以我们插入数据时,需要让plist指向我们新节点。就相当于改变plist的指向。plist是一级指针,那么要改变plist就要传它的地址&plist,为二级指针,所以也需要用二级指针来接收该参数。

二、接口的实现✅✅

1.单链表的创建以及初始化

我们插入数据,都需要创建节点。因为链表是按需分配的,创建即用。如果使用局部变量的话,那么在函数调用结束后节点就销毁了,那么肯定就需要使用动态内存开辟新的节点:

SLTNode* CreatSLTnode(SLTDataType x)
{

	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc:fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;

}

1.单链表的尾插

从尾部插入数据,需要分两种情况考虑:链表为空链表有节点

如果链表为空,那么就需要创建节点,并且将创建的节点赋给原链表;
如果链表不为空,则需要找到链表的尾部,然后将新节点到尾部的后面链接就可以

单链表—C语言实现数据结构

void SLTPushBack(SLTNode**pphead, SLTDataType x)
{
	SLTNode* newnode=CreatSLTnode(x);

	SLTNode* tail = *pphead;
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

2.单链表的头插

我们直接创建新节点,并且将新节点的 next 链接为原来的头,然后将头变为新节点,就可以了
因为就头插来说,如果链表为空,那么头部也为空,所以可以直接链接起来

单链表—C语言实现数据结构

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{

	SLTNode* newnode = CreatSLTnode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
3.单链表的尾删

尾删需要判断链表是否为空,并且需要将链表中 节点数 为单个节点和多个节点的情况分开讨论。

如果是单个节点删除,那么只需要释放节点,将节点置空

如果是两个及以上节点删除,尾删需要将删除元素的前一个链接为空指针,需要删除尾结点,而完成这两个步骤的方法就是遍历单链表,通过条件来求出这两个位置。找到这两个位置后,释放尾结点,将尾结点的前一个位置的next置空
单链表—C语言实现数据结构

void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next==NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;

	}
}

需要注意的是我们的循环终止条件不能写成tail->next!=NULL,在没有指向前一个节点的时候
当我们写成tail->next!=NULL时候,跳出循环之后free(tail)的时候,销毁了这个节点并且将tail=NULL,但是其实没有起到作用,我们通过调试看看
单链表—C语言实现数据结构
可以看到的是,没有起到真正的销毁,所以我们这里的循环条件还是要写成
tail->next->next!=NULL,然后再销毁节点

4.单链表的头删

对于空链表,直接断言判断就可以。

对于1个及以上节点,那么就是释放头结点,并且头结点的next设定为头。
单链表—C语言实现数据结构

void SLTPopFront(SLTNode** pphead)
{
	//空
	assert(*pphead);
	//一个节点
	//多个节点
	SLTNode* cur = *pphead;
	*pphead = cur->next;

	free(cur);
	cur = NULL;

}
5.单链表的查找

对于查找来说,相对比较简单。查找链表中某个元素是否存在,只需要遍历链表,查看里面是否有这个值
如果找到了,返回这个节点的地址
没找到,返回空指针

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* cur = phead;

	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

这里我将空链表定成不可以查找,其实空链表也可以查找,只不过是返回NULL而已

6. 删除pos位置的节点

删除pos位置的节点,需要考虑此时链表是否为空,但这只是一部分,只需要用断言处理一下就好。

而我们着重处理的为,头删和多个节点删除的情况。

如果是头删,那么删除的就是第一个节点,那么此时就需要将头变为pos->next,并且释放pos位置。头删情况也完美处理了单个节点删除时的情况。

如果是多个节点,那么就需要找到pos的前一个位置,将 pos 前一个位置prevnext 链接为我当前 pos 的 next。然后释放我的pos节点
单链表—C语言实现数据结构

void SLTPop(SLTNode** pphead, SLTNode* pos)
{
	
	assert(pphead);
	assert(*pphead);
	assert(pos);
	//只有一个节点
	if ((*pphead)->next == NULL)
	{
		*pphead = NULL;
		return;
	}
	if (pos->next == NULL)
	{
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
		return;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != pos)
			tail = tail->next;
		tail->next = pos->next;
		free(pos);
		pos = NULL;

	}

}
7. 在pos的位置插入

在pos的位置插入,这里我们需要遍历链表,然后在对此操作


void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = *pphead;
		*pphead = newnode;

	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = prev->next;
		prev->next = newnode;

	}

}

这里的来解释一下最后几行代码
当我们找到了pos节点之后,我们prev->next找到了pos节点
这时候我们创建的新节点newnode的next指向下一个节点prev->next
也就是指向pos节点
然后将prev->next赋值为newnode,也就是原来pos的位置现在变成了newnode

8. 在pos的位置之后插入

我只需要让 新节点newnode pos 位置的下一个节点链接,然后将pos位置的next变为我的新节点即可。

单链表—C语言实现数据结构

void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{

	assert(pphead);
	assert(pos);
	if (pos->next == NULL)
	{
		SLTNode* newnode = CreatSLTnode(x);
		pos->next = newnode;
	}
	else
	{

		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = pos->next;
		pos->next = newnode;
	}
}

其实这段代码还可以更加简单,不知道你发现没有
其实只需要就行
仔细体会一下

	SLTNode* newnode = CreatSLTnode(x);
		newnode->next = pos->next;
		pos->next = newnode;
9. 单链表的销毁

因为单链表是由不同地址的节点串联起来的。它不像数组,存储连续,只要释放起始位置。

如果我仅仅释放*pphead,那么只释放了我的第一个节点,后面的节点没释放,函数调用结束后,这些节点也找不到了。所以我们需要逐个销毁。

首先,使用 cur 拷贝头部位置。然后使用循环迭代。迭代过程中,需要记住我的 cur->next ,否则 cur 被释放后,无法找到下一个节点,然后逐个释放就可以了。

注意:当销毁后,记得把*pphead 置空`,防止销毁链表后对链表误操作而导致的野指针问题

单链表—C语言实现数据结构

void SLTDestroy(SLTNode** pphead)
{
	SLTNode* cur = *pphead;
	while (cur != NULL)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = NULL;
		cur = next;
	}
	*pphead = NULL;
}


10.单链表的打印

打印整个链表,只需要遍历链表,控制好循环的停止条件:

void SLTPrint(SLTNode* phead)
{

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

五、完整代码

SList.h

#pragma once

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

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


void SLTPrint(SLTNode* phead);

//尾插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushBack(SLTNode** pphead, SLTDataType x); 
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//销毁
void SLTDestroy(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead,SLTDataType x);
//在pos的位置插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos之后插入
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);

void SLTPop(SLTNode** pphead, SLTNode* pos);

SList.c

#define _CRT_SECURE_NO_WARNINGS


#include"Slist.h"

SLTNode* CreatSLTnode(SLTDataType x)
{

	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc:fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;

}

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{

	SLTNode* newnode = CreatSLTnode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void SLTPushBack(SLTNode**pphead, SLTDataType x)
{
	SLTNode* newnode=CreatSLTnode(x);

	SLTNode* tail = *pphead;
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}


}


void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next==NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next!= NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;

	}
}

void SLTPopFront(SLTNode** pphead)
{
	//空
	assert(*pphead);
	//一个节点
	//多个节点
	SLTNode* cur = *pphead;
	*pphead = cur->next;

	free(cur);
	cur = NULL;

}

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* cur = phead;

	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}


void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = *pphead;
		*pphead = newnode;

	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = prev->next;
		prev->next = newnode;

	}

}


void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{

	assert(pphead);
	assert(pos);
	if (pos->next == NULL)
	{
		SLTNode* newnode = CreatSLTnode(x);
		pos->next = newnode;
	}
	else
	{

		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = pos->next;
		pos->next = newnode;


	}


}


//删除pos位置的值
void SLTPop(SLTNode** pphead, SLTNode* pos)
{
	
	assert(pphead);
	assert(*pphead);
	assert(pos);
	//只有一个节点
	if ((*pphead)->next == NULL)
	{
		*pphead = NULL;
		return;
	}
	if (pos->next == NULL)
	{
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
		return;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != pos)
			tail = tail->next;
		tail->next = pos->next;
		free(pos);
		pos = NULL;

	}

}


void SLTPrint(SLTNode* phead)
{

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



void SLTDestroy(SLTNode** pphead)
{
	SLTNode* cur = *pphead;
	while (cur != NULL)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = NULL;
		cur = next;
	}
	*pphead = NULL;
}


test.c

#define _CRT_SECURE_NO_WARNINGS

#include"Slist.h"


int main()
{

    SLTNode* Slist = NULL;
    printf("原数据:");
    SLTPushBack(&Slist, 1);
    SLTPushBack(&Slist, 2);
    SLTPushBack(&Slist, 3);
    SLTPushBack(&Slist, 4);
    SLTPushBack(&Slist, 5);
    SLTPushBack(&Slist, 6);
    SLTPrint(Slist);

    printf("头插:");
    SLTPushFront(&Slist, 7);
    SLTPrint(Slist);

    printf("尾插:");
    SLTPushBack(&Slist, 8);
    SLTPrint(Slist);
    printf("头删:");
    SLTPopFront(&Slist);
    SLTPrint(Slist);
    printf("尾删:");
    SLTPopBack(&Slist);
    SLTPrint(Slist);
    printf("在pos的位置插入:");
    SLTNode* pos1 = SLTFind(Slist, 3);
    if (pos1!=NULL)
    {
        SLTInsert(&Slist, pos1, 20);
        SLTPrint(Slist);
    }


    printf("在pos的位置之后插入:");
    SLTNode* pos2 = SLTFind(Slist, 3);
    if (pos2 != NULL)
    {
        SLTInsertAfter(&Slist, pos1, 30);
        SLTPrint(Slist);
    }

    printf("删除指定位置:");
    SLTNode* pos3 = SLTFind(Slist, 3);
    if (pos3!= NULL)
    {
        SLTPop(&Slist, pos3);
        SLTPrint(Slist);
    }
    SLTDestroy(&Slist);
    return 0;

}

测试结果

单链表—C语言实现数据结构

六、感谢与交流✅

🌹🌹🌹如果大家通过本篇博客收获了,对顺序表有了新的了解的话
那么希望支持一下哦如果还有不明白的,疑惑的话,或者什么比较好的建议的话,可以发到评论区,
我们一起解决,共同进步 ❗️❗️❗️
最后谢谢大家❗️❗️❗️💯💯💯
文章来源地址https://www.toymoban.com/news/detail-465532.html

单链表—C语言实现数据结构

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

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

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

相关文章

  • 数据结构——单链表的实现(c语言版)

    前言           单链表作为顺序表的一种,了解并且熟悉它的结构对于我们学习更加复杂的数据结构是有一定意义的。虽然单链表有一定的缺陷,但是单链表也有它存在的价值, 它也是作为其他数据结构的一部分出现的,比如在图,哈希表中。 目录 1.链表节点的结构 2.头插

    2024年02月13日
    浏览(60)
  • 【算法与数据结构】 C语言实现单链表队列详解

    前面我们学习了队列的顺序表的实现,本节将用单链表实现队列。 队列也可以数组和链表的结构实现, 使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低 。下面我们先复习一下队列的基本概念: 队列:只允许在一端进行插入

    2024年04月11日
    浏览(60)
  • 【数据结构】单链表的增删查改(C语言实现)

    在上一节中我们提到了顺序表有如下缺陷: 在头部/中间的插入与删除需要挪动数据,时间复杂度为O(N),效率低; 增容需要申请新空间,可能会拷贝数据,释放旧空间,会有不小的消耗; 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容

    2024年02月06日
    浏览(62)
  • 【数据结构】C语言实现单链表的基本操作

    大家好,很高兴又和大家见面啦!!! 在上一篇中,我们详细介绍了单链表的两种创建方式——头插法与尾插法,相信大家现在对这两种方式都已经掌握了。今天咱们将继续介绍单链表的基本操作——查找、插入与删除。在开始今天的内容之前,我们先通过尾插法创建一个单

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

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

    2024年04月11日
    浏览(76)
  • Leetcode刷题---C语言实现初阶数据结构---单链表

    删除链表中等于给定值 val 的所有节点 给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [ ], val = 1 输出:[ ] 示例 3: 输入:head = [7,7,7,7], val = 7 输出:

    2024年02月15日
    浏览(56)
  • 数据结构——单链表(C语言)

    在这⼀条⼗分漫长的路上,我⾛过阳关⼤道,也⾛过独⽊⼩桥。路旁有深⼭⼤泽,也有平坡宜⼈;有杏花春⾬,也有塞北秋风;有⼭重⽔复,也有柳暗花明;有迷途知返,也有绝处逢⽣。——《⼋⼗述怀》 目录 一 . 什么是链表? 二 . 实现单链表 (1)创建相关源文件和头文

    2024年02月08日
    浏览(115)
  • 单链表(数据结构)(C语言)

    这里特指无哨兵位单向非循环链表 目录 背景 概念 单链表的实现 前景提示 单链表的结构体定义 单链表的打印 关于为什么不断言phead 关于单链表的逻辑结构和物理结构 单链表的尾插 关于为什么要用到二级指针 关于尾插的本质 关于找尾整个过程的解释 关于为什么打印单链表

    2023年04月22日
    浏览(77)
  • C语言:数据结构(单链表)

    概念:链表是一种 物理存储结构上非连续 、非顺序的存储结构,数据元素的 逻辑顺序 是通过链表的 指针链接 次序实现的。 链表的结构跟火车车厢相似,淡季时车次的车厢会相应减少,旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上,不会影响其

    2024年04月26日
    浏览(39)
  • 【C语言】数据结构-单链表

    主页:114514的代码大冒险 qq:2188956112(欢迎小伙伴呀hi✿(。◕ᴗ◕。)✿ ) Gitee:庄嘉豪 (zhuang-jiahaoxxx) - Gitee.com 文章目录 目录 文章目录 前言(链表的优势) 一、单链表是什么 二、单链表操作的具体代码实现 1.准备工作 2.打印链表 2.尾插(在链表末端添加数据) 3、头插(

    2024年02月02日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包