python 与 数据结构 第三章 线性表 （上）

Question

3.1 线性表抽象数据类型

ADT List:
  List(self)             # 一个表抽象数据类型
  is_empty(self)         # 判断 self 是否为一个空表
  len(self)              # 获得 self 的长度
  prepend(self, elem)    # 将元素 elem 加入表中作为第一个元素
  append(self, elem)     # 将元素 elem 加入表中作为最后一个元素
  insert(self, elem, i)  # 将 elem 加入表中作为第 i 个元素， 其他元素的顺序不变
  del_first(self)        # 删除表中的首元素
  del_last(self)         # 删除表中尾元素
  del(self)              # 删除表中第 i 个元素
  search(self, elem)     # 查找元素 elem 在表中出现的位置， 不出现时返回 -1
  forall(self, op)       # 对表中的每个元素执行操作 op

3.1.3 线性表实现：基本考虑

提出两种基本实现模型：

• 将表元素存放在一大块连续存储区里，称为顺序表（连续表)
• 将表元素存放在通过链接构造起来的一系列存储块里，称为链接表（链表）

3.2 顺序表实现

3.2.2 顺序表基本操作实现

• 创建和访问操作
  • 不修改表结构的操作只有两种模式，或者是直接访问 O(1), 或者是基于一个整形变量，按下标循环并检查处理 O(n)
• 变动操作：加入元素
  • 尾端加入新数据项：O(1)
  • 新数据存入元素存储区的第 i 个单位： O(n)
• 变动操作： 删除元素
  • 尾端删除数据： O(1)
  • 删除位置 i 的数据：O(1)
  • 基于条件的删除： O(n)

表的顺序实现（顺序表）的缺点：需要连续的存储区
如果连续的存储区容量不够的话，可以动态扩容，主要步骤如下

1. 另外申请一块更大的元素存储区
2. 把表中已有的元素复制到新存储区
3. 用新的元素存储区替换原来的元素存储区（改变表对象的元素区链接）
4. 实际加入新元素

3.2.4 Python 的 list

list 是一种采用分离式技术实现的动态顺序表，实际策略：在建立空表（或者很小的表）时，系统分配一块能容纳 8 个元素的存储区；在执行插入操作时，如果元素区满就换一块 4 倍大的存储区。但如果当时表很大，目前值为 50000，系统将改变策略，换存储区时容量加倍。