单向链表——C语言实现

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

哈喽,大家好,今天我们学习的是数据结构里的链表,这里主要讲的是不带哨兵卫头节点的单向链表,下篇将会继续带大家学习双向链表。

目录

1.链表的概念

2.单向链表接口的实现

2.1动态申请一个节点

2.2单链表打印

2.3单链表尾插

2.4单链表头插

2.5单链表尾删

2.6单链表头删

2.7在pos位置插入x

2.7.1在pos位置前插入x

2.7.2在pos位置后插入x

2.8删除pos位置值

2.9 查找x的地址

2.10销毁链表

3.完整代码


1.链表的概念

在上篇文章,我们已经学习了顺序表,不知大家有没有发现顺序表在一定程度上是存在缺陷的,比如说:

  1. 空间不够了的时候需要扩容,扩容需要付出代价(特别是异地扩空间)
  2. 为了避免频繁扩容,我们满了基本都是扩2倍,可能会导致一定的空间浪费
  3. 顺序表要求数据从开始位置连续存储,那么我们在头部或者中间位置插入删除数据就需要挪动数据,效率不高

针对顺序表的缺陷,就有了链表来存储数据

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

单向链表——C语言实现

 链表的定义:

单向链表——C语言实现

 这里的data就是要存放的数据

2.单向链表接口的实现

下面是要介绍的常用到的链表接口函数以及实现方法:

//打印
void SListPrint(SLTNode* phead);
//创建新节点
SLTNode* BuyListNode(SLTDateType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x);
//头插
void SListPushFront(SLTNode** pphead, SLTDateType x);
//头删
void SListPopBack(SLTNode** pphead);
//尾删
void SListPopFront(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x);
//插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);
//删除
void SListErase(SLTNode** pphead, SLTNode* pos);
//销毁
void SListDestroy(SLTNode** pphead);

2.1动态申请一个节点

由于我们每次给链表插入数据时,都需要动态开辟空间来申请节点,所以我们把这个过程封装成一个函数,方便后续操作。

动态申请一个节点的步骤是先向计算机内存申请一块空间,这里我们将申请的空间用指针变量newnode来存储,然后将newnode中的data赋值,因为这是新开辟的节点,所以暂时将newnode中的next指向空。

注意:为了提高程序的可靠性,我们在动态内存申请后记得检查是否申请失败了,如果申请失败了输出提示信息,并退出程序。

SLTNode* BuyListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)//如果动态内存申请失败就退出程序
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

2.2单链表打印

打印链表就是一个遍历链表的过程,我们首先定义一个指针(cur)指向链表的头节点,然后输出该节点的值,然后将指针指向下一个节点(cur=cur->next),依次进行,直到cur为空指针时停止

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;//将cur指向下一个节点
	}
	printf("NULL\n");
}

2.3单链表尾插

尾插,就是先找到链表中最后一个节点,然后将数据插入到最后。

但是,我们要先判断链表是否为空,如果链表为空,我们直接直接将链表的头指针赋予要插入的数据。

由于尾插要改变链表,所以传参要用二级指针,包括下面的尾插,尾删,头删等都要用二级指针传参

单向链表——C语言实现

