08 数据结构与算法

Posted on Wed, 25 Dec 2024 16:47:52 +0800 by LiangMingJian

1.数据结构 #

1.1 概念 #

• 数据结构是指数据元素的集合或者数据对象的集合，以及元素之间的相互关系和构造方法。
• 数据结构分为逻辑结构（元素间的相互关系）和物理结构（又称存储结构，元素间的存储形式）

1.2 逻辑结构 #

1.2.1 线性结构 #

• 线性结构的第一个元素只有一个后继和最后一个元素只有一个前驱，其它每个元素只有一个前驱元素和一个后继元素。
• 如：线性表（一维数组，链表），栈和队列。
• 注意：栈和队列本身不是一种数据结构，可通过数组或链表实现。

1.2.2 非线性结构 #

• 每个元素可以和多个元素连接，也就是每个元素前驱和后继的个数不确定。
• 如：二维数组，树和图。

2.线性表 #

2.1 概念 #

• 线性表是线性结构的一种表现方式，是零个或多个数据元素构成的有限序列。除第一个元素外，每一个元素有且只有一个直接前驱元素，除了最后一个元素外，每一个元素有且只有一个直接后继元素，数据元素之间的关系是一对一的关系。
• 在线性表查询数值、查询数的位置、插入、删除操作中，查询数值是运算速度最快的操作，因为查询数的位置需要进行比较，插入和删除元素都需要修改前驱和后继的指针，而查询数值只要找到该位置读取即可。

2.2 顺序存储结构 #

• 各个元素存储的地址空间连续，逻辑相邻的元素在物理内存中也相邻，如数组。顺序存储结构中任一数据元素都可以随机存取。
• 优点：因为各个元素是连续储存，而且当元素类型一致时占用空间大小也一致，所以可以直接通过首元素地址计算某个元素的内存地址，使得访问特定元素效率很高。
• 缺点：在删除或插入元素后需要移动其它元素使得整体的存储空间依然是连续的， 删除、插入元素效率低。同时由于元素存储空间连续，所以当有大数据时，较难分配一块连续的大内存空间。

2.3 链式存储结构 #

• 各个元素存储在任意的地址空间，逻辑相邻的元素在物理内存中没有联系，如链表。链式存储结构在存储数据元素时，会额外开辟出一份内存空间去作指针，它总是指向下一个数据节点，一个个节点通过 NEXT 指针相互串联，通过访问 NEXT，可以引导我们去访问链表的下一个节点。
• 优点：由于链式存储的特点，删除或插入节点很方便，不需要移动其它元素，改变元素连接关系即可。
• 缺点：因为存储的任意性，只能通过前一个元素访问下一个元素，每一次访问元素都从头节点开始遍历，所以访问特定元素或查找元素效率低。
• 链式存储结构的实现方式分为：
  • 单链表：A -> B -> C。
  • 双链表：A -> B -> C，也可以 C -> B -> A。
  • 循环链表：A -> B -> C -> A，优点是可以从任意节点开始遍历整个链表。

3.栈 #

• 栈是运算受限的线性结构，其限制是仅允许在一端进行插入和删除操作，不允许在其他任何位置进行添加、查找、删除等操作。
• 栈的入口和出口的都是栈的顶端位置。
• 其特点是先进后出。

4.队列 #

• 队列是一种只允许在一端进行插入，而在另一端进行删除的线性结构。
• 队列中只允许进行插入的一端称为队尾，只允许进行删除的一端称为队头。
• 其特点是先进先出。

5.数组 #

5.1 概念 #

• 数组是一系列类型相同的元素组成的结合。
• 数组一般可以分为一维数组 a[n] 和二维数组 a[i][j]，分别是线性结构和非线性结构的实现。

5.2 一维数组 #

• 一维数组可以看成是一个顺序表，一系列类型相同的元素依此存放。
• a[n]的存储地址等于：a + n*len，a 是首地址，len 是元素长度。

5.3 二维数组 #

5.3.1 概念 #

• 二维数组可以看作一个 m 行 n 列的 m × n 矩阵，因此在定义二维数组时，需要定义多少行多少列。
• 如：a[2][3]是一个 2 行 3 列的矩阵，a[][3]是一个行不定，但列最多为 3 的矩阵。
• 二维数组的存储结构分为按行存储和按列存储。
• 在矩阵运算中，选择合适的按行存储或按列存储有利于提高运算速度。比如在矩阵 A * B 时，由于矩阵相乘是以行 * 列进行的，因此，为了更快的找到数据，可以对 A 进行按行存储，对 B 进行按列存储。

5.3.2 按行存储 #

