线性表（一）

这算是数据结构的第一篇文章，在这篇文章里，我要讲的是最常用，最简单的一种数据结构——线性表。看到表这个字，不要想歪了，它不是一个二维表，而是个类似数组的一维存储结构。

线性表是一种典型的线性结构，线性结构的基本特点是数据元素有序且有限，在这种结构中：

① 存在一个唯一的被称为“第一个”的数据元素；

② 存在一个唯一的被称为“最后一个”的数据元素；

③ 除第一个元素外，每个元素均有唯一一个直接前驱；

④ 除最后一个元素外，每个元素均有唯一一个直接后继。

说概念估计有些抽象，看一下下面这张图

图1 线性表

第一个（首）元素就是$a_1$，最后一个（尾）元素就是$a_6$，除了$a_1$以外，每个元素前面都有元素，这就是前驱。除了$a_6$以外，每个元素后面都有元素，这就是后继。

下面我们看个线性表的实例——学生成绩表

图2 学生成绩表

这个线性表中的每个数据元素是每个学生所对应的一系列信息，它是由学号、姓名、性别和成绩四个数据项组成。

线性表的定义： n（n≥0）个数据元素的有限序列，记作：

    L = ($a_1$,$a_2$,…,$a_n$)，$a_n$是表中数据元素，n是表长度（n = 0为空表），$a_1$称为线性表的第一个（首）结点，$a_n$称为线性表的最后一个（尾）结点。$a_1$,$a_2$…,$a_{i-1}$都是$a_i$的前驱，其中$a_{i-1}$是$a_i$的直接前驱；$a_{i+1}$,$a_{i+2}$,…,$a_n$都是$a_i$的后继，其中$a_{i+1}$是$a_i$的直接后继。

（重点）线性表的基本操作：

（1）InitList(&L)//Initiate：开始，着手

操作结果：构造一个空的线性表

（2）DestroyList(L)

初始条件：线性表L已经存在

操作结果：销毁线性表L

（3）ClearList(L)

线性表L存在，将其清空

（4）ListEmpty(L)

    L存在，若L为空表，返回True；否则返回False

（5）ListLength(L)

    L存在，返回L中数据元素个数

（6）GetElem(L,i,&e)

    L存在，用e返回L中第i个数据元素的值

（7）LocateElem(L,e,compare())

    L存在，compare()函数是数据元素判定函数，返回L中第1个与e满足compare()关系的数据元素的位置，若这样的数据元素不存在，则返回0

（8）PriorElem(L,cur_e,&pre_e)

    L存在，若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则返回false

（9）NextElem(L,cur_e,&next_e)

    L存在，若cur_e是L的数据元素，且不是最后一个，则用next_e返回他的后继，否则返回false

（10）ListInsert(&L,i,e)

    L存在，在L的第i个位置之前插入新的数据元素e，L的长度+1

（11）ListDelete(&L,i,&e)

    L存在，删除L的第i个数据元素，并用e返回其值，L的长度-1

看完这些函数是不是感觉有些懵，不要急，我会在下篇文章给出函数实现以及完整代码，接下来我要把线性表的一些性质讲完

线性表的顺序表示指的是用一组地址连续的存储单元以此存储线性表的数据元素，其特点是：逻辑上相邻的元素，物理位置上也是相邻的

图3 线性表的顺序存储结构

在具体的及其环境下：设线性表的每个元素需要占用c个存储单元，则线性表中第i+1个数据元素的存储位置$LOC(a_{i+1})$和第i个数据元素的存储位置$LOC(a_{i})$之间满足关系：$LOC(a_{i+1}) = LOC(a_i) + c$，线性表的第i个数据元素$a_i$的存储位置为$LOC(a_{i+1}) = LOC(a_1) + (i-1)*c$