2.1 线性表的定义和基本操作

【考纲内容】
（一）线性表的定义和基本操作
（二）线性表的实现
顺序存储;链式存储;线性表的应用
【复习提示】
线性表是考研命题的重点。这类算法题实现起来比较容易而且代码量较少，但却要求具有最优的性能（时间、空间复杂度），才能获得满分。因此，应牢固掌握线性表的各种基本操作（基于两种存储结构），在平时的学习中多注重培养动手能力。另外，需要提醒的是，算法最重要的是思想!考场上的时间有限，在试卷上不一定要求代码具有实际的可执行性，因此应尽力表达出算法的思想和步骤，而不必过于拘泥每个细节。注意算法题只能用 C/C++语言实现
2.1 线性表的定义和基本操作
2.1.1 线性表的定义
线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L 命名线性表，则其一般表示为
L=(a0,a1,a2,…,an)
式中，a1是唯一的"第一个"数据元素，又称表头元素;an是唯一的"最后一个"数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。以上就是线性表的逻辑特性，这种线性有序的逻辑结构正是线性表名字的由来。
由此，我们得出线性表的特点如下;表中元素的个数有限。
表中元素具有逻辑上的顺序性，表中元素有其先后次序。表中元素都是数据元素，每个元素都是单个元素。
表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。注意∶ 线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储构，两者属于不同层面的概念，因此不要将其混淆
2.1.2 线性表的基本操作
一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可通过调用其站本操作来实现。线性表的主要操作如下∶
InitList（&L）∶ 初始化表。构造一个空的线性表。
Length（L）∶ 求表长。返回线性表工的长度，即L中数据元素的个数。 LocateElem（L，e）∶ 按值查找操作。在表工中查找具有给定关键字值的元素。 GetElem（L，i）∶ 按位查找操作。获取表工中第i 个位置的元素的值。 ListInsert（&L，i，e）∶ 插入操作。在表工中的第i个位置上插入指定元素e。
ListDelete（&L，i，&e）∶删除操作。删除表工中第i个位置的元素，并用e返回删除元素的值 PrintList（L）∶ 输出操作。按前后顺序输出线性表工的所有元素值。 Empty（L）∶ 判空操作。若工为空表，则返回 true，否则返回false。
DestroyList（&L）∶销毁操作。销毁线性表，并释放线性表工所占用的内存空间。注意∶① 基本操作的实现取决于采用哪种存储结构，存储结构不同，算法的实现也不同。②"&"表示 C++中的引用调用。若传入的变量是指针型变量，且在函数体内要对传入的指针进行改变，则会用到指针变量的引用型。在 C中采用指针的指针也可达到同样的效果。
2.1.3 本节试题精选单项选择题
1．线性表是具有n个（）的有限序列。
A.数据表 B. 字符 C. 数据元素 D.数据项
2. 以下（）是一个线性表。
A.由n个实数组成的集合    B由 100 个字符组成的序列 C. 所有整数组成的序列 D. 邻接表
3．在线性表中，除开始元素外，每个元素（） 
A.有唯一的前趋元素 B.只有唯一的后继元素 C. 有多个前趋元素 D.有多个后继元素
2.1.4 答案与解析单项选择题 
1. C
线性表由具有相同数据类型的有限数据元素组成的，数据元素由数据项组成的。 
2.B
线性表定义的要求为∶相同数据类型、有限序列。选项C的元素个数是无穷个，错误;选项 A集合中的元素没有前后驱关系，错误;选项D属于存储结构，线性表是一种逻辑结构，不要将二者混为一谈。只有选项B 符合线性表定义的要求。
3. A
线性表中，除最后一个（或第一个）元素外，每个元素只有一个后继（或前驱）元素