写在前面 ：

感觉自己的数据结构学的实在是太辣鸡了，于是自己打算做个笔记，方便记录自己的思考和期末复习，更新到期末考完（1.17）…

期末复习划重点（2024.1.5）

时间复杂度求解顺序表的插入，移动元素的个数
单链表的插入算法，时间复杂度，插入删除的语句片段补写

队列堆栈概念，特点，存放xxx数据适合用什么存储结构
后缀表达式的计算，
循环队列的操作，判断满空，前进
数组求存储地址（行优先，列优先）
给任意两个坐标的元素，看两个差距来判断是行/列优先存储
特殊矩阵存储地址（主要是三角矩阵
稀疏矩阵，转置算法，快速转置过程中的K num数组的值要会求 :::warning image.png这个快速转置好容易忘…放在这里多看几次 ::: 树的术语： :::info 结点的度：一个结点的子树数量，度为0就是叶结点，所有结点的度==分支数
树的度：树中结点最大的度
分支节点：除去叶结点外，其他结点都是分支结点；即有后代的结点
树的层数：根结点的层数是1，往下递增，最大层数即为高度 ::: 二叉树的四个性质，重点记一下n0=n2+1：有两个孩子的个数+1==没有孩子的结点个数
完全二叉树:满树从右往左删掉若干个
（高度【log2(n+1)】向上取整：已知完全二叉树的高度，求解树叶）
满二叉树：高度为h，则结点数是(2^n)-1
B树
二叉树的遍历，先中后：遍历的过程（递归（先中后）法 层序遍历），已知两种遍历求第三组，
根据三种遍历的部分显示画出二叉树，遍历的算法应用
二叉树的线索化，线索数，分支树
森林与二叉树的转化原理
优先权队列，堆（关联堆排序）向下调整： :::info 反过来一个个检查父节点是否小于两个孩子，若不满足就交换父节点和最小孩子，交换之后检查父节点到新位置的二叉树是否满足最小堆，以此类推直到根结点，调整完成 ::: 每次都考：
哈夫曼树哈夫曼编码：权值，wpl，最高高度 :::info 每次都选权值最小的两个合并，最后左0右1，写对应的哈夫曼码，
计算wpl：对应的码制乘路径长度，下图的148
3da9ca2d23fbe2e135654e0ba4db4cb4_720.jpg :::

二分搜索
平均搜索长度：asl
最多比较次数；
搜索树：二叉搜索（排序）树（中序遍历递增序列[考点]），二叉搜索树的插入删除
平衡二叉树的构造建树，（s r u ）调节平衡，旋转
B树
散列表搜索：构造哈希表，冲突（拉链法，线性探查法（缺点），二次探查法，双散列法），同义词
图：图的存储结构：邻接矩阵，邻接表
图的遍历深度优先搜索，宽度优先搜索，时间复杂度
应用：最小生成树一定要会（普利姆算法，克鲁斯卡尔算法）
拓扑排序：判断是否有回路，排除不正确的拓扑序列
单源最短路径
排序：会写手工每一趟的排序，各种排序的结果
简单选择排序，快速排序，合并排序，堆排序，外排序
已知趟数来判断排序的方法：排序的趟数很重要
一定会进行n-1趟排序的排序方法是？简单选择排序、直接插入排序、
冒泡排序1～n-1次
快速排序：最多n-1趟
合并排序：【log2N】趟

填空20 选择20 综合题48 算法填空2*3=6 算法设计6

链表

线性表的顺序/链式操作

顺序存储

线性表的数据结构

利用数组来连续存储
image.png
List 是一个指向 struct LNode 结构体的指针类型的定义。它用 typedef 关键字来创建一个新的类型名，使得 List 可以被用来声明指向 struct LNode 结构体的指针。
访问下标为i的元素，L.Data[i],PtrL->Data[i];
计算线性表的表长：L.Last+1,Ptrl->Last+1

主要操作

1.初始化顺序表

image.png
image.pnglast设置为-1，意味着这是一个空表

2.查找

image.png

3.插入

