线性表的定义及运算

2.1　线性表的定义及运算

2.1.1　线性表的定义

在实际应用中,线性表是最常用而且是最简单的一种数据结构。例如,一副扑克牌的点数是一个线性表,可表示为（2,3,4,5,6,7,8,9,10,J,Q,K,A）；26个英文字母是一个线性表（A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z）。

1.线性表的定义

线性表（linear list）是由n（n≥0）个类型相同的数据元素a₁,a₂,…,a_n组成的有限序列,记作（a₁,a₂,…,a_i－1,a_i,a_i＋1,…,a_n）。这里的数据元素a_i（1≤i≤n）只是一个抽象的符号,其具体含义视具体情况而定,但同一线性表中的数据元素必须属于同一数据对象。此外,线性表中相邻数据元素之间存在着序偶关系,即对于非空的线性表（a₁,a₂,…,a_i－1,a_i,a_i＋1,…,a_n）,表中a_i－1领先于a_i,称a_i－1是a_i的直接前驱结点,而称a_i是a_i－1的直接后继结点。除了第一个元素a₁外,每个元素a_i有且仅有一个被称为其直接前驱的结点a_i－1,除了最后一个元素a_n外,每个元素a_i有且仅有一个被称为其直接后继的结点a_i＋1。线性表中元素的个数n被定义为线性表的长度,当n＝0时称为空表。本书中,将空表的类型设定为elemtype,表示某一种具体的已知数据类型。

2.线性表的特征

线性表的特点可概括如下。

（1）同一性　线性表由同类数据元素组成,每一个a_i必须属于同一数据对象。

（2）有穷性　线性表由有限个数据元素组成,表长度就是表中数据元素的个数。

（3）有序性　线性表中相邻数据元素之间存在着序偶关系,即〈a_i,a_i＋1〉。

由此可看出,线性表是一种最简单的数据结构,因为数据元素之间是由一前驱一后继的直观有序的关系确定。线性表又是一种最常见的数据结构,因为矩阵、数组、字符串、堆栈、队列等都符合线性条件。

3.线性表的表示

线性表是一种典型的线性结构,用二元组表示如下。

L（A,R）

其中:A＝{a_i｜1≤i≤n,n≥0,a_i∈elemtype}；R＝{r}；r＝{＜a_i,a_i＋1｜1≤i≤n－1}。

线性表对应的逻辑结构如图2－1所示。

图2－1　线性表的逻辑结构示意图

2.1.2　线性表的运算

给出了线性表的逻辑结构后,就可以直接定义它的一些基本运算。但这些运算要实现的话,还必须依赖于具体的存储结构。

线性表常见的运算有以下几种。

（1）置空表运算setnull（＆L）:用于将线性表设置成空表。

（2）求长度运算length（L）:用于求给定线性表的长度。

（3）取元素运算geti（L,i）:若1≤i≤length（L）,则取线性表中的第i个元素；否则,取得的元素为NULL。

（4）取元素位置运算locate（L,x）:在线性表中查找值等于x的元素的位置,若有多个为x的元素,则以第一个元素的位置为准,若没有x元素,则位置为0。

（5）插入运算insert（＆L,x,i）:用于在线性表中的第i个位置上插入值为x的元素。

（6）删除运算dele（＆L,i）:用于删除线性表中第i个位置上的元素。

2.1.3　线性表的抽象数据类型描述

上述这些操作可用抽象数据类型描述如下。