2.2 线性表的顺序存储结构和实现_数据结构（C语言）-QQ阅读中文古言网

上QQ阅读APP看书，第一时间看更新

2.2　线性表的顺序存储结构和实现

2.2.1　线性表的顺序存储结构

线性表的顺序存储指使用连续的存储空间，按照数据元素在线性表中的序号依次存储数据元素。采用顺序存储结构的线性表称为顺序表。顺序表借助元素在存储空间中的位置来表示数据元素之间的逻辑关系：逻辑上相邻的数据元素，其物理存储地址也相邻。

设线性表中第一个元素a0在内存中的存储地址是loc(a0)，每个元素占用k个存储单元，则线性表中任意元素ai在内存的存储地址为：

loc(ai)=loc(a0)+i×k　　（2-1）

由公式（2-1）可知，只要给定loc(a0)和k的值，即可计算出任意元素在内存中的存储地址，从而进行数据元素的存取，所以线性表的顺序存储结构是一种随机存取结构。

C语言中，一维数组占用了内存中一组连续的存储单元，具备随机存取的特性，由此可使用一维数组描述线性表的顺序存储结构。线性表中的数据元素（a0,…,ai,…,an−1）在一维数组的存储形式如图2.1所示，图中maxLength是顺序表的最大允许长度。在处理实际问题时，所需线性表的长度会随具体问题的不同而不同，因此在实现顺序表时，使用动态分配的一维数组。

线性表的顺序表示定义如下。

图2.1　顺序表示例

在以上定义中，n是顺序表的长度，即顺序表中数据元素的个数。maxLength是顺序表的最大允许长度。ElemType是自定义类型，它是为了统一描述数据结构中数据元素的数据类型而设定的。在实际使用时，用户可以根据实际需要将ElemType具体定义为所需的数据类型，可以是int、float等基本数据类型，也可以是struct结构体类型等。例如typedef int ElemType，将ElemType定义为int型。指针element指示顺序表的存储空间的首地址。SeqList是类型名，可通过它定义相应变量，例如

SeqList L;

2.2.2　顺序表基本运算的实现

以下讨论顺序表中几个主要运算的具体实现。

1．初始化

顺序表的初始化运算是使用动态分配数组空间方式构造一个空的线性表。动态分配数组空间可以达到有效利用存储空间的目的。

【算法步骤】

（1）为顺序表L动态分配一维数组。

（2）若动态分配一维数组失败，则返回出错信息；否则返回OK。

程序2.1　顺序表的初始化

此处返回值类型Status为整型，返回OK代表1，返回ERROR代表0。之后在代码中出现将不再赘述。malloc是动态分配内存空间的函数。

2．查找

顺序表的查找运算是查找表中元素ai的值。顺序表具有随机存取的特点，因此元素ai的值可以直接通过数组下标定位取得。

【算法步骤】

（1）判断所要查找的元素下标i是否越界，若越界，返回ERROR。

（2）若下标i未越界，则取出element[i]的值通过参数x返回。

程序2.2　顺序表的查找

3．插入

顺序表的插入运算是在顺序表L的元素ai之后插入新元素x。若i=−1，则表示将新元素x插入顺序表的最前面。首先需要对i是否越界、顺序表存储空间是否已满进行判断。新元素x插入顺序表之前，将从n−1到i+1之间的所有元素依次向后移动一个位置。下面以实例进行说明，图2.2所示为新元素55插入前后线性表的变化。为了将新元素55插入下标为2的元素之后，需从下标为5的元素开始依次向后移动一个位置，直到下标为3的元素。

图2.2　顺序表中插入新元素55

【算法步骤】

（1）判断元素下标i是否越界，若已越界，返回ERROR。

（2）判断顺序表存储空间是否已满，若已满，返回ERROR。

（3）将元素（ai+1,…,an−1）依次向后移动一个位置。

（4）将新元素x放入下标i+1的位置。

（5）表长加1。

程序2.3　顺序表的元素插入

【算法分析】

顺序表的元素插入运算过程中，时间主要消耗在移动元素上。对于长度为n的顺序表，在位置i（i=−1,0,1,…,n−1）后插入一个新元素，需要移动n−i−1个元素。设Pi是在位置i之后插入一个新元素的概率，并设在任意位置处插入元素的概率是相等的，则有Pi=1/(n+1)。设Ei是在长度为n的顺序表中插入一个新元素时所需移动元素的平均次数，则

由上述分析可知，顺序表插入算法的平均时间复杂度为O(n)。

4．删除

顺序表的删除运算的功能是将元素ai删除。须先对i是否越界、顺序表是否为空进行判断。在顺序表中，逻辑上相邻的数据元素在物理位置上也需相邻，因此不能直接简单删除元素ai，而需将从i+1到n−1之间的所有元素依次向前移动一个位置。下面以实例进行说明，图2.3所示为删除元素50前后线性表的变化。为了删除元素50，需从下标为3的元素开始依次向前移动一个位置，直到下标为5的元素。

图2.3　删除顺序表中的元素50

【算法步骤】

（1）判断元素下标i是否越界，若不越界，返回ERROR。

（2）判断顺序表是否为空，若为空，返回ERROR。

（3）将元素（ai+1,…,an−1）依次向前移动一个位置。

（4）表长减1。

程序2.4　顺序表的元素删除

顺序表的元素删除运算过程中，时间主要消耗在移动元素上。对于长度为n的顺序表，删除位置i(i=0,1,…,n−1)上的一个元素，需要移动n−i−1个元素。设Pi是在位置i删除一个元素的概率，并设在任意位置处删除元素的概率是相等的，则有Pi=1/n。设Ed是在长度为n的顺序表中删除一个元素时所需移动元素的平均次数，则