• 按行存储是以行序为主序的存储方式，比如 m 行 n 列二维数组 Amn，按行存储次序为 a11,a12,…,a1n,a21,a22,…,a2n,……,am1,am2,…amn。
• 地址计算公式为：LOC(i,j) = LOC(0,0) + (n*(i-1)+(j-1))*L，列乘。
• LOC(i,j) 是 a(i,j) 的存储位置，LOC(0,0) 是 a(0,0) 的存储位置（即二维数组的起始存储位置，为称为基地址或基址），n 是数组的总列数，L 是单个数据元素占据的存储单元。

5.3.3 按列存储 #

• 按列存储是以列序为主序的存储方式，比如 m 行 n 列二维数组 Amn，按列存储次序为 a11,a21,…,am1,a12,a22,…,am2,……,a1n,a2n,…amn。
• 地址计算公式为：LOC(i,j) = LOC(0,0) + (m*(j-1)+(i-1))*L，行乘。
• LOC(i,j) 是 a(i,j) 的存储位置，LOC(0,0) 是 a(0,0) 的存储位置（即二维数组的起始存储位置，为称为基地址或基址），m 是数组的总行数，L 是单个数据元素占据的存储单元。

6.树与二叉树 #

6.1 树 #

• 树是只有一个根节点，没有直接前驱，有零个或多个直接后继的有限集合，没有节点时称为空树。
• 子树是根节点之外 n-1 个节点的有限集，子树互不相交。
• 节点的度是指当前节点，子序的个数，比如下图节点 6 的度是 2。
• 叶子节点是指终端节点，也就是度为 0 的节点，比如下图的 4、5、7、8 都是叶子节点。
• 内部节点是指度不为 0 的节点，也称为非终端节点、分支节点，除根节点之外的分支节点都可以称为内部节点。
• 兄弟节点是指在同一级的节点，比如下图的 4、5。
• 树的高度是指树中所有节点层次的最大值，比如树的高度是 4。
• 节点的高度不同于树的高度，节点的高度指从该节点到叶子节点的最长简单路径的边的条数，从下往上数，比如下图节点 3 的高度是 2。

6.2 二叉树 #

• 二叉树的每个结点至多只有两棵子树，二叉树的子树有左右之分，次序不能颠倒。
• 满二叉树：每层结点均满，每层均具有最大结点数，又称完美二叉树。满二叉树的结点数量为 $2^n$ - 1，n 为层数，第 k 层的结点数量是 $2^{(k-1)}$ 个。
• 完全二叉树：如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。
• 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

6.3 遍历方式 #

• 先序遍历：DLR（根左右，L、D、R 分别表示遍历左子树、访问根结点、遍历右子树）
• 中序遍历：LDR（左根右）
• 后序遍历：LRD（左右根）
• 层序遍历：按层次进行遍历，如 94，31，53，23，16，27，根 94，第一层 31，53，第二层 23，16，27。

6.4 存储结构 #

6.4.1 双亲表示法 #

• 采用顺序表结构进行存储。
• 顺序存储各个节点的同时，给各节点附加一个记录其父节点位置的变量。
• 注意，根节点没有父节点（父节点又称为双亲节点），因此根节点记录父节点位置的变量通常置为 -1。

6.4.2 孩子表示法 #

• 采用 “顺序表+链表” 的组合结构进行存储。
• 从树的根节点开始，使用顺序表依次存储树中各个节点，并给各个节点配备一个链表，用于存储各节点的孩子节点位于顺序表中的位置。
• 注意，如果节点没有孩子节点，则该节点的链表为空链表。

6.4.3 孩子-兄弟表示法 #

• 采用二叉链表结构进行存储。
• 从树的根节点开始，依次存储各个结点的孩子结点和兄弟结点，各个结点包含节点的值；指向孩子结点的指针；指向兄弟结点的指针。

7.堆和图 #

7.1 堆 #

• 堆可以看做一棵具有特殊规则的树的数组对象。
• 堆中每个节点的值，总是不大于或不小于其父节点的值，大于父节点的称为大顶堆，小于的称为小顶堆。
• 堆总是一棵完全二叉树。

7.2 图 #

7.2.1 图的概念 #

• 图是由集合 V 和 E 构成的二元组，记作 G=(V, E)。
• V：代表点，也称为顶点。
• E：代表边，分为有向边、无向边。
• 因此，图也可以简单理解为由点和边构成的集合。

7.2.2 图的分类 #

• 图可以分为有向图和无向图，有向图每条边都有方向，无向图每条边都没有方向。
• 若无向图中有 n 个顶点，则最多有 n(n-1)/2 条边（任意两个顶点之间都有一条边），这种无向图称为完全无向图。
• 在有向图中有 n 个顶点，则最多有 n(n-1) 条边（图中任意两点都有两条边相连），这种有向图称为完全有向图。
• 度是指与某个顶点相关的边的条数，等于出度和入度的和。
• 出度是从某个顶点指出的边的个数。
• 入度是指向某个顶点的边的个数。
• 如下图所示，顶点 A 的出度为 2，入度为 1，度为 3

