第3章 线性表

线性表是n(n≥0)个数据元素的有限序列，记作(a1, a2, …, an)，ai是表中数据元素，n是表长度。

从上述线性表的定义可以得到下述的线性表的特征：

①有且仅有一个开始结点(表头结点)a1，它没有直接前驱，只有一个直接后继；

②有且仅有一个终端结点(表尾结点)an，它没有直接后继，只有一个直接前驱；

③其他结点都有一个直接前驱和直接后继；

④元素之间为一对一的线性关系；

⑤表内的元素可以有序，也可以无序。

线性表的主要操作包括初始化、建立线性表、取第i个元素、查找某个元素、在指定位置插入元素、删除指定元素、判断线性表是否为空、求线性表的长度等。

根据以上讨论，给出线性表基类的抽象方法定义：

list=class(demo)
public
    procedure listinit;virtual;abstract;
    procedure createlist(s:string);virtual;abstract;
    function get(i:integer):string;virtual;abstract;
    function locate(x:string):integer;virtual;abstract;
    procedure insert(i:integer;b:string);virtual;abstract;
    procedure delete(i:integer);virtual;abstract;
    function empty:boolean;virtual;abstract;
    function getlength:integer;virtual;abstract;
    function getlistdemo(hn:string):string;virtual;abstract;
end;

这些方法的具体实现依赖于子类采用什么样的存储结构，下面分别介绍基于顺序存储和链式存储的线性表的操作以及基于抽象类的应用。