数组的插入，略微不如链式存储方便，因为需要把i后的元素都往后挪动一位，由下面的for循环来实现；
当然，还需要判断表满或者插入下标不合理
初始让J指向最后一个元素，向后移，j—，挪完之后，把元素赋值给下标i-1的位置，last++，必须指向最后一个；
image.png

4.删除

删除第i个位置，也就是把i之后的元素往前挪，覆盖之前的元素
一个循环直接搞定，记得last—
image.png

链式存储

链表的数据结构

类型名称：线性表（List），一种抽象数据类型
image.png

结点的数据结构LNode

Data是指结点存储的数据，Next是下一个结点的地址
List 是一个指向 struct LNode 结构体的指针类型的定义。它用 typedef 关键字来创建一个新的类型名，使得 List 可以被用来声明指向 struct LNode 结构体的指针。
image.png

主要操作

访问链表里序号为i的元素

查找元素

（1）按序号查找

image.png
思路：这里的K是目标结点的序号，PtrL是List类型，是链表的头地址，返回的是指针p；定义临时变量p，指向表头，如果链表不为空且i

（2）按值查找

image.png
传入的X是待查找的值，也是定义一个临时指针p，PtrL是List类型，是链表的头地址，返回的是指针p；类似的循环条件p->Data==X即可

求链表的长度

略微比数组更复杂一些，主要思路是定义一个临时指针p指向链表的头节点，然后定义一个计数器J=0，p!=null就继续自增，指针往后指，直到遍历链表结束，来求表长.

时间复杂度：O（n）;
image.png

链表的插入

即在i-1个节点之后插入一个值为X的新结点
1.先构造这个结点，用s指针指向；
2.再找到链表的第i-1个节点，用p指向
3.然后修改指针，插入节点（p之后插入的新节点就是s）
image.png

  1. s->Next=p->Next;//把p的next赋值给s的next
  2. p->next=s//把s赋值给p->next

image.png

链表的删除

想要删除第i个节点，需要先找到第i-1个结点
1.先找到链表的第i-1个结点，用p指向；
2.然后用s指向要被删除的结点；
3.然后修改指针，删除s所指向的结点，释放空间
image.png

  1. p->Next=s->Next;//把p的next赋值给s的next
  2. free(s)

image.png

这里的FindKth就是访问链表里序号为i的元素

广义表和多重链表


双向链表

堆栈与队列

堆栈

元素的插入，删除都在同一端的线性结构。先进后出。
image.png

顺序栈

栈的建立

top=-1,指建立了一个空栈
image.png

栈的销毁

image.png

栈满 ？栈空？

image.png
主要是看top是msize-1(满)还是-1（空）

入栈 出栈

image.png
image.png

为了代码的健壮，都需要提前判断栈空还是栈满，出栈的时候，只要top—即可

链式栈（简要）

image.png
node节点的结构与之前类似，stack只需要定义一个顶部结点

入栈 出栈

image.png

队列

元素的插入，删除都在不同端的线性结构。先进先出

相关概念

image.png

注意：front是队头元素的前一个元素

假溢出

image.png
入队：rear往后移动
出队：front向后

循环队列

image.png

队列为空 front==rear

队列已满 （rear+1）%maxSize==front

image.png

数据结构的实现

image.png

创建一个mSize长度的空队列

image.png

销毁队列

释放创建时的空间，把其他三个变量都置-1
image.png

队列满 队列空

image.png

入队 出队

image.png

rear=(rear+1)%mSize, 理解成rear后移，考虑漫溢现象
image.png
front=(front+1)%mSize,理解成front后移，考虑漫溢现象

数组

已知数组求存储地址

:::info 本质就是问你在这个元素之前一共存了多少个元素，区别行优先，列优先，就很简单了 :::

一维数组

，没什么难度，往后算就可以了
image.png

二维数组

行优先存储

image.png
先存储行下表为0，1，2…的元素，local（a[i][j])，上面有0~i-1,共i行，左边有0~j-1,j个元素，
image.png

列优先存储

列优先也就是竖过来的顺序存储，如下图
image.png :::info 注意：给你一个A[4][3]这样的数组，不是说下标最多是4，3的意思，而是四行，一行最多三个，4x3的矩阵，写不清楚了就画个图表示一下，最大坐标其实是A[3][2] :::

*多维数组的存储

