大话数据结构:线性表(顺序存储结构)

2023-11-19

线性表:零个或多个数据元素的有限序列
直接前驱元素、直接后继元素
线性表的长度:线性表元素的个数n
线性表的抽象数据类型:

ADT线性表(list)

Data
线性表的数据对象集合为{a1,a2,……,an},每个元素的类型均为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返回其值。

ListLenth(L)

返回线性表L的元素个数

endADT

在这里插入图片描述

线性表的顺序存储结构

顺序存储定义
一段地址连续的存储单元依次存储线性表的数据元素。
顺序存储方式
存储空间的起始位置
线性表的最大存储容量
线性表的当前长度
数据长度与线性表长度区别
1.存放线性表的存储空间的长度,存储分配后这个量一般是不变的。
2.线性表长度是线性表中数据元素的个数,随着线性表插入和删除操作的进行,这个量是变化的。
地址计算方法
0~(i-1)
地址:每个存储单元 的编号
顺序存储结构的插入和删除
元素的获取:将线性表L的第i个位置元素值返回
元素的插入:
排错:1.插入位置不合理2.线性表长度大于等于数组长度,抛出异常或动态增加容量
实现:从最后一个元素开始向前遍历到第i个位置,分别将他们都向后移动一个位置,将要插入元素填入位置i处,表长加1.
元素的删除:
排错:删除位置不合理,抛出异常
取出删除元素,从删除元素位置开始遍历到最后一个元素位置,分别将他们都向前移动一个位置,表长减1.

顺序存储的优缺点

1.优点:
无需为表示表中元素之间的逻辑关系而增加额外的存储空间。
可以快速的存取表中任一位置的元素
2.缺点:
插入删除操作需要移动大量元素
线性表长度变化比较大的时候,难以确定存储空间的容量
存储空间的碎片

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

大话数据结构:线性表(顺序存储结构) 的相关文章

随机推荐