顺序表

储存结构

逻辑上相邻的数据元素物理上也相邻

实现方式

静态分配

1. 使用静态数据实现
2. 大小一旦确定就无法改变

动态分配

1. 使用”动态数组”实现
2. 用 malloc 实现
3. 顺序表存满时,可以再用 malloc 动态扩展顺序表的最大容量
4. 将元素复制到新的储存区域,并用 free 释放原区域

特点

1. 随机访问 能在 O(1)时间内找到第 i 个元素
2. 存储密度高
3. 扩容不方便
4. 插入,删除元素数据不方便

基本操作

插入

1. 插入元素应该往后移
2. 时间复杂度 最好 O(1) 最坏 O(n) 平均 O(n)

删除

1. 删除位置之后的位置都要往后移
2. 时间复杂度 最好 O(1) 最坏 O(n) 平均 O(n)

代码要点

1. 注意位序 i 和数组下标的区别
2. 算法要有健壮性,注意判断 i 的合法性

按位查找

1. 查找表中某一个位置的元素值 用数组下标
2. 时间复杂度 最好/最坏/平均时间复杂度都是 O(1)

按照值查找

1. 查找某一个值 从第一个元素依次往后检索
2. 时间复杂度
   • 最好 O(1):目标元素在第一个位置
   • 最坏 O(n):目标元素在最后一个位置
   • 平均 O(n):目标元素在每一个位置概率都相同