扫码获取更多资源

●线性表的顺序表示及操作实现

在实际应用程序中，涉及线性表的基本操作都需要根据线性表的具体存储结构加以实 现。

线性表可以有两种存储表示方法：顺序存储表示和链式存储表示；而顺序存储表示是 计算机中最简单、最常用的一种存储方式。

●顺序表的定义

把线性表中的数据元素按照其逻辑次序依次存放在一组地址连续的存储单元里的方式 称为线性表的顺序存储表示，釆用这种存储结构的线性表称为顺序表(Sequential List)o

1.顺序表中数据元素的存储地址

通常情况下，设线性表中的所有数据元素具有相同的属性，则其占用的存储空间也相同。 假设线性表中的每个数据元素占用d个存储单元

第一个数据元素的起始地址为LOC(ai),则 第2个数据元素的起始地址为

LOC(a2) = LOC(aQ + d

第i个数据元素的起始地址为

LOCCaJ = LOCCaJ + (i-l)d (i = 1, 2, 3,…，n) 因此，线性表中第n个数据元素an的存储地址可以通过式(2-1)计算：

LOC(an) = LOCCaJ + (n-l)d (1< i< n) (2-1)

在顺序表中，每个数据元素a_的存储地址是该元素在线性表中位置i的线性函数，只要 确定了第一个数据元素的起始地址和每个数据元素所占空间的大小

就可以在相同时间内 求出任何一个数据元素的存储地址，因此顺序表是一种随机存取(Random Access)结构。 图2-1给出了顺序表的示意图。

●顺序表的类型定义

采用结构类型来定义顺序表类型，在顺序表的结构定义中：

(1)、由于高级程序设计语言中的数组类型也具有随机存取的特性，并且在内存中占据 的是一组地址连续的存储单元，因此可以釆用数组来描述顺序表中数据元素的存储区域。

(2)、除了采用一维数组存储线性表的数据元素以外，还应该设计一个表示线性表当前长度域

(3)、考虑到线性表的长度可变，需要设计一个表示线性表当前存储空间的域。

因为线性表所需要的容量会随问题不同而异，所以为顺序表定义了一个“存储空间的分 配增补量”，为动态扩充数组容量提供方便。

也就是说，一旦插入数据元素造成空间不足，则 可进行再分配，为顺序表增加一个大小为LIST_INCREMENT个数据元素的空间。

●顺序表的主要特点

顺序表是用一维数组实现的线性表，数组的下标可以看作线性表数据元素在内存中的 相对地址

因此顺序表的最大特点是逻辑上相邻的两个数据元素在物理位置上也相邻,即以 数据元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。

联系我们：