我命由我,不由天!


  • 搜索
prometheus docker golang linux kubernetes

线性表

发表于 2021-07-06 | 0 | 阅读次数 457

线性表的顺序结构

定义

用一段地址连续的存储单元一次存储线性表的数据元素

在内存中找了块地,通过占位的形式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空地中。

描述顺序存储结构需要三个属性

  1. 存储空间的起始位置
  2. 线性表的最大存储容量
  3. 线性表的当前长度

数据的长度是存放线性表的存储空间的长度,线性表长度是线性表中数据元素的个数

地址计算方法

数数是从1开始,可下标是从0开始,元素的序号和存放它的数组下表之间存在对应关系
image.png
存储器中的每个存储单元都有自己的编号,这个编号称为地址。(LOC表示获得存储位置的函数)

第i个数据元素的存储位置

LOC(ai)=LOC(a1)+(i-1)*C

可以随时算出线性表中任意位置的地址,存取时间性能为O(1),把具有这一特点的存储结构称为随机存取结构

顺序存储结构的插入与删除

获得元素

只要i的数值在数组下标范围内,就是把数组第i-1下标的值返回

插入操作

  1. 如果插入位置不合理,抛出异常
  2. 如果线性表长度大于等于数组长度,则抛出异常或动态增加容量
  3. 从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置
  4. 将要插入元素填入位置i处
  5. 表长加1

删除操作

  1. 如果删除位置不合理,抛出异常
  2. 取出删除元素
  3. 从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置
  4. 表长减1

在存、读数据时,不管是哪个位置,时间复杂度都是O(1);而插入或删除时,时间复杂度都是O(n)

优缺点

优点
  • 无需为表示表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速地存取表中任一位置的元素
缺点
  • 插入和删除操作需要移动大量元素
  • 当线性表长度变化较大时,难以确定存储空间的容量
  • 造成存储空间的“碎片”

线性表的链式存储结构

线性表链式存储定义

特点:用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着,这些数据元素可以存在内存未被占用的任意位置。

现在链式结构中,除了要存数据元素信息外,还要存储它的后继元素的存储地址。

为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息。我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像,称为节点。

n个节点链结成一个链表,即为线性表的链式存储结构,因为此链表的每个结点中只包含一个指针域,所以叫做单链表。

头指针

  • 链表中的第一个节点的存储位置叫做头指针

  • 头指针具有标识作用,所以常用头指针冠以链表的名字

  • 无论链表是否为空,头指针均不为空。头指针是链表的必要元素

头结点

  • 在单链表的第一个结点前附设一个结点,称为头节点。头节点的数据域可以不存储任何信息
  • 有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其它结点的操作就统一了
  • 头结点不一定是链表必须要素

单链表的读取

  1. 声明一个结点P指向链表第一个结点,初始化j从1开始
  2. 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1
  3. 若链表末尾p为空,则说明第i个元素不存在
  4. 否则查找成功,返回结点p的数据

最坏时间复杂度O(n),主要核心思想“工作指针后移”

单链表的插入

image.png

  1. 声明一结点P指向链表第一个结点,初始化j从1开始
  2. 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1
  3. 若链表末尾p为空,则说明第i个元素不存在
  4. 否则查找成功,在系统中生成一个空结点s
  5. 将数据元素e赋值给s->data
  6. 单链表的插入标准语句:s->next=p-next; p->next-s;
  7. 返回成功

单链表的删除

image.png

  1. 声明一结点p指向链表第一个结点,初始化j从1开始
  2. 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1
  3. 若链表末尾p为空,则说明第i个元素不存在
  4. 否则查找成功,将欲删除的结点p->next赋值给q
  5. 单链表的删除标准语句p->next=q->next
  6. 将q结点中的数据赋值给e,作为返回
  7. 释放q结点

单链表插入和删除算法,第一部分是遍历查找第i个元素,第二部分是插入和删除元素。时间复杂度都是O(n)。在不知道第i个元素指针的位置,单链表数据结构在插入和删除操作上,与线性表的顺序存储结构没有太大优势,但对于插入或删除数据越频繁的操作,单链表的优势就越明显

单链表的整表创建

对于每个链表来说,它所占用空间的大小和位置都不需要预先分配,根据系统的情况和实际的需求即时生成。

创建单链表的过程就是一个动态生成链表的过程,即从“空表”的初始状态起,依次建立各元素结点,并逐个插入链表

单链表结构与顺序存储结构优缺点

存储分配方式

  • 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
  • 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素

时间性能

  • 查找
    • 顺序存储结构O(1)
    • 单链表O(n)
  • 插入和删除
    • 顺序存储结构需要平均移动表长一半的元素,时间为O(n)
    • 单链表在找出某位置的指针后,插入和删除时间仅为O(1)
  • 空间性能
    • 顺序存储结构需要预分配存储空间,分大了,浪费,分小了,易发生上溢
    • 单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点,就使得整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表

循环链表解决了一个很麻烦的问题,如何从当中一个结点出发,访问到链表的全部结点。

为了使空链表与非空链表处理一致,通常设一个头结点。

可以用O(1)的时间访问第一个结点,但对于要访问到最后一个结点,却需要O(n)时间。使用尾指针来表示循环链表,此时查找开始结点和终端结点都很方便了。

image.png
终端结点用尾指针rear指示,则查找终端结点是O(1),而开始结点,其实就是rear->next->next,其时间复杂也为O(1)

双向链表

在单链表的每个结点中,再设置一个指向其前驱结点的指针域

插入

image.png
先搞定s的前驱和后继,再搞定后结点的前驱,最后解决前结点的后继

删除

image.png

  1. 把p->next 赋值给p->prior的后继
  2. 把p->prior赋值给p->next的前驱

双向链表相对于单链表来说,要更复杂一些,毕竟它多了prior指针,对于插入和删除时,需要格外小心。另外由于每个结点都需要记录两份指针,所以在空间上时要占用略多一些的。不过,由于它的良好对称性,使得对某个结点的前后结点操作,带来了方便,用空间换了时间

  • 本文作者: Dante
  • 本文链接: https://gaodongfei.com/archives/线性表
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
UML类图
leetcode链表相关
  • 文章目录
  • 站点概览
Dante

Dante

119 日志
5 分类
5 标签
RSS
Creative Commons
0%
© 2023 Dante
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4
沪ICP备2020033702号