【玩转408数据结构】线性表——定义和基本操作

考点剖析

        线性表是算法题命题的重点，该类题目实现相对容易且代码量不高，但需要最优的性能（也就是其时间复杂度以及空间复杂度最优），这样才可以获得满分。所以在考研复习中，我们需要掌握线性表的基本操作，在平时多进行代码练习。当然在考场上，我们并不一定要求代码具有实际的可执行性，但我们需要去清晰的表达出算法的思路步骤，且算法题目只允许使用 C/C++ 语言进行实现。

线性表知识点

        关于线性表这章内容其实并不多，我们将其分为两大部分：顺序存储（也就是我们常说的顺序表）和链式存储（链表），其中对于链表部分我们需要掌握其中的 单链表、双链表、循环链表、静态链表等部分链表。

        关于线性表的内容并不是太难，我将用3-4篇文章带着大家一起了解线性表以及其实现，当我们可以自己去实现其功能的时候，我们对于该部分内容的知识掌握也就十分的熟练了，那么废话不多说，我们下面开始正式的进入线性表的学习。

线性表的定义

        线性表是具有相同数据类型的 n ( n   0) 个数据元素的有限序列，其中n为表长；当n=0时，线性表为空表。在这里我们以L命名线性表，可以将其表示为：

        其中： 是线性表的第一个元素，我们也称其为表头元素；是线性表的最后一个元素，我们称其为表尾元素。

        除了第一个元素外，每个元素有且仅有一个直接前驱（前一个元素）；除了最后一个元素外，每个元素有且仅有一个直接后续（后一个元素）。当然我们也可以将“直接前驱”称为“前驱”，将“直接后续”称为“后续”。

        通过已上知识我们总结出线性表的特点如下所示：

• 线性表元素个数有限
• 线性表元素都是数据元素，每个元素都是单个元素
• 线性表的元素具有逻辑上的顺序性，表中的元素有其先后次序
• 线性表的数据类型都相同，所以其每个元素所占空间大小相同
• 线性表的元素具有抽象性，我们讨论元素间的逻辑关系，不考虑元素究竟表示什么内容

 注：线性表是逻辑结构，表示元素一对一的相邻关系，而我们前面所了解的链表以及顺序表指的是存储结构。（也就是说线性表的顺序存储是顺序表，线性表的链式存储是链表；这两个只是在存储结构上存在差异，而其逻辑结构归根结底都是线性表）。

线性表的基本操作

        对于线性表，有一些基本操作是需要我们去学习的，至于为什么要学习这些基本操作，当然408大纲要求是要学习的，但在这里我们还是可以了解一下原因的。我们去对一些数据结构的基本操作进行封装实现，这样我们在进行复杂的操作时，可以去调用相关基本操作进行实现，并且这样进行封装也有利于减少错误的产生。

        线性表的基本操作如下所示：

InitList(&L);    //线性表的初始化
DestroyList(&L);    //销毁线性表ListInsert(&L,i,e);    //线性表的插入
ListDelete(&L,i,&e);    //线性表的删除LocateElem(L,e);    //按值查找
GetElem(L,i);    //按位查找Length(L);    //求线性表长
PrintList(L);    //按顺序输出线性表的所有值
Empty(L);    //判断线性表是否为空

（如果不懂为什么要加“&”的同学可以去学习一下，简单来说加“&”的元素我们可以修改其值，它会将其值带回来，而不加的我们在函数中修改其值是在主函数中无效的）。        

注：在这里线性表只是一种逻辑结构，我们对于其基本操作的实现是要基于存储结构的，不同的存储结构实现其功能的方法是不同的，所以对于这些基本操作的实现，我会在后面顺序表和链表的讲解中进行代码的实现，在这里我们仅对其基本操作有一个了解即可。 

小测试

1.  线性表是一个可以存不同数据类型的n ( n   0) 个数据元素的有限序列吗？
2. 在线性表中每一个元素都有自己的前驱和后续元素吗？
3. 不同的线性表的逻辑结构必然存在一些差异性。对吗？

---

答案

1. 错，线性表需要存储相同的数据类型。

2. 错，第一个元素不存在前驱，最后一个元素不存在后续。

3. 错，线性表的逻辑结构是相同的。