初阶数据结构之单链表的实现(四)

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



链表的概念及结构

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


一、链表的逻辑结构是什么样的?

所谓的逻辑结构其实就是能让我们自己能够更好的理解这个东西是什么?那么我们就用画图来理解理解吧!!在单链表中,存放着两个量,一个是地址量,一个是数据量,如图所示,这是一个带头的单链表。

初阶数据结构之单链表的实现(四)

二、链表的初始化

2.1链表初始化的示意

正如上图所说,单链表中存在一个数据量和一个地址量,所以我们定义结构体的时候,应该定一个data数据量,和一个指针用来存放自己所以定义的地址量。

2.2链表初始化代码实现

代码如下:

typedef int SLTDataType;

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

并且还需要定义几个头文件如下所示

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

这里介绍一个查询头文件的网站CPlusplus


三、链表的各类接口函数定义

void SLTPrint(SLTNode* phead);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);

void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//在pos之前插入
void SLInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x);
void SLInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos);
void SLEraseAfter(SLTNode* pos);

void SLTDestroy(SLTNode* phead);

四、链表的各类接口函数的代码实现

4.1链表的打印代码实现

因为我们写的是带头的单链表,所以我们就可以从头开始遍历。我们定义一个结构体指针用来存放头结点,因为头结点此时存放的是下一个位置的地址,所以我们只需要拿一个指针去接收它就行啦。

那我们此时该思考一下,我们虽然是通过遍历来打印数据,但是我们是不是得想一下结束条件呢?如果我们用cur->next == NULL 作为结束条件,那么我们是不是想错了呢?我们画图解释一下吧!从图中看,如果我们以cur->next为结束条件那么,最后一个数我们是不是就打印不了,所以我们就想错啦

初阶数据结构之单链表的实现(四)

我们在来看看下图,我们发现用cur本身去遍历就可以把全部都遍历完,好啦这里我们算是解释通啦!

初阶数据结构之单链表的实现(四)

4.1.1打印代码的实现

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

4.2链表的尾插代码实现

尾插顾名思义就是在尾部进行插入,那么我们应该怎么样去实现单链表的尾部插入呢?我们还是画图进行理解,如下图所示。

我们想要在尾部进行插入,我们是不是应该先遍历到尾结点呢?是的没错!但是这里我们就得注意我们遍历结束的条件了,为什么这么说呢?假设如果按照我们上面打印那样遍历的话,我们就会遍历成野指针,所以我们遍历的条件为cur->next ,这样是不是就解决啦!

初阶数据结构之单链表的实现(四)

这里我们得考虑两种情况。
1、当这个链表是空的时候我们应该怎么去处理他呢?我们直接让新建立的节点赋值给我们的头就行啦
2、也就是正常的插入啦!让最后一个节点的指针指向新节点,然后再把最后一个节点的位置改变就完成啦!

4.2.1尾插代码实现

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuyLTNode(x);
	if ((*pphead) == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

4.3链表的头插代码实现

关于头插我们应该这样处理:
1、因为我们是带有头结点的单链表,又因为我们头结点存储的是第一个节点的地址,所以只需要把头结点所存储的地址赋给新开的节点的next位置,此时的新节点所指向的就是原来第一个节点的位置
2、因为头结点存储第一个节点的地址,所以我们要把新开的节点的地址赋给头结点,这样就完成了头插!

1图文解释:插入前:

初阶数据结构之单链表的实现(四)

2、插入中:

初阶数据结构之单链表的实现(四)

3、结束插入:
初阶数据结构之单链表的实现(四)

4.3.1头插代码的实现

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuyLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

4.4BuyLTNode函数的实现

本函数的意思是动态的开辟一个节点在堆上!

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

4.5链表的尾删代码实现

在单链表中,尾删的效率其实是非常的差的,因为单链表需要一直遍历查找,所以效率耗费的十分的严重。

在尾删的过程中,我们也需要考虑两种情况!
第一种情况:当链表中只有一个节点的时候我们应该怎么样的删除
第二种情况:当链表中有多个节点的时候我们应该怎么删除呢?

当只有一个节点的时候,我们应该直接把节点free掉,因为我们的节点都是动态开辟的,所以我们应用free这个函数,把节点摧毁掉

当有多个节点的时候,我们应该用两个指针,一个在前面一个在后面,当前面的节点为空时,说明我们找到了尾,我们free掉尾结点就行啦!

4.5.1尾删代码的实现

void SLTPopBack(SLTNode** pphead)
{
	//当只有一个节点的时候
	//多个节点
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* prev = NULL;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

4.6链表的头删代码实现

如下图所示,先让pphead往前先走一步,提前找好一个前节点,然后free掉他,然后把pphead赋值给prev,再让*pphead往前走!

初阶数据结构之单链表的实现(四)
初阶数据结构之单链表的实现(四)

4.6.1头插代码的实现

void SLTPopFront(SLTNode** pphead)
{
	//空链表
	assert(*pphead);
	assert(pphead);
	SLTNode* prev = *pphead;
	*pphead = prev->next;
	free(prev);
}

五、完整代码的实现

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"listnode.h"

void test1()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 0);
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPrint(plist);
	SLTPushBack(&plist, -1);
	SLTPrint(plist);
}
void test2()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, -1);
	SLTPushBack(&plist, 0);
	SLTPushBack(&plist, 1);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
}
void test3()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, -1);
	SLTPushBack(&plist, 0);
	SLTPushBack(&plist, 1);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
}
void test4()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SLTNode* pos = SLTFind(plist, 3);
	pos->data = 30;
	SLInsert(&plist, pos, 20);
	SLTPrint(plist);
	SLInsertAfter(pos, 40);
	SLTPrint(plist);
	SLEraseAfter(pos);
	SLTPrint(plist);
	SLTDestroy(plist);
}
int main()
{
	test4();
	return 0;
}

