第 3 章 线性表

2022/02/27晴21℃
2022/03/06多云17℃

1. 线性表的定义

具有像线一样的性质的表

线性表(List)：零个或多个数据元素的有限序列。这里数据元素是指相同类型的数据。

💕说明：

①首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
②然后，线性表强调是有限的，元素个数当然是有限的。事实上，在计算机中处理的对象都是有限的，那种无限的数列，只存在于数学的概念中。

🎈如果用数学语言来进行定义。可如下：

若将线性表记为(a1,...ai-1,ai,ai+1,...,an)，则表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当**i = 1,2,...,n-1**时，**a****i**有且仅有一个直接后继，当**i=2,3,...,n**时，**a****i**有且仅有一个直接前驱。

线性表元素的个数**n(n>0)**定义为线性表的长度，当**n = 0**时，称为空表。

在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称**i**为数据元素**a****i**在线性表中的位序。

在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

2. 线性表的抽象数据类型

对于不同的应用，线性表的基本操作是不同的，上述操作是最基本的，对于实际问题中涉及的关于线性表的更复杂操作，完全可以用这些基本操作的组合来实现。

💡例子：

要实现两个线性表集合A和B的并集操作。即要使得集合A = A ∪ B。说白了，就是把存在集合B中但并不存在A中的数据元素插入到A中即可。

仔细分析以下这个操作，发现只要循环B中的每个元素，判断当前元素是否存在A中，若不存在，则插入到A中即可。

这里，对于union操作，用到了前面线性表操作ListLength、GetElem、LocateElem、ListInsert等，可见，对于复杂的个性化的操作，其实就是把基本操作组合起来实现的。

3. 线性表的顺序存储结构

1. 顺序存储定义

线性表的顺序存储结构，指的是用一段地址连续的存储区单元依次存储线性表的数据元素。

2. 顺序存储方式

可以用C语言(其他语言也相同)的一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。
估算这个线性表的最大存储容量，建立一个数组，数组的长度就是这个最大存储容量。

描述顺序存储结构需要三个属性：

• 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
• 线性表的最大存储容量：数组长度MaxSize。
• 线性表的当前长度：length。

3. 数据长度与线性表长度区别

数组的长度：存放线性表的存储空间的长度，存储分配后这个量一般是不变的。
线性表的长度：线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。

在任意时刻，线性表的长度应该小于等于数组的长度。

4. 地址计算方法

线性表的第**i**个元素是要存储在数组下标为**i - 1**的位置，即数据元素的序号和存放它的数组下标之间存在对应关系。

用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表的长度。
存储器中的每个存储单元都有自己的编号，这个编号称为地址。
假设占用的是c个存储单元，那么线性表中第i + 1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系(LOC表示获得存储位置的函数)

对于第i个数据元素ai的存储位置可以由a1推算得出：

通过这个公式，可以随时算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间。那么我们对每个线性表位置的存入或者取出数据，对于计算机来说都是相等的事件，也就是一个常数，因此用算法中学到的时间复杂度的概念来说，它的存取时间性能为O(1)。通常把具有这一特点的存储结构称为随机存取结构。

4. 顺序存储结构的插入与删除

1. 获得元素操作

对于线性表的顺序存储结构来说，如果实现GetElem操作，即将线性表L中的第i个位置元素值返回，其实是非常简单的。就程序而言，只要i的数值在数组下标范围内，就是把数组第i - 1下标的值返回即可。

注意这个返回值类型Status是一个整型，返回OK代表1，ERROR代表0。

2. 插入操作

刚才提到，这里的时间复杂度为O(1)，现在来考虑，如果要实现ListInsert(*L,i,e)，即在线性表L中的1第i个位置插入新元素e，应该如何操作？

插入算法的思路：

• 如果插入位置不合理，抛出异常；
• 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
• 从最后一个元素开始向前遍历到第**i**个位置，分别将它们都向后移动一个位置；
• 将要插入元素填入位置**i**处；
• 表长加1。

