大话数据结构之线性表顺序存储结构

大学IT圈

关注公众号，及时获取最新洞察

阅读文本大概需要 7 分钟。

昨天学习了「时间复杂度」，今天来看一下「线性表的顺序储存结构」。

首先来看「线性表」定义：

线性表(List)：零个或多个数据元素的有序排列。

关于线性表的基本操作：

Data：线性表的数据对象集合为，每个元素的 类型均为 DataType 。其中，除第一个元素 a1 外，每一个元素有且只有一个直接前驱元素，除了 最后一个元素 an 外，每一个元素都有且只有一个直接后继元素。数据元素之间的关系是一一对应的。

InitList( *L )：初始化操作，建立一个空的线性表 L 。

ListEmpty( L )：若线性表为空，返回 true ，否则返回 false 。

ClearList ( *L )：将线性表清空。

GetElem( L, i, *e )：将线性表 L 中第 i 个位置的元素值返回给 e 。

LocateElem( L, e )：在线性表 L 中查找与给定值 e 相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回 0 表示失败。

ListInsert( *L, i, e )：在线性表 L 中的第 i 个位置插入新元素 e 。

ListDelete( *L, i, *e)：删除线性表 L 中第 i 个位置元素，并用 e 返回其值。

ListLength( L )：返回线性表 L 的元素个数。

关于线性表集合 A(La) 和 B(Lb) 的并集操作：

/* 将所有的在线性表 Lb 中但不在 La 中的数据元素插入到 La 中 */

voidunion( List *La, List Lb ){

intLa_len, Lb_len, i;

ElemType e;/* 声明与 La 和 Lb 相同的数据元素 e */

La_len = ListLength( La );

Lb_len = ListLength( Lb );

for( i =; i

GetElem( Lb, i, e);/* 取 Lb 中第 i 个数据元素赋给 e */

if( !LocateElem( La, e, equal))/* La 中不存在和 e 相同数据元素 */

ListInsert( La, ++La_len, e);/* 插入 */

}

}

顺序储存方式

顺序储存方式是在一定的内存空间中，把相同的数据类型的数据依次存放在这块内存空间中。

线性表顺序储存的结构代码：

#defineMAXSEZE 20/* 存储空间初始分配量 */

typedefintElemType;/* ElemType 类型根据实际情况而定，这里假设为 int */

typedefstruct{

ElemType data[MAXSIZE];/* 数组存储数据元素，最大值为 MAXSEZE */

intlength;/* 线性表当前长度 */

}SqList;

在这里我们发现描述顺序储存结构需要三个属性：

存储空间的起始位置：数组 data，它的存数位置就是存储空间的存储位置。

线性表的最大储存容量：数组长度 MAXSIZE。

线性表的当前长度：length。

数组长度与线性表长度区别：

数组的长度是存放线性表的储存空间的长度，存储分配后这个量一般是不变的。 线性表的长度是线性表黄总数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。

地址计算方法：

假设每个数据元素占 c 个存储单元(LOC 表示获取存储位置的函数。

LOC( a(i+1) ) = LOC( ai ) + c;

所以对于第 i 个数据元素 ai 的地址可以由 a1 推算得出：

LOC( ai ) = LOC( a1 ) + (i-1) * c

顺序存储结构的插入与删除操作

插入操作：

算法思路：

如果插入位置不合理，抛出异常；

如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；

从最后一个元素开始向前遍历到第 i 个位置，分别将他们都像后移动一个位置；

将要插入元素填入位置 i 处；

表长增加 1 。

#defineOK 1

#defineERROR 0

#defineTRUE 1

#defineFALSE 0

typedefintStatus;

/* Status 是函数的类型，其值是函数结果状态码，如 OK 等 */

/* 初始条件：顺序线性表 L 已存在，1

/* 操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度加 1 */

StatusListInsert(SqList *L,inti, ElemType e){

intk;

if(L.length == MAXSEZE)

returnERROR;

if(i L.length +1)

returnERROR;

if(i

for(k = L.length -1; k > i -1; k--){

L.data[k+1] = L.data[k];

}

}

L.data[i-1] = e;/* 将新元素插入 */

L.length++;

}

删除操作：

算法思路：

如果删除位置不合理，抛出异常；

取出删除元素；

从删除元素位置开始遍历到最后一个元素位置，分别将他们向前移动一个位置；

表长减 1 。

/* `` */

/* 操作结果：删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减 1 */

StatusListDelete(SqList *L,inti, ElemType *e){

intk;

if(L.length ==)/* 线性表为空 */

returnERROR;

if(i L.length)

returnERROR;

*e = L.data[i-1];

if(i

for( k = i ; k

L.data[k-1] = l.data[k];

}

}

L.length--;

returnOK;

}

时间复杂度：

根据上次学习，可以推导出 线性表的顺序储存结构在存，读数据时，不管哪个位置时间复杂度都是 O(1)；而插入删除时时间复杂度都是 O(n)。这就说明，它比较适合元素个数不太变化，而更多的是存取数据的应用。当然，它的优缺点还不仅这些...

线性表顺序存储结构的优缺点：

优点：

无须为表示表中元素之间的逻辑关系而增加额外的存储空间

可以快速的存取表中任一位置的元素

缺点：

插入和删除操作需要移动大量元素

当线性表长度变化较大时，难以确定储存空间的容量

造成存储空间的“碎片”

下期学习「线性表的链式储存结构」。