线性表
来自KlniuWiki
线性结构(linear structure)是一个数据元素的有序（次序）集合。
目录 |
1 特征
- 集合中必存在唯一的一个"第一元素"；
- 集合中必存在唯一的一个"最后元素"；
- 除最后元素之外，其它数据元素均有唯一的"后继"；
- 除第一元素之外，其它数据元素均有唯一的"前驱"。
2 定义
- 通常可以下列" n 个数据元素的序列"表示线性表 (Linear_List)
- 序列中数据元素的个数 n 定义为线性表的表长；n=0 时的线性表被称为空表。称 i 为
在线性表中的位序。
- 线性表的操作很多，为讨论方便起见，在此将它归为四类：
- 任何数据结构在被使用之前都必须进行"初始化" ，它类似于编程中使用的变量都必须先有定义。
- 任何数据结构不再使用时都必须进行"结构销毁" ，其实质为"释放"它所占有的存储空间。
- 其抽象数据类型的定义如下，以下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 参见
- 数据结构
- 数据结构-清华大学视频教程
