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

大学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)。这就说明,它比较适合元素个数不太变化,而更多的是存取数据的应用。当然,它的优缺点还不仅这些...

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

优点:

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

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

缺点:

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

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

造成存储空间的“碎片”

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180520G098XK00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券