Python数据结构与算法（二）----- 顺序表

一. 顺序表

1. 顺序表的基本形式

2. 顺序表的结构与实现

(1) 顺序表的结构

一个顺序表的完整信息包括两部分，一部分是表中的元素集合，另一部分是为实现正确操作而需记录的信息，即有关表的整体情况的信息，这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项。
（2）顺序表的两种基本实现方式

图a为一体式结构，存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。

一体式结构整体性强，易于管理。但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。

图b为分离式结构，表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。

（3）元素储存区扩充
每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置，这种策略可称为线性增长。

特点：节省空间，但是扩充操作频繁，操作次数多。

每次扩充容量加倍，如每次扩充增加一倍存储空间。

特点：减少了扩充操作的执行次数，但可能会浪费空间资源。以空间换时间，推荐的方式。（用空间换时间）

3. 顺序表的操作

1. 增加元素
   
   a. 尾端加入元素，时间复杂度为O(1)

b. 非保序的加入元素（不常见），时间复杂度为O(1)

c. 保序的元素加入，时间复杂度为O(n)

2. 删除元素
   
   a. 删除表尾元素，时间复杂度为O(1)

b. 非保序的元素删除（不常见），时间复杂度为O(1)

c. 保序的元素删除，时间复杂度为O(n)

4. Python中的顺序表

Python中的list和tuple两种类型用了顺序表的实现技术

1. list的基本实现技术
   （1）基于下标（位置）的高效元素访问和更新，时间复杂度应该是O(1)；
   为满足该特征，应该采用顺序表技术，表中元素保存在一块连续的存储区中。
   （2）允许任意加入元素，而且在不断加入元素的过程中，表对象的标识（函数id得到的值）不变。
   为满足该特征，就必须能更换元素存储区，并且为保证更换存储区时list对象的标识id不变，只能采用分离式实现技术。
   list就是一种采用分离式技术实现的动态顺序表