7.2.3 图的存储结构：邻接矩阵 #

• 无向图的邻接矩阵，有连接的节点置 1，无连接的为 0

• 有向图的邻接矩阵，入度的节点置 1，无连接或出度的为 0

• 有权图的邻接矩阵，入度的节点置为权值，无连接或出度的为无限

7.2.4 图的存储结构：邻接链表 #

• 使用邻接链表存储数据时，将存储目标节点与其对应指向的节点，并按顺序构成链表存储。
• 比如下图节点 V1 指向 V2，V4，所以存储数据时，将 V1，V2，V4 的位置按链表存储。
• 注意：有向图存储时，不存储入度。

8.算法 #

8.1 概念 #

• 算法是对特定问题求解的一种描述，是一个指定的、有序的序列。也可以简单理解为一个有序的指令序列用来求解一个特定的问题。
• 算法具有以下特性：
  • 有穷性：一个算法必须在有穷的时间之内完成；也就是求解的步骤是有限的，完成每一步的时间是有限的。
  • 可行性：一个算法是可行的；也就是针对特定问题的求解，能够在有限步，有限时间内完成。
  • 确定性：在算法中的指令序列，每一个指令都有确定的含义，不存在二义性。同一个条件里执行多次得到的结果都会是相同的输出。
  • 输入：一个算法可以有 0~n 个输入。
  • 输出一个算法一定有 1~n 个输出。
• 算法往往使用伪代码进行描述，伪代码是介于自然语言和程序语言之间的，对算法实现的一种表现形式。

8.2 算法复杂度 #

8.2.1 时间复杂度 #

• 时间复杂度是对一个算法在运行过程中所花费时间长短的量度。
• 算法执行时间的度量不采用算法执行的绝对时间来计算。因为算法在不同机器上执行所花的时间不一样，所以在计算时，采用算法基本操作的执行次数（计算量）来度量。
• 在计算时间复杂度的时候，先找出算法的基本操作，并根据相应的语句确定其执行次数 $T(n)$ ，若存在某个辅助函数 $f(n)$ ，使得 $T(n)/f(n)$ 的极限 c 为不等于 0 的常数，则 $f(n)$ 称为 $T(n)$ 的同数量级，记 $T(n) = O(f(n))$，称 $O(f(n))$ 为算法的渐进时间复杂度，简称时间复杂度。
• 同数量级一般可以取：$1，log2n，n，nlog2n ，n^2，n^3，2^n，n!$
• 例如下面的代码， $T(n)=n^2+n^3$，有同数量级 $n^3$ ，对 $(n^2+n^3)/n^3$ 求极限，化简求 $1+1/n$ 极限，$1/n$ 无限趋向 0，看成 0，极限 c = 1，是不等于 0 的常数，所以时间复杂度 $T(n)=O(n^3)$。

for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
        c[i][j]=0;  // 基本操作，执行了 n^2 次，两个循环，每个 n 次
        for(k=1;k<=n;k++){
            c[i][j]+=a[i][k]*b[k][j]  // 基本操作，执行了 n^3 次
        }
    }
}

• 常见的算法复杂度：
  • 常数阶 O(1) ：无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是 O(1)，表示它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用 O(1) 来表示它的时间复杂度。
  • 线性阶 O(n) ：单个循环代码，每循环 n 次代码就会执行 n 遍，因此它消耗的时间是随着 n 的变化而变化。 如：for(i=1; i<=n; ++i){j=i;j++;}。
  • 对数阶 O(logN)：单个循环代码，但循环体不断逼近循环条件。如：int i=1; while(i<N){i=i*2;}，执行 $log_2N$ 次便已经到达循环条件 N（$2^x = N$）。
  • 线性对数阶 O(nlogN)：将时间复杂度为 O(logN) 的代码循环 n 遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了 O(nlogN)。
  • 平方阶 O(n²)：把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了，嵌套多少次，时间复杂度就是多少次方阶 $O(n^k)$
  • 上述时间复杂度，从上至下，越来越大，执行的效率越来越低。

8.2.2 空间复杂度 #

• 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。
• 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。
• 常见的空间复杂度：
  • O(1)：如果算法执行所需要的临时空间不随着某个变量 n 的大小而变化，即此算法空间复杂度为一个常量。
  • O(n)：如果算法执行时，需要开辟新的空间存储数据，如：int[] m = new int[n]，new 了一个大小为 n 的数组出来，那么这段代码的空间复杂度随 n 的大小而变化。

8.3 排序算法 #

注意：当序列基本有序时，使用插入排序的效率最高。