2.2　线性表的顺序存储结构

2.2.1　线性表的顺序存储结构

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素,使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。

假设线性表中有n个元素,每个元素占k个单元,第一个元素的地址为LOC（a₁）,则可以通过如下公式计算出第i个元素的地址。

LOC（a_i）＝LOC（a₁）＋（i－1）×k

其中,LOC（a₁）称为基地址。顺序表存储结构示意图如图2－2所示。

图2－2　顺序表存储结构示意图

顺序存储结构可以借助于高级程序设计语言中的一维数组来表示,一维数组的下标与元素在线性表中的序号相对应。线性表的顺序存储结构可用C语言定义如下。

说明:

（1）elemtype数据类型是为了统一的描述而自定义的,在实际应用中,用户可根据自己实际需要而定义顺序表中数据元素的数据类型。例如:int、float或某种结构体类型等。

（2）在上述描述中,由于a为一个数组类型,故第一个元素为a[0]而非a[1],存储空间为a[0]～a[MAXSIZE]而非a[1]～a[MAXSIZE],故不使用a[0]。这样,在线性表中序号值为i,在顺序表对应的数组a中的下标也为i。

利用顺序表的数据类型struct seqList就可以定义变量了,变量L的定义方法有以下两种。

（1）通过变量定义语句来定义,具体语句如下。

structseqListL；

可利用L.a[i]来访问顺序表中序号为i的元素a_i。则L.a[last]为最后一个元素,L.last为顺序表的长度。

（2）通过指针变量定义语句来定义,具体语句如下。

structseqList *L；

可利用L－＞a[i]来访问顺序表中序号为i的元素a_i。则L－＞a[last]表示最后一个元素,L－＞last表示顺序表的长度。

2.2.2　顺序表运算

1.置空表运算

置空表运算的算法如下。

2.求线性表的长度

求线性表长度的算法如下。

3.按序号查找

按序号查找运算可使用函数getdata（L,i）来查找线性表L中的第i个数据元素,其结果是L.a[i]或L－＞a[i]。

顺序表的按序号查找运算的算法如下。

4.按内容查找

按内容查找运算可使用函数locate（L,x）来查找线性表L中与给定值x相等的数据元素,即从第一个元素开始,依次将表中元素与x相比较。若在线性表L中找到与x相等的元素,则返回该元素在表中的序号；若找不到相等的元素,则返回一个“空序号”,如－1。其具体算法如下。

5.插入运算

线性表的插入运算是指在表的第i（1≤i≤n＋1）个位置,插入一个新元素x,使长度为n的线性表（e₁,…,e_i－1,e_i,…,e_n）变成长度为n＋1的线性表（e₁,…,e_i－1,x,e_i,…,e_n）。用顺序表作为线性表的存储结构时,由于结点的物理顺序必须和结点的逻辑顺序保持一致,因此,必须将原表中位置n,n－1,…,i上的结点,依次后移到位置n＋1,n,…,i＋1上,空出第i个位置,然后在该位置上插入新结点x。当i＝n＋1时,是指在线性表的末尾插入结点,所以无须移动结点,直接将e插入表的末尾即可。

【例2－1】　已知线性表（4,9,15,28,30,30,42,51,62）,需在第4个元素之前插入一个元素“21”,则需要将第9个位置到第4个位置的元素依次后移一个位置,然后将“21”插入到第4个位置,如图2－3所示。请注意区分元素的序号和数组的下标。

图2－3　顺序表插入元素前后的状态

在顺序表中插入一个数据元素时,其时间主要耗费在移动数据元素上。设P_i为在第i个位置插入元素的概率,并假设在任何位置上插入元素的概率相等,即

P_i＝1/（n＋1）　i＝1,2,…,n＋1

设E_ins为在长度为n的表中插入一个元素所需移动元素的平均次数,则

可以看出,当i＝L－＞last＋1时,语句L.a[k＋1]＝L.a[k]将不会执行,因为循环的终值大于初值,此时不需要移动元素,可直接在表尾插入x。当i＝1时,语句L.a[k＋1]＝L.a[k]需执行n次,即将表中已存在的n个元素依次后移一个位置才能将x插入。因此,语句L.a[k＋1]＝L.a[k]的频度与插入位置i有关。

6.删除运算

线性表的删除运算是指将表中的第i（1≤i≤n）个元素删去,使长度为n的线性表（e₁,…,e_i－1,e_i,e_i＋1,…,e_n）变成长度为n－1的线性表（e₁,…,e_i－1,e_i＋1,…,e_n）。

【例2－2】　线性表（4,9,15,21,28,30,30,42,51,62）,若删除第5个元素,则需将第6个元素到第10个元素依次向前移动一个位置,如图2－4所示。

图2－4　顺序表删除前后的状态

具体算法如下。

与插入运算类似,在顺序表上实现删除运算也必须移动结点,这样才能反映出结点间的逻辑关系的变化。

同理,设Q_i为删除第i个元素的概率,并假设在任何位置上删除的概率相等,即

Q_i＝1/n,　i＝1,2,…,n

删除一个元素所需移动元素的平均次数E_del为

可以看出,若i＝L－＞last,则移位语句L.a[k－1]＝L.a[k]不执行,因为循环变量的初值大于终值,此时不需要移动元素,仅将表长度减1即可。显然,删除算法中移位语句L.a[k－1]＝L.a[k]的执行频度也与删除位置i有关。

这说明,在顺序表中进行一次插入或删除操作平均要移动一半的元素。两个算法的执行时间均为O（n）。

【例2－3】　有两个顺序表LA和LB,其元素均为非递减有序排列。编写一个算法,将它们合并成一个顺序表LC,要求LC也是非递减有序排列。例如,LA＝（1,2,5）,LB＝（1,3,4,7）,则LC＝（1,1,2,3,4,5,7）。

【算法思想】　设表LC是一个空表,为使LC也是非递减有序排列,可设置两个指针i、j分别指向表LA和表LB中的元素。若LA－＞a[i]＞LB－＞a[j],则当前先将LB－＞a[j]插入到表LC中；若LA－＞a[i]≤LB－＞a[j],则当前先将LA－＞a[i]插入到表LC中。如此进行下去,直到其中一个表被扫描完毕,然后再将未扫描完的表中剩余的所有元素放到表LC中,具体程序如下。

由上面的讨论可知,线性表顺序表示的优点如下。

（1）无须为表示结点间的逻辑关系而增加额外的存储空间（因为逻辑上相邻的元素其存储的物理位置也是相邻的）。

（2）可以很方便地随机存取表中的任一元素。

线性表顺序表示的缺点如下。

（1）插入或删除运算不方便,除表尾的位置外,在表的其他位置上进行插入或删除操作都必须移动大量的结点,其效率较低。

（2）由于顺序表要求占用连续的存储空间,其存储分配只能预先进行静态分配,因此当表长变化较大时,难以确定合适的存储规模。若按可能达到的最大长度预先分配表空间,则可能造成一部分空间长期闲置而得不到充分利用；若事先对表长估计不足,则插入操作可能使表长超过预先分配的空间而造成溢出。