线性表的Python描述

线性表概念

线性表可以看做抽象的数据类型。可以看做有穷个元素排列成的列表，这个列表可以包含零个或多个元素。
在一个非空的线性表中存在唯一的首元素和尾元素，除了首元素外其他任意元素都有一个前驱元素；处尾元素外其他任意元素都有后一个继元素。

线性表的基本操作：

判空is_empty(self)；长度len(self)；表前插入元素prepend(self, item)；表后插入元素append(self, item)；任意位置插入元素insert(self, elem, i)；删除第一个元素del_first(self)；删除最后一个元素del_last(self)；删除任意元素del(self, i)；查找任意元素search(self, i)；

线性表的实现方式

顺序表，链接表（链表）。顺序表是在内存中开辟一大块连续的空间作为存储区；而链表则是链接一系列的存储空间来存储元素

顺序表

顺序表的两种布局

顺序表的两种基本形式.png

a中顺序表对象的存储对象类型相同且存储区起始位置为l0，表元素地址计算公式为l0+c*i，其中i为存储对象的大小。对于不同占用不同内存大小的存储对象可以采用b方式。b顺序表各单元保存相应元素的引用信息，引用信息的大小是相同的。

基本操作

• 创建
  创建空表时，需要分配一块元素内存，记录表的容量并将元素计数设置为0。创建好存储去后应立即设置表的信息域。

• 加入元素
  顺序表增加元素.png

  不需要保留原有的顺序，操作时间复杂度为O(1)，保序时间复杂度为O(n)

• 删除元素
  顺序表增加元素.png

  尾部删除和非保序定位删除时间复杂度为O(1)，保序定位删除的时间复杂度为O(n)。

顺序表实现方式

顺序表两种基本的实现方式

1. 一体式存储表的信息与元素存储区连续的排列在一起，整体性强易于管理。表一旦创建存储区的大小确定，存储量满后需要重新创建一个更大的空间，需要修改原来元素的所有存储位置。
2. 分离式通过两个对象实现，创建和管理相对复杂。改变容量过程：
   • 申请更大的存储空间
   • 把表中已有的元素复制到新的存储区。
   • 用新的元素存储区替换原来的元素存储区
   • 加入新的元素

存储区的扩充策略

1. 固定扩充：操作次数多节约空间
2. 加倍扩充：空间换时间

Python中的list和tuple

python中的list和tuple都采用顺序表结构。其中tuple是不可变结构不支持内部操作。
list采用连续表（访问：O(1)时间复杂度，顺序不变），分离式技术（更换存储区id不变）

总结

1. 顺序表可以实现O(1)时间的元素访问。
2. 顺序表的建立需要提前考虑元素存储区的大小，一旦确定了存取块的大小，可容纳单元不会随着元素的插入/删除而改变。若存储块很大却只存储很少的元素会造成存储空间的浪费。
3. 插入或删除表元素需要移动表内的元素，效率低。