2.2　线性表的顺序表示与实现

视频二维码（扫码观看）

一、线性表的顺序存储结构

顺序存储：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。

顺序存储的线性表的特点：

①线性表的逻辑顺序与物理顺序一致；

②数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。

设有非空的线性表：（a₁，a₂，…，a_n）。顺序存储如图2-1所示。

图2-1　线性表的顺序存储表示

在具体的机器环境下：设线性表的每个元素需占用1个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i＋1个数据元素的存储位置Loc（a_i＋1）和第i个数据元素的存储位置Loc（a_i）之间满足下列关系：Loc（a_i＋1）＝Loc（a_i）＋1。

线性表的第i个数据元素a_i的存储位置为：Loc（a_i）＝Loc（a₁）＋（i－1）*l

在高级语言（如C语言）环境下：数组具有随机存取的特性，因此，借助数组来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度的属性，所以用结构类型来定义顺序表类型。

二、顺序表的基本操作

顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、插入、删除、求长度等。

1顺序线性表初始化

2顺序线性表的插入

在线性表L＝（a₁，…，a_i－1，a_i，a_i＋1，…，a_n）中的第i（1≤i≤n）个位置上插入一个新结点e，使其成为线性表：L＝（a₁，…，a_i－1，e，a_i，a_i＋1，…，a_n）

（1）实现步骤

①将线性表L中的第i个至第n个结点后移一个位置。

②将结点e插入到结点a_i－1之后。

③线性表长度加1。

（2）算法描述（假定下标从1开始，与上述L一致）

（3）时间复杂度分析

在线性表L中的第i个元素之前插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。

设在线性表L中的第i个元素之前插入结点的概率为P_i，不失一般性，设各个位置插入是等概率，则P_i＝1/（n＋1），而插入时移动结点的次数为n－i＋1。总的平均移动次数：E_insert＝∑P_i*（n－i＋1）（1≤i≤n），因此E_insert＝n/2。

即在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O（n）。

3顺序线性表的删除

在线性表L＝（a₁，…，a_i－1，a_i，a_i＋1，…，a_n）中删除结点a_i（1≤i≤n），使其成为线性表：

L＝（a₁，…，a_i－1，a_i＋1，…，a_n）

（1）实现步骤

①将线性表L中的第i＋1个至第n个结点依此向前移动一个位置。

②线性表长度减1。

（2）算法描述

（3）时间复杂度分析

删除线性表L中的第i个元素，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。

设在线性表L中删除第i个元素的概率为P_i，不失一般性，设删除各个位置是等概率，则P_i＝1/n，而删除时移动结点的次数为n－i。则总的平均移动次数：E_delete＝∑P_i*（n－i）（1≤i≤n），因此E_delete＝（n－1）/2。

即在顺序表上做删除运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O（n）。

4顺序线性表的查找定位删除

在线性表L＝（a₁，a₂，…，a_n）中删除值为x的第一个结点。

（1）实现步骤

①在线性表L查找值为x的第一个数据元素；

②将从找到的位置至最后一个结点依次向前移动一个位置；

③线性表长度减1。

（2）算法描述

（3）时间复杂度分析

时间主要耗费在数据元素的比较和移动操作上。首先，在线性表L中查找值为x的结点是否存在；其次，若值为x的结点存在，且在线性表L中的位置为i，则在线性表L中删除第i个元素。

设在线性表L删除数据元素概率为P_i，不失一般性，设各个位置是等概率，则P_i＝1/n。

比较的平均次数为

因此E_compare＝（n＋1）/2。

删除时平均移动次数为

因此E_delete＝（n－1）/2。

平均时间复杂度：E_compare＋E_delete＝n，即为O（n）。