线性表

线性结构(linear structure)是一个数据元素的有序（次序）集合。

1 特征

1. 集合中必存在唯一的一个"第一元素"；
2. 集合中必存在唯一的一个"最后元素"；
3. 除最后元素之外，其它数据元素均有唯一的"后继"；
4. 除第一元素之外，其它数据元素均有唯一的"前驱"。

2 定义

• 通常可以下列" n 个数据元素的序列"表示线性表 (Linear_List)

序列中数据元素的个数 n 定义为线性表的表长；n=0 时的线性表被称为空表。称 i 为 在线性表中的位序。

• 线性表的操作很多，为讨论方便起见，在此将它归为四类：

1. 任何数据结构在被使用之前都必须进行"初始化" ，它类似于编程中使用的变量都必须先有定义。
2. 任何数据结构不再使用时都必须进行"结构销毁" ，其实质为"释放"它所占有的存储空间。

• 其抽象数据类型的定义如下，以下i-1和i均为下标：

ADT List {
 数据对象：D＝{ ai |ai ∈ ElemSet, i=1,2,...,n, n≥0 }

 数据关系：R1＝{ <ai-1 ,ai>| ai-1 ,ai ∈D, i=2,...,n } 
  //注释：序偶 <ai-1 ,ai> 表示ai-1是ai的直接前驱，反之，ai是ai-1的直接后继。

 基本操作：

   {结构初始化}
   InitList( &L )
     操作结果：构造一个空的线性表 L。

   {销毁结构}
   DestroyList( &L )
     初始条件：线性表 L 已存在。
     操作结果：销毁线性表 L。

　　{引用型操作}
　　ListEmpty( L )
　　　初始条件：线性表L已存在。
　　　操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE。

　　ListLength( L )
　　　初始条件：线性表 L 已存在。
　　　操作结果：返回 L 中元素个数。

　　PriorElem( L, cur_e, &pre_e )
　　　初始条件：线性表 L 已存在。
　　　操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回它的前驱，
　　　　　　　　否则操作失败，pre_e 无定义。

　　NextElem( L, cur_e, &next_e )
　　　初始条件：线性表 L 已存在。
　　　操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返回它的后继，
　　　　　　　　否则操作失败，next_e 无定义。

　　GetElem( L, i, &e )
　　　初始条件：线性表 L 已存在，1≤i≤LengthList(L)。
　　　操作结果：用 e 返回 L 中第 i 个元素的值。

　　LocateElem( L, e, compare( ) )
　　　初始条件：线性表 L 已存在，compare( ) 是元素判定函数。
　　　操作结果：返回 L 中第1个与 e 满足关系 compare( ) 的元素的位序。
　　　　　　　　若这样的元素不存在，则返回值为0。

　　ListTraverse(L, visit( ))
　　初始条件：线性表 L 已存在，visit( ) 为元素的访问函数。
　　操作结果：依次对 L 的每个元素调用函数 visit( )。
　　　　　　　一旦 visit( ) 失败，则操作失败。

　　{加工型操作}
　　ClearList( &L )
　　　初始条件：线性表 L 已存在。
　　　操作结果：将 L 重置为空表。

　　PutElem( &L, i, &e )
　　　初始条件：线性表L已存在，1≤i≤LengthList(L)。
　　　操作结果：L 中第 i 个元素赋值同 e 的值。

　　ListInsert( &L, i, e )
　　　初始条件：线性表 L 已存在，1≤i≤LengthList(L)+1。
　　　操作结果：在 L 的第 i 个元素之前插入新的元素 e，L 的长度增1。

　　ListDelete( &L, i, &e )
　　　初始条件：线性表 L 已存在且非空，1≤i≤LengthList(L)。
　　　操作结果：删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减1。

} ADT List

3 实现

3.1 顺序表

顺序表是线性表的顺序存储表示的简称，它指的是，"用一组地址连续的存储单元依次存放线性表中的数据元素"，即以"存储位置相邻"表示"位序相继的两个数据元素之间的前驱和后继的关系(有序对)"，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址。如下图所示。

假设每个数据元素占据的存储量是一个常量 C，则后继元素的存储地址和其前驱元素相隔一个常量，即：

C 为一个数据元素所占存储量

由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到：

↑基地址

用C语言描述的顺序表类型如下所示：

4 参见

• 数据结构
• 数据结构-清华大学视频教程