2.3 性表的顺序存储结构★2◎3

2.3 线性表的顺序存储结构★2◎3

　　采用顺序存储结构的线性表，其数据元素都存储在一段连续的存储单元上，相邻的两个元素在存储位置上也相邻。
　　1．线性表的顺序存储结构表示
　　在高级语言中，通常采用数组来描述顺序存储的线性表，如下定义了一个数据元素为Elemtype的顺序存储线性表的例子：
　　
　　如图2-1所示是用以上结构描述“年份”线性表的例子：

　　在以上结构中，线性表的最多数据元素数为定值LISTMAXSIZE，数据元素数量不能随意增加，这是以数组方式描述线性表的缺点。为了实现线性表最大存储数据元素数可随意变化，可以使用一个动态分配的数组来取代上面的固定长度数组，如下所示：
　　
　　当线性表的数据元素数等于当前最大数据元素数（nLength==nSize）时执行增加元素操作，此时线性表将自动增加分配LISTSTEP个数据元素存储空间，并修改nSize取值“nSize = nSize + LISTSTEP”，从而满足无限增加数据元素的要求。
　　2．线性表的顺序存储结构寻址算法
　　线性表中每个元素的物理位置与其逻辑位置相关联，每个元素相对于线性表首物理地址的物理偏移量与其逻辑位置成正比，比如图2-1中，线性表首元素的地址是x，每个元素占用l字节的空间，那么计算线性表中第i个逻辑元素（从1开始计算）的物理地址的算法为：
　　物理地址＝线性表首地址+(逻辑序号－1)×单个元素空间=x+(i－1)×l
　　假设某顺序线性表首地址为“10000”，数据元素为整型，占用4字节空间，则其每个数据元素的首地址空间如表2-3所示。

表2-3 顺序线性表元素地址示意

元素序号	1（线性表头）	2	i	n（线性表尾）
首地址	10000	10004	10000+(i-1)×4	10000+(n-1)×4

　　顺序线性表的随机查找数据元素的时间复杂度是O(1)，即常数。
　　以下代码为读取顺序线性表中第i个元素（从1开始计数）的取值：
　　
　　3．线性表的顺序存储结构置空算法
　　将线性表的数据元素数量置为0即可，如以下代码所示：
　　
　　4．线性表的顺序存储结构插入算法
　　算法可以分为以下4步：
　　①确保线性表具有空闲且未使用的存储空间。
　　②将插入位置以后的所有数据元素依次向后移动一个存储单元。
　　③在插入位置更新存储的数据元素信息。
　　④将线性表当前数据元素数量（nLength）增加1。
　　例如，在空线性表中插入一个数据元素，插入前，当前数据元素量为0，插入后该值置为1，由于原线性表中不存在任何数据元素，故没有数据移动过程，如图2-2所示。

　　又如，在线性表（1997，1998，2001，2002，2003）的第3个元素位置处插入数据元素1999，插入前的线性表如同2-3（a）所示。插入后，原线性表中第3个元素之后（含第3个元素）的所有数据元素均向后移动一位，并且线性表当前数据元素个数（nLength）取值加1。插入后的线性表为（1997，1998，1999，2001，2002，2003），如图2-3（b）所示。
　　
　　以下代码在顺序存储线性表的第i个元素（从1开始计数）前插入一个数据元素：

　　
　　顺序存储线性表的插入过程涉及数据元素移动，在插入位置平均分布的情况下，具有n个元素的线性表，其插入位置和需要移动数据元素个数的关系如表2-4所示。

表2-4 线性表插入操作数据元素移动数量统计表

插入位置	1（线性表头）	2	i	n	n+1（线性表尾）
移动数量	n	n-1	n-i+1	1	0

　　顺序线性表插入操作平均移动数据元素次数为“n/2”，求解过程如下：

　　当在线性表尾插入时，不需要移动数据元素。
　　5．线性表的顺序存储结构删除算法
　　线性表的删除操作是插入操作的逆过程，算法也分为四步：
　　①确保删除元素位置正常。
　　②读取被删除元素信息。
　　③将删除位置之后的数据元素依次前移。
　　④将线性表当前数据元素数量（nLength）减小1。
　　例如，删除线性表（1997，1998，1999，2001，2002，2003）的第3个元素，删除前的线性表如同2-4（a）所示。删除后，原线性表中第3个元素之后的所有数据元素均向前移动一位，并且线性表当前数据元素个数（nLength）取值减1。删除后的线性表为（1997，1998，2001，2002，2003），如图2-4（b）所示。

　　
　　以下代码删除顺序存储线性表的第i个元素（从1开始计数）：
　　
　　顺序存储线性表的删除过程涉及数据元素移动，在删除位置平均分布的情况下，具有n个元素的线性表，其删除位置和需要移动数据元素个数的关系如表2-5所示。
　　

表2-5 线性表删除操作数据元素移动数量统计表

插入位置	1（线性表头）	2	i	n（线性表尾）
移动数量	n-1	n-2	n-i	0

　　顺序线性表删除操作平均移动数据元素次数为“(n-1)/2”，求解过程如下：

　　当在线性表表尾删除时，不需要移动数据元素。
　　6．线性表的顺序存储结构的特点
　　顺序结构存储线性表的特点有：
　　（1）支持随机查找，查找时间复杂度为常数。
　　（2）程序设计简单。
　　（3）需要一次性分配所需的存储空间，因此当线性表实际存储数未达到最大数据元素数时浪费了存储空间。
　　（4）除了在线性表表尾执行插入或删除操作外，在其他位置执行插入和删除操作都需要移动数据元素。
　　因此以顺序结构存储的线性表适用于数据元素总数固定，并只在线性表尾有插入和删除操作的应用中，比如栈等。

2.3 性表的顺序存储结构★2◎3