【2.2】顺序表

一、基本概念

• 也称向量，采用定长的一维数组存储结构
• 主要特性
• 元素的类型相同
• 元素顺序地存储在连续存储空间中，每一个元素有唯一的索引值
• 使用常数作为向量长度
• 数组存储
• 读写其元素很方便 ，通过下标即可指定位置
• 只要确定了首地址，线性表中任意数据元素都可以随机 存取

二、顺序表类定义

三、顺序表上的运算

• 重点讨论
• 插入元素运算 bool insert(const int p, const T value);
• 删除元素运算 bool delete(const int p);

顺序表的插入图示

顺序表的插入

顺序表的删除图示

四、算法分析

顺序表插入删除运算的算法分析

五、讨论

• 顺序表中，插入删除操作需要考虑哪些 问题?
• 顺序表有哪些优缺点?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾蛟