Python3数据结构01 - 顺序表
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)
分享
相关推荐
作者
0 条评论
评论者的用户名
评论时间暂时还没有评论.