3. 删除操作

删除算法的思路：

• 如果删除位置不合理，抛出异常；
• 取出删除元素；
• 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
• 表长减1。

分析插入和删除的时间复杂度

最好的情况：如果元素要插入到最后一个位置，或者删除最后一个元素，此时时间复杂度为O(1),因为元素要插入到最后一个位置，或者删除最后一个元素，此时时间复杂度为O(1)，因为不需要移动元素的。

最坏的情况：如果元素要插入到第一个位置或者删除第一个元素，那就意味着要移动所有的元素向后或者向前，所以这个时间复杂度为O(n)。

平均的情况：由于元素插入到第i个位置，或者删除第i个元素，需要移动n - i个元素。根据概率原理，每个位置插入或删除元素的可能性是相同的，也就说位置靠前，移动元素多，位置靠后，移动元素少。最终平均移动次数和最中间的那个元素的移动次数相等，为n - 1 / 2。

平均时间复杂度：O(n)

线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是**O(1)**；而插入或删除时，时间复杂度都是**O(n)**。这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。

4. 线性表顺序存储结构的优缺点

5. 线性表的链式存储结构

1.顺序存储结构不足的解决方法

缺点：插入和删除时需要移动大量元素，这显然就需要耗费时间。

原因：相邻两元素的存储位置也具有邻居关系。它们的编号是1,2,3,...,n,它们在内存中的位置也是挨着的，中间没有空隙，当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补。

思路：我们反正也是要让相邻元素间留有足够余地，那干脆所有的元素都不要考虑相邻位置了，哪有空位就到哪里，而只是让每个元素知道它下一个元素的位置在哪里，这样，我们可以在第一个元素时，就知道第二个元素的位置(内存地址)，而找到它；在第二个元素时，再找到第三个元素的位置(内存地址)。这样所有的元素我们就都可以通过遍历而找到。

2. 线性表链式存储结构定义

线性表的链式存储结构的特点：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。

以前在顺序结构中，每个数据元素只需要存数据元素信息就可以了。现在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址。

为了表示每个数据元素**a****i**与其直接后继数据元素**a****i+1**之间的逻辑关系，对数据元素**a****i**来说，除了存储其本身的信息之外，还需存储一个指令其直接后继的信息(即直接后继的存储位置)。把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素**a****i**的存储结构，称为结点(Note)。

