【数据结构】第二章——线性表(1)

线性表的定义和基本操作

封面

导言

大家好，很高兴又和大家见面啦！！！从今天开始，我们将进入线性表的学习。
线性表是算法题命题的重点。这类算法题实现起来比较容易且代码量较少，但是要求具有最优的性能（时间复杂度、空间复杂度），因此，我们应该牢固掌握线性表的各种基本操作（基于两种存储结构），在平时的学习中多注重培养动手能力。
今天这个篇章是对线性表的一个基本知识点的介绍，在这个篇章里，我们将学习到什么是线性表，线性表的基本操作又有哪些，下面我们开始介绍今天的内容。

1.线性表的定义

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。

1.1 理解定义

从线性表的定义中我们可以提取到几个信息：

  1. 相同类型
  2. n>=0
  3. 有限序列

通过这几个信息，我可以知道：

  • 线性表的数据元素的元素类型，只要是相同的数据类型就行；
  • 线性表的元素个数可以为0，即线性表中没有元素；
  • 线性表的元素个数是有上限的，即线性表的元素有一个终点；
  • 线性表的元素的排列是有序的，并不是杂乱无章的；

大家现在可以思考一下，在我们学习C语言的过程中有没有与线性表的这些条件吻合的知识点呢？

有朋友很快就想到了——数组。
现在我们来看一下数组的一些特点：

  • 数组的元素是相同数据类型的；
  • 数组的元素的下标是从0开始依次递增的；
  • 在定义数组时是需要指定数组大小的；
  • 数组最后一个元素的下标 = 数组大小 - 1；

现在咱们再来对比一下线性表的定义，是不是完全符合呀！因此我们可以得到结论：

  • 数组就是一种线性表

在线性表中，数据元素因为是有序排列的，所以每一个元素都有自己对应的序号，我们将这个序号称为位序；

与数组下标不同的是，线性表数据元素的位序是从1开始的，位序为1的元素就是线性表中的第一个元素，位序为n的元素就是线性表中的第n个元素，若用L命名线性表，则其一般表示为：
L = ( a 1 , a 2 , … … , a i , a i + 1 , … … , a n ) L=(a_1,a_2,……,a_i,a_{i+1},……,a_n) L=(a1​,a2​,……,ai​,ai+1​,……,an​)

在这个式子中 a 1 a_1 a1​和 a n a_n an​分别代表的是线性表的第一个元素和线性表的最后一个元素。

1.2 线性表的图像

在线性表中，只有唯一的“第一个”数据元素，所以我们又将 a 1 a_1 a1​称为表头元素；
在线性表中，也只有唯一的“最后一个”数据元素，所以我们又将 a n a_n an​称为表尾元素；
如果用图像来表示的话，线性表的图像应该如下所示：
线性表的定义
从图中可以看到，线性表就像是被一条线串起来的。

这时可能就有朋友有疑惑了，既然它是被一条线串起来的那为什么不叫他线性串呢？

对于这个问题，我是通过字符串来进行理解的。

在数组篇章中，我们在介绍字符串时有说过，字符串是由双引号引起的一个或多个字符，这里不管是一个字符也好，还是多个字符也好，它的本质上就是单一的字符，就比如"abc123" 这个字符串，它是由字符a、b、c、1、2、3这六个字符加上\0组成的，我们在看到这些元素的时候能够得到的信息也就是单一的信息。

而对于线性表而言，它的每一个数据元素都是由不同的数据项组成的，也就是说，一个数据元素中可能含有多个数据项，就比如班级里每次考试完会按学生的总分进行排名，如下图所示：
线性表的定义2
在这个排名表中，这里的数据元素 a 1 a_1 a1​到 a 6 0 a_60 a6​0它们包含了4个数据项，并不是像字符串这种只有单一数据项的元素，因此，我们在看到 a 1 a_1 a1​后可以了解到这所有的信息，就像这里的这张排名表一样；

