打开《Python 编程与应用实践》_成为Python大佬_9.1.2 线性表的顺序存储结构

【摘要】 本书摘自《Python 编程与应用实践》一书中第9章，第1节，由冯伟森，王建，杨宁主编。

9.1.2 线性表的顺序存储结构

顺序表是指顺序存储结构的线性表，指的是用一组地址连续的存储单元依次存储线性 表的数据元素。相邻的两个元素在物理位置上也是相邻的。

Python 内部的 tuple 与 list 采用的就是顺序表结构，其不同点在于tuple 是固定结构， 一旦创建就无法进行改动，而 list 支持变动操作，具有如图9-1所示的全部操作。

顺序表中最常见、最简单的一种情况就是表中只保存同种元素类型的数据，那么表中 每个元素存储时需要的存储空间也是相同的，这种安排可以使表中元素直接在内存中顺序 存储。

假设现有一顺序表第0个元素的存储位置为loc(0), 每个元素占用的空间为c=size(e), 那么第i 个元素的存储位置就是loc(i)=loc(0)+c* i, 此时实现对某个位置元素的访问， 表中任意元素位置可以直接计算出来，时间复杂度为O(1)。

图9 - 2(a) 为顺序表元素存储区的基本布局方式，表中元素的下标是该元素的逻辑 地址，元素的物理地址就是通过公式loc(i)=loc(0)+c*i 计算得到的。

当顺序表中的数据元素类型不相同时，顺序表元素存储区的布局方式又是什么样子的 呢?我们按照之前的方法，在顺序表中存放元素的存储位置，而元素另行存储，这个顺序 表就称作是这组数据的索引，这就是最简单的索引结构。如图9-2(b) 所示，索引顺序 表的每个元素为地址，占用空间一样，直接访问索引再依据索引中存放的地址找到实际元 素，时间复杂度依然为O(1)。

线性表除了有顺序储存结构外，还有链式存储结构，链式存储结构的线性表称为链 表，链表与顺序表的不同之处在于，顺序表储存数据是有序的而链表存储数据是无序的。 链表又可分为单链表和双链表。

9.1.3 线性表的链式存储结构

9.1.3.1 单链表

链表是一种动态数据结构，它是用一组任意的存储单元存放数据元素。链表中的每一 个元素称为“节点”,每个节点都是由数据域和指针域组成的。数据域用于存储我们要保 存的数据，指针域用于存储下一个数据元素的地址。我们可以通过首节点对整个链表进行 操作

我们使用一个变量来保存单链表的首节点的指针称为表头指针，通过表头指针就可以 对单链表进行一系列的操作。 一个非空的单链表中最后一个节点无后继元素，它的指针域 为None 值。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们 18664393530@aliyun.com 处理，核实后本网站将在24小时内删除侵权内容。