2.2.2　顺序表基本运算的实现

由于C语言中的一维数组也是采用顺序存储表示，故可以用C语言中动态分配的一维数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。顺序表的存储定义如下：

根据此定义，顺序表的初始化操作就是为顺序表分配一个容量为MAXSIZE大小的数组空间，并将线性表的当前长度length设为0。

现在介绍线性表在顺序存储结构上的运算，这些算法都是从下标0开始存放元素的。

1.查找操作

对于线性表的顺序存储结构来说，如果我们要实现查找操作，将第i个元素值返回是非常简单的。在程序里就是把数组第i－1下标的值返回。

算法2.1 查找位置的元素

算法2.1的时间复杂度是O（1）。思考一下：某个数据元素的值已经给出，要找到这个元素在线性表中的位置，如何实现？算法时间复杂度是多少？

2.插入操作

当需要在线性表的第i个位置上插入一个元素时，必须首先将线性表中原有的元素an，an－1，…，a1依次移到表中的第n＋1，n，…，i＋1各位置上，以便腾出一个空位置i，再把新元素存入该位置上，插入新元素以后，原来第i至第n个元素的序号自动变为i＋1，i＋2，…，n＋1，此时线性表的长度为n＋1。如果在第n＋1个位置上进行插入，则不需要移动表中原有的元素。插入工作的具体过程如图2－3所示。

图2－3 顺序表插入过程

图2－3所示为一个有8个数据元素的递增有序表，现在要插入一个值为25的元素，并要求插入后该表仍是有序的，因此，25必须插在24与28之间，而值为28、30、42和77的元素必须依次往后移动一个位置。在插入时我们还要考虑空间是不是足够，插入位置是不是合理。

根据图2－3可以总结出插入算法实现思想：

①判断表是不是已经满，如果已经满不能插入；

②判断位置是否合理，不合理提示错误；

③表不满并且插入位置合理，从最后一个元素到第i个位置元素依次后移；

④将元素插入第i个位置；

⑤表长加1。

算法2.2 向线性表中插入元素

3.删除操作

如果希望删除线性表中第i个元素x，这时需将第i＋1到第n个元素依次移至第i到第n－1的位置上。删除元素x之后，表中原有的第i＋1，i＋2，…，n个元素的序号自动变为i，i＋1，…，n－1，线性表的长度减1，改为n－1。如果删除的元素x为表中的第n个元素（最后一个元素），则不需要移动任何元素，只要将表的长度减1。若表中没有元素x，则删除工作什么事情也不做。若表中只有一个元素且它就是要删除的x，则删除后此表成为空表。

图2－4（a）展示了一个有8个元素的递增有序表。当删除元素24时，删除后的状态如图2－4（b）所示。从图中可以看到，元素28、30、42和77都向前移动了一个位置，且表长由8变为7。

图2－4 线性表的删除过程

根据图示可以总结出插入算法实现思想：

①判断表是不是空，如果空不能作删除操作；

②判断位置是否合理，不合理提示错误；

③表不空并且插入位置合理，从第i个位置到最后一个元素依次前移；

④表长减1。

算法2.3 删除算法

以上几个算法，查找算法时间复杂度O（1），插入和删除算法的执行时间均为O（n）。

最好的情况，元素插到最后一个位置，或者删除最后一个元素，此时时间复杂度是O（1），因为不需要移动元素。

最坏的情况，元素插到第一个位置或者删除第一个元素，所有的元素都要前移或者后移，这时时间复杂度是O（n）。

平均情况，根据概率原理，每个位置插入和删除的可能性是相同的，最终平均移动次数和最中间的元素移动次数相等，是（n－1）／2。

根据时间复杂度推导规则可以得出，平均时间复杂度是O（n）。

由此可见，对顺序分配的线性表，每插入或删除一个元素，大约需要移动表中的一半数据元素。若表的长度值n很大，且要求经常进行插入或删除运算，则相当费时间。但是这种存储结构简单，便于随机存取，因为没有类似于指针的辅助空间，所以存储空间的利用率很高。顺序表一般适用于表不大或插入、删除不频繁的情况。

4.顺序存储结构的优缺点

顺序存储结构的优缺点如表2－1所示。

表2－1 顺序存储结构的优缺点