顺序表(二)

作者: 焰火青春 | 来源:发表于2020-06-11 16:51 被阅读0次

    2.1 线性表

    线性表是最基本的数据结构之一,它是某类元素的集合,记录着元素之间的一种顺序关系,是实现更复杂数据结构的基础。

    根据存储方式不同,可分为(顺序存储和链式存储):

    • 顺序表:将元素放在一块连续的内存空间中,顺序存储,存储元素是连续的
    • 链表:元素之间链接起来,不需要连续的内存空间,链式存储,存储元素不一定连续,元素节点中存放数据元素以及相邻元素的地址信息

    2.2 顺序表

    顺序表在内存中是以连续存储的方式存储的,即元素之间没有其他数据结构的内存空间,基本布局方式存储每个元素所占的存储单元大小相同

    顺序表结构

    image

    图 a 表示顺序表的基本形式,数据元素本身连续存储,每个元素所占的存储单元大小固定相同,元素下表为逻辑地址,而元素存储的物理地址(即实际内存地址)可通过存储区的起始地址 Loc(e0) 加上逻辑地址(第 i 个元素)与存储单元大小 c 的乘积计算而得:

    Loc(ei) = Loc(e0) + c*i
    

    故,访问指定元素时无需从头遍历,通过计算便可获得对应地址,其时间复杂度为O(1)。


    顺序表计算

    假设每个顺序表中每个元素占用内存空间为 c,起始物理地址(内存地址)为 L0,那么相应地:

    # 第一个元素
    L0
    
    # 第二个元素
    L0 + 1c
    
    # 第三个元素
    L0 + 2c
    
    # 第 n 个元素
    L0 + (n-1)c
    
    # 由此可以推算出顺序表的计算公式为:
    L(n) = L(a0) + c*i              # c 为每个元素占用的内存大小,i 为元素的逻辑地址,即下标
    

    访问指定元素时无需从头遍历,通过计算便可获得对应地址,其时间复杂度为O(1)

    元素外置型

    基本布局结构,每个元素所占的存储单元大小相同,若元素大小不统一,则须采用图 b 的元素外置的形式。

    而顺序表中各单元位置保存对应元素的地址信息(即链接)。由于每个链接所需的存储量相同,通过上述公式,可以计算出元素链接的存储位置,而后顺着链接找到实际存储的数据元素。注意,图b中的c不再是数据元素的大小,而是存储一个链接地址所需的存储量,这个量通常很小。

    2.3 顺序表结构

    一个完整的顺序表由两部分组成:元素集合区以及表结构信息记录区(存储表中元素个数和存储区容量大小)。

    image

    顺序表两种基本实现方式

    image
    • 一体式:存储表信息的单元与元素存储区以连续的方式安排在一块存储区里,结构整体性强,易于管理。但是由于数据元素存储区域是表对象的一部分,顺序表创建后,元素存储区就固定了。
    • 分离式:表对象里只保存与整个表有关的信息(即容量和元素个数),实际数据元素存放在另一个独立的元素存储区里,通过链接与基本表对象关联。

    元素存储区扩充

    分离式结构在扩充时(即新增元素时),可在不改变表对象的前提下对数据存储区进行扩充,这种技术实现的顺序表称为动态顺序表,因为其容量可以在使用中动态变化。

    扩充容量有两种策略:

    • 线性增长:

      • 每次按固定数量增加,如:每次增加 10 个元素位置
      • 节省空间,但是扩充操作频繁,操作次数多。
    • 成倍增长

      • 每次扩充容量加倍,如每次扩充增加一倍存储空间。

      • 减少了扩充操作的执行次数,但可能会浪费空间资源。以空间换时间,推荐的方式。

    2.4 顺序表操作

    在前面我们说了,数据的常用操作有插入、删除、查找、修改、排序,而在五个操作中最常用的两个操作应该就是插入和删除了,下面来看看顺序表的插入、删除操作。

    插入元素

    image

    在一个顺序表中插入一个元素有三种方式:

    • 表的尾部插入:时间复杂度为 O(1),不需要改变其他元素的位置
    • 中间插入:
      • 非保序(不常见):即要插入的元素放在相应位置,将该位置之前的元素放置在最后一位,时间复杂度 O(1)
      • 保序:需要改变要插入位置后面所有元素所有的位置,往后移动一位(如果空间不够还要扩容),时间复杂度 O(n)
    • 头部插入:和保序插入一样,时间复杂度也是 O(n),因为它需要将所有元素往后移动

    删除元素

    image

    删除元素和插入元素类似:

    • 表尾元素:O(1)
    • 非保序:O(1)
    • 保序:O(n)

    2.5 Python中的顺序表

    Python 中的所有数据类型,tuple 和 list 是基于顺序表实现的。tuple 不可变,采用的是基本布局(即表信息区和元素区在一块)。而 list 从用的是 分离式结构

    list 实现技术

    Python list 就是一种元素个数可变的线性表,可加入、删除元素,并在各种操作中维持已有元素的顺序(即保序),并具有以下特征:

    • 基于下标访问或更新元素,时间复杂度为 O(1),因此元素应保存在一块连续的存储空间中
    • 允许任意加入元素,且在不断加入元素的过程中,表对象的身份标识(即 ID)不变;因此就必须要能更换元素存储区,并且为保证更换存储区时 list 对象的标识 ID 不变,只能采用分离式结构实现

    list 采用 分离式技术实现的动态顺序表,同时在插入、删除时能保序,是一种标准的可变线性表。存储计划:新建空表时,分配一块能存储 8 个元素大小的空间,如果插入操作时空间不够则换一块 4 倍大小的空间。当整个空间超过 50000 时,则采用一倍的策略,其目的是为了能避免出现过多的空闲存储位置。

    相关文章

      网友评论

        本文标题:顺序表(二)

        本文链接:https://www.haomeiwen.com/subject/hxobtktx.html