前言

有了前面的基础，现在开始正式学习数据结构最常用也是最简单的一种结构——线性表。

学习本文需要掌握一定的 C语言基础。

本部分内容参考程杰老师《大话数据结构》，青岛大学王卓老师的授课，王道考研公开课等综合个人所学的总结笔记。

线性表的定义

线性表，顾名思义，是具有像线一样串联起来的表。串联则意味着存在一个头部，一个尾部，且中间的每个元素都是一个挨着一个，这样的表就可以称为线性表。

线性表(List)：零个或多个数据元素的有限序列。

需要强调的是：

首先它是一个序列，也就是说，元素之间是有顺序的，如果元素存在多个，那么第一个元素无前驱，最后一个元素无后继，其他的元素都有且只有一个前驱和后继。
其次，线性表是有限的。事实上，计算机中处理的对象都是有限，无限的序列，只存于数学中的概念。

如果使用数学语言来进行定义的话，如下：

若将线性表记为（$a_1,·····,a_{i-1},a_i,a_{i+1},···,a_n$），则表中 $a_{i-1}$ 领先于 $a_i$ ，$a_i$ 领先于 $a_{i+1}$，称 $a_{i-1}$ 是 $a_i$ 的直接前驱，$a_{i+1}$ 是 $a_i$ 的直接后继。当 $i=1,2,···，n-1$ 时，$a_i$ 有且仅有一个直接后继；当 $i=2,3,···，n$ 时，$a_i$ 有且仅有一个直接前驱。如下图所示：

所以线性表元素的个数 $n$ ($n\geq0$)定义为线性表的长度，当 $n=0$ 时，称为空表。

在非空表中的每个数据元素都有一个确定的位置，如 $a_1$是第一个数据元素，$a_n$是最后一个数据元素，$a_i$ 是第 $i$ 个数据元素，称 $i$ 为数据元素 $a_i$ 在线性表中的位序。

线性表的例子

26个英文字母组成的英文表
($A,B,C,···,Z$)
元素都是字母；元素关系是线性的；
学生情况登记表

学号姓名性别年龄班级

001 于春梅女 18 01级计算机1班

002 何仕鹏男 20 01级计算机2班

003 王亚女 19 01级计算机4班

：：：：：

学号	姓名	性别	年龄	班级
001	于春梅	女	18	01级计算机1班
002	何仕鹏	男	20	01级计算机2班
003	王亚	女	19	01级计算机4班
：	：	：	：	：

线性表的抽象数据类型

线性表的抽象数据类型定义如下：

线性表的类型定义

ADT List{
    数据对象：对象的基本信息
    数据关系：数据元素之间的关系
    基本操作：
        InitList(&L);    //创建线性表
        DestroyList(&L);    //销毁线性表
        ListInsert(&L,i,e);    //插入数据
        ListDelete(&L,i,&e);    //删除数据
        ....等等
}

基本操作

InitList(&L)
- 操作结果：构造一个空的线性表L
  
  initialization /i,niʃəlai’zeiʃən/ 初始化，设定初值
DestoryList(&L)
- 初始条件：线性表L已经存在
- 操作结果：销毁线性表L
ClearList(&L)
- 初始条件：线性表L已经存在
- 操作结果：将线性表L重置为空表
ListEmpty(L)
- 初始条件：线性表L已经存在
- 操作结果：若线性表L为空表，则返回TRUE；否则返回FLASE
ListLength(L)
- 初始条件：线性表L已经存在
- 操作结果：返回线性表L中的数据元素的个数。
GetElem(L,i,&e);
- 初始条件：线性表L已经存在，$1 \leq i \leq ListLength(L)$。
- 操作结果：用 e 返回线性表L中第 i 个数据元素的值。
LocateElem(L,e,compare())
- 初始条件：线性表L已经存在，compare()是数据元素判定函数。
- 操作结果：返回L中第一个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0。
PriorElem(L,cur_e,&pre_e)
- 初始条件：线性表L已经存在
- 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败；pre_e无意义。
  
  prior /‘praɪɚ/ 在前的，在先的；优先的；
  pre- 【前缀】先于；在….前；
NextElem(L,cur_e.&next_e)
- 初始条件：线性表L已经存在
- 操作结果：若cur_e是L的数据元素，且不是第最后一个，则用Next_e返回它的后继，否则操作失败，next_e无意义。
  
  currently /‘kʌrəntli/ 当前；目前；眼下
ListInsert(&L,i,e)
- 初始条件：线性表L已经存在，$1 \leq i \leq ListLength(L)+1$。
- 操作结果：在L的第 i 个位置之前插入信的数据元素e，L的长度加一。
ListDelete(&L,i,&e)
- 初始条件：线性表L已经存在，$1 \leq i \leq ListLength(L)$
- 操作结果：删除L的第 i 个数据元素，并用 e 返回其值，L的长度减一。
ListTraverse(&L,visited())
- 初始条件：线性表L已经存在
- 操作结果：依次对线性表中的每个元素调用visited()