线性表之顺序存储结构
0 / 0 / 创建于 4年前 /
Galois 的个人博客
线性表
零个或多个数据元素的有限序列。
元素之间是有顺序的，有先来后到的。第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
线性表元素的个数n(n\geqslant0)定义为线性表的长度，当n=0时，称为空表。
描述顺序存储结构需要三个属性：
- 存储空间的起始位置：数组 data，它的存储位置就是存储空间的存储位置。
- 线性表的最大存储容量：数组长度 MaxSize。
- 线性表的当前长度：length。
数组的长度和线性表的长度
数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。
线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。在任意时刻，线性表的长度应该小于等于数组的长度。
存储器中的每个存储单元都有自己的编号，这个编号称为地址。
线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系：
LOC(a_i+1)=LOC(a_i)+c
所以对于第i个数据元素a_1推算得出：
LOC(a_i)=LOC(a_1)+(i-1)c
对每个线性表位置的存入或者取出数据，对计算机来说都是相等的时间，用算法中的时间复杂度的概念来说，它的存取时间性能为 O(1)。
具有这一特点的存储结构称为「随机存取结构。」
插入和删除的时间复杂度
插入到最后一个位置或删除最后一个元素的时间复杂度为 O(1)
插入到第一个位置或删除第一个元素的时间复杂度为 O(n)
平均移动次数和最中间的那个元素的移动次数相等，为 (n-1)/2
线性表顺序存储结构的优缺点
优点
无须为表示表中元素之间的逻辑关系而增加额外的存储空间
可以快速地存取表中任一位置的元素
缺点
插入和删除操作需要移动大量元素
当线性表长度变化较大时，难以确定存储空间的容量
造成存储空间的“碎片”
本作品采用《CC 协议》，转载必须注明作者和本文链接
本帖由 Galois
于 4年前 加精
关于 LearnKu
粤公网安备 44030502004330号