Python3数据结构01 - 顺序表

  • 原创
  • Madman
  • /
  • 2018-09-02 13:40
  • /
  • 0
  • 54 次阅读

Synopsis: 线性表包括顺序表和链表,本文先介绍顺序表的元素内置和元素外置两种基本形式,再介绍一体式和分离式两种顺序表的结构,最后说明了Python中列表和元组高级数据结构的本质其实就是元素外置的、分离式的动态顺序表

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

1. 线性表

线性表(Linear List)是由 n(n≥0) 个数据元素(节点)a[0]a[1]a[2]…,a[n-1]组成的有限序列。一个线性表是某类元素的一个集合,还记录着元素之间的一种顺序关系。这种结构具有下列特点:

  • 存在一个唯一的没有前驱节点的数据元素(头)
  • 存在一个唯一的没有后继节点的数据元素(尾)
  • 除此之外,每一个数据元素均有一个直接前驱和一个直接后继数据元素

根据线性表的实际存储方式,分为两种实现模型:

  • 顺序表: 将元素顺序地存放在一块连续的存储区里,元素间的顺序关系由它们的存储顺序自然表示
  • 链表: 将元素存放在通过链接构造起来的一系列非连续的存储块

2. 顺序表

2.1 顺序表的基本形式

假设存储一个整数要占用4个字节内存空间,存储一个英文字符要占用1个字节内存空间。内存是按字节编址的,操作系统内核会给内存的每个字节分配一个内存地址

(1) 元素内置

顺序表 元素内置

上图中的数据元素本身连续存储,每个元素所占的存储单元大小固定相同,左边是每个元素的下标,而每个元素的起始内存地址可以通过存储区的起始地址 Loc(e0) 加下标(i)与每个元素所占的存储单元大小(c)的乘积计算出来,即:Loc(ei) = Loc(e0) + i*c

为了方便计算顺序表中的每个元素的起始内存地址,下标从0开始计数,而不是从1开始,下标表示偏移量

比如已知顺序表的第一个元素(下标为0)的起始内存地址为0x00000010,那么第三个元素(下标为2)的起始内存地址为0x00000012(每个英文字符占1个字节)

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

(2) 元素外置

顺序表 元素外置

如果每个元素所占的存储单元大小不相同,要采用上图中的元素外置形式。将实际数据元素另行存储,每个实际数据元素的存储空间地址可以不连续。由于内存地址大小是相同的,比如32位系统中内存地址是32位二进制(即占4个字节),所以顺序表中的每个元素保存的是指向实际数据元素的内存地址(也叫链接或指针)

比如已知顺序表的第一个元素(下标为0)的起始内存地址为0x00000010,如果要读取第三个实际数据元素,先找顺序表的第三个元素(下标为2)的起始内存地址为0x00000018(每个内存地址占4个字节),然后读取它的内容从而获取到第三个实际数据元素的起始内存地址为0x00003001,顺着这个指针找到字符串'Python'

2.2 顺序表的结构

一个顺序表的完整信息包括两部分: 表中的元素集合; 元素存储区的容量和当前表中已有的元素个数

用户进程向操作系统内核申请顺序表的连续空间时,必须告知要多大空间(即最多能存储多少个元素)

(1) 一体式结构

一体式顺序表

上图为一体式结构,存储表信息的单元与元素存储区以连续的方式安排在一块存储区里,两部分数据的整体形成一个完整的顺序表对象

一体式结构整体性强,易于管理。但是由于数据元素存储区域是表对象的一部分,顺序表创建后,元素存储区就固定了

元素存储区扩充

有两种扩充策略:

  • 每次扩充增加固定数目的存储位置,如每次扩充增加8个元素位置,这种策略可称为线性增长,优点是节省空间,但是扩充操作频繁,操作次数多
  • 每次扩充容量加倍,如每次扩充增加一倍存储空间,优点是减少了扩充操作的执行次数,但可能会浪费空间资源。以空间换时间,推荐使用此方式

一体式结构由于顺序表信息区与数据区连续存储在一起,所以若想扩充数据区,则只能重新申请更大的完整的顺序表信息区与数据区,此时顺序表指向新的内存地址,即在用户程序中看到顺序表的指向会改变

一体式顺序表 扩充

(2) 分离式结构

分离式顺序表

上图为分离式结构,表对象里只保存与整个表有关的信息(即容量和元素个数),实际数据元素存放在另一个独立的元素存储区里,通过链接与基本表对象关联

元素存储区扩充

分离式结构若想更换数据区,只需将表信息区中的数据区链接地址更新即可,而该顺序表对象不变

分离式顺序表 扩充

分离式顺序表扩充后,原顺序表对象不变,用户程序中所有使用这个表的地方都不必修改,所以它也被称为动态顺序表

2.3 顺序表的操作

(1) 新增元素

顺序表新增元素

  • 在尾端插入元素,时间复杂度为O(1)
  • 在指定位置插入(非保序),这种情况很少用,时间复杂度为O(1)
  • 在指定位置插入(保序),时间复杂度为O(n)

(2) 删除元素

顺序表删除元素

  • 在尾端删除元素,时间复杂度为O(1)
  • 在指定位置删除(非保序),这种情况很少用,时间复杂度为O(1)
  • 在指定位置删除(保序),时间复杂度为O(n)

2.4 Python中的顺序表

Python中的ListTuple两种高级数据类型都采用了顺序表的实现技术,具有前面讨论的顺序表的所有性质。Tuple是不可变类型,即不变的顺序表,因此不支持改变其内部状态的任何操作(不支持新增或删除元素),而其他方面,则与List的性质类似

Python的List如何实现?

  • 基于下标(位置)的高效率的元素访问和更新,时间复杂度要求为O(1),则需要采用顺序表技术,将列表中元素的指针保存在一块连续的存储区中
  • 允许存储不同类型的对象,则需要采用元素外置式的顺序表
  • 允许添加或删除元素,而且在不断新增元素后,列表对象的id(内存地址)不变,则需要采用分离式顺序表

所以,在Python的官方实现中,列表List是一种采用了元素外置的、分离式的动态顺序表。这也说明了,使用alist.append(item)在尾部插入元素比alist.insert(index, item)在指定位置插入元素效率高的原因

另外,Python中的List扩充元素存储区的策略为: 如果建立的列表很小(或空列表)时,默认分配8个元素(存储指向实际数据对象的内存地址,4个字节)的存储区; 需要扩充时,更换为4倍大小的连续存储区; 但是如果列表已经很大了(比如50000个元素时),则改变策略,只增加1倍空间,引入这种改变策略的方式,是为了避免出现过多空闲的存储位置

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3数据结构01 - 顺序表

分享

作者

作者头像

Madman

如果博文内容有误或其它任何问题,欢迎留言评论,我会尽快回复; 或者通过QQ、微信等联系我

0 条评论

暂时还没有评论.

发表评论前请先登录