2.2.2 顺序表上基本操作的实现
原书定位
印刷页P15起,对应PDF第27页。下文为目视整理的知识提要;完整内容见原书对照。
| 操作 | 边界与动作 | 时间复杂度 |
|---|---|---|
| 初始化 | 表长置零;动态表还需分配空间 | 取决于是否初始化数组元素 |
| 按位访问 | 检查 ,访问 data[i-1] | |
| 按值查找 | 从头逐个比较;成功返回位序 | 最好 ,平均、最坏 |
| 在位序 插入 | ;从后向前移动 项 | 平均、最坏 |
| 删除位序 | ;从前向后移动 项 | 平均、最坏 |
等概率插入平均移动 个元素;等概率删除平均移动 个。尾部操作可为 ,但容量不足时需另外分析扩容。批量筛除可用读、写两个下标一次压缩,避免反复删除导致 。

图2.2 顺序表的插入和删除,原书P17。
对应练习
关联知识
原书对照
展开原书对照截图