没有行列的概念，也就没有优先存储的概念
loc=首地址+偏移量的形式
偏移量的计算记忆方式如下image.png

特殊矩阵

矩阵具有行列的特征，适合用二维数组实现

对称矩阵

image.png
只需要存储对角线加上上三角矩阵的内容。nxn个元素，只需要存n(n+1)/2个元素【上底1，下底n，高n】
也有行优先，列优先的区别
例如：10x10的矩阵，A00=100，单位=2，存储上三角矩阵，要求A76的地址
a76=a67，上面0-5共6行，10+9+8+7+6+5=45个，第七行开始，从66开始计数，所以67之前共46个元素
a76=a67=46*2+100=192

稀疏矩阵

概念 数据类型

1、矩阵稠密度很小，大部分的元素都为零元素的矩阵成为稀疏矩阵
2、对0的分布没有要求
3、针对稀疏矩阵，更好的做法是只存储非零元素
image.png

如何存储

节省空间：存储非零元素，同时连通非零元素对应的元素一起存储
image.png
用三元组来表示稀疏矩阵元素，行号，列号，元素值
image.png
矩阵的数据结构如上

按照行优先，列优先可以画出行三元组表（从左到右），列三元组表（从上到下）
image.png
需要掌握的能力：根据一个稀疏矩阵，正确的写出对应的行三元表，列三元表（i,j,value）

转置算法

image.png
转置就是交换行列号
在普通矩阵里，转置矩阵很容易，例如如果要把A的内容转置并存入B中，只要两层循环遍历A的行列mxn，
B[i][j]=A[i][j]即可

转置算法1

第一步：依次访问A的行三元表中的各个三元组，，然后交换行与列号之后存入一个新的行三元表B里
image.png
第二步：整理一下序号，满足行三元组的要求，如果是行三元组，必须保证（1）行号有序递增（2）同一行的列号有序递增。整理好后的行三元组表B如下
image.png

这里的第二步是一个排序算法，需要稳定的排序算法。

转置算法2

依次扫描行三元组n次，依次把列数为0，1，2，3….的交换i,j，排序
image.png

快速转置算法

算法12容易理解，但是时间复杂度不低，故引出快速转置算法
核心算法：经观察不难看出，原稀疏矩阵的k列有几个元素，转置后的行k里就有几个元素
所以如果能统计处转置前每一列的非零元个数，就能把转置后的每一行的非零元的所占区域划分出来
规律：转置后三元组表中，行号为j的第一个元素的下标=前j列的非零元个数
image.png
前0列，0个，前1列2个，前2列4个，前3列5个

算法前的准备工作

1.num数组求解

num[j]表示，转置前稀疏矩阵A里的列号为j的一列里有num[j]个元素
如上图就是num[0]=2，num[1]=2,num[2]=1,num[3]=2,num[4]=0,num[5]=0
num=[2,2,1,2,0,0]，计数工作完成

2.构造k数组

k数组长度也是n，每一项表示前j列的非零元总数之和，也就是说第j列前的累加和，可以看到六列的稀疏矩阵，只有到k[5]就是这个原因，第六列前面也只有5列需要累加
k[0]=0,k[1]=2,k[2]=4,k[3]=5,k[4]=7,k[5]=7
k=[0,2,4,5,7,7]


二叉树(BT)

使用递归的算法遍历二叉树

image.png
如果是中序，后序遍历那么则调整If模块里printf的顺序，此算法主要借助递归思想
先序遍历那么就在最前面，中序遍历则在查询左右树中间，后续遍历在最后一行

借助堆栈（非递归）来遍历二叉树

image.png
创建一个stack，借助此来存储被遍历到了但不应该直接print的元素
1.先while（T）循环不断往下寻找左子树，只要有左子树继续往左走，并压入stack；直到没有左子树，即找到了第一个叶子节点，跳出while，将这个节点弹出堆栈，输出他的data即节点，然后指针转向右子树再次进入循环遍历右子树的左边

  1. 注：while(T||!IsEmpty){
  2.     //树不空或者堆栈不空
  3. }