n个结点(ai的存储映像)链结成一个链表，即为线性表(a1,a2,...,an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起

把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。最后一个结点指针为“空”(通常用NULL或“^”符号表示)

有时会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域不存储任何信息，有这个特权。也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。

3. 头指针与头结点的异同

4. 线性表链式存储结构代码描述

若线性表为空表，则头结点的指针域为“空”。

这只是它所表示的线性表中的数据元素及数据元素之间的逻辑关系。所以改用更方便地存储示意图来表示单链表。

若带有头结点的单链表。

空链表。

结点由存放数据元素的数据域存放后继结点地址的指针域组成。假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p → data来表示，p → data的值是一个数据元素，结点ai的指针域可以用p → next来表示，p → next的值是一个指针。p → next指向第i + 1个元素，即指向ai+1的指针。也就是说，如果p → data = ai，那么p → next → data = ai+1

6. 单链表的读取

对于单链表实现获取第i个元素的数据的操作GetElem，在算法上，相对要麻烦一些。

获得链表第i个数据的算法思路：

1. 声明一个结点**p**指向链表第一个结点，初始化**j**从**1**开始。
2. 当**k < j**时，就遍历链表，让**p**的指针向后移动，不断指向下一结点，**j**累加**1**。
3. 若到链表末尾**p**为空，则说明第**i**个元素不存在。
4. 否则查找成功，返回结点**p**的数据。

就是从头开始找，直到第i个元素为止。由于这个算法的时间复杂度取决于i的位置，当i = 1时，则不需遍历，第一个就取出数据了，而当i = n时则遍历n - 1次才可以。因此最坏情况的时间复杂度是O(n)。

主要核心思想：“工作指针后移”

7. 单链表的插入与删除

1. 单链表的插入

假设存储元素e的结点为s，要实现结点p、p → next和s之间逻辑关系的变化，只需将结点s插入到结点p和p → next之间即可。

根本用不着惊动其他结点，只需要让s → next和p → next的指针做一点改变即可。

就是说让p的后继结点改成s的后继结点，再把结点s变成p的后继结点。

考虑一下，这两句的顺序可不可以交换？
如果先p → next = s；再s → next = p → next；因为此时第一句会使得将p → next给覆盖给s的地址了。那么s → next = p → next，其实就等于s →next = s，这样真正的拥有ai+1数据元素的结点就没了上级。这样的插入操作就是失败的，造成了临场掉链子的尴尬局面。这两句话是不可以反的。

对于单链表的表头和表尾的特殊情况，操作是相同的。

单链表第i个数据插入结点的算法思路：

1. 声明一结点p指向链表第一个结点，初始化j从1开始；
2. 当j < i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；
3. 若到链表末尾p为空，则说明第i个元素不存在；
4. 否则查找成功，在系统中生成一个空结点s；
5. 将数据元素e赋值给s → data；
6. 单链表的插入标准语句s → next = p → next``p → next = s；
7. 返回成功。

用到了C语言的mallbc标准函数，它的作用就是生成一个新的结点，其类型与Node是一样的，其实质就是在内存中找了一小块空地，准备用来存放e数据s结点。

2. 单链表的删除

设存储元素ai的结点为q，要实现将结点q删除单链表的操作，其实就是将它的前继结点的指针绕过，指向它的后继结点即可

实际上就是一步，p → next = p → next → next，用q来取代p → next，即是

让p的后继的后继结点改成p的后继结点。

单链表第i个数据删除结点的算法思路：

1. 声明一结点p指向链表第一个结点，初始化j从1开始；
2. 当j < i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
3. 若到链表末尾p为空，则说明第i个元素不存在；
4. 否则查找成功，将欲删除的结点p → next赋值给q；
5. 单链表的删除标准语句p → next = q → next；
6. 将q结点中的数据赋值给e，作为返回；
7. 释放q结点；
8. 返回成功。

用到了C语言的标准函数free。它的作用就是让系统回收一个Note结点，释放内存。

单链表插入和删除算法，其实都是由两部分组成：第一部分就是遍历查找第**i**个元素；第二部分就是插入和删除元素。
对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。

8. 单链表的整表创建

创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。

单链表整表创建的算法思路：

1. 声明一结点p和计数器变量i；
2. 初始化—空链表L；
3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
4. 循环：

• 生成—新结点赋值给p；
• 随机生成—数字赋值给p的数据域p → data；
• 将p插入到头结点与前一新结点之间。

这段算法代码里，用的是插队的办法，就是始终让新结点在第一的位置。也可以把这种算法简称为头插法。

所谓的先来后到。把每次新结点都插在终端结点的后面，这种算法称之为尾插法。

注意L与r的关系：L是指整个单链表，而r是指向尾结点的变量，r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表
r → next = p;的意思，其实就是将刚才的表尾终端结点r的指针指向新结点p，当中点①位置的连线就是表示整个意思。

r → next = p;这一句应该还好理解，r = p;是什么意思呢?看下图

就是本来r是在ai-1元素的结点，可现在它已经不是最后的结点了，现在最后的结点是ai，所以应该要让将p结点这个最后的结点赋值给r。此时r又是最终的尾结点了。

循环结束后，那么应该让这个链表的指针域置空，因此有了“r → next = NULL”，以便以后遍历时可以确认其是尾部。

9. 单链表的整表删除

单链表整表删除的算法思路：

1. 声明一结点p和q；
2. 将第一个结点赋值给p；
3. 循环：

• 将下一结点赋值给q；
• 释放p；
• 将q赋值给p。

常见的错误就是有同学会觉得q变量没有存在的必要。在循环体内直接写free(q);p = p → next;即可。

要知道p是一个结点，它除了有数据域，还有指针域。在做free(p);时，其实是在对它整个结点进行删除和内存释放的工作。

变量q使得下一个结点是谁得到了记录，以便于等当前结点释放后，把下一结点拿回来补充。

10. 单链表结构与顺序存储结构优缺点

结论：

• 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构
• 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。

总之，线性表的顺序存储结构和单链表结构各有其优缺点，不能简单的说哪个好，哪个不好，需要根据实际情况，来综合平衡采用哪种数据结构更能满足和达到需求和性能。

11. 静态链表

有人就想出来用数组来代替指针，来描述单链表。
首先让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每个下标都对应一个data和一个cur。数据域data，用来存放数据元素，也就是通常要处理的数据；而游标cur相当于单链表中的next指针，存放该元素的后继在数组中的下标。

用数组描述的链表叫做静态链表，这种描述方法还有起名叫做游标实现法。

为了方便插入数据，通常会把数组建立得大一些，以便有一些空闲空间可以便于插入时不至于溢出。

另外对数组第一个和最后一个元素作为特殊元素处理，不存数据。通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点作用，当整个链表为空时，则为O2。

假设已经将数据存入静态链表，比如分别存放着“甲”、“乙”、“丁”、“戊”、“己”、“庚”等数据

此时，“甲”这里就存有下一个元素“乙”的游标2，“乙”则存有下一元素“丁”的下标3。而“庚”是最后一个有指元素，所以它的cur设置为0。而最后一个元素的cur则因“甲”是第一有值元素而存有它的下标为1。而第一个元素则因空闲空间的第一个元素下标为7，所以它的cur存有7。

1. 静态链表的插入操作

静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。

在动态链表中，结点的申请和释放分别借用malloc()和free()两个函数来实现。在静态链表中，操作的是数组，不存在像动态链表的结点申请和释放问题，所以需要自己实现这两个函数，才可以做插入和删除的操作。

为了辨明数组中哪些分量未被使用，解决的办法：将所有未被使用过的及被已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。

一方面它的作用就是返回一个下标值，这个值就是数组头元素的cur存的第一个空闲的下标。上面的例子，返回7
下标为7的分量准备要使用了，就得有接替者，所以把分量7的cur值赋值给头元素，也就是把8给space[0].cur，之后就可以继续分配新的空闲分量，实现类似maloc()函数的作用。
现在如果需要在“乙”和“丁”之间，插入一个值为“丙”的元素，按照以前顺序存储结构的做法，应该要把“丁”、“戊”、“己”、“庚”这些元素都往后移一位。但目前不需要，因为有了新的手段
先在队伍最后一排第7个游标位置待着，接着找到“乙”，cur不再是游标为3的“丁”了，把它的下一位的游标改为7。“乙”把cur值改了。此时“丙”的cur改为3。就这样，整个排队的次序发生了改变。

• 当执行插入语句时，目的地是要在“乙”和“丁”之间插入“丙”。调用代码时，输入i值为3
• 第4行让k = MAX_SIZE -1 = 999
• 第7行，j = Malloc_SSL(L) = 7。此时下标为0的cur也因为7要被占用而更改备用链表的值为8
• 第11~12行，for循环l由1到2，执行两次。代码k = L[K].cur，使得k = 999，得到k = L[999].cur = 1，再得到k = L[1].cur = 2
• 第13行，L[j].cur = L[k].cur；因j = 7，而k = 2得到L[7].cur = L[2].cur = 3。这就是刚才让“丙”把它的cur改为3的意思
• 第14行，L[k].cur = j；意思就是L[2].cur = 7。也就是让“乙”得点好处，把它的cur改为指向“丙”的下标7

在数组中，实现不移动元素，却插入了数组的操作

2. 静态链表的删除操作

for循环因为i = 1而不操作，j = k[999].cur = 1，L[k].cur =L[j].cur也就是L[999].cur = L[1].cur = 2。这其实就是告诉计算机现在“甲”已经离开了，“乙”才是第一个元素。Free_SSL(L,j)表示什么意思呢？

意思就是“甲”现在要走，这个位置就空出来了，也就是，未来如果有新人来，最优先考虑这里，所以原来的第一个空位分量，即下标是8的分量，它降级了，把8给“甲”所在下标为1的分量的cur，也就是space[1].cur = space[0].cur = 8，而space[0].cur = k = 1其实就是让这个删除的位置成为第一个优先空位，把它存入第一个元素的cur中

静态链表也有相应的其他操作的相关实现。比如代码中的ListLength

3. 静态链表优缺点

12. 循环链表

对于单链表，由于每个结点只存储了向后的指针，到了尾标志就停止了向后链的操作。这样，当中某一结点就无法找到它的前驱结点了。

将单链表中中断结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表(circular linked list)

为了使空链表与非空链表处理一致，我们通常设一个头结点，这并不是说，循环链表一定要头结点

循环链表和单链表的主要差异：就在于循环的判断条件上，原来是判断p → next是否为空，现在则是p → next不等于头结点，则循环未结束。
在单链表中， 我们有了头结点时，可以用O(1)的时间访问第一个结点，但对于要访问到最后一个结点，却需要O(n)时间，因为需要将单链表全部扫描一遍。
有没有可能用O(1)的时间由链表指针访问到最后一个结点
不过需要改造以下这个循环链表。不用头指针，而是用指向终端结点的尾指针来表示循环链表，此时查找开始结点或终端结点都很方便

终端结点用尾指针rear指示，则查找终端结点是O(1)，而开始结点，其实就是rear → next → next，其时间复杂也为O(1)

举个例子：要将两个循环链表合并成一个表时，有了尾指针就非常简单了。比如下面的这两个循环链表，它们的尾指针分别是rearA和rearB

要想把它们合并，只需要如下的操作即可

13. 双向链表

在单链表中，有了next指针，这就使得要查找下一结点的时间复杂度为O(1)。可是要查找的是上一结点的话，最坏的时间复杂度就是O(n)了，因为每次都要从头开始遍历查找。
为了克服单向性这一缺点，设计出了双向链表。双向链表(double linked list)是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

既然单链表也可以有循环链表，那么双向链表当然也可以是循环表。

由于这是双向链表，那么对于链表中的某一个结点p，它的后继的前驱还是它自己。它的前驱的后继自然也是它自己。

双向链表是单链表中扩展出来的结构，所以它的很多操作是和单链表相同的，比如求长度的ListLength，查找元素的GetElem，获得元素位置的LocateElem等，这些操作都只要涉及一个方向的指针即可，另一指针多了也不能提供什么帮助。

双向链表既然是比单链表多了如可以反向遍历查找等数据结构，那么也就需要付出一些小的代价：在插入和删除时，需要更改两个指针变量。

1. 插入操作

假设存储元素e的结点为s，要实现将结点s插入到结点p和p → next之间需要下面几步

关键在于它们的顺序，由于第2步和第3步都用到了p → next。如果第4步先执行，则会使得p → next提前变成了s，使得插入的工作完不成。不妨把上面这张图在理解的基础上记忆，顺序是先搞定s的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继。

2. 删除操作

若要删除结点p，只需要下面两步骤

总结一下，双向链表相对于单链表，更复杂一些。因为多了prior指针，对于插入和删除时，需要格外小心。另外它由于每个结点都需要记录两份指针，在空间上是要占用略多一些的。不过，由于它良好的对称性，使得对某个结点的前后结点的操作，带来了方便，可以有效提高算法的时间性能。就是用空间换时间。

14. 总结

1. 线性表的定义
2. 线性表的抽象数据类型
3. 线性表的两大结构
4. 顺序存储结构和链式存储结构
5. 单链表、循环链表、双向链表
6. 静态链表