线性表

一轮

线性表的定义和基本操作

数据结构包含三个要素： 逻辑结构、数据的运算、存储结构。

线性表的逻辑结构

线性表是典型的一对一线性结构。

线性表是具有相同数据类型（每个数据元素所占的空间是一致的）的 $n$ 个数据元素的有限序列，其中 $n$ 为表长，当 $n=0$ 的时候，线性表是一个空表，若用 $L$ 命名线性表，则一般表示为 $L=(a_1,a_2,...,a_i,a_{i+1},...,a_n)$

一些概念：

• 位序：$a_i$ 这里的第 $i$ 个就表示位序
• $a_1$ 是表头元素，$a_n$ 是表尾元素
• 除了第一个元素外，每一个元素有且仅有一个直接前驱；除了最后一个元素外，每一个元素有且仅有一个直接后继。

线性表的基本操作

线性表的基本操作包括（创建销毁，增删改查）：

• 初始化与销毁
  • initList(&L) 初始化表，构造一个空的线性表 $L$，分配内存空间。
  • DestroyList(&L) 销毁操作，销毁线性表 $L$，释放线性表所占的内存空间。
• 插入与删除
  • ListInsert(&L, i, e) 插入元素操作，在线性表 $L$ 中的第 $i$ 个位置插入指定元素 $e$ 。
  • ListDelete(&L, i, &e) 删除元素操作，将线性表 $L$ 中的第 $i$ 个元素删除，并用 $e$ 返回删除元素的值。
• 查找
  • LocateElem(L, e) 按值查找操作，在表 $L$ 中查找具有给定关键字值的元素的位置。
  • GetItem(L, i) 按位置查找，在表 $L$ 中查找指定位置 $i$ 对应的元素。
• 其他操作
  • Length(L) 求表长，返回线性表 $L$ 的长度，也就是 $L$ 中元素的个数
  • PrintList(L) 输出操作，按照前后顺序，输出线性表 $L$ 中的所有元素
  • Empty(L) 判空操作，判断线性表 $L$ 是否为空表，若为空表返回 true，否则为 false

线性表的物理/存储结构

顺序表

链表