线性表初识

线性表是最常用和最简单的一种结构，它是学好其他数据结构比如栈、队列的基础。

先举个栗子：

幼儿园为了保障小朋友的安全，避免漏掉小朋友，给他们安排了出门的次序，事先规定好，谁在谁的前面，谁在谁的后面。这样养成习惯后，如果谁没有到位，他前面和后面的小朋友就会主动报告老师，某人不在。

一、线性表的定义

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

示意图：

1. 这里有几个关键的地方：

1）首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。

2）然后，线性表强调是有限的，小朋友班级人数是有限的，元素个数当然也是有限的。

3）这里指的是具有相同类型的数据元素。

2. 用数学语言来定义：

若将线性表记为（a1,…,ai-1,ai,ai+1,…an）,则表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素。当i=1,2,...,n-1时,ai有且仅有一个直接后继，当i=2,3,...,n时，ai有且仅有一个直接前驱。

所以线性表元素的个数n（n>=0）定义为线性表的长度，当n=0时，称为空表。

二、线性表的抽象数据类型

1. 回到最开始提到的幼儿园小朋友的例子，老师为了让小朋友有秩序地出入，所以就考虑给他们排一个队，并且是长期使用的顺序，这个考虑和安排的过程其实就是一个线性表的创建和初始化过程。

2. 刚开始没经验，把小朋友排好队后，发现有的高有的低，队伍很难看，于是解散重新排—这是一个线性表重置为空表的操作。

3. 排好队后，我们随时可以叫出队伍中某一位置的小朋友名字以及他的具体情况—这种可以根据位序得到数据元素也是一种很重要的线性操作。

4. 有时我们想知道，某个小朋友是否是班里的小朋友—这种查找某个元素是否存在的操作很常用。

5. 有家长问老师，班里现在到底有多少个小朋友呀—这种获得线性表长度的问题也很普遍。

显然，对于一个幼儿园来说，有一个新的小朋友要加入到队列中，或因某个小朋友生病，需要移除某个位置，都是很正常的情况。对于一个线性表来说，插入数据和删除数据都是必须的操作。

 1 // 线性表的抽象数据类型
 2 
 3 ADT 线性表（List）
 4 Data 
 5     线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataType。其中，除第
 6     一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个
 7     元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
 8 Operation
 9     InitList(*L):   初始化操作，建立一个空的线性表L。
10     ListEmpty(L):   若线性表为空，返回true，否则返回false。
11     clearList(*L)： 将线性表清空。
12     GetElem(L,i,*e):将线性表L中的第i个位置元素值返回给e。
13     LocateElem(L,e):在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中的序号表示成功；否则，返回0表示失败。
14     ListInsert(*L,i,e): 在线性表L中的第i个位置插入新元素e。
15     ListDelete(*L,i,e): 删除线性表L中第i个位置元素，并用e返回其值。
16     ListLength(L):   返回线性表L的元素个数。
17 endADT

参考资料：程杰《大话数据结构》