1.2 性表的实现

1.2 线性表的实现

　　线性表的存储结构有多种方式，包括顺序存储结构的无序顺序表和有序顺序表，链式存储结构的单链表、双链表和循环链表等。

1.2.1 顺序存储结构

　　采用顺序存储结构存储的线性表简称为顺序表，它采用一组地址连续的存储单元依次存放线性表中的数据元素，如图1-1所示。

　　顺序表具有以下3个特点：
　　① 所有的数据元素存储在同一个区域内，而此区域也只存储该线性表的数据元素。
　　② 数据元素的存储地址与其在线性表中的顺序相同。假设线性表中存在元素a_i和a_j（i<j），即线性表中a_i在a_j之前，则a_i的存储地址也将在a_j之前。线性表的头元素存储在所有数据元素的最前面，尾元素存储在所有数据元素的最后面。
　　③ 线性表中逻辑上相连的两个数据元素的物理存储地址也相连。假设线性表中存在元素a_i和a_i+1（1<i<n），即a_i是a_i+1的直接前驱，a_i+1是ai的直接后继，那么a_i与a_i+1的物理存储地址相连，即a_i后面直接存储a_i+1。
　　在顺序表的连续地址存储空间中存在一个首地址，称为该线性表的基地址，它存储了线性表中的第一个数据元素。
　　1．顺序存储结构的定义
　　在高级语言中，由于数组具有连续空间和随机访问的特性，因此，一般采用数组来描述顺序存储的线性表，如下定义了一个数据类型为Elemtype的顺序存储线性表的例子：
　　
　　在上述定义中，成员变量Elem存储了线性表的数据元素信息，其中数组名Elem描述了连续地址空间的首地址，成员变量nLength描述了线性表的长度。
　　【例1-1】已知线性表如下所示，采用结构LIST存储，请画出其示意图：
　　（2000，2001，2002，2003，2004，2005，2006，2007，2008，2009）
　　【解析】如图1-2所示，Elem是线性表的基地址，nLength即表明线性表中当前数据元素数为10，又指向下一个数据元素存储的位置Elem[10]（C语言数组从0开始记数，Elem[10]表示数组中第11个元素）。

　　结构LIST采用静态数组简单地描述一个线性表，但也有一个很大的缺陷，就是其描述线性表的最大元素的个数为定值（LISTMAXSIZE），不能随意增加，这将造成线性表元素的无限增长与线性表最大空间有限之间的矛盾，从而影响了其应用范围。
　　2．顺序存储结构的元素寻址
　　线性表中每个元素的物理位置与其逻辑位置存在关联关系，定义LOC(a_i)为数据元素ai的物理地址，那么基地址的取值为LOC(a₁)，即元素a₁的物理地址。设每个数据元素占用k个字节空间，那么每个元素的物理地址如表1-2所示。

表1-2 顺序存储线性表数据元素物理地址

　　从表1-2中可以看出，线性表中每个元素相对于线性表基地址的物理偏移量与其逻辑位置成正比。假设线性表基地址为LOC(a₁)，每个数据元素占用k个字节的空间，那么线性表中逻辑第i个元素a_i的物理地址的推导公式为：

LOC(a_i) = LOC(a_i-1)+k = LOC(a_i-2)+k+k = LOC(a_i-3)+3×k
　　= LOC(a_i-4)+4×k = …
　　= LOC(a₁)+(i-1)×k

　　其中，LOC(a₁)是基地址，所以，逻辑第i个元素a_i的物理地址为：

物理地址 = 线性表基地址+(逻辑序号-1)×单个元素空间

