2.2.2 顺序表上基本操作的实现

教材导航 · 第2章

原书定位

印刷页P15起,对应PDF第27页。下文为目视整理的知识提要;完整内容见原书对照。

操作边界与动作时间复杂度
初始化表长置零;动态表还需分配空间取决于是否初始化数组元素
按位访问检查 1≤i≤n1\le i\le n,访问 data[i-1]O(1)O(1)
按值查找从头逐个比较;成功返回位序最好 O(1)O(1),平均、最坏 O(n)O(n)
在位序 ii 插入1≤i≤n+11\le i\le n+1;从后向前移动 n−i+1n-i+1 项平均、最坏 O(n)O(n)
删除位序 ii1≤i≤n1\le i\le n;从前向后移动 n−in-i 项平均、最坏 O(n)O(n)

等概率插入平均移动 n/2n/2 个元素;等概率删除平均移动 (n−1)/2(n-1)/2 个。尾部操作可为 O(1)O(1),但容量不足时需另外分析扩容。批量筛除可用读、写两个下标一次压缩,避免反复删除导致 O(n2)O(n^2)。

图2.2 顺序表的插入和删除

图2.2 顺序表的插入和删除,原书P17。

对应练习

2.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P15,PDF第27页

原书对照,原书P16,PDF第28页

原书对照,原书P17,PDF第29页