第二章 线性表

专业基础►数据结构 评论

第二章 线性表

线性表的定义

  • 线性表是一个具有相同特性的数据元素的有限序列。
  • 特性：
    • 相同特性：所有元素属于同一数据类型。
    • 有限：数据元素个数是有限的。
    • 序列：数据元素由逻辑序号唯一确定。一个线性表中可以有相同值的元素。
    • 结构：除第一个元素无前驱、最后一个元素无后继外，其余每个元素都有唯一前驱和唯一后继元素。
  • 线性表中所含元素的个数叫做线性表的长度。
  • 线性表的逻辑表示：

线性表的顺序存储结构

线性表的顺序存储结构定义

  • 把线性表中元素按照顺序存储的方法存储（即存储位置为一篇连续的空间，如数组）
  • 静态存储顺序表
    • 定义：（意味着last是从0开始的）
    • 特性：
      • 随机存取
  • 动态存储顺序表：
    • 创建动态存储的顺序表：
      • 关键在于数组的长度是根据具体情况来分配的L->elem = (ElemType *)malloc(maxSize*sizeof(ElemType))

线性表在静态顺序存储结构上的基本运算

    1. 求某个元素在顺序表中的序号
    • 因为数组中计数是从0开始，而实际生活中数数是从1开始，所以需要i + 1
    • 控制条件为找到数组的最后一个元素i <= L.last
    1. 求序号为i的数据元素值

    • 法一：

      • 注意控制条件，i过大或者过小都会超出数组边界，故需i < 1 || i > L->last +1

    • 法二：

    • 二者的区别在于直接返回元素的值还是通过指针传递元素的值。

    1. 在顺序表的第i个位置插入数据元素 (1 <= i <= last + 2)
    • 控制条件：此时插入位置i的范围要比数组原来的范围增加一，因为数组整体要先增加一个位置，所以有i < 1 || i > L->last + 2.
    • 关键的元素后移操作：先在数组末尾增加上一个位置，然后从后往前逐次将第i位起的元素后移，for(k = L->last; k >= i - 1 ; k--) L->elem[k+1] = L->elem[k];
    • 末尾别忘了last的更改。
    • 算法的时间复杂度：

    1. 顺序表删除第i个位置的元素（1 < i < last + 1)
    • 先将特殊的情况考虑，再做常规处理：i超出数组的范围和顺序表为空的两种情况。i < 1 || i > L->last + 1和L->last < 0.(i = 0 不行是因为此处的i代表的是实际生活中的计数，而不是数组从零开始的计数)
    • 关键的元素前移操作：从第i个元素之后的一个元素开始逐渐前移 for(k = i; k <= L->last; k++) L->elem[k-1] = L->elem[k];，控制条件为k <= L ->last的原因是，此时的k作为数组的下标而不是实际生活中的计数，与last的意义相同了，所以不需要再做元素个数与数组下标之间+1 的转换。
    • 算法的时间复杂度：

线性表动态顺序存储结构的算法

  • 二路归并算法
    • 将两个非递减顺序表合并为一个有序表，称为二路归并。
    • 基本原理：同时遍历两个顺序表，遍历过程中比较元素的大小并存入有序表中，并根据比较结果调整两个顺序表遍历的速度。
    • 注意：两表的同时遍历进行结束之后，还要检查是否有哪个表没有遍历完。

线性表的链式存储结构

线性表的链式存储结构的定义

  • 链式存储结构即使用链表存储。使用链表时，每个逻辑结点单独存储，为了表示逻辑关系，每个结点里增加一个指针域。
  • 链表的分类：
    • 单链表：每个物理结点里增加一个指向后继结点的指针域。
      • 当访问过一个结点后，只能接着访问它的后继结点，而无法访问它的前驱结点。
    • 循环单链表：将表中尾结点的指针域改为指向表头结点，整个链表形成一个环。
      • 从表中任一结点出发均可找到链表中其他结点。
      • 链表中没有空指针域（最后一个结点的空指针域现在指向头结点）
    • 双向链表: 每个物理结点增加一个指向后继结点和一个指向前驱结点的指针。
      • 从任一结点出s发可以快速找到其前驱结点和后继结点。
      • 从任一结点出发可以访问其他任一结点。

单链表

结点类型定义

  • 单独创建一个 LinkList类型的目的是区分普通数据结点和头结点。

建表

  • 头插法建表

    • 基本原理：
      • 读取是从前往后，但最终形成的链表顺序是原来数据排列方式的从后往前。
      • 最终的表头是一个不含数据的空结点。
    • 算法：
      • 每一个结点（包括头结点）都是现场分配的内存。
      • 头结点的指针域始终指向刚插入的结点（开始为NULL除外）。
      • 每次插入操作需将头结点指针域赋给新结点的指针域，然后头结点指针域指向新结点。这样达到断开头结点与旧结点之间的旧链,而形成头结点与新结点之间新链的效果。

  • 尾插法建表：

    • 基本原理：
      • 增加一个移动的尾指针，使其一直指向链表的尾结点（开始时指向头结点）
    • 算法：
      • 先使用尾指针，使旧尾结点的指针域指向新结点，然后将尾指针指向新结点。
      • 注意：最后要将尾结点的指针域设置为NULL。

求线性表中第i个位置的数据元素

  • 设置一个移动的指针（最开始指向头结点），在计数（从0开始）的同时，移动指针。
  • 在找到第i个元素之前，用循环移动指针。（注意控制条件：计数变量比i小，且不能超出链表元素数目）

按元素值查找

  • 设置一个移动的指针，从第一个有值域的结点开始查找，每一个元素和所找元素比较，若不相等，则指针向后移。

