线性表
线性表是零个或多个数据元素的有限序列。
线性表的定义
线性表，从名字上你就能感觉到，是具有像线一样的性质的表。线性表（List）：零个或多个数据元素的有限序列。
这里需要强调几个关键的地方。
- 首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
- 然后，线性表强调是有限的，元素个数当然也是有限的。事实上，在计算机中处理的对象都是有限的，那种无限的数列，只存在于数学的概念中。
如果用数学语言来进行定义。可如下： 若将线性表记为（a1，…，ai-1，ai，ai+1，…，an），则表中ai-1领先于ai，ai+1领先于ai，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1，2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱。
所以线性表元素的个数n（n≥0）定义为线性表的长度，当n=0时，称为空表。
在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。
线性表例子
我现在说一些数据集，大家来判断一下是否是线性表。
先来一个大家最感兴趣的，一年里的星座列表，是不是线性表呢？ 当然是，星座通常都是用白羊座打头，双鱼座收尾，当中的星座都有前驱和后继，而且一共也只有十二个，所以它完全符合线性表的定义。
公司的组织架构，总经理管理几个总监，每个总监管理几个经理，每个经理都有各自的下属和员工。这样的组织架构是不是线性关系呢？
不是，为什么不是呢？哦，因为每一个元素，都有不只一个后继，所以它不是线性表。那种让一个总经理只管一个总监，一个总监只管一个经理，一个经理只管一个员工的公司，俗称皮包公司，岗位设置等于就是在忽悠外人。
班级同学的点名册，是不是线性表？是，这和刚才的友谊关系是完全不同了，因为它是有限序列，也满足类型相同的特点。这个点名册中，每一个元素除学生的学号外，还可以有同学的姓名、性别、出生年月什么的，这其实就是我们之前讲的数据项。在较复杂的线性表中，一个数据元素可以由若干个数据项组成。
一群同学排队买演唱会门票，每人限购一张，此时排队的人群是不是线性表？是，对的。此时来了三个同学要插当中一个同学A的队，说同学A之前拿着的三个书包就是用来占位的，书包也算是在排队。如果你是后面早已来排队的同学，你们愿不愿意？肯定不愿意，书包怎么能算排队的人呢，如果这也算，我浑身上下的衣服裤子都在排队了。于是不让这三个人进来。
这里用线性表的定义来说，是什么理由？嗯，因为要相同类型的数据，书包根本不算是人，当然排队无效，三个人想不劳而获，自然遭到大家的谴责。看来大家的线性表学得都不错。
线性表的抽象数据类型
线性表的抽象数据类型定义如下：
ADT 线性表(List)
Data
线性表的数据对象集合为{a1, a2, ......, an}，每个元素的类型均为DataType。
其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，
除了最后一个元素an外，每一个元素有且只有一个直接后继元素。
数据元素之间的关系是一对一的关系。
Operation
InitList(*L): 初始化操作，建立一个空的线性表L。
ListEmpty(L): 若线性表为空，返回true，否则返回false。
ClearList(*L): 将线性表清空。
GetElem(L, i, *e): 将线性表L中的第i个位置元素值返回给e。
LocateElem(L, e): 在线性表L中查找与给定值e相等的元素，
如果查找成功，返回该元素在表中序号表示成功；
仔细分析一下这个操作，发现我们只要循环集合B中的每个元素，判断当前元素是否存在A中，若不存在，则插入到A中即可。思路应该是很容易想到的。
/* 将所有的在线性表Lb中但不在La中的数据元素插入到La中 */
void unionL(List *La, List Lb)
{
int La_len, Lb_len, i;
/* 声明与La和Lb相同的数据元素e */
ElemType e;
/* 求线性表的长度 */
La_len = ListLength(*La);
Lb_len = ListLength(Lb);
for (i = 1; i <= Lb_len; i++)
{
/* 取Lb中第i个数据元素赋给e */
GetElem(Lb, i, &e);
/* La中不存在和e相同数据元素 */
if (!LocateElem(*La, e))
/* 插入 */
ListInsert(La, ++La_len, e);
}
}
这里，我们对于union操作，用到了前面线性表基本操作ListLength、GetElem、LocateElem、ListInsert等，可见，对于复杂的个性化的操作，其实就是把基本操作组合起来实现的。
注意一个很容易混淆的地方：当你传递一个参数给函数的时候，这个参数会不会在函数内被改动决定了使用什么参数形式。如果需要被改动，则需要传递指向这个参数的指针，如果不用被改动，可以直接传递这个参数。