void SListPushBack(SLTNode** pphead, SLTDateType x)
{
	SLTNode* newnode = BuyListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

2.4单链表头插

头插是比较简单的一种操作,只需要申请新节点,将新节点的next指向链表的头,再让新节点成为链表的头即可。

单向链表——C语言实现

void SListPushFront(SLTNode** pphead, SLTDateType x)
{
	SLTNode* newnode = BuyListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

2.5单链表尾删

尾删:每次找到链表的最后一个节点和倒数第二个节点,然后释放最后一个节点所占的看空间并将最后一个节点置空,同时将倒数第二个节点的next指向NULL;如果链表只剩下一个节点,直接释放并置空该节点(这一步需要单独考虑)

注意:为了避免链表为空但有调用尾删的情况,我们需要断言一下,当传过来的链表是空链表的时候,程序就会报错

单向链表——C语言实现

void SListPopBack(SLTNode** pphead)
{
	//保证链表不是空链表
	assert(*pphead != NULL);
	if ((*pphead)->next == NULL)
	{
		//当链表中只有一个节点
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* prev = NULL;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		prev->next = NULL;
		free(tail);
		tail = NULL;
	}
}

2.6单链表头删

头删是将第一个节点释放然后指向第二个节点,在此之前需要定义一个指针next来保存第二个节点的地址。

单向链表——C语言实现

void SListPopFront(SLTNode** pphead)
{
	//保证链表不是空链表
	assert(*pphead != NULL);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

2.7在pos位置插入x

在pos位置插入x分为两种情况,一种是在pos前位置插入x ,另一种是在pos后位置插入x,下面将分别为大家介绍:

2.7.1在pos位置前插入x

在pos位置前插入x,只需要找到pos的前一个位置,我们把pos的前一个位置命名为posPrev,然后创建一个新节点newnode,将posPrev的下一个节点指向newnodenewnode的下一个节点指向pos即可,如下图:

单向链表——C语言实现

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(pphead != NULL);
	assert(pos != NULL);

	SLTNode* newnode = BuyListNode(x);
	if (*pphead == pos)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		//找到pos的前一个位置
		SLTNode* posPrev = *pphead;
		while (posPrev->next != pos)
		{
			posPrev = posPrev->next;
		}
		posPrev->next = newnode;
		newnode->next = pos;
	}
}

2.7.2在pos位置后插入x

在pos位置后插入x比在pos位置前插入x要简单,不需要遍历链表即可完成

void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
    assert(pos != NULL);
    SLTNode* newnode = BuyListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

2.8删除pos位置值

删除pos位置值也需要先找到pos的前一个节点,因此也要考虑pos是链表的头节点的情况

单向链表——C语言实现

void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(*pphead != NULL);
	assert(pos != NULL);
	if (*pphead == pos)
	{
		*pphead = pos->next;
		free(pos);
	}
	else
	{
		SLTNode* posPrev = *pphead;
		while (posPrev->next != pos)
		{
			posPrev = posPrev->next;
		}
		posPrev->next = pos->next;
		free(pos);
	}
}

2.9 查找x的地址

查找x的地址,如果查找到了x,则返回该节点的地址,否则返回空指针。这个步骤也要遍历链表。

SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
	SLTNode* tail = phead;
	if (tail->data == x)
	{
		return tail;
	}
	while (tail ->data != x)
	{
		tail = tail->next;
		if (tail->data == x)
		{
			return tail;
		}
	}
	return NULL;
}

2.10销毁链表

销毁链表需要将所有节点所占的内存全部释放,再将链表的头置为空即可。

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

3.完整代码

SList.h文件:

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

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;//存放下一个链表的地址
}SLTNode;

//打印
void SListPrint(SLTNode* phead);
//创建新节点
SLTNode* BuyListNode(SLTDateType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x);
//头插
void SListPushFront(SLTNode** pphead, SLTDateType x);
//头删
void SListPopBack(SLTNode** pphead);
//尾删
void SListPopFront(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x);
//插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);
//删除
void SListErase(SLTNode** pphead, SLTNode* pos);
//销毁
void SListDestroy(SLTNode** pphead);

SList.c文件:

#include"SList.h"

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;//将cur指向下一个节点
	}
	printf("NULL\n");
}

SLTNode* BuyListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)//如果动态内存申请失败就退出程序
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

void SListPushBack(SLTNode** pphead, SLTDateType x)
{
	SLTNode* newnode = BuyListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

void SListPushFront(SLTNode** pphead, SLTDateType x)
{
	SLTNode* newnode = BuyListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void SListPopBack(SLTNode** pphead)
{
	//保证链表不是空链表
	assert(*pphead != NULL);
	if ((*pphead)->next == NULL)
	{
		//当链表中只有一个节点
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* prev = NULL;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		prev->next = NULL;
		free(tail);
		tail = NULL;
	}
}


void SListPopFront(SLTNode** pphead)
{
	//保证链表不是空链表
	assert(*pphead != NULL);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
	SLTNode* tail = phead;
	if (tail->data == x)
	{
		return tail;
	}
	while (tail ->data != x)
	{
		tail = tail->next;
		if (tail->data == x)
		{
			return tail;
		}
	}
	return NULL;
}

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(pphead != NULL);
	assert(pos != NULL);

	SLTNode* newnode = BuyListNode(x);
	if (*pphead == pos)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		//找到pos的前一个位置
		SLTNode* posPrev = *pphead;
		while (posPrev->next != pos)
		{
			posPrev = posPrev->next;
		}
		posPrev->next = newnode;
		newnode->next = pos;
	}
}

