数据结构-线性表

线性表的定义

线性表：
零个或多个数据元素的有限序列

线性表的顺序存储结构

顺序存储结构的定义

线性表的两种物理结构的第一种一一顺序存储结构。

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

image

顺序存储方式

就是在内存中找了块地，通过占地的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。

数据长度与线性表长度的区别

两个概念"数组的长度"和"续性表的长度"需要区分一下。
数组的长度是存放线性表的存储空间的长度，存储分配后这个量是一般是不变的。有个别同学可能会问，数组的大小一定不可以变吗?我怎么看到有书中谈到可以动态分配的一维数组。是的，一般高级语言，比如C、VB、 C++都可以用编程手段实现动态分配数组，不过这会带来性能上的损耗。

线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。
在任意时刻，线性表的长度应该小于等于数组的长度。

地址计算方法

由于我们数数都是从 1 开始数的，线性表的定义也不能免俗，起始也是 1， 可 C 语言中的数组却是从 0 开始第一个下标的，于是线性表的第 i 个元素是要存储在数组下标为 i-1 的位置，即数据元素的序号和存放它的数组下标之间存在对应关系
(如下图所示)。

image

用数组存储顺序表意味着要分配固定长度的数组空间，由于线位表中可以进行插 入和删除操作，因此分配的数组空间要大于等于当前线性表的长度。

其实，内存中的地址，就和图书馆或电影院里的座位一样，都是有编号的。 存储器中的每个存储单元都有自己的编号，这个编号称为地址。当我们占座后，占座的第一个位置确定后，后面的位置都是可以计算的。 试想一下，我是班级成绩第五名，我后面的 10 名同学成绩名次是多少呢?当然是 6， 7 ，…、 15 ，因为 5 + 1 , 5 + 2,…, 5 + 10。由于每个数据元素，不管它是整型、实型还是字符型，它都是需要占用一定的存储单元空间的。假设占用的是c个存储单元，那么线性表中第 i+1 个数据元素的存储位置和第 i 个数据元素的存储位置满足下列关系 (LOC 表示获得存储位置的函数)。

image

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

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

插入算法的思路;

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

删除算法的思路:

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

插入与删除的时间复杂度

image

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

image

线性表的链式存储结构

顺序存储结构不足的解决办法

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

线性表链式存储结构定义

单线索，无分支的情况。
线性表的链式存储结构的特点是用一组任意 的存储单元存储线性表的数据元素，这组存储单 元可以是连续的，也可以是不连续的。这就意味 着，这些数据元素可以存在内存未被占用的任意位置
(如下图所示)。

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

image

image

有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，谁叫它第一个呢，有这个特权。也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针，如下图所示

image

头指针与头结点的异同

image

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

image image image

单链表的读取

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

1. 声明一个结点p指向链表第一个结点，初始化j从1开始；
2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
3. 若到链表末尾p为空，则说明第i个元素不存在；

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

由于单链袤的结构中没有定义表长，所以不能事先知道要循环多少次，因此也就 不方便使用 for 来控制循环。其主要核心思想就是 "工作指针后移”，这其实也是很多 算法的常用技术。

单链表的插入与删除

单链表的插入

image
image
image

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

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

单链表的删除

image
image

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

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