Z`BQPE0_U(EHXK6EG$@J03D.png

一共三次遇到每一个结点，第一次碰到是push进栈，第二次是pop出栈，第三次
由此可知，如果要改成先序遍历，那么就在第一次碰到这个结点时print即可，在代码实现上就是把print放在push后面

image.png

层序遍历（借助队列来遍历树）

二叉树遍历的本质：把二维的结构线性化
image.png
image.png
image.png
层序遍历的结果就是一层一层写出元素
代码实现
先创建一个队列Q，把第一个根节点入列
while循环就做三件事
1.把这个结点抛出.队列
2.把这个结点（data）打印
3.把他的左右子树放入对列
image.png

一些二叉树的应用

1.输出二叉树的叶子节点

在递归遍历的时候，判断是不是既没有左也么有右儿子，如果是那么就打印，其余就正常遍历
image.png

2.求二叉树的高度

分析：因为要求二叉树的高度，必须先知道左右子树的高度，然后取较大值+1，则应该改造后序递归遍历来实现
image.png

3.由两种遍历方法来确定一颗二叉树

前提，给的两种里面必须有中序；
先序/后序：第一个/最后一个就是总根节点
中序：由上面确立的根节点来分隔左右子树
image.png

树和森林

树转成二叉树

1.把是兄弟的结点连起来，注意，不是同一层的全都连接起来，必须有同一个父亲才叫兄弟结点
2.把每个有孩子的结点，只保留最左边的分支，其余的都划掉。
3.调整形态
d210da697f71923031454ede9712a61b_720.jpg

二叉树转化成森林或树

1.整形：整体逆时针转过来，也就是左孩子垂直化，右孩子水平化
2.连线：把一个水平线的第一个结点的父亲，连接该水平线上的其余结点
注意，同一水平线的第一个结点，指的互相之间有连线的第一个字结点，下图第三行的K才是
3.去线“：删除掉所有的水平连线
4.整形：调整形态
8c7395591f2a13d3b9144aa0fb63c95b_720.jpg
转化成森林也是类似过程
f3cfff0163634f4499eeb318a04297f7_720.jpg

堆&&优先队列

什么是堆

优先队列的完全二叉树表示

image.png

完全二叉树的定义：

从上往下写，从左往右写，不能空；也可以看作是满二叉树从后面删除几个

最大堆&最小堆：

首先要是完全二叉树，其次，从上往下找路径必须是单调递增或者单调递减
即从根节点到任意路径上结点序列的有序性
示例：
image.png

堆的插入

堆的数据结构

image.png

最大堆的插入思路分析

朴素的想法：直接放在最大堆堆元素数组的最后一个位置上，然后检查是否破环了最大堆的有序性
如果不破坏有序性那没事，倘若破坏了有序性，那么则依次和父节点交换位置，保证有序性

最大堆的插入算法实现

image.png
和父节点比较大小：如果当前元素的下标是i，那么其父元素的下标就是i/2
如果发现有序性被破坏（element[i]>element[i/2]，就把父节点的的值赋值给子节点（
父节点的较小值往下，更大的item应该放在更上边）
依次比较，不断地i/2向上比较……
直到不满足红框里的条件了，那么执行H->Element[i]=item,这时的i已经经过了很多次自除2的操作，相当于已经在最大堆的顶峰了，这时只要把item赋值到H->Element[i]处即可了。
插入的时间复杂度：image.png

堆的删除

最大堆删除的思路分析

朴素的想法：如果要去掉最大值，即最大堆的根节点，只要把这棵完全二叉树的最后一个叶子节点赋值给根节点，然后再判断是不是破坏了最大堆的序列有序性。

最大堆删除的算法实现

image.png
1.先把要删除的元素（H->Element[1]）保存起来，赋值给MaxItem,在程序的最后需要return这个maxItem的；
2.把H->Element[size]赋值给交换介质temp，然后size—，最大堆的长度自减；
3.Parent2<=H->size来判断该结点是否有左儿子
4.下一步找出左右儿子里更大的一项与父元素交换；child=parent2，先假设左儿子更大，自然，此时的右儿子就是H->Element[Child+1]

堆的建立

最大堆的建立

image.png
这个问题不难，重在推理

二叉搜索树(BST)

什么是二叉搜索树

1.左子树的键值都小于根节点的键值
2.右子树的键值都大于根节点的键值
3.左右子树本身都是BST
示例如下：
image.png
二叉搜索树：中序遍历的结果正好是从小到大排列的顺序，所以已知先序或者后序的bst是可以推断出完整二叉树的！！

二叉搜索树的递增性质

中序遍历一颗二叉搜索树，得到的序列是单调递增的
image.png

二叉树的查找

思路1：递归方法

如果待查的数字大于根节点，那就找右子树，递归寻找
反之，去左子树查找
效率很低，都是尾递归；思考可以把尾递归转换成迭代函数；
若函数在尾位置调用自身（或是一个尾调用本身的其他函数等等），则称这种情况为尾递归。
image.png

思路2：迭代方法

依赖指针的移动转换子树
image.png

查找的效率决定于树的高度，尽量不要往一边倒

查找最大最小元素

也就是一直向左或者一直向右查找
image.png

二叉搜索树的添加，删除

二叉平衡树

1.首先是二叉搜索树，左>根>右
2.左子树高度减去右子树高度=-1，0，1

插入后的调整

1.找到需要调整的最小子树，尽量让树更平衡

哈夫曼树

什么是哈夫曼树？

发现问题：

如下图的按分数段查询赋分的程序，由于先判断60以下，但是六十分以下的占比很少，绝大部分都是70分以上，却不得不经历下面的四次判别，很浪费效率；例如，30%的同学都必须要经历<60?<70?<80?的判断，这是可以优化的
image.png

解决方法：修改判定树

由此大大提高了判别效率
image.png
怎么构造一个最好的搜索树，正是哈夫曼树要解决的问题
image.png
例如这里:权值乘路径长度，由不同的二叉树构造方式，WPL值也不同

哈夫曼树的构造

*每次把权重最小的两棵树合并

image.png

12合并成3，和3合并，最后选45合并
image.png

哈夫曼树的特点

1.没有度为1的结点
2.n个叶子节点的哈夫曼树共有2n-1个节点
3.对于同一组权重，存在不同的两棵哈夫曼树
image.png

哈夫曼编码

image.png
image.png
频率高的代码用短些的编码，频率低的字符可以编码长些

不等长编码注意：避免二义性

二义性如下：image.png

解决方法：避免前缀码

前缀码：任何字符的编码都不是另一个字符编码的前缀即可

使用二叉树进行编码

（1）左右分支分别为0，1
（2）字符只在叶节点上，若非叶结点上出现字符，那么就没法避免前缀码的出现
image.png
image.png
14<16

怎么构造编码代价最小的二叉树

答：每次从每一层挑出频率最小的两个叶子合成一个树，依次合成
image.png
1<3<4<10<12<13<15
image.pngimage.png

image.pngimage.png
image.pngimage.png
然后,每一棵二叉树的左枝为0，右枝为1；从上到下依次读出每一个字符对应的编码
例如：
a:111
e:10
i:00
s:11011
t:1100
sp:01
nl:11010
COST=权重*路径长度（1/0的根数）（哈夫曼树Cost最小）
南邮的课本上这里的cost就是WPL
image.png

散列表（哈希表）

一种组织集合元素的数据结构，也叫哈希表。是一种根据关键字值实现直接数据元素访问的数据结构。存储元素时，建立关键字和散列表中存储关系的映射关系，把元素存储到相应位置。访问时也依赖着这种映射关系，高效的查找到对应存储位置；

相关概念

散列函数/哈希函数：

关键字和其存储位置的函数，这个函数计算出的值被称为散列值
通常形式就是h(key)=value，h就被称为哈希函数

散列表/哈希表：

用哈希函数建立起来的表，用于存储集合元素，例子如下
image.png

散列表冲突

通过某哈希函数，使不同的key计算出的哈希值相同，映射到相同位置，产生冲突
同义词：key1!=key2;但是h(key1)=h(key2)时叫做冲突，key1和key2叫做同义词

为了避免冲突，也不是能用一切办法：value的值不能超出地址
image.png

常见的哈希函数

什么是好的哈希函数？首先需要做到key->value的映射一一对应
其次计算快速，其次应该充分覆盖散列表的存储空间
最重要的，为了降低冲突的同时充分利用散列空间，需要保证映射到各个位置的概率接近，避免出现很多元素扎堆的现象
不过这里应该不会考吧？

1.除留余数法

即取模，膜值取不超过M（散列表长）的素数为宜
image.png
image.png

2.除留余数法的改进MAD

image.png
b:偏移量，解决了不动点的问题
a:间隔量，保证了相邻地址从1变成a

3.平方取中法

image.png
image.png

4.折叠法

也就是把较长的key值，先分段，在累加
image.png

5.数字分析法

也就是瞪眼法，经过观察一拍大腿决定
image.png

解决冲突的技巧

主要分为开散列法和闭散列法，拉链法是开散列法，其余的线性探查和二次探查，双散列法是闭散列法

1.拉链法

image.png
对于h哈希函数对11取余数，这个散列表存在冲突现象

闭散列法

闭散列法也叫开放地址法，开放指的是元素在撒列表的位置下标不完全取决于散列值，也取决于冲突处理策略，散列表已经存的元素。
开发地址法都有一个统一的思路
image.png
探查序列：指依次被探查的位置

2.线性探查法

image.png
image.png
总结，线性探查法也就是先试试看能不能直接找到对应的空位，有则直接插入，没有的话向后调剂，如果一直没有空位那就从0开始找，直到找到空位并插入

查找

从坐标开始查找，往右遍历，如果遍历到空格还是没有找到或者满散列表，则宣布查找失败

删除

第一，不能只是简单的清除元素，否则后面的元素会被隔离而不好查找
第二，删除元素之后，该位置应该要能重新使用

解决方案如下，如果元素值为NU,标志却是False，意味着这个位置不是本来empty，只是被删除了
image.png

3.二次探查法

二次：指加减二次方项摇摆插入
image.png
左右摇摆的探查，对11取模，那么i最大就取为（11-1）/2，即5；当然这是最极端的情况，一般几次摇摆就能找到空位了 :::info 例1
image.png
基地址2被占用，先加后减1，加一时余3，也被占用，接着减去一的平方，余1，可以插入。完成； ::: :::info 例2image.png基地址占用，+1占用，-1占用，+4有位置，插入 ::: 35和13是同义词，经过二次探查法却相隔的很远，很好的证明了二次探查法可以解决过度聚集的现象； :::info image.png
答案：key,key+1,key-1,key+4,key-4,key+9,key-9…..image.png :::

4.双散列法

顾名思义，有两个散列函数，h1和h2，探查序列为
h1,
h1+h2,
h1+2h2,
h1+3h2…..
即使用h2对h1产生一个固定的增量
h1是取M的模，那么h2可以对M-2取模后+1
image.png
比如，h1对11取模，那么设置h2为对9取模加1； :::info image.png
先计算出h1=3.h2=5
然后对基地址3检查，然后(3+5)%11，(3+10)%11，(3+15)%11….. :::

图

图的基本概念

image.png image.png
image.png
image.png
image.png
image.png

邻接表示法

邻接表

image.png

把图中的每一个顶点都建立一个单链表，把与该顶点的相邻接的顶点都写在这个单链表后
每一个单链表的开头元素叫做头结点，其余的叫做边结点。

无向图类似，但是不区分出度入度了

网多加一个存储空间存储权值；
image.png

邻接矩阵

有向图，无向图，网的邻接矩阵有一些差别。
无向图有向图和离散数学的概念类似 ，网上对角线为0，其余为有向写权值，无向写∞
image.png

图的遍历

深度优先遍历（搜索）DFS

image.png
当wt的所有临界结点都访问过了，则回退到上一次访问的结点，查看是否还有未访问的结点
image.png

看图深度优先搜索

image.png

深度优先生成树

把一次深度优先搜索的前进边都保留下来，就是一棵深度优先生成树
image.png

有向图的深度优先搜索

image.png
一次搜索可能不足以搜索全部，如果发现无法回退了，那么就重新选择一个起点进行第二次深度优先搜索
比如这里 0123 /465

看邻接表深度优先搜索

image.png

宽度优先遍历（搜索）BFS

每次向前一次都会连着访问一批结点，不存在回退现象；image.png

看图宽度优先搜索

image.png
过程：
0/
1，11，10////1的未曾访问的结点没了
接着依次访问1 11 10的未曾访问的结点
2 5 // // 6 9
3//4//7//8

综上 宽度优先搜索类似树的层次遍历

看邻接表宽度优先搜索

和上面一个思想就行
image.png
241 50 3或者241 3 50

拓扑排序，AOV网

一些事情是必须有先决条件的
image.png
AOV网不应该有环，因为不能以自己为先决条件
image.png

关键路径，AOE网

image.png
源点：工程开始的点
汇点：工程结束的点

应用

关键路径

完成工程的最短时间，也就是图上的从起点到终点的最长路径，称为关键路径 :::info 什么？为什么最长路径居然是最短时间？？
其实是理解有误，这个AOE网的多线程同时开工，想让这个项目落地，最短的时间也必须等到最长路径的完工才能结束，所以称这个最长路径是关键路径，关键在这个地方，决定了这个工程的最短时间 ::: image.png
关键活动就是关键路径上的活动，上面的数字代表了对应活动需要的时间。如果关键路径的活动可以提前完成，那么对于整个活动的工期都可以缩短。

最早发生时间—可能的最早时间

Eearly(vi)：从开始到顶点vi的最长路径，必须最长耗时的工程完成了，才是vi事件发生的最早时间

最迟发生时间—允许发生的最晚时间

Elate(vj):不影响工期的前提下，该活动的允许发生的最晚时间
活动的最迟开始时间，是他后面的事件发生的最迟时间-这件活动的耗时
image.png

最小代价生成树

概念：也是就是找一个子集，使得各边权值之和最小
image.png

普里姆算法

image.png
image.png
image.png

从0开始，这时的入边是10，20，30
image.pngimage.png
这一步之后，2加入T了，这样入边就更多了，包括10，30 ，12，32，42，52，权值最小的是52，所以是5加入T；接下来12，32，42，52，35，45最小的边是35，所以3加入T.
image.pngimage.png
接下来重复，最后使所有的节点都加入
image.pngimage.png

克鲁斯卡尔算法

image.png

image.pngimage.png
以0为原点生成最小代价生成树

image.png
从G里删去代价最小的边02，加入T

image.png
image.png
然后依次找G里最小的代价边，分别加入T里，直到生成回路
image.png

单源最短路径

最短路径：路径上边的权值之和最小image.png

迪杰斯特拉算法

基本思想：按路径长度的非递减次序逐一产生最短路径
战略放弃了，爱考不考，考到我认了

排序

期末要求：image.png

简单选择排序

主要思想就是分成有序区和无序区，左边有序，右边无序。
初始状态下，左边都是无序的，然后找出最小元素和最左边的元素交换位置，相当于最小元素进入了有序区域。以此类推重复即可。
一句话说明白，就是每次把最小的拎到最前面
image.png

程序实现

第一步 找到最小的元素
image.png
第二步 交换最小元素和无序区的下标StartIndex
每次更新有效区，无效区的时候startIndex++,始终是无效区的开头元素
startindexn-1:无效区个数小于2时退出
image.png

算法分析

image.png

快速排序

平均情况下，排序速度最快的排序
主要思想，选择一个分割元素D，左边都是不大于D的元素，右边都是不小于D的元素。达成这个目标称为一次快排，重复几次完成排序。
分割元素，快速排序的核心
image.png

image.png

可以在i，j两边写个大于等于和小于等于号注意这里大于等于或者小于等于的比较对象都是分割元素即第一个元素，和移动的方向一致，也是停止扫描的条件；
i,j停止了，如果i，j坐标前后顺序不变，那么交换两个数的位置
如果i,j交错了，j到i左边了，那么 交换 j 和low（分割元素），结束一趟排序。
一趟排序之后，这组数字被分割元素分成两组，对两边继续递归使用快速排序
image.png
线上期末快排的实例，记住核心就是大于等于和小于等于的对象都是分割元素
e1c6c4522c6f6b40f0d1782d6fb0808b_720.jpg

程序实现

算法分析

image.png

两路合并排序

image.png

程序实现

算法分析

堆排序

程序实现

算法分析