2.2 线性表的顺序存储及其实现
2.2.1 线性表的顺序存储
1．顺序表的定义
所谓顺序表就是顺序存储的线性表。顺序存储是用一组地址连续的存储单元依次存放线性表中各个数据元素的存储结构，如图2-2所示。
图2-2 线性表的顺序存储结构
假设线性表的数据元素类型为ElemType，则每个数据元素所占用的存储空间大小为sizeof（ElemType），长度为n的线性表所占用的存储空间大小为n×sizeof（ElemType）。
2．顺序存储中数据元素的地址计算公式
因为线性表中所有数据元素的类型是相同的，所以每一个数据元素在存储器中占用相同大小的空间。假设每一个数据元素占C个存储单元，且a1的存储地址为Loc（a1）（线性表的基地址），则根据顺序存储的特点可得出第i个数据元素的地址计算公式为
以上表明，只要知道顺序表的基地址和每一个数据元素所占存储空间大小，就可以计算出线性表中任何位序号上的数据元素的存储地址。由此可知：线性表的顺序存储结构是一种随机存取的存储结构。
3．线性表顺序存储的特点
（1）在线性表中，逻辑上相邻的数据元素，在物理存储位置上也是相邻的。
（2）存储密度高。
在线性表的顺序存储结构中，只要存放数据元素值本身，其数据元素之间的逻辑关系是通过物理上的存储位置关系来反映的，所以，数据元素的存储密度为1。
（3）便于随机存取。在线性表基地址已知的情况下，只要明确数据元素在线性表中的位序号就可由式2-1方便地计算出该元素在顺序存储中的地址。计算机根据地址就可快速对该地址空间中的元素进行读与写。
上述特点，可谓是线性表顺序存储的优点，但它也存在不尽如人意的地方：
（1）要预先分配“足够应用”的存储空间，这可能会造成存储空间的浪费，也可能会造成空间不够实际应用而需要再次请求增加分配空间，从而扩充存储容量。
（2）不便于插入和删除操作。这是因为在顺序表上进行插入和删除操作时，为了保证数据元素的逻辑位置关系与存储位置关系一致，则必然会引起大量数据元素的移动。如图2-2所示，要在这个顺序表中第i个位置前插入一个新元素，则一定要将第i个元素及其之后的所有元素都先往后移一位，使第i个存储单元腾空后才能将新元素插入。
4．顺序存储结构的描述
高级程序设计语言在程序编译时会为数组类型的变量分配一片连续的存储区域，数组元素的值就能依次存储在这片存储区域中；其次，数组类型也具有随机存取的特点。因此，可用数组来描述数据结构中的顺序存储结构，其中数组元素的个数对应于存储区域的大小，且应根据实际需要定义为“足够大”，假设为MAXSIZE（符号常量）。考虑到线性表的实际长度是可变的，故还需用一个变量length来记录线性表的当前长度。下述类型说明就是线性表的静态顺序存储结构描述。
#defineMAXSIZE 80 //线性表预分配空间的容量
typedef int ElemType； //为方便后续算法的描述，将ElemType类型自定义为int类型
typedef struct {
ElemType elem[MAXSIZE]； //线性表的存储空间
int Length； //线性表的当前长度
}SqListTp；
根据上述描述，对于线性表L={34，12，25，61，30，49}，其顺序存储结构可用图2-3表示。
图2-3 线性表L={34，12，25，61，30，49}的顺序存储结构
由于在C语言中数组空间是在程序编译时分配的，所以线性表上面描述的顺序存储空间被称为静态顺序存储空间。它的容量在程序运行时是不能够根据需要进行动态增加的，这就不能满足线性表的长度在实际应用时是动态变化的需求。为此，可以使用动态的顺序存储空间来存储线性表。下述类型说明就是动态顺序存储结构的描述：
C0 2-2-1
#define LIST_INIT_SIZE 80 //线性表初始分配空间的容量
#define LISTINCREMENT 10 //线性表增加分配空间的量
typedef int ElemType；
typedef struct {
ElemType *elem； //线性表的存储空间基地址
int length； //线性表的当前长度
int listsize； //线性表当前的存储空间容量
}SqList；
其中常量LIST_INIT_SIZE设定为线性表初始分配空间的容量，而常量LISTINCREMENT是在线性表需扩充空间时，而设定的增加分配空间的量。与静态顺序存储结构的描述相比，动态顺序存储结构描述中elem是用来存储连续存储空间的基地址，listsize是用来记载当前为线性表分配空间的容量值。开始时它们的值并未确定，只有在程序运行时，当为线性表分配了具体大小的存储空间后才能确定其值，并且其空间容量在程序运行时也可以根据需要进行动态的增加，从而克服了静态顺序存储结构的不足。
对于线性表L={a1，a2，…，ai，…，an}，其动态顺序存储结构如图2-4所示。
图2-4 线性表L={a1，a2，…，ai，…，an}的顺序存储结构
特别说明：
（1）本书后面的顺序存储结构全部采用动态顺序存储结构描述。
（2）对于已知如图2-4所示的顺序表L，其存储空间基地址的直接访问形式为L.elem；第i个数据元素ai的直接访问形式为L.elem[i-1]（注意元素在表中的位序号与在数组中下标之间的差别）；表长的直接访问形式为L.length；预分配空间容量的直接访问形式是L.listsize。
2.2.2 顺序表上基本操作的实现
从上述线性表的顺序存储结构示意图或特别说明中的内容可知，对顺序表的清空、判空、求长度和取第i个元素的操作都非常容易实现，算法简单。因此，下面只介绍顺序表的初始化、插入、删除和查找操作的实现算法。
1．顺序表的初始化操作
顺序表的初始化操作InitList（&L）的基本要求是创建一个空的顺序表L，也就是一个长度为0的顺序表。其存储结构如图2-5所示。要完成此操作的主要步骤可归纳如下：
图2-5 顺序表插入前、后的存储结构状态
（1）分配预定义大小的数组空间。数组空间用于存放线性表中各数据元素，分配空间可用C语言中的库函数malloc来实现，空间的大小遵守“足够应用”的原则，可通过符号常量LIST_INIT_SIZE的值进行预先设定。
（2）如果空间分配成功，则置当前顺序表的长度为0，置当前分配的存储空间容量为预分配空间的大小。
【算法2-4】顺序表的初始化操作算法
Status InitList（SqList&L）
//创建一个空的顺序表L
//分配预定义大小的存储空间
{ L.elem=（Elem Type*）malloc（LIST_INIT_SIZE*sizeof（ElemType））；
if（! L.elem） //如果空间分配失败
exit（OVERFLOW）；
L.length=0； //置当前顺序表的长度为 0
L.listsize=LIST_INIT_SIZE； //置当前分配的存储空间容量为LIST_INIT_SIZE的值
return OK；
}//算法2-4 结束
2．顺序表上的插入操作
顺序表上进行插入操作ListInsert（&L，i，e）的基本要求是在已知顺序表L上的第i个数据元素ai之前插入一个值为e的数据元素，其中1≤i≤L.length+1。当i=1时，在表头插入e；当i=L.length+1时，在表尾插入e。插入操作后顺序表的逻辑结构由原来的（a1，a2，…，ai，ai+1，…，an）变成了（a1，a2，…，ai-1，e，ai，…，an），且表长增加1，如图2-5所示。
根据顺序表的存储特点，逻辑上相邻的数据元素在物理上也是相邻的，要在数据元素ai之前插入一个新的数据元素，则需将第i个数据元素ai及之后所有的数据元素后移一个存储位置，再将待插入的数据元素插入到腾出的存储位置上。下面将顺序表上的插入操作的主要步骤归纳如下：
（1）插入操作的合法性判断。在进行插入操作之前需对插入位置i的合法性和存储空间是否满进行判断。若i不合法，即i＜1或i＞L.length+1，则以操作失败结束算法；若当前存储空间已满，即当前存储空间中存放数据元素的个数大于或等于当前存储空间的容量（L.length＞=L.listsize）时，则需对线性表的存储空间进行扩充，扩充后再进行以下操作。
（2）确定插入位置。说明：此操作的插入位置在已知条件中已明确规定是i。若将操作要求改为在有序的顺序表中插入一个值为e的数据元素时，则插入位置必须经过一定次数的比较后才能确定。
（3）将插入位置及其之后的所有数据元素后移一个存储位置。
注意：必须先从最后一个数据元素开始依次逐个进行后移，直到第i个数据元素移动完毕为止。
（4）表长加1。
C0 2-2-2
【算法2-5】顺序表的插入操作算法
1 Status ListInsert（SqList&L，int i，ElemType e）
2 //在顺序表L的第i个元素之前插入新的元素e，其中 1≤i≤L.length+1
3 { ElemType *newbase，*p，*q；
4 if（i ＜ 1||i ＞ L.length+1） //如果插入位置i不合法
5 return ERROR；
6 if（L.length ＞=L.listsize） //当前存储空间已满，则增加分配以扩充空间
7 { newbase=（ElemType*）realloc（L.elem，（L.listsize+LISTINCREMENT）*sizeof（ElemType））；
8 if（! newbase） //如果空间分配失败
9 exit（OVERFLOW）；
10 L.elem=newbase； //修改增加空间后的基址
1 1 L.l istsize+=LISTINCREMENT； //修改增加空间后的存储空间容量
12 }
13 q=&（L.elem[i-1]）； //q指示插入位置
14 for（p=&（L.elem[L.length-1]）；p＞=q；--p）//p始终指示待移动的元素
15 *（p+1）=*p； //插入位置及其之后的所有元素后移一位
1 6 *q=e； //e插入腾空的位置
17 ++L.length； //表长增 1
18 return OK；
19 }//算法2-5 结束
算法2-5与下面的算法2-6实现的功能是等价的。前者在算法中是通过指针来间接访问到数据元素，而后者在算法中是通过数组元素的访问形式直接访问到数据元素，读者可以根据自己的理解选择使用。
【算法2-6】顺序表的插入操作算法
1 Status ListInsert_1（SqList&L，int i，ElemType e）
2 //在顺序表L的第i个数据元素之前插入新的元素e，其中 1≤i≤L.length+1
3 { ElemType *newbase；
4 if（i＜1||i＞L.length+1） //如果插入位置i不合法
5 return ERROR；
6 if（L.length＞=L.listsize） //当前存储空间已满，则增加分配以扩充空间
7 {newbase=（ElemType*）realloc（L.elem，（L.listsize+LISTINCREMENT）*sizeof（ElemType））；
8 if（! newbase） //如果空间分配失败
9 exit（OVERFLOW）；
10 L.elem=newbase； //修改增加空间后的基址
1 1 L.l istsize+=LISTINCREMENT；//修改增加空间后的存储空间容量
12 }
13 for（int j=L.length-1；j＞=i-1；j--）
14 L.elem[j+1]=L.elem[j]； //将插入位置及其之后的所有元素后移一位
15 L.elem[i-1]=e； //e插入腾空的位置
16 L.length++； //表长增 1
1 7 return OK；
18 }//算法2-6 结束
顺序表上的插入操作算法，其执行时间主要花费在数据元素的移动上，即算法2-5中的第15行和算法2-6中的第14行语句的执行上，所以此语句的操作是该算法的关键操作。若顺序表的表长为n，要在顺序表的第i（1 ≤i≤n+1）个数据元素之前插入一个新的数据元素，则第15行或第14行语句的执行次数为n-i+1，即会引起n-i+1个数据元素向后移动一个存储位置，所以算法中数据元素移动的平均次数为
其中：pi是在顺序表的第i个存储位置之前插入数据元素的概率。假设在任何位置上插入数据元素的概率相等，即
，则式2-2可写成：
由式2-3可知，算法2-5与算法2-6的时间复杂度为O（n）。
3．顺序表上的删除操作
顺序表上的删除操作ListDelete（&L，i，&e）的基本要求是将已知顺序表L上的第i个数据元素ai从顺序表中删除，并用e返回被删元素的值。其中：1≤i≤L.length。
删除操作后会使顺序表的逻辑结构由原来的（a1，a2，…，ai-1，ai，，ai+1，…，an）变成（a1，a2，…，ai-1，ai+1，…，an），且表长减少1，如图2-6所示。
图2-6 顺序表删除前、后的存储结构状态
删除操作后为保持逻辑上相邻的数据元素在存储位置上也相邻，就要将第i个数据元素ai之后的所有数据元素都向前移动一个存储位置。下面将顺序表上的删除操作的主要步骤归纳如下：
（1）判断删除位置i的合法性，若i不合法，则以操作失败结束算法。
C0 2-2-3
说明：当1≤i≤L.length时为合法值。
（2）将第i个数据元素之后的所有数据元素向前移动一个存储位置。
（3）表长减1。
【算法2-7】顺序表的删除操作算法
1 Status ListDelete（SqList&L，int i，ElemType&e）
2 //删除顺序表L中的第i个数据元素，并用e返回其值，其中 1≤i≤L.length
3 { ElemType *p，*q；
4 if（（i ＜ 1）||（i ＞ L.length））//如果删除位置i不合法
5 return ERROR；
6 p=&（L.elem[i-1]）； //p先指示被删除元素的位置
7 e=*p； //被删除元素的值用e保存
8 q=L.elem+L.length-1； //q指示表尾元素的位置
9 for（++p；p ＜=q；++p） //p始终指示待移动的元素
1 0 *（p-1）=*p； //将被删元素之后的所有元素前移一位
1 1 --L.length； //表长减 1
12 return OK；
13 }//算法2-7 结束
注意：读者也可以按照算法2-6的实现方法来改写算法2-7，请思考并完成。其实本节中所有的基本操作算法都可以考虑用这两种方法来实现，下面也都只给出了其中一种实现算法。
在顺序表中删除一个数据元素，其执行时间仍然主要花费在数据元素的移动操作上，也就是算法2-7中第10行的语句的执行上。这里移动的数据元素的个数与插入操作中相似，取决于被删除元素的起始存储位置。在长度为n的顺序表上删除第i（1≤i≤n）个数据元素会引起n-i个数据元素发生移动，所以算法中数据元素移动的平均次数为
假设在任何位置上删除元素的概率相等，即
，则式2-4可写成：
由式2-5可知，算法2-7的时间复杂度仍为O（n）。
4 ．顺序表上的查找操作
查找操作一般有两种情况：一种是查找指定位置上的数据元素的值；另一种是查找满足指定条件的数据元素初次出现的位置。前者在顺序表的实现简单，用随机存取的方式就可找到对应的数据元素，时间复杂度为O（1）。对于后者的查找操作LocateElem（L，e）的基本要求是在顺序表L中查找值为e的数据元素初次出现的位置。该操作实现的方法是将e与顺序表的每一个数据元素依次进行比较，若经过比较相等，则返回该数据元素在顺序表中的位序号，若所有数据元素都与e比较且不相等，表明值为e的数据元素在顺序表中不存在，返回0。
【算法2-8】顺序表的查找操作算法
1 int LocateElem（SqList L，ElemType e）
2 //查找线性表L中值为e的数据元素，并返回线性表中首次出现指定数据元素e的位序号，若线性
表中不包含此数据元素，则返回 0
3 { int i；
4 for（i=1；i＜=L.length&&L.elem[i-1]!=e；i++）；
5 if（i＜=L.length）
6 return i；
7 else
8 return 0；
9 }//算法2-8 结束
此算法的执行时间主要体现在数据元素的比较操作上，即算法中第5行语句的执行时间，该执行时间取决于值为e的数据元素所在的存储位置。若顺序表中第i（1 ≤i≤n）个位置上的数据元素值为e，则需比较i次；若顺序表中不存在值为e数据元素，则需将顺序表中所有的数据元素都比较一遍后才能确定，所以需要比较n次。因此，在等概率条件下，数据元素的平均比较次数为
由式2-6可知，算法2-8的时间复杂度为O（n）。
5．顺序表的输出操作
输出操作DisplayList（L）的基本要求是将数组空间中的每个数据元素值依次输出。
【算法2-9】顺序表的输出操作算法
void DisplayList（SqList L）
//输出顺序表L中各数据元素值
{ for（int i=0；i＜=L.length-1；i++）
printf（"%4d"，L.elem[i]）；
printf（"\n"）；
}
//算法2-9 结束
此算法的时间复杂度为O（n）。
2.2.3 顺序表应用举例
对数据结构最常用的操作就是增、删、查，但在解决实际问题时，其具体操作的已知条件往往会发生变动，所以读者在理解顺序表上这三种基本操作的实现方法时，一定要抓住其通用性的主要操作步骤和每个步骤的实现方法是什么，这样才能灵活使用这些通用性的内容方法去解决其他一些实际问题。下面希望通过一些实例来进一步熟悉常用操作的通用性方法的套用。
【例2-4】已知一个有序顺序表L，设计一个算法在L中插入一个数据元素值为x的新元素，并使顺序表L仍然保持有序。
【分析】本题涉及的知识点是顺序表的插入操作。前面已经介绍过：若要在顺序表上实现插入操作，如果当前顺序表的存储空间未满，则主要操作步骤是先确定待插入的位置，再将插入位置及其之后的所有数据元素后移一位，然后将待插入的数据元素插入到空出的位置上，最后表长加1。这些步骤中最关键的是如何确定待插入的位置。假设顺序表是一种非递减的有序表，所以要确定待插入的位置可以有两种实现方法。方法一：从顺序表的表头开始依次往后将数据元素值与x进行比较，当数据元素值比x值小时，则继续往后进行比较，直至遇到一个值比x大或相等的数据元素为止，则此数据元素所处的位置就是x待插入的位置。方法二：从顺序表的表尾开始依次往前将数据元素值与x进行比较，当数据元素值比x的值大时，则继续往前进行比较，直至遇到一个值比x小或相等的数据元素为止，则此数据元素所处的位置的后面一个位置就是x待插入的位置。当待插入的位置确定后，则要进行数据元素的移动，由于数据元素的移动都是从表尾元素开始的，因而采用方法二时，可以在确定待插入位置的同时一边进行比较，一边进行移动，这样可以简化算法的描述形式并提高算法效率。
【算法2-10】例2-4中方法一的设计算法
Status SqListInsert_1（SqList&L，ElemType x）
{ int i； ElemType * newbase；
if（L.length＞=L.listsize） //若当前顺序表分配空间满，则追加分配
{ newbase=（ElemType*）realloc（L.elem，（L.listsize+LISTINCREMENT）*sizeof（ElemType））；
if（! newbase） //如果空间分配失败
exit（OVERFLOW）；
L.elem=newbase； //修改增加空间后的基址
L.l istsize+=LISTINCREMENT； //修改增加空间后的存储空间容量
}
for（i=0；i＜L.length&&L.elem[i]＜x；i++）；//确定插入位置
for（int j=L.length-1；j＞=i；j--） //插入位置i及其之后的所有元素后移一位
L.elem[j+1]=L.elem[j]；
L.elem[i]=x； //插入x
L.length++； //表长加 1
return OK；
}//算法2-1 0 结束
【算法2-11】例2-4中方法二的设计算法
Status SqListInsert_2（SqList&L，ElemType x）
{int i； ElemType *newbase；
if（L.length＞=L.listsize）//若当前顺序表分配空间满，则追加分配
{ newbase=（ElemType*）realloc（L.elem，（L.l istsize+LISTINCREMENT）*sizeof（ElemType））；
if（! newbase） //如果空间分配失败
exit（OVERFLOW）；
L.elem=newbase； //修改增加空间后的基址
L.l istsize+=LISTINCREMENT；//修改增加空间后的存储空间容量
}
for（i=L.length-1；i＞=0&&L.elem[i]＞x；i--）
L.elem[i+1]=L.elem[i]； //一边比较，一边进行后移
L.elem[i+1]=x； //插入x到第i+1个位置上
L.length++； //表长加 1
return OK；
}//算法2-1 1 结束
这两种算法的时间复杂度虽然都为O（n）（n为顺序表的表长），但算法2-10中有两个并列的for循环语句，而算法2-11中只有一个for循环语句，显然，后者运行时的时间开销更少。
【例2-5】已知一个顺序表L，设计一个算法删除L中数据元素值为x的所有元素，并使此操作的时间复杂度为O（n），空间复杂度为O（1），其中n为顺序表的长度。
【分析】本题涉及的知识点是顺序表的删除操作。如果这题没有时间复杂度限制的话，很容易想到下面这种方法：从顺序表的表头开始依次对每个数据元素进行扫描，如果遇到值为x的数据元素则将其删除，直到所有的数据元素都处理完为止。由于在顺序表中删除一个数据元素的时间复杂度为O（n），所以要对n个数据元素进行处理，时间复杂度为O（n2），所以这种设计思想是不符合题目要求的。下面介绍符合题目要求的一种设计思想：
先引进一个计数变量k，用来记录顺序表中值不等于x的数据元素的个数，初始值为0，然后从顺序表的表头开始依次对每个数据元素进行扫描，边扫描边统计，当统计到第k个值不等于x的数据元素时，则将其放置到第k个存储位置中，最后将顺序表的长度修改为k即可。
【算法2-12】例2-5的设计算法
Status SqListdel_x（SqList&L，ElemType x）
//删除当前顺序表中所有值为x的数据元素
{int k=0； //用k记录值不等于x的数据元素的个数
for（int i=0；i＜L.length；i++）
{ if（L.elem[i]!=x）
//将第k个值不等于x的数据元素放置到第k个存储位置中，然后k值加 1
{ L.elem[k++]=L.elem[i]；
}
}
L.length=k； //修改顺序表的长度为k
}//算法2-12 结束
从此算法的结构本身就可以知道它的时间复杂度为O（n），空间复杂度为O（1）。