文章目录
- 一、顺序表的概念
- 二、顺序表的实现
- 1. 顺序表的创建
- 1.1 扩容
- 1.2 整体建立顺序表
- 2. 顺序表的基本运算算法
- 2.1 顺序表的添加（尾插）
- 2.2 指定位置插入
- 2.3 指定位置删除
- 2.4 顺序表的查找
- 2.5 顺序表元素的索引访问
- 2.6 顺序表元素的修改
- 2.7 顺序表长度
- 2.8 顺序表的输出
- 三、完整代码
- 四、代码验证
一、顺序表的概念
顺序表是一种线性的数据结构，其中数据元素按照特定的顺序依次存储在连续的内存空间中。它由一系列元素组成，每个元素都与唯一的索引（或者叫下标）相关联，索引从 0 开始递增。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
下面这张图中，最下面那行数字0~9代表的是元素的索引，天蓝色的柱子中的数字代表的是顺序表中的元素，顺序表中的元素必须是同一数据类型的，数据类型可以是整数、浮点数、字符串等等。
二、顺序表的实现
设计顺序表类为SqList，主要包含存放元素的data列表和表示实际元素个数的size属性。因为Python属于弱类型语言，没必要专门设计像C++或则Java中的泛型类，在应用SqList时可以指定其元素为任意合法数据类型。
创建顺序表类：
# 顺序表类 class SqList: # 初始化 def __init__(self): self.initcapacity = 5 # 初始容量设置为5 self.capacity = self.initcapacity # 容量设置为初始容量 self.data = [None] * self.capacity # 设置顺序表的空间 self.size = 0 # 长度设为01. 顺序表的创建
1.1 扩容
顺序表在实现各种基本运算如插入和删除时会涉及到容量的更新，所以要设计一个方法将data列表的容量改变为newcapacity。
# 扩容 def resize(self, newcapacity): # 改变顺序表的容量为newcapacity assert newcapacity >= 0 oldata = self.data self.data = [None] * newcapacity self.capacity = newcapacity for i in range(self.size): self.data[i] = oldata[i]这里就是先让olddata指向data，为data重新分配一个容量为newcapacity的空间，再将olddata中的所有元素复制到data中，复制中所有的元素的序号和长度size不变。原data空间会被系统自动释放掉。
1.2 整体建立顺序表
该方法就是从空顺序表开始，由含若干个元素的列表a的全部元素整体创建顺序表，即依次将a中的元素添加到data列表的末尾，当出现上溢出时按实际元素个数size的两倍扩大容量。
# 整体创建顺序表 def CreateList(self, a): # 有数组a中的元素整体建立顺序表 for i in range(0, len(a)): if self.size == self.capacity: # 出现上溢出时 self.resize(2 * self.size) # 扩容 self.data[self.size] = a[i] self.size += 1 # 添加后元素增加1时间复杂度为O（n）， n表示顺序表中的元素个数。
2. 顺序表的基本运算算法
2.1 顺序表的添加（尾插）
将元素e添加到顺序表的末尾：Add（e）
在data列表的尾部插入元素e，在插入中出现上溢出时按实际元素个数size的两倍扩大容量。
# 顺序表的添加（尾插） def Add(self, e): # 在线性表的末尾添加一个元素 if self.size == self.capacity: self.resize(2 * self.size) # 顺序表空间满时倍增容量 self.data[self.size] = e # 添加元素e self.size += 1 # 长度加1该算法中调用一次resize（）方法的时间复杂度为O（n），但n次Add操作仅需要扩大一次data空间，所以平均时间复杂度仍然为O（1）。
2.2 指定位置插入
在顺序表中插入e作为第i个元素：Insert（i，e）
在顺序表中序号i的位置上插入一个新元素e。若参数i合法（0
