数据结构和算法之线性表

yuanmengFF 8年前

来自: http://www.cnblogs.com/wsnb/p/5182516.html

前言

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

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

线性表

基本概念

线性表(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的元素个数。

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

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