数据结构和算法之线性表

前言

上一篇《 数据结构和算法之时间复杂度和空间复杂度 》中介绍了时间复杂度的概念和常见的时间复杂度，并分别举例子进行了一一说明。这一篇主要介绍线性表。

线性表属于数据结构中逻辑结构中的线性结构。回忆一下，数据结构分为物理结构和逻辑结构，逻辑结构分为线性结构、几何结构、树形结构和图形结构四大结构。其中，线性表就属于线性结构。剩余的三大逻辑结构今后会一一介绍。

线性表

基本概念

线性表（List）：由零个或多个数据元素组成的有限序列。

注意：

1.线性表是一个序列。

2.0个元素构成的线性表是空表。

3.线性表中的第一个元素无前驱，最后一个元素无后继，其他元素有且只有一个前驱和后继。

4.线性表是有长度的，其长度就是元素个数，且线性表的元素个数是有限的，也就是说，线性表的长度是有限的。

如果用数学语言来进行定义，可如下：

若将线性表记为（a1,…,ai-1,ai,ai+1,…an）,则表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素。

线性表基本操作

InitList ( *L ) : 初始化操作，建立一个空的线性表L。

ListEmpty (L ) : 判断线性表是否为空表，若线性表为空，返回 true，否则返回 false。

ClearList ( *L ) : 将线性表清空。 GetElem (L ,i ,*e ) : 将线性表L中的第i个位置元素值返回给e。

LocateElem (L ,e ) : 在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回 0表示失败。

ListInsert ( *L ,i ,e ) : 在线性表L中第i个位置插入新元素e。

ListDelete ( *L ,i ,*e ) : 删除线性表L中第i个位置元素，并用e返回其值。

ListLength (L ) : 返回线性表L的元素个数。

对于不同的应用，线性表的基本操作是不同的，上述操作是最基本的。

对于实际问题中涉及的关于线性表的更复杂操作，完全可以用这些基本操作的组合来实现。