线性表知识点总结(1) - 顺序存储结构
线性表概念
线性表(List):零个或多个数据元素的有限序列
抽象数据类型
ADT 线性表(List)
Data
线性表的数据对象集合为{a₁, a₂..., a𝗇.}。数据元素之间的关系是一对一的关系
Operation
InsertList(*L): 初始化操作,建立一个空的线性表L
ListEmpty(L): 线性表为空,返回true;否则返回false
ClearList(*L): 清空线性表
GetElem(L, i, *e): 将线性表中第 i 个元素返回给 e
LocateElem(L, e): 查找元素e,找到返回index,没找到返回-1
ListInsert(*L, i, e): 在线性表的第 i 个位置插入元素 e
ListDelete(*L, i, *e): 删除线性表的第 i 个位置元素,并用 e 返回其值
ListLength(L): 返回线性表 L 的元素个数
线性表的顺序存储结构
线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素
1. 顺序存储结构的三个属性
- 存储空间的其实位置:数据data
- 线性表的最大存储容量:数组长度MaxSize
- 线性表的当前长度:length
注意:数组的长度是存放线性表的存储空间的长度,分配后一般是不可变的。线性表的长度是线性表中元素的个数。在任意时间,线性表的长度应该小于或等于数组的长度。
2. 数组的寻址计算公式
数组从零开始的公式为:LOC(aᵢ) = LOC(a₀) + i * c
,每次CPU可以减少一次运算
3. 顺序存储结构的操作
获取元素
将线性表中的第 index 个位置的元素返回,也就是数组的index -1
的下标,时间复杂度为:O(1)
/**
* 线性表顺序存储结构获取 index 处的元素
* @param {*} list
* @param {*} index
* @returns
*/
function getElem(list, index) {
if (list.length == 0 || index < 1 || index > list.length) {
return false
}
return list[index - 1]
}
插入元素
插入元素,需要将插入位置后面的元素全部向后挪一位,所以时间复杂度为O(n)
。具体实现如下:
- 如果插入位置不合理,抛出异常
- 如果线性表的长度大于等于数组的长度,抛出异常或动态扩容
- 从最后一个元素开始向前遍历到第 index 个位置,分别将它们都向后挪动一位
- 将要插入的元素填入位置 index
- 表长度加 1
/**
* 线性表顺序存储结构的插入
* @param {*} list 线性表
* @param {*} index 插入的位置
* @param {*} ele 插入的元素
*/
function listInsert(list, index, ele) {
//如果插入的位置不对,返回错误
//插入的位置可以是线性表中任意一个位置或者在线性表的末端插入,也就是list.length + 1
if (index < 1 || index > list.length + 1) {
return false
}
//若插入的位置不在表尾
if (index <= list.length) {
//将要插入位置后的数据元素向右移动一位
let i = list.length - 1
for (i; i >= index - 1; i--) {
list[i + 1] = list[i]
}
}
//插入新元素
//list.length++; js可以直接通过赋值的方式给数组扩容,不存在越界,所以不需要手动加长度
list[index - 1] = ele
return list
}
删除元素
删除元素,跟插入元素类似,需要将删除位置后面的元素全部向前挪一位,所以时间复杂度为O(n)
。具体实现如下:
- 如果删除位置不合理,抛出异常
- 取出删除元素
- 从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前挪动一位
- 表长度减 1
/**
* 线性表顺序存储结构的删除
* @param {*} list 线性表
* @param {*} index 删除的位置
*/
function listDelete(list, index) {
//线性表为空
if (list.length == 0) {
return false
}
//如果删除的位置不对,返回错误
if (index < 1 || index > list.length) {
return false
}
//取出删除位置的元素
const ele = list[index - 1]
//如果删除的不是最后位置
if (index < list.length) {
//将要删除的位置后的元素数据向左移动一位
let i = index
for (i; i < list.length; i++) {
list[i - 1] = list[i]
}
}
list.length--
return ele
}
4. 线性表顺序存储结构的优缺点
优点:
- 无需为表示表中元素之间的逻辑关系而增加额外的存储空间
- 可以快速地存取表中任一位置的元素
缺点:
-
插入和删除操作需要移动大量元素
-
当线性表长度变化较大时,难以确定存储空间的容量
-
造成存储空间的”碎片“