Chapter2.1：线性表基础

该系列属于计算机基础系列中的《数据结构基础》子系列，参考书《数据结构考研复习指导》(王道论坛 组编)，完整内容请阅读原书。

---

---

1.线性表的定义和基本操作

1.1 线性表的定义

• 线性表是具有相同数据类型的$n(n\ge 0)$个数据元素的有限序列，其中$n$为表长，当$n=0$时，线性表为一个空表；
• 若用$L$命名线性表，则一般表示为：$L(a_1,a_2,\cdots ,a_i,a_{i+1},\cdots ,a_n)$；其中：$a_1$是唯一的"第一个"数据元素，称为表头元素，$a_n$是唯一的"最后一个"数据元素，称为表尾元素；
• 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继；
• 线性表的特点：
  • 表中元素的个数有限；
  • 表中元素具有逻辑上的顺序性，表中元素有其先后次序；
  • 表中元素都是数据元素，每个元素都是单个元素；
  • 表中元素的数据类型都相同，即每个元素占有相同大小的存储空间；
  • 表中元素具有抽象性，即仅讨论元素间的逻辑关系，不考虑元素究竟表示什么内容；
• 注：线性表是一种逻辑结构，表示元素间一对一的相邻关系；顺序表和链表是指存储结构；

1.2 线性表基本操作

线性表的主要操作：

• $\mathrm{InitList}(\&L)$：初始化表，构造一个空的线性表；
• $\mathrm{Length}(\mathrm{L})$：求表长，返回线性表$L$的长度，即$L$中数据元素的个数；
• $\mathrm{LocateElem}(\mathrm{L},\mathrm{e})$：按值查找操作，在表$L$中查找具有给定关键字值的元素；
• $\mathrm{GetElem}(\mathrm{L},\mathrm{i})$：按位查找操作，获取表$L$中第$i$个位置的元素的值；
• $\mathrm{ListInsert}(\&L,\mathrm{i},\mathrm{e})$：插入操作，在表$L$中的第$i$个位置上插入指定元素$e$；
• $\mathrm{ListDelete}(\&L,\mathrm{i},\&e)$：删除操作，删除表$L$中第$i$个位置的元素，并用$e$返回删除元素的值；
• $\mathrm{PrintList}(\mathrm{L})$：输出操作，按前后顺序输出线性表$L$的所有元素值；
• $\mathrm{Empty}(\mathrm{L})$：判空操作，若$L$为空表，则返回$\mathrm{true}$，否则返回$\mathrm{false}$；
• $\mathrm{DestroyList}(\&L)$：销毁操作，销毁线性表，并释放线性表$L$所占用的内存空间；

1.3 线性表定义习题

1. 线性表是具有$n$个( )的有限序列；
   • 数据表；
   • 字符；
   • 数据元素；
   • 数据项；
2. 以下( )是一个线性表；
   • 由$n$个实数组合的集合；
   • 由$100$个字符组成的序列；
   • 所有整数组成的序列；
   • 邻接表；
3. 在线性表中，除开始元素外，每个元素( )。
   • 只有唯一的前驱元素；
   • 只有唯一的后继元素；
   • 有多个前驱元素；
   • 有多个后继元素；