分析一下刚才我们讲解的单链表插入和删除算法，我们发现，官们其实都是由两部分组成;第一部分就是遍历查找第 i 个元素；第二部分就是插入和删除元素。
从整个算法来说，我们很容易推导出：它们的时间复杂度都是 O(n)。如果在我们不知道第 i 个元素的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的。但如果，我们希望从第 i 个位置，插入 10 个元素，对于顺序存储结构意味着，每一次插入都需要移动 n一i 个元素，每次都是 O(n)。而单链表，我们只需要在第一次时，找到第 i 个位置的指针，此时为 O(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是 0(1)。显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。

单链表的整表创建

回顾一下， 顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就不一样，它不像顺序存储结构这么集中，它可以很散，是一种动态结构。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。
所以创建单链表的过程就是一个动态生成链表的过程。即从"空表"的初始状态起，依次建立各元素结点，并逐个插入链衰。

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

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

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

头插法：就是始终让新结点在第一的位置。

image

尾插法：我们把每次新结点都插在终端结点的后面。

单链表的整表删除

单链表整表删除的算法思路如下:

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

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

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

简单地对单链表结构和顺序存储结构做对比：

1. 存储分配方式

• 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
• 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

2. 时间性能

• 查找
  - 顺序存储结构O(1)
  - 单链表O(n)
• 插入和删除
  - 顺序存储结构需要平均移动表长一半的元素，时间为O(n)
  - 单链表在线出某位置的指针后，插入和删除时间仅为O(1)

3. 空间性能

• 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢
• 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

通过上面的对比，我们可以得出一些经验性的结论：

• 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。
• 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间大小的问题。而如果事先知道线性表的大致长度，比如一年十二个月，一周就是七天，这种顺序存储结构效率会高很多。

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

静态链表

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

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

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

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

image

假设我们已经将数据存入静态链袭，比如分别存放着"甲"、 "乙"、 "丁"、"戊"、 "己"、"庚" 等数据

image

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

静态链表的插入操作

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

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

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

image

静态链表的删除操作

静态链表优缺点

总结一下静态链表的优缺点

优点：

• 在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了顺序存储结构中的插入和删除操作需要移动大量元素的缺点。

缺点：

• 没有解决连续存储分配带来的表长难以确定的问题
• 失去了顺序存储结构随机存取的特性

总的来说，静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。尽管大家不一定会用得上，但这样的思考方式是非常巧妙的，应该理解其思想，以备不时之需。

循环链表

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

为了使空链表与非空链表处理一致，我们通常设一个头结点，当然 ，这并不是说，循环链表一定要头结点，这需要注意。循环链表带有头结点的空链表如图 3-13-3 所示 :

image

对于非空的循环链表就如图 3-13-4 所示。

image

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

image

从上图中可以看到，终端结点用尾指针 rear 指示，则查找终端结点是 0(1) ，而开始结点，其实就是 rear->next->next，其时间复杂也为 0(1)。

举个程序的例子，要将两个循环链袭合并成一个表时，有了尾指针就非常简单了。 比如下面的这两个循环链衰，它们的尾指针分别是 rearA 和 rearB，如图 3-13-6 所示。

image
image

双向链表

双向链表 (也uble linked List) 是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域， 一个指向直接后继，另一个指向直接前驱。

既然单链表也可以有循环链衰，那么双向链表当然也可以是循环衰。
双向链表的循环带头结点的空链表如图3-14-3 所示。

image

由于这是双向链表，那么对于链表中的某一个结点 p，它的后继的前驱是谁?当然还是它自己。它的前驱的后继自然也是它自己，即:
p->next->prior = p = p->prior->next

插入操作时，其实并不复杂，不过顺序很重要，千万不能写反了。
我们现在假设存储元素 e 的结点为:S，要实现将结点 s 插入到结点 p 和 p -> next 之间需要下面几步，如图 3-14-5 所示。

image

关键在于它们的顺序，由于第 2 步和第 3 步都用到了 p->next。如果第 4 步先执行，则会使得p->next 提前变成了 S，使得插入的工作完不成。 所以我们不妨把上面这张图在理解的基础上记忆，顺序是先搞定 s 的前驱和后继，再搞定后结点的前驱，最 后解决前结点的后继。
如果插入操作理解了，那么删除操作，就比较简单了。
若要删除结点 p，只需要下面两步骤，如图 3-14-6 所示。

image

线性表的这两种结构

image

参考：大话数据结构

感谢你花时间读到结尾！：D

后端一枚，默默搬砖撸代码，如果觉得不错欢迎关注我的公众号