1.3 线性表的逻辑特性

同样还是一张排名表，下面大家来判断一下，这个排名表是不是线性表：
线性表的定义3

在这个排名表中，有两个并列第一，两个并列第五，三个并列第八，我们现在来根据线性表的定义来判断；

  • 这里的数据元素的数据类型都是相同的——由排名、姓名、学号、总分这四个元素组成的结构体类型；
  • 这里的排名都是有序的，按照从小到大的次序来排列的；
  • 这里的元素是有限的，总共有十个元素；

单从这些点看的话，这张表也是属于线性表的。但是对于一个线性表，它不仅仅只需要满足这些条件，它还需要满足以下的逻辑特性：

  • 表头元素与表尾元素都是唯一的；
  • 除了表头元素外，其它的每个元素有且仅有一个直接前驱；
  • 除了表尾元素外，其它的每个元素有且仅有一个直接后继；

下面我们再来看这张表：

  • 刘一和陈二并列第一——并不满足唯一的表头元素；
  • 对于张三来说，他拥有两个直接前驱——并不满足有且仅有一个直接前驱；
  • 王五和赵六并列第五，对于李四来说，他拥有两个直接后继——并不满足有且仅有一个直接后继；
  • 对于孙七来说，他拥有两个直接前驱——并不满足有且仅有一个直接前驱；
  • 周八、吴九和郑十并列第八——并不满足唯一的表尾元素；
  • 对于孙七来说，他拥有三个直接后继——并不满足有且仅有一个直接后继；

通过这些逻辑特性判断，这张表并不是一个线性表。

因此我们可以得知线性表是指这种线性有序的逻辑结构，这也是线性表这个名字的由来；

2.线性表的特点

对于线性表这种线性有序的逻辑结构，它具有以下的特点：

  1. 表中元素的个数是有限的；
  2. 表中元素具有逻辑上的顺序性，表中元素有其先后次序；
  3. 表中元素都是数据元素，每个元素都是单个元素；
  4. 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间；
  5. 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。后面提到的顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆。

3.线性表的基本操作

一个数据结构的基本操作是指其最核心、最基本的操作。其它较复杂的操作可通过调用其基本操作来实现。线性表最主要的操作如下：

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

对于这些基本操作，有些地方我们需要注意：

  1. 对数据的操作无非就是——创建、销毁、增删改查；
  2. 我们可以根据实际情况来定义其它的基本操作，如这里的求表长、输出、判空等；
  3. 这里的操作内容并不是C语言提供的库函数，而是需要我们自己进行自定义的函数；
  4. 对于这些操作名，我们可以根据自己的喜好来定义，但是命名要有可读性；
  5. 这里展示的符号&表示C++语言中的引用调用，在C语言中采用指针也可达到同样的效果；
  6. 基本操作的实现取决于采用那种存储结构，存储结构不同，算法的实现也不同；

在了解完这些基本操作后，下面大家来思考一个问题：

为什么要实现对数据结构的基本操作？

这是因为我们在今后的工作中经常是团队合作的形式进行编程的，所以我们在编程的过程中需要将自己定义的数据结构通过函数的形式进行封装，以此来方便其他的成员进行使用；
其次将常用的操作/运算封装成函数也可以避免重复工作，降低出错的风险，大大的提高编程的效率；

结语

今天的内容到这里就结束了，在这个篇章中，我们介绍了什么是线性表，线性表有哪些特点，以及对于线性表有哪些基本操作。
在介绍这些内容的同时，我们了解了几个重要的术语——表长、空表、表头、表尾、前驱、后继、数据元素的位序（从1开始）。
今天对线性表的基本操作只是简单的提及了一下，并未展开进行详细介绍，在后续的篇章中，我会代码来实现这些基本操作，大家在阅读完这一篇章只需要了解这些基础知识点就行。
最后，感谢大家的翻阅，咱们下一篇再见！！！