Loli的杂货铺
数算关键概念一览
justaLoli
  2023-04-10 21:41:45   2023-11-09 18:57:46      5.8k 字  20 分钟

https://justaloli.cn/posts/39276.html

https://justaloli.cn/posts/51676.html

话不多说，直入正题

课上说到的重点

数据结构按逻辑结构和存储结构的分类

链表的操作细节

KMP搜索算法

循环队列空和满的判断

树的三种深度周游（非递归实现）

二叉树、K叉树的各种性质!!!

绪论

  • 程序

是使用程序设计语言精确描述的实现模型，它是问题求解的一个可以在 计算机上运行的模型。程序中描述的数据用来表示问题中涉及的对象，程序中描 述的过程表示了对于数据的处理算法;通过接受实际问题的输入，经过程序的运 行，便可以得到实际问题的一个解。

  • 数据类型 data type

通常是指在计算机(语言）中可以使用的一个类型，它不 但包括这个类型的值的集合，还包括定义在这个类型上的一组操作。例如，整数作 为一个数据类型是指在计算机上所能表示的(不是数学意义上任意大小的）所有整 数和语言中定义的对于这些整数的全部操作(整数的加、减、乘、除、取余等）。在不 会造成误解的上下文中，本书中提到的许多类型（例如整数类型、实数类型等）多数 都指数据类型。

  • 抽象数据类型 ADT

可以定义为具有一定行为（操作）的 抽象(数学）类型。它不关心类型中值的具体表示方式和数据类型中定义的各种操 作的具体实现方法，是所有可能的值的具体表示和各种操作的具体实现的抽象。

  • 数据结构

通常，可以把数据结构理解为：计算机中表示(存储）的、具有一定逻辑关系和行为特征的一组数据。

其中的每 个数据元素称为这个结构的一个结点。

本书把 数据结构 理解为 “抽象数据类型的物理实现” 。

  • 需要注意的是，无论从什么观点出发，算法和数据结构在程序设计中的核心地位 和作用并没有任何改变。对于数据结构的不同理解，实际上都离不开以下三个要素：
    • 逻辑结构：它定义了数学模型中的基本元素(结点)和元素之间的相互关系。
    • 存储结构：它给出了数学模型的具体表示方式，包括结点的表示和关系的表示。
    • 操作：它给出抽象数据类型关心的各种行为在存储结构上的具体实现算法。
  • 数据结构的分类
    • 逻辑结构
      • 重要概念
        • B = <K,R>
        • R 关系 “二元组的集合”
        • <k,k'> 前驱k，后继k’
        • 开始结点：没有前驱的结点，终端结点：没有后继的结点
      • 集合
      • 线性结构
      • 树形结构（老师ppt称层状）
      • 复杂结构（老师ppt称网状）
      • 包含关系：集合包含线性结构包含树形结构包含复杂结构
    • 存储结构
      • 顺序表示：用一个连续的空间顺序存放数据结构中的各个结点。
      • 链接表示：结点的存放位置是任意的,结点之间的关系通过与结点关联的指针(或者引用）方式显式表达出来。
      • 散列表示：又称为关键码——地址转换法。即选择适当的散列（杂凑）函数，根据关键码的值将结点映射到给定的存储空间(散列表）中。
      • 索引表示：索引与散列一样，都给出一种从关键码到存储地址的映射方法。不同的是，散列法的映射是通过函数定义，而索引法是通过建立辅助的索引结构解决。
  • 结点

组成结构的元素抽象成结点。分成初等类型和组合类型

  • 算法

算法是由有穷规则构成的为解决某一类问题的运算序 列(方法或过程）。

算法可以有若干输入，这些输入是在算法开始时给出的初始值 或条件;算法通常又有若干个输出，它们是同输入有某种关系的计算结果。

算法的性质如下： 有穷性。 一个算法必须在执行了有穷步之后结束。在某些领域也需要研究不 终止的算法，但这不属于本书讨论的范畴。 确定性。 算法的每一步必须有确切的定义。也就是说，对于每步需要执行的 动作必须严格地和清楚地给出规定。 可行性。 算法是可行的，意味着算法中的每个动作，原则上都是能够由机器或 人准确完成的。整个算法好像是一个解决问题的“工作序列〞，其中的每一步都是 我们力所能及的一个动作。

算法正确性：如果一个算法以一组满足初始条件的输入开始，那么该 算法的执行一定会终止,并且在终止时得到满足要求的(输出）结果。

  • 算法的设计

贪心法

分治法

回溯法（深度优先

动态规划法

分枝界限法（广度优先

线性表

  • 线性表

线性表简称为表，是零个或多个元素（也称表目）的有穷序列。

K中所含元素的个数称为表的长度,长度为零 的表称为空表。

  • 顺序表

采用顺序存储是表示线性表最简单的方法，具体做法是：将线性表中的元素一个 接一个地存储在一片相邻的存储区域中。这种顺序表示的线性表也称为顺序表。

  • 链表

每个结点就包括两个域：数据域（info)—存放元素本身的信息；指针域 (link）——存放其后继结点的存储位置。由于最后一个元素没有后继，它的指针 不指向任何结点，称为空指针。空指针图示中用“^”表示，算法中用“NULL”

假设一个线性表有n个元素，则这几个元素所对应的几个结点就通过指针链 接成一个链表。由于这种链表中每个结点只有一个指针城，故又称为单链表。指 向链表中第一个结点的指针称为该链表的头指针。

有时，为了处理方便，可以在单链表的第一个结点之前另加一个结点，称之为 头结点。

循环链表，双链表，循环双链表

  • 稀疏矩阵的表示方法

  • 三元组表示法，伪地址表示法

  • 行-列表示法

字符串

  • 字符串

字符串简称串,是一种特殊的线性表，其特殊性主要在于表中的每个元素是一 个字符。

  • KMP模式匹配

（书p82）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
makeNext(){PSeqString p,int *next}{
	int i=0,k=-1;
	next[0] = -1;
	while(i< p->n-1){
		while(k>=0 && p->c[i]!=p->c[k]){
			k = next[k];
		}
		i++;k++;
		if(p->c[i] == p->c[k]){
			next[i] = next[k];
		}
		else{
			next[i] = k;
		}
	}
}

改进后算法分析 算法 3.8 从形式上看是一个二重循环，每重循环最多执行 m次,最大运行时间 可能达到0(m^2）。但仔细分析一下可知，因为每执行一次外层循环(第4行),i严 格增1(第6行),所以外层循环正好执行m-1 次;另外k 的值从-1 开始（第2 行）,执行k +m-1次(第6行),并且只有在这一语句中k 被增值。在内层循环 (第5行)中,语句k= next[k]至少使长减少1,所以整个算法中，这个语句的执行 次数累计起来不可能超过m-1次(否则k将小于 -1,这是不可能的），所以内层 循环总的执行次数最大为m-1。因此算法3.8的执行时间为0(m）。与算法3.6 的执行时间合在一起，得到用长度为m的模式串p与长度为n的目标串t进行匹 配所需的总计算时间为 O(m +n)。 Knuth 等人提出的快速模式匹配算法，当 n≥m时，其优越性是显然的，特别在 一个模式被反复使用时，只要花一次0(m）的时间计算 next 数组，以后的每次匹配 只要用0(n）的时间;但是，当n与m 接近，并且处理只匹配一次的模式时，朴素的 匹配算法所花的时间代价也可能会更为节省。 快速匹配的算法意义还在于：算法本身的设计方法具有代表性，它首先建立了 next 数组，以此作为匹配过程的工具，从而提高了匹配的速度；另外，算法3.6 和算 法3.8 的时间分析方法也是常用的方法之一，希望读者掌握。

栈与队列

  • 栈

栈是一种特殊的线性表，它所有的插入和删除操作都限制在表的同一端进行。 表中允许进行插入、删除操作的一端叫做栈顶，另一端则叫做栈底。当栈中没有元素时，称为空栈。

因此，栈又称为后迸先出(Last in First Out, LIFO)表或下推表。

由于栈是一种动态结构，而数组是静态结构，因此，当栈中已经有 MAXNUM个 元素时，如果再做进栈运算，则会产生溢出，通常称为上溢(overflow）；而对空栈进行出栈运算时也会产生溢出,通常称为下溢(underlow）。为了避免溢出，在对栈进行进栈运算和出栈运算前，应分别检测栈是否已满或是否已空。

中缀表达式的计算，书p100

  • 队列

队列也是一种特殊的线性表，是一种只允许在表的一端进行插人操作,而在另 一端进行删除操作的线性表。允许进行删除的一端称为队头，允许进行插入的一 端叫做队尾。当队列中没有任何元素时，称为空队。

队列的插入操作通常称为入队，队列的删除操作通常称为出队。

队列同现实生活中等车、买票的排队相仿，新来的成员总是加入到队尾，每次 离开队列的总是队头上的，即当前“最老的”成员。因此，队列也称为先进先出 (First In First Out, FIFO)表。

在顺序表示的队列中，同栈一样存在队列溢出问题。即当队列满时，再做入队 操作，这种现象称为上溢;而当队空时，做出队操作，这种现象称为下溢。这些现象在运算中都要考虑。

环形队列

为区分空队列与满队列两种情况的环形队列，一般是牺牲队列中的一个结点，当队列中已有 MAXNUM-1 个结点时就称满，再要 插入就发生溢出。（p105

注意形如(k+1)%n的形式

双端队列是一种特殊的线性表，对它所有的插人和删除都限制在表的两瑞进 行。它好像一个特别的书架，取书和存书限定在两边进行。

双栈是一种加限制的双端队列，它规定从一端插入的元素只能从同一端删除， 它就好像两个底部相连的栈。

超队列是一种输出受限的双端队列，即删除限制在一端进行,而插入仍允许在 两端进行。它好像一种特殊的队列,允许有的最新插入的元素最先删除。

超栈是一种输人受限的双端队列，即插入限制在一端进行,而删除仍允许在两 端进行。它可以看成对栈溢出时的一种特殊的处理，即当栈溢出时，可将栈中保存 最久的元素删除。

树和二叉树

default定义：

！！根的层数为0

所有节点的最大层数为树的高度。

只有根节点的树的高度为0

空树的高度为-1

树

  • 运算:

创建一颗空树、判断是否为空树、求根结点、求父结点、求第一个子结点、求右兄弟、遍历树（树的周游）

  • 树的存储方式

  • 树的遍历（周游

    • 深度方向
    • 广度方向

  • 深度方向

    • 先根遍历
    • 中根遍历
    • 后根遍历

  • 先根遍历

任何结点，先根遍 历完后： 如有右兄弟，进入 右兄弟；否则，进 入上一层（父结点） 的右兄弟。

  • 中根遍历

任何结点，中根遍历完（长子子树 也已经遍历完）后：

1)如有第2颗子树，进入。 2）否则（也无其它子树），父结点 第2颗和2后的子树，进入前需要保 存右兄弟，以便子树遍历完后，进 入右兄弟。

  • 后根遍历

任何结点，后根 遍历完后： 如有右兄弟，进 入右兄弟；否则， 上一层（父结点）

  • 三种深度遍历的非递归实现（重要‼️）看ppt

  • 广度方向（层次遍历）

利用队列

二叉树

二叉树的定义: 结点的有限集合，该集合或者为空集，或者由一个称为根的结点和两颗互不相交的分别称为根的“左子树”和“右子树”的二叉树组成。

注意：左子树存在，右子树不存在，和左子树不存在，右子树存在是两种不同情况。

运算: 创建、判断是否为空、求根、求父节点、求左子女、求右子女、周游

‼️重要：二叉树并不属于树，二叉树不是树的特殊形态。二叉树在只有一棵子树时，也要明确是左子树还是右子树。这和普通的树是完全不同的。

满二叉树：如果一棵二叉树的任何结点或者是树叶，或者有两棵非空子树，则此二叉树称作“满二叉树”。 注意这个定义和普通定义不同。

全满二叉树：为普通定义的“满二叉树”。

完全二叉树：如果一棵二叉树至多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为“完全二叉树”。

扩充二叉树：把原来二叉树节点中，度小于2的节点都扩充为度为2的节点。注意：在扩充二叉树的过程中，新增加的“外部节点”一定比原来存在的“内部节点”个数多1

假定内部结点数为n，则扩充二叉树中有2n条边，2n+1个结点，因此外部结点数目为:2n+1-n=n+1。

外部路径长度E：在扩充的二叉树里从根到每个外部结点的路径长度之和。

内部路径长度I：在扩充的二叉树里从根到每个内部结点的路径长度之和。

E = I + 2n

二叉树的性质：

  1. 在二叉树的“i层”上至多有 个结点(i>=0)。
    1. 在二叉树的“第i层”上至多有 个结点(i>=1)。
  2. 深度为k的二叉树至多有 个结点(k>=0)。

常考的性质！！！

  1. 对任何一棵二叉树T，如果其叶子结点(度为0的节点)数为n0，度为2的结点数为n2，则n0=n2+1。

  2. 具有n个结点的完全二叉树的深度k = log(n+1)。

  3. 对于有n个节点的完全二叉树，从上到下，从左往右编号（从1开始）

    1. i=1 i为根
    2. i > 1，i的父节点为i/2
    3. 如果2i > n,i无左子女，否则i的左子女为2i
    4. 如果2i+1 > n,i无右子女，否则i的右子女为2i+1

  4. 在扩充二叉树中，外部节点比内部节点多1

  5. 扩充二叉树中，外部路径长度E = 内部路径长度I + 2 * 内部节点数n

要掌握性质7的证明

K叉树

满（之后叶子和度为K的）K叉树；完全（顺序）K叉树；完全满K叉树

集合与字典

集合

基于位向量的集合

1
2
3
4
struct BitSet{
	int size;
	char *array;//一个字节存储8个0或1
}
  1. size = (n+7)/8
  2. which_char = idx / 8 = idx >> 3
  3. which_bit = inx % 8 = idx & 7

运算包括:

  1. 创建 size = (n+7) / 8
  2. 插入 array[idx >> 3] |= (1 << (idx & 7))
  3. 删除 array[idx >> 3] &= ~(1 << (idx & 7))
  4. 判断是否属于 return (array[idx >> 3] & (1 << (idx & 7)))
  5. 集合合并 res[i] = array1[i] | array2[i]
  6. 集合交集 res[i] = array1[i] & array2[i]
  7. 集合差 res[i] = array1[i] & ~array2[i]

基于链表的集合(几乎用不到)

字典

组成: 关键码 + 属性

检索: 按照关键码进行

存储结构: 静态(不再增删)、动态(频繁增删)

标准: ASL(平均查找长度), p为查找概率, c为查找当前元素需要的比较次数.

基本运算: 关键码和给定值的比较

字典的表示: 顺序表、散列表、树表

顺序表检索

1
2
3
4
5
6
7
8
9
struct DicElement{/*元素结构*/
	KeyType key;  /*元素的关键码*/
	DataType other; /*其它属性字段*/
}; 

struct SeqDictionary{ /*字典结构*/
	DicElement elementMAXNUM]; /*字典数组*/
	int n; /*实际元素个数*/
};

顺序检索的ASL

  1. 顺序检索 O(n)

“+1”不能忘记！

二分检索（折半检索）的ASL

  1. 二分法检索 中间: (最左+最后)/2

顺序字典的二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int BinSearch(SeqDictionary *pdic, KeyType key, int *pos){
	int low,mid,high;
	low = 0; high = pdic->n - 1;
	while(low <= high){ //注意这里的判断
		‼️mid = (low + high) / 2; //注意中间位置
		if(key < pdic->elem[mid].key){
			‼️high = mid - 1; //注意边界变化
		}else if(key > pdic->elem[mid].key){
			‼️low = mid + 1; // 注意边界变化
		}else{
			*pos = mid;
			return true;
		}
	}
	‼️*pos = low; //它“应该在”的位置,用于后续插入
	return false;
}

全满二叉树中，

“+1”, “-1”不能忘记！

折半检索必须要是有序的顺序表。

分块检索的ASL

分块，块间有序，块内无序

  1. 分块检索

假定b块，每块s个记录；s = n / b

对于b：可以顺序、可以折半；

对于s：只能顺序

  1. 对块间顺序检索

当 时

  1. 块间折半检索

散链表检索的ASL

  • 散列函数：h(key)

  • 散列地址：location = h(key)

  • 散列表：通过h(key)建立起来的线性表（能够随机存取的顺序表）。

  • “碰撞”：h(key1) = h(key2)。需要避免。key1和key2称同义词。

  • “基本区间”：通过散列函数得到的散列地址。同义词可以放在基本区域里未占用的空间，也能另开辟一片空间（溢出区）。

  • “负载因子”：

散列表中的节点数目基本区域能容纳的节点数

当时，碰撞不可避免。

  • “二次聚集”，利用基本区域存储同义词时，不同关键码争夺同一个散列地址。

处理碰撞

  1. 开放地址法
  2. 再散列
  3. 拉链法

如果有一组散列函数，就加上“再散列”，如果没有，答1或3

排序

排序的类别和性能

shell排序

堆排序

图

一大堆概念

基本概念

顶点、边（无向图）&弧（有向图）

完全图（任意两个顶点都有边&弧）

度（无向图）入度、出度（有向图）

有向图中，度=入度+出度

节点数

路径：从v1到v2经过的顶点的序列

路径长度：边的数目；带权：权值之和

环

根：到任何顶点都有路径

子图

【针对无向图的】连通图：

v1和v2连通：v1和v2存在路径

图连通：任意两个顶点都连通

不连通的图可以被划成多个极大连通子图

无向图的极大连通子图也称作连通分量

【针对有向图的】强连通图

强连通：任意两个顶点都双向连通

不强连通的图，可以分成几个极大强连通子图（又称作强连通分量）

权，网络

网络：带权的（无向的）连通图或（有向的）强连通图

生成树：包含原图中所有节点的极小连通子图

生成树具有n-1条边。

两种表示法

邻接矩阵；

邻接表，逆临接表；

周游

DFS

BFS

最小生成树

P算法

K算法

最短路径

单源最段路

D算法

多源最短路

F算法

AOV和拓扑排序

拓扑排序可以检测一个有向图是否有回路。

算法思路：选取入度为0的节点；删除这个节点的出弧，减小相连的节点的入度，继续选取入度为0的节点；如果最后尚有顶点剩余，则有环，返回失败。

需要开辟一个数组计算每隔节点的入度。

对所有入度为0的节点，可以建立一个静态栈（用数组的值表示下一个入度为0的节点）。利用栈控制，拿出入度为0的节点。

AOE和关键路径

关键路径算法可以用来解决最长路径

AOE网中有些活动可以并行进行，所以完成整个工程的最短时间是从开始顶点到完成顶点的 最长路径长度 、路径长度为路径上各边的权值之和。把开始顶点到完成顶点的 最长路径称为关键路径。

顶点为“事件”，边为“活动”

  1. 到达事件的最早时间

进入vj的活动都结束，才能到达vj这个事件

有活动<vi,vj>则

  1. vi允许发生的最迟发生时间

为了不拖延整个工期，vi发生的最晚时间不得迟于其后继 事件vj的最晚发生时间减去活动<vi,vj>的持续时间。

  1. 活动ak=<vi,vj>的最早开始时间

就是ak的起始点vi的最早开始时间

  1. 活动ak=<vi,vj>的最迟开始时间

就是ak的终点vj的最迟开始时间减去ak的持续时间

时间余量：la(k) - ea(k)，即可以推迟的时间

关键活动：时间余量为0的活动

关键路径由关键活动构成。

  • 延误关键活动的持续时间，推迟整个工程时间；
  • 缩短非关键活动的持续时间，对整个工程时间无影响；
  • 只有缩短关键活动的持续时间，才能缩短整个工程时间， 但可能引起关键活动的变化；
  • 缩短某些关键活动的持续时间，并不一定提前工程完成时间；

计算ee，le时需要按照一定顺序计算。这种顺序是拓扑序列。因此在算法中要首先执行拓扑排序。

数算关键概念一览
posts/11144.html
作者
justaLoli
发布于
2023-04-10 21:41
许可
  1. 课上说到的重点
  2. 绪论
  3. 线性表
  4. 字符串
  5. 栈与队列
  6. 树和二叉树
    1. 树
    2. 二叉树
      1. 二叉树的性质：
      2. K叉树
  7. 集合与字典
    1. 集合
      1. 基于位向量的集合
      2. 基于链表的集合(几乎用不到)
    2. 字典
      1. 顺序表检索
      2. 顺序检索的ASL
      3. 二分检索（折半检索）的ASL
      4. 顺序字典的二分查找
      5. 分块检索的ASL
      6. 散链表检索的ASL
  8. 排序
    1. 排序的类别和性能
    2. shell排序
    3. 堆排序
  9. 图
    1. 一大堆概念
      1. 基本概念
    2. 两种表示法
    3. 周游
    4. 最小生成树
    5. 最短路径
      1. 单源最段路
      2. 多源最短路
    6. AOV和拓扑排序
    7. AOE和关键路径
  1. 课上说到的重点
  2. 绪论
  3. 线性表
  4. 字符串
  5. 栈与队列
  6. 树和二叉树
    1. 树
    2. 二叉树
      1. 二叉树的性质：
      2. K叉树
  7. 集合与字典
    1. 集合
      1. 基于位向量的集合
      2. 基于链表的集合(几乎用不到)
    2. 字典
      1. 顺序表检索
      2. 顺序检索的ASL
      3. 二分检索（折半检索）的ASL
      4. 顺序字典的二分查找
      5. 分块检索的ASL
      6. 散链表检索的ASL
  8. 排序
    1. 排序的类别和性能
    2. shell排序
    3. 堆排序
  9. 图
    1. 一大堆概念
      1. 基本概念
    2. 两种表示法
    3. 周游
    4. 最小生成树
    5. 最短路径
      1. 单源最段路
      2. 多源最短路
    6. AOV和拓扑排序
    7. AOE和关键路径