Question

数据结构与算法———顺序表

Answer 1

By FastHorse March 5, 2017

按顺序方式存储的线性表称为 顺序表(arry - based list) ，又称为 向量(vector) ，通过创建 数组 来建立。顺序表中的每个元素按其顺序有唯一的索引值，又称下标值，可以用来方便地访问元素内容。

只要确定了基地址，线性表中的任意元素的地址都可以方便地计算出来，从而达到随机存取的效果，因此元素间的物理相邻关系表示了他们逻辑上的相邻关系。

下面着重介绍基于数组的顺序表插入、删除运算。

根据位置插入是将指定元素插入到指定位置。除了涉及被更新的那个元素之外，其他的线性关系的相对顺序应保持不变。为此，需要对顺序表实施一系列的元素移动操作来维护逻辑和存储的线性关系。
c++程序实现：

根据大小插入算法适用于数据元素递增的顺序表。从顺序表的第一个元素开始寻找，找到比自己大的元素就插在该元素前面。输入一个数字x，从顺序表的第一个元素开始循环，判断输入的元素是否小于等于顺序表中元素，若成立，则将输入元素插入表中，若不成立，则继续判断顺序表中下一个元素。
c++程序实现：

删除运算需要事先检查顺序表是否为空表，只在非空表是才能进行删除。该算法要求输入一个删除的位置，判断该位置是否有效。若有效，通过左移运算将data[i-1]数组元素删除，从而完成对指定位置元素删除的功能。
c++程序实现：

区域删除算法适用于要在顺序表中删除多个相邻元素。首先输入两个删除的位置，同样通过左移运算将该区域内的所有元素删除。
c++程序实现：

张铭，王腾蛟，赵海燕. 数据结构与算法. 高等教育出版社，2008.6