数据结构与算法（第五次课）

顺序表的查找算法分析

• 对含有n个记录的表，查找成功的时候：
• ASL = 
• 顺序查找的平均查找长度：
• 
• 假设每个记录的查找概率相等：
• 则

顺序表的插入算法分析

• 算法的思想：
  • 1.判断插入位置 i 是否合法
  • 2.判断顺序表的存储空间是否已经满，若是满了返回error
  • 将第n至第i位的元素依次向后面移动一位，空出第i个位置
  • 将要插入的新元素e放入第i个位置
  • 表长加1，插入成功，返回ok
• 算法的时间主要耗在移动元素的操作上
  • 平均的移动次数是：

顺序表的删除算法分析

• 算法思想
  • 判断删除位置i是否合法（合法值为,<=i<=n）
  • 将欲删除的元素保留在e中
  • 将第i+1至第n位的元素依次向前移动一个位置
  • 表长减1，删除成功返回ok
• 算法时间主要耗费在移动元素的操作上
  *平均移动次数

顺序表小结

顺序（线性表的顺序存储结构）的特点

1. 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致
2. 在访问线性表时候，可以快速地计算任何一个数据元素地存储地址，因此可以初略地认为，访问每一个元素所花地时间相等
3. 这种存储元素地方法称为随机存取法

顺序表地基本操作地实现

• 时间复杂度： 查找、插入、删除算法地平均时间复杂度为O(n)
• 空间复杂度：顺序表操作算法空间复杂度为S(n) = O(1) ,没有占用辅助空间

顺序表优缺点

• 优点：
  • 存储密度大（结点本身所占存储量/结点结构所占存储量）
  • 可以随机存取表中任一元素
• 缺点：
  • 在插入、删除某一元素时，需要移动大量元素
  • 浪费存储空间
  • 属于静态存储形式、数据元素地个数不能自由扩充