数据结构——单链表

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

数据结构——单链表

🐨0. 前言

  • 我们需要在程序中存储一系列的数据,这些数据不是一成不变的,需要满足随时的动态增删查改。
  • 顺序表,虽然能满足这些要求,可是顺序表在头插或者中间插入数据时,需要将数据一个一个挪动,效率较低;而且需要频繁的扩容,扩容也是需要付出一定的代价。
  • 为有效解决这些问题,数据结构中有一种链式存储,它不要求逻辑上相邻的元素在物理上也相邻,由此解决了顺序表的缺陷,但同时也失去了顺序表可随机存取的优点。

🌸1.链表的概念及结构

链表由一些节点组成,节点包含两个部分:数据域指针域

  • 数据域: 用来存储节点的数据。
  • 指针域: 指向下一个节点的地址。

链表可以分为单向链表双向链表循环链表等类型。本篇文章讲解的是单链表的实现。

🦖2. 单链表概念

单链表:每个节点只有一个指针域,指向下一个节点。链表的头结点是第一个节点,尾节点是最后一个节点,其指针域指向 NULL。
数据结构——单链表

🐳3.单链表接口声明

#pragma once

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

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;//存储的数据
	struct SListNode* next;//指向下一个节点
}SLTNode; 

//单链表打印
void SLTPrint(SLTNode* phead);

//尾插
void SLTPushBcak(SLTNode** pphead, SLTDateType x);

//头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);

//尾删
void SLTPopBack(SLTNode** pphead);

//头删
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x);

//pos之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);

//pos位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos);

//pos之后插入
void SLTInsertAfter(SLTNode* pos, SLTDateType x);

//pos位置后面删除
void SLTEraseAfter(SLTNode* pos);

🦋4. 接口实现

💐4.1 尾插与尾删

//买节点
SLTNode* BuySLTNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//尾插
void SLTPushBcak(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	//买
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	//只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;

	}
	else
	{
		//多个节点
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}

小贴士:

  • 这里在插入或删除数据的时候,防止第一个数据是空,所以传过来的是二级指针。第一个数据为空,我们需要改变的是结构体指针,更改指针,需要二级指针;如果不为空,我们只需改变结构体的内容,这里只是更改内容,所以用一级指针即可
  • 尾删时,如果链表本身就为空,那么无法继续删除,所以需要使用断言判断
    另外,prev是用来保存尾节点的前一个节点的指针,因为在删除尾节点之前需要找到尾节点的前一个节点,将其next指针置为NULL。如果不保存prev指针,将无法将尾节点的前一个节点的next指针置为NULL,从而导致删除操作失败或出现错误的节点连接。数据结构——单链表

💐4.2 头插与头删

//头插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

💐4.3 查找与修改

查找其实就意味着修改,既然能找到这个值,那也就代表着可以将其内容修改。

//查找or修改
SLTNode* SLTFind(SLTNode* phead, SLTDateType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;

		cur = cur->next;
	}
	return NULL;
}

💐4.4 pos位置前(后)插入

数据结构——单链表

//pos之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(pos);
	assert(pphead);
	if (pos == *pphead)
	{
		//头插
		SLTPushFront(&pos, x);
	}
	else
	{
		//找pos前一个位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

//pos之后插入
void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

💐4.5 pos位置(后面)删除

数据结构——单链表

//pos位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	assert(*pphead);
	if (pos == *pphead)
	{
		SLTPopFront(&pos);
	}
	else
	{
		//找pos前一个位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		//形参改变不影响实参
		//pos = NULL;
	}
}

//pos位置后面删除
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

💐4.6 关于断言的使用

我们发现有些位置断言有些位置不用,这其实很好理解:文章来源地址https://www.toymoban.com/news/detail-416597.html

  1. 打印或者查找链表时,不管是不是空链表,都可以进行,所以不需要断言。
  2. 进行插入的时候,空链表也是可以的;但是链表的地址,必定不能为空,所以这里必定不能为空,这防止我们在传入的时候出错。
  3. 删除也同理,空链表是不能进行删除的,所以需要对链表断言判断是否为空。

🌻5. 接口测试

