线性表是线性数据结构吗（数据结构-线性表）

线性表是线性数据结构吗（数据结构-线性表）接下来看有关线性表插入和删除的操作。首先来看插入的操作，叫 ListInsert ，它的传入参数有三个，第一个是线性表的引用，这里传引用类型同样是为了达到实现更方便。第二个传入参数是 i ，也就是在第 i 个位置进行插入。第三个传入的参数是插入的元素 e 。要注意的一点就是在所有线性表的插入操作中，所有的插入都是前插，也就是第 i 个位置的前一个位置进行插入，这是一个小的规定。接下来看删除操作。删除操作叫 ListDelete ，它传入的参数也是三种，第一个是线性表的引用，第二个表示要删除的第 i 个位置的元素，最后一个参数是值的引用，通过该引用返回该元素的值。插入与删除操作同样要注意，这个传入参数 i 一定也在表长范围之内，一旦超过表长，插入和删除操作都没有意义了。然后看输出操作。输出操作很简单，就是按前后顺序输出线性表 L 的所有元素的值。接下来有两种查找操作，一种是按值查找，另一种是

声明

本文非原创，内容来自cnblogs的【湫兮如风】(https://www.cnblogs.com/qiuxirufeng/p/10391938.html) 数据结构系列博文，写得真的非常棒，可以去看看，所以小编我也是一边学，一遍与大家分享，如有不足之处，还请大家多多指教，谢谢

什么是线性表？

线性表是具有相同类型的 n (n>=0) 个元素的有限序列，其中 n 为表长，当 n=0 时，该表为空表。为什么要相同类型？计算机在处理大量数据的时候，把相同的数据元素称作为数据对象。往往要处理相同的数据元素，也就是处理一种数据对象。不会把音频和图片杂糅到一起进行处理。也不会把抽象事物，比如说人和汽车组合到一起进行处理。因为这样没有意义，也没有高的效率。

对于相同类型，在接下来所学到的所有的数据结构中都有这样的要求。因为具有相同类型的数据结构，它在解决实际问题，实现算法时，才更加的有意义。其次，对于这个类型的范围，它的定义其实并不狭隘，并不仅仅局限于我们常见的类型，比如说整型、浮点型这样的类型。对于从实际生活中抽象出来的类型，比如说一本书、一个人也是可以作为一个元素的。它与 C 中的面向对象的类比较相似。

除了相同类型，定义中还有一个比较重要的点，那就是有限列。什么是有限？就是说明该线性表的长度是有限的，因为计算机无法处理无限多的数据。第二个是序列，根据下面的表示方法可以发现，线性表中每一个元素都是有序号的，序列的意思就是有序号的一种排列。这就是在线性表定义中比较重要的两个点。若 L 命名为线性表，则一般表示为：

在 L 当中，线性表的每一个元素都具有相同类型，都是属于同一个数据对象的数据元素，分别是 a1、a2 一直到 an 。可以发现，对于所有的元素它都是有序号的。那么在表中，第一个元素，称它为表头元素，最后一个元素称它为表尾元素。除了这样，该线性表还有一些其他的逻辑关系。

在线性表中，每一个元素除了表头元素，它都有一个前驱结点。也就是 ai 1 的前驱结点，即是 ai 。同样在表中，每一个元素除了表尾元素，它都有一个后继结点。也就是 ai 的后继结点 ai 1 这就是线性表在定义上的所有知识点。根据定义，总结一下线性表的特点：

• 表中元素个数有限
• 表中元素具有逻辑上的顺序性，在序列中各个元素排序有其先后次序
• 表中元素都是数据元素，每个元素都是单个元素
• 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间
• 表中元素具有抽象性，即讨论元素间一对一的逻辑关系，而不考虑元素究竟表示的内容
• 线性表是一种逻辑结构，表示元素之间一对一相邻的关系

线性表的基本操作

首先对于任何一种数据结构，都有一个创建它的方法，也有一个销毁它的方法。在线性表中创建它的方法叫做 InitList，传入的参数是一个线性表，它的作用是初始化这个线性表，构造一个空的线性表。注意传入的参数是引用类型。第二个就是销毁的操作，叫 DestroyList，传入的参数依旧是一个引用类型的线性表。它是销毁这个线性表，并释放线性表所占用的内存空间。注意针对不同的存储结构而言，它们具体的实现方式可能有非常大的差异。

接下来有两种查找操作，一种是按值查找，另一种是按位查找。首先是按值查找操作，它叫做 LocateElem，Elem 指的是元素。传入的参数是线性表以及一个值 e 来表示，它的意思是在表 L 中查找具有给定关键字值的元素，也就是找到该表中值是 e 的元素。注意，往往查找的过程当中，返回的值是第一个查找到的元素，也就是说假如在该表中有多个符合该值的元素，只返回查找的第一个。接下来看按位查找，它叫 GetElem，传入的参数依旧是线性表，但是第二个参数有所不同，它是一个 i 。这个 i 表示获取表中第 i 个位置的元素。因为线性表每一个元素都是有序号的，返回的就是序号是 i 的这个元素的值。还有一点需要注意的就是，按位查找这个输入的参数 i ，一定是在 0 到表长的大小之间，因为不可能找到比表长 大的位置元素的值。

接下来看有关线性表插入和删除的操作。首先来看插入的操作，叫 ListInsert ，它的传入参数有三个，第一个是线性表的引用，这里传引用类型同样是为了达到实现更方便。第二个传入参数是 i ，也就是在第 i 个位置进行插入。第三个传入的参数是插入的元素 e 。要注意的一点就是在所有线性表的插入操作中，所有的插入都是前插，也就是第 i 个位置的前一个位置进行插入，这是一个小的规定。接下来看删除操作。删除操作叫 ListDelete ，它传入的参数也是三种，第一个是线性表的引用，第二个表示要删除的第 i 个位置的元素，最后一个参数是值的引用，通过该引用返回该元素的值。插入与删除操作同样要注意，这个传入参数 i 一定也在表长范围之内，一旦超过表长，插入和删除操作都没有意义了。然后看输出操作。输出操作很简单，就是按前后顺序输出线性表 L 的所有元素的值。

最后还有两个操作，一个是判空操作，判断该表是否为空表，若是空表则返回 TRUE，否则返回 FALSE。另一个是求表长，求表长的意思就是返回线性表的长度，即 L 中数据元素的个数。

顺序表的定义

线性表的顺序存储又称为顺序表，来看一个生活中的例子：周末和朋友一起吃火锅，人非常多，我们需要在等候区等候，这个等候区就与顺序表有非常多的相似之处，借助它去理解顺序表的特点。首先，在等候区有非常多的椅子，这些椅子往往是排成一排连续排放的，中间不会空出很大的空间造成浪费。这就与在顺序表中选取存储单元的方法是一样的，我们会选取一段地址连续的存储单元去存放顺序表。接着工作人员会安排我们在椅子上连续的坐下等候。在存储单元当中去进行数据的存放是一样的，也是依次地存放线性表当中的数据元素，中间也不会空出许多存储单元造成空间的浪费。最后结伴而行的朋友也会坐在相邻的椅子上，这与顺序表的存放是相同的。在逻辑上相邻的两个元素在物理位置上也要保证它相邻，也会把它存放在相邻的存储单元上。在这个例子当中，其实椅子就代表着存储单元，而每一个等候的人就是要存放的数据元素。来总结一下顺序表的特点：一组地址连续存放的存储单元依次存放线性表的元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻，所以顺序表中逻辑顺序与物理顺序相同

其中在逻辑上相邻的两个数据元素，在顺序表中也存放在相同的存储单元当中，每一个小格子就代表一个存储单元。在程序语言设计中，往往使用数组来实现顺序表。但是数组和顺序表又有一些差别，第一个差别是数组下标是从 0 开始的，而顺序表是从 1 开始的。还有一个就是数组的容量是不可以增加的，而顺序表的容量是可以增加的。还有一些其他的差别，比如说数组可以是多维的，而顺序表是一维的。

根据顺序存储可以知道，它是可以实现随机存取的。这是因为我们可以从第一个元素的地址直接推算出其他元素的地址。在顺序表当中，每一个存放的元素都属于同一种数据对象。那么每一个数据元素，它的大小都是一样的。根据这一特点，我们可以计算出每一个数据元素存储的地址。

第一个元素的地址假设它是 LOC(A) 计算第二个元素的地址就可以用第一个元素的地址加上第一个数据元素 a1 所消耗的存储空间，用 sizeof 可求得该数据元素所消耗的存储空间大小。这里需要注意的一点是，n 与 MaxSize 是有含义上的不同的，其中 an 代表的是顺序表中最后一个数据元素，而 MaxSize 代表的是数组的最后一个存储单元。

顺序表的两种实现方法

顺序表可以用数组来实现。根据数组的两种分配方式，也就有两种描述顺序表的方法。分别是静态描述分配顺序表的方法和动态描述分配顺序表的方法。首先来看数组静态分配时是如何描述一个顺序表的。

#define MaxSize 50 typedef struct{ ElemType data[MaxSize]; int length; }SqList;

这就是描述顺序表的语句。第一句是定义了一个宏，也就是把 MaxSize 定义为 50，这也就是数组的最大容量。接着定义了一个结构体。结构体就是把多个基本数据类型组合到一起构成一个新的数据类型。它的定义语句是用 typedef struct ，然后用大括号圈起来所要包含的基本数据类型。最后 SqList 代表着该结构体的名字。这个结构体当中有一个存放顺序表的数组，它是 ElemType 类型，其中数组大小是 MaxSize，也就是 50，还有一个整型的 length，它是代表顺序表的长度。这就是一个顺序表的程序设计语言描述。接下来看数组动态分配是如何描述顺序表的：

#define MaxSize 50 typedef struct{ ElemType *data; int length; }SqList;

这是动态分配时描述顺序表的语句，观察发现这里用的是指针，指针是存放一个存储单元地址的。顺序表根据第一个数据元素的地址和数据元素的大小，就可以计算出任意数据元素的位置。那么只要定义了第一个数据元素的指针，就可以描述整个顺序表。但是这一个变量它仅仅是一个地址，而没有确切的空间，所以在使用时，需要动态的申请空间。申请空间有这样两条语句：

C语言 L.data = (Elemtype*)malloc(sizeof(ElemType)*InitSize); C 语言 L.data = new ElemType[InitSize];

L 是 SqList 类型的一个变量，也就是 L 代表这一个顺序表，接着用 malloc 这个动态函数来申请空间，函数参数部分是申请空间的大小，是用 sizeof 计算每一个数据类型的大小乘以它的个数，就计算出整个需要申请空间的大小，malloc 前面的括号部分可以理解为强调了申请空间的类型。这是 C 语言中的方法。C 中直接 new 一个申请空间的类型和大小。在使用动态分配时，一定要先申请空间才能使用，因为如果没有申请空间，它仅仅是一块地址，而没用所需要的空间。静态分配和动态分配有什么不同呢？其实也就是数组的不同。在静态分配时，我们在编写的时候，就已经确定了数组的大小。而动态分配时，没有确定它的大小，是根据动态分配语句在运行时才将它的大小进行分配。这样有一点的好处就是，在静态分配时，当我想要存放顺序表的数据元素过超过 50 的时候则会产生错误溢出，而动态分配时，如果一旦超过了分配的空间大小，可以再重新分配一块内存空间，把旧的空间和所增加的数据元素转移到新申请的空间上，这样就不会产生溢出的问题了。这是动态分配的一个优点。记住，动态分配依旧是一块连续的存储空间，绝非是链式存储。

顺序表上基本操作的实现

线性表在采用不同的存储结构时，它的描述方法是不一样的，那么它的基本操作实现方法也截然不同。下面来看线性表在顺序存储下，也就是顺序表的每一个基本操作的具体实现方法以及编写方法。

插入操作

以生活中的例子为例，一群朋友去吃火锅。此时有一个女生过来了，她叫小红。小红是小绿的女朋友，当然想和小绿坐在一起，但是小绿旁边是没有空位置的。所以小绿麻烦他旁边的朋友小黄和小黑依次移动了一个位置。这样就空出了一个位置，小红就可以过来坐下了。这样就完成了一个类似顺序表插入的过程。

知道了顺序表插入的大致过程，来看它用程序语言是如何编写的。首先画出了一个顺序表

其中的数据元素是连续存放的。接着标出了存放该顺序表数据元素的数组下标。注意一下，数组下标是从 0 开始的，而顺序表的元素标号是从 1 开始的。接着用 C 写出了该插入操作的函数体：

它的返回值类型是一个布尔类型，表示如果插入成功会返回一个 True ，插入失败会返回一个 False。它有三个参数，分别是一个引用类型的顺序表 L，这里为什么用引用类型？因为在函数体内部进行操作，其实是作用一个局部变量上的，不会真正作用到这个参数上，如果不用引用类型，是不能把插入操作真正作用到传入的顺序表上的。接着是一个整型变量 i，它表示的是插入的位置，要注意在采用插入操作时，往往是前插法，这是一个默认规定。还有一点要注意的就是，i 对应的是顺序表的表号而非数组的下标。最后一个参数是所插入的数据元素 e。

首先第一个条件 i<1 || i>L.length 1 ，顺序表的元素标号是从 1 开始的，i 表示的是插入的位置，如果插入的位置是 0 或者更小，又或者比 L.length 1 还大，都是不合法的。第二个条件判断的是插入的数组是否有足够空间去插入，因为数组不可以增加容量，一旦满了就没用新的空间去提供插入了。循环语句中申请了变量 j 初始化为顺序表的长度，j 进行减一操作，一直到 j=i 的时候中止循环。循环体中 L.data[j] = L.data[j-1] 的意思就是把每一个数据元素向后移了一位，一直移动到 ai 移动到原先 ai 1 的位置。 执行完了所有的循环，空出了一个位置用于插入，L.data[i-1] = e 就是把要插入的元素放到该位置。注意，在 i 的位置，元素对应的下标是 i-1。最后将顺序表的长度加一。

再来看一下这个程序的时间复杂度，当循环次数最少时，它就是最好的时间复杂度，什么时候循环次数最少呢？发现当在顺序表的尾部，也就是 L.length 1 的时候，这时候不用进行元素的移动，它的循环次数是 0，所以它的最好时间复杂度是 O(1) ，因为它的语句频度是常数级别的。接着来看平均时间复杂度，平均时间复杂度是在所有情况等概率的情况下，计算它的期望。这里的等概率，一定是合法的情况。所以 i 一共有 n 1 个合法位置，n 个数据元素，加上第 n 个数据元素之后的那个位置，都可以进行插入。所以每一个插入等概率的情况下，它的概率是：

接着根据概率的知识，可以用每一个位置的概率乘以它循环的次数，它是从尾部一直循环到 i ，所以循环了 n-i 1 次，根据等差数列求和公式可以计算：

计算结果与 n 同阶无穷大，所以它的平均时间复杂度为 O(n) 。

最坏就是循环次数最多，即每一个数据元素都要向后移动一位，也就是插入在第一个位置时是最坏的情况，所以要循环 n 次，所以最坏情况下的时间复杂度是 O(n) 。

删除操作

还是一群小伙伴在等候区等待吃火锅，这时小绿被他的女朋友叫回去一起学习数据结构，那么小绿要走了，小绿走了之后就空出了一个位置。在等候区中间是不可以有空的位置的，所以说小黄和小黑两个人会依次向前移一位。

知道了顺序表删除的大致过程，来看它用程序语言是如何编写的。首先画出了一个顺序表：

代码如下：

函数的返回值依旧是一个布尔类型。它有三个参数，分别是一个引用类型的顺序表 L，一个整型变量 i 表示删除的位置，一个引用类型的数据元素 e ，这里使用引用类型也是因为在函数体内部进行操作，是作用在一个局部变量上的，不会真正作用到这个参数 e 上，所以说使用引用类型来将所删除的这个数据元素真正的返回到函数外部。第一个条件是判断删除的位置是否合法。接着 e = L.data[i-1] 是在保存要删除的数据元素，将 i 位置的数据元素，对应下标 i-1，赋值给 e 。然后循环从 i 开始，每次进行加一操作，一直循环到 L.length-1 为止，也就是从 i 一直循环到 n-1，将 ai 赋值给 ai 1 ，也就是将数组下标为 i 的赋值给 i-1 的，这样就将 ai 之后的所有数据元素都向前移了一位。接着将顺序表的长度减一。

再来看一下这个程序的时间复杂度，最好的时间复杂度是删除最后一个元素，它的最好时间复杂度是 O(1) 。所有合法的删除位置有 n 个，因为有 n 个数据元素。所以每一个合法位置的概率都是 1/n ，它的循环次数是从 i 循环到 L.length-1 ，所以是 n-i 次，所以它的期望是 (n-1)/2 ，它与 n 同阶无穷大，所以它的平均时间复杂度为 O(n) 。删除第一个数据元素循环的次数最多，此时需要循环 n-1 次，与 n 同阶无穷大，因此最坏时间复杂度为 O(n) 。

按值查找

需要找到等候区的小绿，等候区是这样依次坐下的。于是依次进行查找，从第一个位置开始，一直找到第三个位置，发现他是小绿。

首先画出了一个顺序表：

代码实现：

这个函数的返回值是一个整型变量，它表示返回的是一个顺序表的下标。两个参数分别是查找的顺序表以及查找的值。所有对输入参数进行修改的操作，都使用引用类型。所有进行查找的操作都不会使用引用类型。首先是一个整型变量 i ，它用来存放最终的输出结果。接着是一个循环，变量 i 从下标 0，也就是第一个元素开始，每一次循环进行加一操作，一直循环到 L.length-1 ，也就是下标 n-1 的位置，一共执行了 n 次。循环体的内容是一个判断语句，判断此时数据元素是否为要找的那个元素，如果相等返回当前顺序表的下标，也就是 i 1。最后 return 0 表示循环结束了，还没有找到对应的这个值的位置，那么就说明顺序表当中是没有该值的，此时就返回一个 return 0 表示查找失败。

再来看一下这个程序的时间复杂度，好的时间复杂度依旧是循环的次数最少，也就是第一个数据元素就是要找的那个值，所以最好的时间复杂度为 O(1) 。一共有 n 个元素，查找概率是 1/n ，查找次数是 n-i 次，它的期望是 (n 1)/2 ，它与 n 同阶无穷大，所以它的平均时间复杂度为 O(n) 。最后一个元素被找到是最坏的情况，循环了 n 次，因此最坏时间复杂度为 O(n) 。

单链表的定义

顺序表它虽然可以实现随机存取，但是在初始化时需要申请一大块连续的存储空间，而且它在执行例如插入、删除操作时也需要大量的移动元素，时间复杂度较高。今天讲述线性表的一种新的存储表示方法，也就是线性表的链式表示。首先，还是先来看单链表的定义。书中说，线性表的链式存储，把它称作为单链表。来看一个小例子，今天又是周末，小明和他的小伙伴们又想来吃火锅。今天与上次不同，他们不是一同前来的，而是各自来的火锅店，所以他们被安排在等候区等候的位置就不一定连续了。这与线性表的链式存储，也就是单链表相同，它们在存储单元上是不一定连续的。单链表通过一组任意的存储单元来存储线性表中的数据元素，也就是数据元素存储的位置不一定连续

接下来，如果一号小朋友知道了有位置消息，他会通过手机告诉下一个小伙伴他等到了位置，接下来四号小朋友也会用手机通知下面的小伙伴，接着依旧六号小朋友会通知最后的小伙伴，告诉他等到位置了，这样就用手机维持这样一个线性的逻辑关系。

在链式存储中，手机这样的用以维持线性逻辑关系的事物叫做指针，所以，在单链表中，是通过指针来实现线性的逻辑关系的，它与顺序存储是不同的。顺序存储是通过存储单元相连就可以实现逻辑上的线性关系，但是在单链表中，数据元素是存储在任意位置的，所以只能通过指针来实现线性逻辑关系。

单链表的实现

首先给出一个线性表，存放数据元素，a1 到 an 有这样的线性逻辑关系。单链表在存储空间上是这样存放的，它是存放在任意位置的，这个任意位置表示它们不一定要连续。如图所示的 a2、a3 与 a3、a4 。第二个很明显的差别是单链表在存放数据元素同时，不仅仅存放了数据本身，还存放了下一个数据元素地址，通过这样的地址来维持了线性的逻辑关系。表示 a2 是 a1 的后继，a3 是 a2 的后继。这样地址像一条链子一样，把所有的数据元素串了起来，形成了一个单链表，我们管这样的数据加地址的组合叫做单链表的一个节点。该节点是由存放数据元素的数据 data 和存放下一个数据元素的地址的指针域 next 共同来组成。代码实现如下：

在程序设计语言上，我们会通过一个结构体来实现这样一个节点，它的名字叫做 LNode ，其中包含保存数据元素的变量 data 和存放下一个数据元素的指针 LNode *next 。它这个结构体的名字不仅仅叫做 LNode，还叫做 LinkList。通过名字可以发现一个节点也可以表示为一个单链表。因为只要给出第一个节点的地址，就可以依次找到属于这个单链表的所有节点。所以通过一个指针，还可以表示该单链表。单链表虽然有一些优点，但是它也存在一些弊端。比如说单链表在存放数据元素的同时，还要存放指向下一个节点位置的指针域，那么这些指针域会造成空间的浪费。单链表在存放数据元素时，没有像顺序表那样存储空间连续相邻这样一个特点，所以不能实现随机存取，只能实现顺序存取。也就是说，想要找到其中的一个数据元素，只能从第一个数据元素的位置依次查找，遍历单链表。这就是单链表的具体实现方式。

这是所画出的一个单链表 L。其中保存的数据元素是 a1 到 an ，并且 a2 是 a1 后继 ，a3 是 a2 后继这样的线性逻辑关系。在线性表的表头也就是 a1 节点的位置有一个指针 head 指向了第一个数据节点，这样指针管它叫做头指针。如果知道了头指针，也就知道了整个线性表所有的节点。因为可以通过头指针，按照遍历的方法找到线性表当中的每一个节点。但是在平时利用单链表去解决问题时，往往会利用这样一种引入头结点的单链表。

此时头指针指向的是头结点，而头结点的 next 域指向的是线性表当中的第一个数据元素的位置。头结点中的数据域，往往是不存放数据元素的，但是可能有时会利用它来存放一些关键的信息，比如说单链表的表长等。在引入头结点之后，很多东西都发生变化了，其中一个就是如何判断单链表是一个空表。观察第一种单链表，发现判断他为空的方法为头指针是否为空，如果头指针为空时，那么单链表就为空。第二种判断单链表为空的方法是头结点的 next 域，也就是 head -> next 为 null 时，单链表 L 为空。

要记住引入头结点之后，第一个数据元素依旧是头结点的 next 域指向的那个节点，而绝非是头结点。在平常我们利用单链表解决问题时，为什么会用这种引入头结点的单链表呢？它有两个优点，第一个优点是链表的第一个位置和其他位置的操作进行统一了。为什么可以统一操作，比如说在单链表没有头结点时，想要实现插入操作，在表中进行插入操作时，两边都是有节点的，而在表头进行插入操作时，前面是没有节点的，所以在具体实现上，这里会有所不同。接着来看带有头结点的单链表，在表头进行插入时，它两边依旧是都有节点的，所以它就达到了一个统一操作的目的。第二个优点是空表和非空表的操作统一。如何统一？我们知道，无论是有没有数据节点，带有头结点的，单链表始终 head 指针都不为空，它始终指向了头结点，所以说空表和非空表的操作也统一了。这就是为什么在利用单链表时要引入一个头结点。