求带头单链表的长度

  • 设置一个移动的指针（开始指向头结点），设置一个计数变量(开始设为0表示头结点的序号为0，不算在数据结点的个数中），每移动一次指针，计数变量加一。
  • 结束的控制条件：最后一个结点的指针域为NULL。

在链表的第i个位置插入数据元素

删除链表的第i个位置的数据元素

  • 查找到第i-1个结点，利用它的指向后继结点的指针域（所以结束查找的条件是找到第i-1个元素或者当前结点的指针域为NULL），来删除第i个结点。
  • 使用free()来删除一个结点。

合并两个有序链表为一个有序链表

  • 占用其中一个链表来合并

    • 基本原理类似二路归并算法
    • 设置两个可移动指针，指向原来两个链表的数据元素。
    • 新链表头指针指向原来某个链表的头结点，以此来占用该链表的空间。

  • 合并为一个全新的链表

    • 所不同的是每一次插入都需要重新分配空间，故采用尾插法重新建立一个链表。
    • 最后没有遍历完的结点，需要使用循环来插入新链表中。
    • 注意最后新链表尾结点的指针域要置为NULL。

循环单链表

  • 找到尾结点的条件变为：p->next = L。
  • 结点类型：同单链表

初始化循环单链表

  • 形参为指向头结点指针的指针。
  • 最开始时，头结点即为尾结点，故头结点的指针域指向自己。

创建循环单链表

  • 使用尾插法创建循环链表
  • 最后要将尾结点的指针域设为头结点。

循环单链表的合并

  • 传入两个循环单链表的头指针

    • 找尾结点的循环：while(p->next != LA) p = p->next;
    • 第一个链表的尾结点的指针域设为第二个链表的第一个数据结点（不是头结点），第二个链表的尾结点的指针域设为第一个链表的头结点。

  • 传入两个循环单链表的尾指针

    • 先找到两个链表的头结点，在修改各自尾结点的指针域。

双向链表

  • 结点类型定义

建立双向链表

  • 头插法建表

    • 头结点刚创立时前后驱指针域都设为空(*L)->prior = (*L)->next = NULL;
    • 新插入结点的前驱指针域设为头结点，后驱指针域设为原来头结点后原第一个数据结点。s->next = (*L)->next; s->prior = *L
    • 原第一个数据结点的前驱指针需修改为新插入结点(*L)->next->prior = s;,头结点的后驱指针域设为新插入结点(*L)->next = s;
    • 头插法的共性是建成的线性表是逆序的；
    • 注意：传入函数的是指向头结点指针的指针，又有->的优先级高于*，所以需使用（*L）。

  • 尾插法建表

    • 设立一个可移动的尾指针，始终指向当前的尾结点；
    • 最后注意将尾结点的后驱指针域设为NULL
    • 相较头插法，只需修改两个结点的三个指针域，修改较少。

  • 建表的变式：逆置双向链表

    • 本质是头插法的运用;
    • 需要新设两个可移动指针来扫描原来的链表。

在第i个位置插入数据元素

  • 本质是头插法
  • 查找第i-1个结点即为尾插法

删除第i个结点

  • 可以找到第i个结点，也可以找第i-1结点；
  • 只需修改两个指针；

循环双向链表

  • 找到尾结点的条件变为了：L->next = L
  • 判断循环链表是否对称相等的算法

    • 设置两个可移动指针分别从链表头尾扫描向中间
    • 数据结点数目不同，扫描完是两个扫描指针的相对位置不同。为奇数时，最后两个结点指向同一个数据结点p == q;为偶数时，最后两个扫描指针相邻p->next == q或者p == q->prior

线性表的应用

一元多项式的运算

  • 基本原理（一元稀疏多项式的线性表表示）
  • 单链表储存一元多项式的结点定义
  • 创建一元多项式单链表存储的算法
    • 尾插法创建
    • 需要申请一个空的头结点
  • 两个一元多项式相加的算法


    • 默认即将要相加的两个一元多项式是按照次数从小到大排好序的。
    • 从头开始遍历，将指数较小的存入新表，两个的指数相等时系数相加后存入新表。
    • 采用头插法创建相加后的新表

线性表经典题目

1.删除顺序表中值为x的元素

  • 先找到第一个值为x的元素
  • 之后将其后面值不为x的元素逐个前移
  • 最后修改last的值。因为在移动最后一个元素后，i还加了1，所以L->last = i-1

2.带头结点单链表就地逆置

  • 将原来链表的头结点分离出来。
  • 遍历原来链表的数据结点，然后用头插法插入分离出来的头结点中，从而实现就地逆置。

3.以第一个元素为标准将数据元素分为两边

  • p1为固定指针，始终指向第一个结点，方便其它结点与第一个结点比较大小。
  • pre、p、q为一套移动指针，其中p指向当前扫描到的与第一个结点比较大小的结点,q指向当前结点的下一个结点，pre指向当前结点的前一个结点。
  • pre的作用是当需要把当前结点移走时，能够使其它两个结点能够连起来。pre->next = p->next。
  • q的作用一方面是使p能够持续进行扫描，另一方面使在中间结点被移走的情况下协同pre建立边上两个结点的联系。

4.存放一个二进制数的链表


  • 二进制的加法关键在于找到第一个值为0的位，然后进行01的互换（怪不得计算机要用二进制，确实好操作）
  • 链表实现加法有两种情况，第一种是，不需增加位数，直接01互换即可；第二种是位数需进一位，此时需要增加一个新结点。
  • q指针的作用是扫描链表;r指针的作用是指向为最后一个值域为1的结点，若没有则指向头结点；temp指针的作用是在需要新增一个结点时，指向原来的第一个数据结点，以便与新增结点建立连接。

Zestaken计算机小白一枚

吾好梦中读书~