2.1 线性表的定义及运算

2.1.1 线性表的定义

线性表（linear list）是一种最简单且最常用的数据结构。一个线性表是n（n≥0）个相同类型的数据元素构成的有限序列（a1,a2,…,an）。其中元素的个数n定义为线性表的长度，当n=0时称为空表，空表中没有任何数据元素。线性表中数据元素的含义在不同情况下可以不同，它既可以是原子类型，也可以是结构类型，但同一线性表中的数据元素必须属于同一数据对象。例如，由26个英文字母构成的表（a,b,c,…,z）是一个线性表，再如由全体职工的基本工资构成的表（1236.60,1669.80,900.00,890.00,…,1842.00）是一个线性表。这两个线性表中的每个数据元素都只由一个数据项构成，是简单的原子类型。而如表2-1所示的电话号码表也是一个线性表，其数据元素是由姓名、职务、所在部门和联系电话4个数据项构成的，是复杂的结构类型。

表2-1 电话号码表

对于线性表（a1,a2,…,ai-1,ai,ai+1,…,an），元素ai-1领先于元素ai，称ai-1是ai的直接前驱，而称ai是ai-1的直接后继。除了第一个元素a1外，每个元素ai有且仅有一个直接前驱ai-1，除了最后一个元素an外，每个元素ai有且仅有一个直接后继ai+1。由此可见，线性表中数据元素之间的（相对位置）关系是线性的，即一维的。若元素间满足a1≤a2≤…≤ai-1≤ai≤ai+1≤…≤an，则这种线性表称为非递减有序表；若元素间满足a1≥a2≥…≥ai-1≥ai≥ai+1≥…≥an，则这种线性表称为非递增有序表。

2.1.2 线性表的基本运算

（1）InitList(l)，初始化线性表l。

（2）EmptyList(l)，判断线性表l是否为空表，如果l为空表则返回1，否则返回0。

（3）ListLength(l)，求线性表l的长度。

（4）Locate(l,e)，求线性表l中元素e的位置。

（5）GetData(l,i)，返回线性表l中第i个元素的值。

（6）InsList(l,i,e)，在l中第i个元素（位置）之前插入数据元素e。

（7）DelList(l,i)，删除l中的第i个数据元素。

在实际使用中线性表可能还有其他的运算，如将两个或两个以上的线性表合并成一个线性表；把一个线性表拆分成两个或两个以上的线性表；多种条件的合并、拆分、复制和排序等运算。这通常都可借助于这些基本运算的组合来实现。