线性表 (Linear List)
也称顺序表 (Sequential List)或有序表 (Ordered List)。它是元素的一个有序集合,其长度有限,并且可以根据需要自动伸缩。其形式如下:
其中 是有穷自然数, 是线性表中的一个元素, 是元素的索引,索引从 0 开始, 是线性表的长度或大小。当 时,线性表为空。 是线性表的最后一个元素1。
线性表中的顺序通常是指数据添加的顺序,并非按照元素大小的顺序存储。
按照元素大小顺序存储的线性表称为排序列表 (Sorted List) ,它是一个始终保持其元素按指定顺序排列的列表。元素的顺序可以基于自然顺序(如数字的升序或降序)或自定义比较规则(如字符串的字典序)。它是线性表的一种,其实现也会在后文中讲述。
抽象数据类型(ADT)
ADT LinearList {
属性
elements; // 有限个元素的有序集合
操作
size();
isEmpty();
get(int index);
... // 更多操作见下文
}
线性表的操作
在 Java 中对应的接口为 java.util.List
,其主要的一些方法说明如下:
size
:返回线性表的长度isEmpty
:判断线性表是否为空contains(Object e)
:判断一个元素是否在顺序表中get(int index)
:获取指定位置的元素add(T e)
:添加元素add(int index, T e)
:添加元素到指定位置,此为止的元素后移remove(T e)
:删除元素remove(int index)
:删除指定位置元素,其后元素前移indexOf(Object o)
:获取元素的所在位置iterator
:生成序列表的迭代器,用于元素遍历
📄️ 有序表的数组实现
📄️ 有序表的链表实现
参考资料
-
Sartaj Sahni. 数据结构、算法与应用:C++语言描述.(第二版). (王立柱,刘志红译). 北京:机械工业出版社. 2015. ISBN 978-7-111-49600-7 ↩