定义
线性表（linear list）是具有相同的数据类型的n(n 0 ) 个数据元素的有限序列（有限序列是指序列中的元素个数是有限的，即序列的长度是有限的）, 其中n为表长, 当n = 0 时线性表是一个空表. 若用L命名线性表, 其一般表示为
L = (, , ..., , , ..., )
线性表是一种逻辑结构, 讨论的是元素之间的逻辑关系, 表示元素之前一对一的相邻关系.后面的顺序表和链表是指存储结构, 他们之间属于不同层次的概念.
特征
- 是唯一的"第一个数据元素", 又称表头元素.
- 是唯一一个 "最后一个元素" 又称表尾元素.
- 除第一个元素外, 每个元素有且仅有一个直接前驱.
- 除最后一个元素外, 每个元素有且仅有一个直接后继.
- 元素之间为一对一的线性关系.
特点
- 表中的元素个数有限
- 表中元素具有逻辑上的顺序性, 表中的元素有先后次序
- 表中元素都是数据元素且每个元素都是单个元素
- 表中元素的数据类型都相同(这意味着每个元素占有相同大小的存储空间)
线性表抽象数据类型描述
一个数据结构最基本操作是指最核心、最基本的操作。（其他复杂的操作可通过调用其基本操作来实现）
- InitList(&L) 初始化表(构造空的线性表L)
- Length(L) 求表长(即表 L 中数据元素的个数)
- LocateElem(L, e) 按值查找操作
- GetElem(L, i) 按位查找操作(查找表 L 中第 i 个位置的元素)
- ListInsert(&L, i, e) 插入操作(在表 L 中第 i 位置插入 e 元素)
- ListDelete(&L, i, &e) 删除操作
- PrintList(L) 输出操作(按照前后顺序输出表 L 中的数据元素)
- Empty(L) 判空操作(空 true 否则 false)
- DestoryList(&L) 销毁操作(销毁并释放表 L)
