第三节 线性表的顺序存储
一、顺序表
1、顺序表的定义
线性表的顺序存储又称为顺序表,它是用一组地址连续的存储单元,依次存储线性表中的数据元素。从而使得逻辑上相连的两个元素在物理上也是相邻的。表中元素的逻辑顺序与物理顺序相同。
2、线性表的顺序存储表示
3、线性表顺序存储类型描述
4、顺序表的特点
-
顺序表的主要特点是随机访问,即通过首地址和元素序号可以在O(1) 的时间内找到指定元素。
-
顺序表的存储密度高,每个节点只存储数据元素。
-
顺序表逻辑上相邻的元素物理上也相邻,所以插入和删除操作需要移动大量元素。
二、顺序表的基本操作实现
1、插入操作:ListInsert(&L , i , e)
在顺序表L的第 i (1=< i && i <= L.length + 1 ) 个位置插入新元素e.如果 i 的输入不合法则返回false,表示插入失败;否则将顺序表的第 i 个元素以及其后所有元素右移一个位置,插入元素 e ,顺序表长度加 1,插入成功返回true.
2、删除操作 : ListDelete(SqList &L , int i, int &e)
删除顺序表L中第 i 个位置的元素,成功返回true,并将被删除的元素用引用变量e 返回。
3、按值查找(顺序查找):LocateElem(SqList L ,ElemType e)
在顺序表L中查找第 一个元素值等于 e ,并返回其位序。
(1)时间复杂度计算:
最好情况:查找的元素就在表头时间复杂度为O(1)
最坏情况:查找的元素在表尾时间复杂度为O(n)
平均情况:时间复杂度为T(n) = O(n)