数据结构对链表的初步认识(一)

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

已经两天没有更新了,今天就写一篇数据结构的链表吧,巩固自己也传授知识,不知道各位是否感兴趣看看这一篇有关联表的文章。

目录

链表的概念与结构

 单向链表的实现

链表各个功能函数


首先我在一周前发布了一篇有关顺序表的文章,其中我们通过简单的介绍和代码实践,已经基本了解顺序表了,那么即使我们把顺序表弄成动态的顺序表,但其实我们运用顺序表还是有以下问题:

1. 如果空间不够,我们进行增容。但增容回付出一定的性能消耗,其次可能存在一定的空间浪费,因为我们每次增容都是2倍的增容我们可能并用不完这两倍的空间。

2.头部和中部左右两部分的插入效率太低,因为我饿们需要将数据一个一个的往后移,所以效率不高。

 

那么我们要怎么解决这个问题呢?

1.空间上  ,按照需求给空间,比如我要101个空间就给我101个空间而不是两倍。

2.不要求物理空间上的连续,这样在头部和中部时我们就不需要挪动数据,那么这种解决方法就是用链表实现。

 

OK,我们下面就展开展开链表的知识了。


链表的概念与结构

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

其逻辑结构(这里说的逻辑结构是我们想象出来便于理解的结构):

数据结构对链表的初步认识(一),数据结构,链表,visualstudio,开发语言,c语言

上方逻辑结构可以是n个数据和指针,这样我们就完成了,非物理空间上的连续的表。

链表有许多结构我们今天就讲一种简单的结构——————单向链表。


 单向链表的实现  

我们继续创建一个结构体,里面是数据和指针。

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

代码中将结构体命名为SLTNode是为了方便写代码。 

typedef int SLTDataType  为了易于改变数据类型时,只需将int 改成其他类型即可改变 ,整个链表的数据类型。

struct SListNode* next   这里面储存一个结构体指针用来链接下一个结构体。

既然结构体已经完成了,那么我们现在就简单用函数链接一个链表了。


链表各个功能函数

 

链表必须要找一个头,即链表的首个结构体,那么我们就将这个头命名为 plist,传给其他函数完成其功能。

现在我们就实现第一个函数,开辟空间的函数。

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

这个函数主要用于链表的增加,在各个部位进行插入数据都需要这个函数开辟空间。 


头插函数

如何头插呢?这是我们需要思考的。

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	newnode->next = *pphead;
	*pphead = newnode;
}

链表头插即开辟一块新的空间,将这块空间作为头(*pphead = newnode;),而这块空间的next则储存着原来的头结构体(newnode->next = *pphead;) 。

注意:这里要改变pist本身则我们就要使用指针进行传址,改变其地址。


 头删函数

这个函数也相较简单,我们也是将第一个节点删除,然后将第二个节点设为头节点,而第二个节点就是原来头节点里储存的 next了,我们必须先储存第二节点的地址然后再进行销毁。

void SListPopFront(SLTNode** pphead)
{
	SLTNode* next = (*pphead)->next;
	free(*pphead);

	*pphead = next;
}

尾插函数

尾插函数,我们只需先创建一个新空间newnode,然后将原来的尾的结构体中的 next 改为现在newnode 即可。但需要注意当链表还一个节点都没有的时候,原来是没有尾的,这又是一种情况,我们只需将*pphead变为newnode,即可。由此得出下面代码。

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾节点的指针
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		// 尾节点,链接新节点
		tail->next = newnode;
	}
}

 


 尾删函数

尾删时我们需要考虑三种情况 

 1、空
 2、一个节点
 3、一个以上的节点

空的时候我们不需要任何操作,直接return即可。

一个节点时我们需要用free函数进行销毁空间,然后将该*phead 赋一个NULL。

一个节点i以上我们要考虑的又有些不同,因为当我们将尾节点删除时我们还需将倒数第二个节点赋为NULL不然程序可能会崩掉。我们知道找最后一个尾节点很容易但是我们要找倒数第二个节点很难 ,这里我们就需要借助第三指针变量,一前一慢进行往后遍历,最后即可得到这两个节点了。

void SListPopBack(SLTNode** pphead)
{
	// 1、空
	// 2、一个节点
	// 3、一个以上的节点
	if (*pphead == NULL)
	{
		return;
	}
	else 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);
		prev->next = NULL;
	}
}

 


打印函数

以NULL为链表结束标志,即打印结束。 

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

 下面给大家展示一下这些函数:

void Test()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 8);
	SListPushFront(&plist, 88);
	SListPushBack(&plist, 29);
	// 88 8 29
	SListPrint(plist);
	SListPopBack(&plist);
	SListPushFront(&plist, 5);
	SListPushBack(&plist, 89);
	// 5 88 8 89
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
	//88 8 89


}




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

数据结构对链表的初步认识(一),数据结构,链表,visualstudio,开发语言,c语言


 文章到这就结束了。

数据结构对链表的初步认识(一),数据结构,链表,visualstudio,开发语言,c语言文章来源地址https://www.toymoban.com/news/detail-827417.html

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

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

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

相关文章

  • 【数据结构】反转链表、链表的中间节点、链表的回文结构(单链表OJ题)

    正如标题所说,本文会图文详细解析三道单链表OJ题,分别为:  反转链表 (简单)  链表的中间节点 (简单)  链表的回文结构 (较难) 把他们放在一起讲的原因是:  反转链表 和  链表的中间节点 是  链表的回文结构 的基础 为什么这样说?请往下看: 目录 1. 反转链

    2024年02月13日
    浏览(68)
  • 【数据结构】链表的回文结构

    单链表的操作算法是笔试面试中较为常见的题目。 本文将着重介绍平时面试中常见的关于链表的应用题目,马上要进行秋招了。希望对你们有帮助 _ 😀 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。 给定一个链表的头指针

    2024年02月12日
    浏览(52)
  • 【数据结构】链表的分类和双向链表

    本篇是基于上篇单链表所作,推荐与上篇配合阅读,效果更加 http://t.csdnimg.cn/UhXEj 链表的结构非常多样,以下情况组合起来就有8种(2 x 2 x 2)链表结构: 我们一般叫这个头为哨兵位 我们上回讲的单链表就是不带头单项不循环链表。 今天我们要讲带头双向循环的链表。 不过

    2024年01月25日
    浏览(38)
  • 数据结构-二叉链表的结构与实现

    目录 一、引言 二、什么是二叉链表 三、二叉链表的结构 四、二叉链表的实现 1. 创建二叉链表 2. 遍历二叉链表 3. 插入节点 4. 删除节点 五、应用场景 六、总结 七、代码示例 数据结构是计算机科学中的重要概念,它是计算机程序设计的基础。二叉链表是一种常见的数据结构

    2024年02月08日
    浏览(48)
  • 数据结构----链表介绍、模拟实现链表、链表的使用

    ArrayList底层使用连续的空间,任意位置插入或删除元素时,需要将该位置后序元素整体往前或者往后搬移,故时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后

    2024年02月21日
    浏览(50)
  • 【(数据结构)— 双向链表的实现】

    注意: 这里的 “带头” 跟前面我们说的 “头节点” 是两个概念,实际前面的在单链表阶段称呼不严 谨,但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表里的头节点,实际为 “哨兵位” ,哨兵位节点不存储任何有效元素,只是站在这里“放哨 的” “哨

    2024年02月06日
    浏览(42)
  • 【数据结构】双向链表的实现

    我要扼住命运的咽喉,他却不能使我完全屈服。                      --贝多芬 目录 一.带头循环的双向链表的特点 二.不带头不循环单向链表和带头循环的双向链表的对比 三.初始化链表,创建哨兵结点 四.双向链表的各种功能的实现 1.双向链表的尾插 2.双向链表的打印 

    2023年04月10日
    浏览(43)
  • 数据结构——双向链表的实现

    注意: 双向链表又称带头双向循环链表 这⾥的“带头”跟前⾯我们说的“头节点”是两个概念,实际前⾯的在单链表阶段称呼不严 谨,但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表⾥的头节点,实际为“ 哨兵位 ”,哨兵位节点不存储任何有效元素,只

    2024年02月06日
    浏览(46)
  • 【数据结构】十字链表的画法

    有向边又称为弧 假设顶点 v 指向 w,那么 w 称为弧头,v 称为弧尾 顶点节点采用顺序存储 顶点节点 data:存放顶点的信息 firstin:指向以该节点为终点(弧头)的弧节点 firstout:指向以该节点为起点(弧尾)的弧节点 弧节点 tailvex:起点(弧尾)在数组中的索引 headvex:终点(

    2024年02月11日
    浏览(47)
  • 数据结构——链表的实现(Java版)

    目录 一、链表 二、代码实现 1.创建结点 2.构造函数 3.链表的相关属性 4.添加虚拟节点 5.判断链表是否为空 6.添加方法 (1)在头部添加 (2)在尾部添加 (3)在索引位置添加 (4)对头插法和尾插法代码进行简化(调用任意位置添加的方法) 7.打印链表(遍历,重写toString方

    2024年01月23日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包