listnode.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "listnode.h"

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

SLTNode* BuyLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuyLTNode(x);
	if ((*pphead) == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuyLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
//尾删的第一种方式
void SLTPopBack(SLTNode** pphead)
{
	//当只有一个节点的时候
	//多个节点
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* prev = NULL;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}
//尾删的第二种方式
/*
void SLTPopBack(SLTNode** pphead)
{
	SLTNode* tail = *pphead;
	while (tail->next->next)
	{
		tail = tail->next;
	}
	free(tail->next);
	tail->next = NULL;
}
*/
void SLTPopFront(SLTNode** pphead)
{
	//空链表
	assert(*pphead);
	assert(pphead);
	SLTNode* prev = *pphead;
	*pphead = prev->next;
	free(prev);
	//一个节点
	//if ((*pphead)->next == NULL)
	//{
	//	free(*pphead);
	//	*pphead = NULL;
	//}
	多个节点
	//else
	//{
	//	SLTNode* prev = *pphead;
	//	*pphead = prev->next;
	//	free(prev);
	//}
}

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}


//在pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuyLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
	
}
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuyLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
//删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}
void SLEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* next = pos->next;
	pos->next = next->next;
	free(next);
}

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

listnode.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;

typedef struct SListnode
{
	SLTDataType data;
	struct SListnode* next;
}SLTNode;
 
void SLTPrint(SLTNode* phead);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);

void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//在pos之前插入
void SLInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x);
void SLInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos);
void SLEraseAfter(SLTNode* pos);

void SLTDestroy(SLTNode* phead);

总结

好啦,今天的单链表的大部分解决思路我都给大家详细的写出来啦!我们下期再见!嘿我们天天见!!!文章来源地址https://www.toymoban.com/news/detail-456863.html

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

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

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

相关文章

  • 【数据结构】单链表的简单实现

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元

    2024年02月04日
    浏览(57)
  • 【数据结构】单链表的层层实现!! !

    关注小庄 顿顿解馋(●’◡’●) 上篇回顾 我们上篇学习了本质为数组的数据结构—顺序表,顺序表支持下标随机访问而且高速缓存命中率高,然而可能造成空间的浪费,同时增加数据时多次移动会造成效率低下,那有什么解决之法呢?这就得引入我们链表这种数据结构 概念

    2024年03月12日
    浏览(163)
  • 【数据结构】实现单链表的增删查

    链表类和节点类的定义: 图解: 从中间位置插入: 图解:假定index=2 尾插: 删除当前线性表中索引为index的元素,返回删除的元素值: 图解: 删除当前线性表中第一个值为element的元素: 删除当前线性表中所有值为element的元素: 将当前线性表中index位置的元素替换为eleme

    2024年02月14日
    浏览(164)
  • 数据结构:单链表的实现(C语言)

    个人主页 : 水月梦镜花 个人专栏 : 《C语言》 《数据结构》 本博客将要实现的无头单向不循环链表。 我们将节点定义为如下结构: 其成员变量有data,next。 将int重命名为STLDataType,方便我们以后修改数据域的内容。 动态申明一个空间,来放置数据。如下: 将data的内容置

    2024年02月14日
    浏览(59)
  • 【数据结构】 链表简介与单链表的实现

    在【数据结构】 ArrayList简介与实战中我们已经熟悉了ArrayList的使用,并且进行了简单模拟实现。通过源码知道,ArrayList底层使用数组来存储元素 由于其底层是一段连续空间, 当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为

    2024年02月12日
    浏览(202)
  • 数据结构——单链表的实现(c语言版)

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

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

    优势 : 可通过 下标i (数据连续(物理空间连续)) 便捷查询查找顺序表中的信息,也会在后面的 排序算法 和 堆算法 中尽显身手 问题 : 在头部/中间的插入与删除需要 挪动数据 ,时间复杂度为O(N),效率低; 增容需要申请新空间, 可能会拷贝数据 ,释放旧空间,会有

    2024年02月05日
    浏览(59)
  • 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语言实现)

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

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

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

    2024年02月03日
    浏览(65)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包