4.1.2 顺序表操作

在现实应用中，有两种实现线性表数据元素存储功能的方法，分别是顺序存储结构和链式存储结构。顺序表操作是最简单的操作线性表的方法，此方法的主要操作功能有以下几种。

（1）计算顺序表的长度。

数组的最小索引是0，顺序表的长度就是数组中最后一个元素的索引last加1。

（2）执行清空操作。

清空操作是指清除顺序表中的数据元素，最终目的是使顺序表为空，此时last等于−1。

（3）判断顺序表是否为空。

当顺序表的last为−1时，表示顺序表为空，此时会返回true；否则返回false，表示不为空。

（4）判断顺序表是否已满。

当顺序表已满时，last等于maxsize−1，此时会返回true；如果不满，则返回false。

（5）执行附加操作。

在顺序表不满的情况下进行附加操作，在表的末端添加一个新元素，然后将顺序表的索引last加1。

（6）执行插入操作。

在顺序表中插入数据的方法非常简单，只需要在顺序表的第i个位置插入一个值为item的新元素即可。插入新元素后，会使原来长度为n的表（a1，a2，…，ai−1，ai，ai+1，…，an）的长度变为（n+1），也就是变为（a1，a2，…，ai−1，item，ai，ai+1，…，an）。i的取值范围为1≤i≤n+1，当i为n+1时，表示在顺序表的末尾插入数据元素。

在顺序表中插入一个新数据元素的基本步骤如下。

① 判断顺序表的状态，判断是否已满和插入的位置是否正确。当表已满或插入的位置不正确时，不能插入。

② 当表未满且插入的位置正确时，将an～ai依次向后移动，为新的数据元素空出位置。在算法中用循环来实现。

③ 将新的数据元素插入到空出的第i个位置。

④ 修改last以修改表长，使其仍指向顺序表的最后一个数据元素。

在顺序表中插入数据的示意图如图4-1所示。

（7）执行删除操作。

可以删除顺序表中的第i个数据元素，删除后使原来长度为n的表（a1，a2，…,ai−1，ai，ai+1，…，an）变为长度为（n−1）的表，即（a1，a2，…，ai−1，ai+1，…，an）。i的取值范围为1≤i≤n。当i为n时，表示删除顺序表末尾的数据元素。

在顺序表中删除数据元素的基本流程如下。

① 判断顺序表是否为空，判断删除的位置是否正确。当表为空或删除的位置不正确时，不能删除。

② 如果表为空且删除的位置正确，将ai+1～an依次向前移动，在算法中用循环来实现移动功能。

③ 修改last以修改表长，使它仍指向顺序表的最后一个数据元素。

图4-2展示了在顺序表中删除元素的前后变化过程。图4-2中，表原来的长度是8，如果删除第5个元素E，在删除后为了满足顺序表的先后关系，必须将第6～8个元素（下标为5～7）向前移动一位。

（8）获取表元。

通过获取表元运算可以返回顺序表中第i个数据元素的值，i的取值范围是1≤i≤last+1。因为表中的数据是随机存取的，所以当i的取值正确时，获取表元运算的时间复杂度为O(1)。

（9）按值查找。

所谓按值查找，是指在顺序表中查找满足给定值的数据元素。给定值就像住址的门牌号一样，必须具体到某单元某室，否则会找不到。按值查找就像Word中的搜索功能一样，可以在繁多的文字中找到需要查找的内容。在顺序表中找到给定值的基本流程如下所示。

① 从第一个元素起，依次与给定值进行比较，如果找到，返回在顺序表中首次出现的与给定值相等的数据元素的序号，称为查找成功。

② 如果没有找到，说明在顺序表中没有与给定值匹配的数据元素，返回一个特殊值来表示查找失败。