　　【例1-2】某顺序存储的线性表，最多可存储100个数据元素，其基地址为10000，数据元素为整型，每个数据元素占用4个字节空间，求其逻辑第1、2、i个和最后一个数据元素的地址。
　　【解析】可根据元素物理地址计算公式求解。
　　第1个元素的物理地址：LOC(a₁) = 10000
　　第2个元素的物理地址：LOC(a₂) = 10000+4
　　第i个元素的物理地址：LOC(a_i) = 10000+(i-1)×4
　　最后一个元素的物理地址：LOC(a₁₀₀) = 10000+(100-1)×4
　　3．顺序存储结构的操作算法
　　由于数组的随机访问特性，采用数组存储的顺序结构线性表的元素定位和读取操作显得特别简单，例如，第i个元素a_i可表示为“L.Elem[i-1]”。
　　① 初始化、销毁和置空算法。对于采用静态数组（例如，LIST结构）描述的线性表，只需将其数据元素数量变量（即表长变量）强行置为0即可：
　　
　　而对于采用动态数组（例如，LISTEXT结构）描述的线性表，则还需要申请或释放空间和清零等操作。例如，初始化代码如下：
　　
　　② 获取长度算法。直接读取长度变量nLength即可：
　　
　　③ 获取元素取值算法。利用数组特性直接获取，以下代码为读取顺序线性表中第i个元素（从0开始计数）的取值：
　　
　　可以看出，顺序存储线性表中随机查找数据元素操作的时间复杂度是常数，表示为O(1)。
　　④ 插入元素算法。在顺序存储结构的线性表中插入元素需要移动数据。在第i个位置插入，则需要将原线性表中编号为n，n-1，…，i+1，i的元素依次先后移动一个位置，变为编号为n+1，n，…，i+2，i+1的元素。
　　【例1-3】已知线性表（2001，2002，2004，2005，2006），现需在其第3个元素位置处插入数据2003，请画出插入前后的示意图。
　　【解析】插入前线性表如图1-3（a）所示。插入时，首先将原线性表中第3个元素之后（含第3个元素）的所有数据元素依次向后移动一位，如图1-3（b）～图1-3（d）所示，再将新线性表中第3个元素赋值为2003，最后把线性表长nLength加1即可，如图1-3（e）所示。插入后的线性表为（2001，2002，2003，2004，2005，2006）。
　　⑤ 删除元素算法。在顺序存储结构的线性表中删除元素需要移动数据。在第i个位置删除，则需将原线性表中编号为i+1，i+2，…，n的元素依次向前移动一个位置，变为编号为i，i+1，…，n-1的元素。
　　【例1-4】已知线性表（2001，2002，2003，2004，2005，2006），现删除其中第3个元素，请画出删除前后的示意图。
　　【解析】删除前线性表如图1-4（a）所示。删除时，首先将原线性表中第3个元素之后（不含第3个元素）的所有数据元素按照“从前到后”的顺序依次“向前”移动一位，最后把线性表长（nLength）减小1即可。删除后的线性表为（2001，2002，2004，2005，2006），如图1-4（d）所示。

　　4．顺序存储结构的特点
　　根据本节的介绍，顺序存储结构的特点可以归纳如下：
　　① 采用顺序存储结构的线性表最大的优点是支持随机查找，定位数据元素的时间复杂度为一个常数。其最大的缺点是除线性表尾外，在其他任何位置插入或删除元素或多或少都需要移动线性表中的数据元素，从而提高了时间复杂度。
　　② 顺序存储结构的线性表需要一次性分配所需的存储空间，因此，当线性表长小于最大表长时，就浪费了“最大表长实际表长+1”个数据元素的存储空间，降低了数据元素的存储密度。但也正是由于存储空间已提前分配，当线性表未满时，插入元素无须再申请存储空间，从而减小了插入操作的时间复杂度。
　　③ 线性表采用静态数组描述时不能增加最大表长，因此，只适用于线性表长在一定范围内的应用中；采用动态数组描述的线性表虽然可以弥补此缺陷，但申请或释放内存都需耗费一定的时间，从而提高了时间复杂度。
　　④ 相对于链式存储结构来说，顺序存储结构的线性表的程序设计要简单得多，程序员无须考虑指针等内容，直接使用数组就可以完成大多数的功能。