线性表之顺序存储结构

线性表

零个或多个数据元素的有限序列。
元素之间是有顺序的,有先来后到的。第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。
线性表元素的个数n(n\geqslant0)定义为线性表的长度,当n=0时,称为空表。

描述顺序存储结构需要三个属性:

  • 存储空间的起始位置:数组 data,它的存储位置就是存储空间的存储位置。
  • 线性表的最大存储容量:数组长度 MaxSize。
  • 线性表的当前长度:length。

数组的长度和线性表的长度

数组的长度是存放线性表的存储空间的长度,存储分配后这个量一般是不变的。
线性表的长度是线性表中数据元素的个数,随着线性表插入和删除操作的进行,这个量是变化的。在任意时刻,线性表的长度应该小于等于数组的长度。

FQ8y0a7KBf.png!large

存储器中的每个存储单元都有自己的编号,这个编号称为地址。

线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系:

LOC(a_i+1)=LOC(a_i)+c

所以对于第i个数据元素a_1推算得出:

LOC(a_i)=LOC(a_1)+(i-1)c

zuhM1huNRW.png!large

对每个线性表位置的存入或者取出数据,对计算机来说都是相等的时间,用算法中的时间复杂度的概念来说,它的存取时间性能为 O(1)。
具有这一特点的存储结构称为「随机存取结构。」

插入和删除的时间复杂度

插入到最后一个位置或删除最后一个元素的时间复杂度为 O(1)
插入到第一个位置或删除第一个元素的时间复杂度为 O(n)
平均移动次数和最中间的那个元素的移动次数相等,为 (n-1)/2

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

优点

无须为表示表中元素之间的逻辑关系而增加额外的存储空间
可以快速地存取表中任一位置的元素

缺点

插入和删除操作需要移动大量元素
当线性表长度变化较大时,难以确定存储空间的容量
造成存储空间的“碎片”

ai
本作品采用《CC 协议》,转载必须注明作者和本文链接
不要试图用百米冲刺的方法完成马拉松比赛。
本帖由 Galois 于 4天前 加精
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!