Python3数据结构01 - 顺序表

  • 原创
  • Madman
  • /
  • /
  • 0
  • 2198 次阅读

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)

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

分享

作者

作者头像

Madman

如需 Linux / Python 相关问题付费解答,请按如下方式联系我

0 条评论

暂时还没有评论.

专题系列