当前位置: article > 正文

线性表(大话结构略读)_线性表删除表尾元素时间复杂度

作者：小惠珠哦 | 2024-07-27 08:42:09

踩

线性表删除表尾元素时间复杂度

线性表定义

ddf

线性表的抽象数据类型

![[../../attach/Pasted image 20231010225948.png|800]]

![[../../attach/Pasted image 20231010230301.png|825]]

线性表的顺序储存结构

在这里插入图片描述

顺序储存表插入元素

在这里插入图片描述

顺序储存表删除元素

在这里插入图片描述

顺序存储表插入与删除时间复杂度总结

若元素要插入到最后一位,或者删除最后一个元素,此时时间复杂度为O(1),因为此时不需要移动元素
若元素要插入到第一位,或者删除第一个元素,此时时间复杂度为O(n),因为此时要移动所有元素向前或者向后
若是平均情况,将元素插入第i个位置,或者删除第i个元素,需要移动n-i个元素;根据概率原理,每个位置插入或者删除元素可能性相同.也就是说位置靠前,移动元素多;位置靠后,移动元素少.最终平均移动次数和最中间的那个元素的移动次数相等,为(n-1)/2

总结:线性表的顺序储存结构,在存、读数据时，不管哪个位置，时间复杂度都是O（1）；而插入或删除时，时间复杂度都是O（n）。这就说明，它适合元素不太变化，而更多是存取数据的应用。

线性表顺序存储结构的优缺点

在这里插入图片描述

线性表的链式存储结构

在这里插入图片描述
单链表中,我们在C语言中用结构指针来描述.

上方的Node和Linklist分别是指结点和链表两个不同的概念,但是都是用该结构体的成员构成

链表结点之间的插入元素

在这里插入图片描述

注意插入元素的代码写法：是先对s->next=p->next,这是将结点s"链接"到后半段链表中,再讲p->next=s,是把前半段链表"链接"到结点s
如果两者反了,先对p->next=s,此时结点p->next直接变成了结点s,而s->next则变成了p->next->next

链表结点之间的删除元素

在这里插入图片描述

链表创建整表

单链表是一种动态结构,对于每个链表来说,它所占空间大小与位置不需要预先分配划定,可以根据系统情况和实际需求即时生成。
所以创建链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。

头插法创建链表

这段算法代码中，我们使用插队的办法，始终让新结点在第一的位置，将此算法简称为头插法

尾插法创建链表

将新节点都放在最后,这是排队的正常思维,所谓的先来后到
在这里插入图片描述

循环结束后,应让此链表的指针域置空,因此有了"r->next=NULL",以便以后遍历时可以确认其是尾部

链表整表删除

在这里插入图片描述

注意:有人觉得q的存在不必要,可以直接释放结点p,再p=p->next;可释放结点p后,p的指针域也消失了,就无法找到p的下一个结点

链表读取

在单链表中,由于第i个元素的位置没办法一开始就知道,必须得从头开始找
在这里插入图片描述
由于单链表的结构中未定义表长,所以不知道是先知道要循环多少次,因此也就不方便使用for来控制循环,其主要核心思想是**“工作指针后移”**

链表结构和顺序存储结构优缺点

在这里插入图片描述

若线性表需频繁查找,很少需要插入和删除操作时,宜使用顺序存储结构;若需要频繁插入和删除时,宜采用单链表结构.

如游戏开发中,用户注册的个人信息,除了注册时插入数据外,绝大多数是读取,可以考虑用顺序存储结构.而玩家的武器或者装备列表,可能会随时增加或者删除,此时就可以使用单链表

如果线性表中元素个数变化较大或者根本不知道有多大,最好用单链表结构,这样可以不考虑存储空间大小问题;而事先知道线性表的大致长度,顺序存储结构效率会很高