void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(pos != NULL);
	SLTNode* newnode = BuyListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(*pphead != NULL);
	assert(pos != NULL);
	if (*pphead == pos)
	{
		*pphead = pos->next;
		free(pos);
	}
	else
	{
		SLTNode* posPrev = *pphead;
		while (posPrev->next != pos)
		{
			posPrev = posPrev->next;
		}
		posPrev->next = pos->next;
		free(pos);
	}
}

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

总结:这篇文章主要写的是单向链表,后续将继续带领大家学习双向链表。如果我写的有什么的不好之处,请在文章下方给出你宝贵的意见。如果觉得我写的好的话请点个赞赞和关注哦~😘文章来源地址https://www.toymoban.com/news/detail-438989.html

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

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

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

相关文章

  • 数据结构——单向链表(C语言版)

    在数据结构和算法中,链表是一种常见的数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。在C语言中,我们可以使用指针来实现单向链表。下面将详细介绍如何用C语言实现单向链表。 目录 1. 定义节点结构体 2. 初始化链表 3. 插入节点 4. 删除节点

    2024年03月24日
    浏览(43)
  • C语言单向链表的增删操作

    2024年04月23日
    浏览(48)
  • 数据结构:详解【链表】的实现(单向链表+双向链表)

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

    2024年03月26日
    浏览(65)
  • 【2023】华为OD机试真题全语言-题目0233-单向链表中间节点

    求单向链表中间的节点值,如果奇数个节点取中间,偶数个取偏右边的那个值。 第一行 链表头节点地址 后续输入的节点数 n n n 后续输入每行表示一个节点,格式 节点地址 节点值 下一个节点地址( -1 表示空指针) 输入保证链表不会出现环,并且可能存在一些节点不属于链表

    2024年02月05日
    浏览(39)
  • 数据结构——实现单向链表

    单链表是一种常见的数据结构,用于存储一系列的数据元素,每个节点包含数据和指向下一个节点的指针。 单链表通常用于实现某些算法或数据结构,如链式前向星、哈希表、链式栈、队列等等。 单链表在程序设计中的作用不可忽略,是很多基础算法的核心数据结构之一。

    2024年02月07日
    浏览(57)
  • 【数据结构】单向链表实现 超详细

    目录 一. 单链表的实现 1.准备工作及其注意事项 1.1 先创建三个文件 1.2 注意事项:帮助高效记忆和理解 2.链表的基本功能接口 2.0 创建一个 链表 2.1 链表的 打印  3.链表的创建新节点接口 4.链表的节点 插入 功能接口 4.1 尾插接口 4.2 头插接口     4.3 指定位置 pos 之前  插入

    2024年02月19日
    浏览(66)
  • 【数据结构和算法】使用数组的结构实现链表(单向或双向)

    上文我们通过结构体的结构实现了队列 、以及循环队列的实现,我们或许在其他老师的教学中,只学到了用结构体的形式来实现链表、队列、栈等数据结构,本文我想告诉你的是,我们 可以使用数组的结构实现链表、单调栈、单调队列 目录 前言 一、用数组结构的好处 1.数

    2024年01月20日
    浏览(74)
  • [Collection与数据结构] 链表与LinkedList (一):链表概述与单向无头非循环链表实现

    上篇文章我们已经对顺序表进行了实现,并且对ArrayList进行了使用,我们知道ArrayList底层是使用数组实现的. 由于其底层是一段连续空间,当在ArrayList任意位置插入或者删除元素时, 就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低 ,因此ArrayList不适合做

    2024年04月26日
    浏览(64)
  • 【数据结构】单向链表

    哈喽,大家好,今天我们学习的是数据结构里的链表,这里主要讲的是不带哨兵卫头节点的单向链表,下篇将会继续带大家学习双向链表。 目录 1.链表的概念 2.单向链表接口的实现 2.1动态申请一个节点 2.2单链表打印 2.3单链表尾插 2.4单链表头插 2.5单链表尾删 2.6单链表头删

    2024年02月11日
    浏览(53)
  • 【算法】Java-使用数组模拟单向链表,双向链表

    目录 试题1:实现一个单链表,并实现以下功能: 试题2:实现一个双链表,并实现以下功能 思路总结: 什么情况下可能涉及到用数组实现链表呢?       在学习时了解到了可以用数组模拟链表,使其兼顾数据查找快,链表新增和删除快的缺点,找来一些试题实现了下,如下

    2024年02月09日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包