#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:6031)
#include"SList.h"
void TestSList1()
{
	//尾插测试
	//SLTNode s = { 1,NULL };
	//SLTNode* plist = &s;
	SLTPushBcak(&plist, 1);
	plist->data = 1;
	plist->next = NULL;
	//SLTPushBcak(plist, 2);
	//SLTPushBcak(plist, 3);
	//SLTPushBcak(plist, 4);
	//SLTPrint(plist);
	SLTNode* plist = NULL;
	SLTPushBcak(&plist, 1);
	SLTPushBcak(&plist, 2);
	SLTPushBcak(&plist, 3);
	SLTPushBcak(&plist, 4);
	SLTPrint(plist);

	//头插测试
	/*SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 1);
	SLTPrint(plist);*/

	//尾删测试
	/*SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);*/

	//头删测试
	/*SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);*/

	//查找测试
	SLTNode* ret = SLTFind(plist, 2);
	ret->data *= 2;
	SLTPrint(plist);

	//pos前插入测试
	SLTInsert(&plist, ret, 9);
	SLTPrint(plist);

	//pos位置删除测试
	/*SLTErase(&plist, ret);
	ret = NULL;
	SLTPrint(plist);*/

	//pos位置之后插入测试
	SLTInsertAfter(ret, 10);
	SLTPrint(plist);

	//pos位置后面删除
	SLTNode* a = ret->next;
	SLTEraseAfter(ret);
	SLTPrint(plist);
}

int main()
{
	TestSList1();
	return 0;
}

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

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

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

相关文章

  • 【数据结构】单链表详解

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

    2024年02月09日
    浏览(35)
  • 数据结构——单链表(上)

    🌇个人主页:_麦麦_ 📚今日名言:“生活总是让我们遍体鳞伤,但到后来,那些受伤的地方一定会变成我们最强壮的地方。”        ——海明威《永别了武器》 目录 ​编辑 一、前言 二、正言  3.1链表的概念及结构 3.2链表的分类 3.3链表的实现【无头单向非循环】 3.

    2024年02月02日
    浏览(41)
  • 数据结构入门——单链表

    目录 前言 链表的定义 链表的创建 头插法创建链表 尾插法创建链表 链表的删除 在头部删除元素 在尾部删除元素 查找固定元素 在链表中插入元素 在pos位置前插入 在pos位置后插入 删除链表结点 删除pos位置的结点 删除pos后的结点 链表的销毁 写在最后 前面我们学习了顺序表

    2024年02月20日
    浏览(40)
  • 【数据结构】单链表(详解)

    所属专栏:初始数据结构 博主首页:初阳785 代码托管:chuyang785 感谢大家的支持,您的点赞和关注是对我最大的支持!!! 博主也会更加的努力,创作出更优质的博文!! 关注我,关注我,关注我,重要的事情说三遍!!!!!!!! 前面我们已经用顺序表方式来实现接口

    2023年04月24日
    浏览(53)
  • 【数据结构】单链表(超全)

    前言:  上一次我们分享了线性表中的一种结构顺序表,它存在着一些其缺点,比如:在中间位置或者头部进行元素插入或者删除的时候时间复杂度是 O ( N ) O(N) O ( N ) 效率比较低,并且顺序表在扩容的时候也存在时间和空间上的消耗,由于我们每次都是按照二倍来扩的,那

    2024年02月11日
    浏览(41)
  • 数据结构--单链表

    目录 1.单链表的定义: 单链表基本操作的实现: 2.单链表的初始化(构造带头结点的空表) 2.将头结点的指针域置空 3.链表是否为空: 4.单链表的销毁: 5.单链表的清空: 6.求单链表的表长: 7.   取值  取单链表第i个元素: 8按值查找 根据指定数据查找指定数据所在位置序

    2024年02月15日
    浏览(42)
  • 数据结构单链表

    单链表 1 链表的概念及结构 概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 。 在我们开始讲链表之前,我们是写了顺序表,顺序表就是类似一个数组的东西,它的存放是连续的,优点有很多,比如支持

    2024年02月12日
    浏览(45)
  • 数据结构:单链表

    单链表的全称为\\\"不带头单向不循环链表\\\" 注意:         下文提到的头节点与带头链表时两个概念,文中的头节点指的是第一个有效节点,二带头节点中的头指的是第一个无效节点 链表和顺序表一样,都是线性表,逻辑结构上是线性的,但不同的是,链表在物理结构上不是线性的

    2024年01月21日
    浏览(41)
  • 数据结构—单链表

    目录 1.前言 2.了解单链表 3.单链表代码实现       3.1 单链表结构体实现       3.2 创建节点       3.3  打印单链表       3.4 尾插        3.5  头插        3. 6 头删       3.7  尾删       3.8  查找       3.9  插入            3.9.1 在pos位置之前插入             3.9.

    2023年04月20日
    浏览(105)
  • 数据结构——单链表(下)

    🌇个人主页:_麦麦_ 📚今日名言:年轻时候的我以为坚持是永不动摇,到这个年纪明白了坚持就是犹疑着,退缩着,心猿意马着,一步三停着,还在往前走。——《十二月历》 目录 一、引言  二、单链表剩余功能的实现         1.单链表的查找         2. 单链表指定位

    2024年01月17日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包