不定积分

　　大致分为以下几类积分：有理函数积分，三角函数积分，无理函数积分，反三角积分。
　　
　　１.反三角积分——被积表达式中出现反三角函数
　　　　消除反三角函数，因为反三角函数没有积分公式。
　　　　方法是使用第二类换元法把整个反三角换掉（相当于把x换成三角，三角复合反三角达到消除效果）；或分部积分法。

　　２.无理函数积分——被积表达式含有根号
　　　　分为两种：可以使用三角换元的，以及不能使用三角换元的。
　　　　2.1可以使用三角换元的：令x = asint/acost/atant/asect...，化为三角函数积分。
　　　　2.2不可以三角换元的：将根式换掉，化为有理函数积分

　　3.三角函数积分——被积表达式含有三角函数
　　　　技巧法（不一定成功）：令sinx = t或cosx = t...，或直接用三角变换积分。
　　　　万能法：令tanx/2 = t，然后使用万能公式将原积分转化为有理函数积分。

　　4.有理函数积分——一般为分式，分子分母都为多项式
　　　　分为两类——真分式与假分式，但归根结底一个字：拆。
　　　　4.1真分式：
　　　　　一般方法——部分分式法：
　　　　　　分母可因式分解为一次式的k次方与二次式的一次方的乘积时可以使用，具体见p116例题12
　　　　　特殊方法：
　　　　　　对于分母而言，思考如果分子是什么形式会使得整体可积。这些分子形式的线性组合是否能成为已有分子。
　　　　4.2假分式——化为真分式

定积分

　　前四种方法与不定积分相同。
　　但都可以考虑对称性与周期性。无理函数积分为二次式开根号的，就可以画圆。
　　新增公式：半π找n次，整π可提x。
　　●对于上下限有x，被积表达式亦有x的定积分函数，需通过拆项或换元，尽量把被积表达式中的x提到积分符号外面去，让被积表达式中不要出现x。

在C语言中，原子量（Atomic）用于实现多线程环境下的无锁同步操作，确保对共享变量的操作是不可分割的（即原子性）。C11标准引入了 <stdatomic.h> 头文件，提供了对原子操作的支持。
互斥量用于保护多行代码块，原子量可以保护一行代码（对原子变量的操作）。以下是原子量的核心用法和注意事项：

1. 原子类型声明

使用 _Atomic 修饰符声明原子变量：

#include <stdatomic.h>

_Atomic int counter = ATOMIC_VAR_INIT(0); // 声明并初始化为0

或简写：

atomic_int counter = 0; // 等效于 _Atomic int

2. 基本原子操作

加载（Load）和存储（Store）

int value;
value = atomic_load(&counter);        // 原子读取
atomic_store(&counter, 42);          // 原子写入

交换（Exchange）

int old = atomic_exchange(&counter, 100); // 将counter设为100，返回旧值

比较并交换（CAS, Compare-And-Swap）

int expected = 10;
int desired = 20;
if (atomic_compare_exchange_strong(&counter, &expected, desired)) {
    // 成功：counter原值为expected，被更新为desired
} else {
    // 失败：counter当前值 != expected，expected被更新为实际值
}

3. 原子算术/位运算

atomic_fetch_add(&counter, 5);    // 原子加5，返回旧值
atomic_fetch_sub(&counter, 3);    // 原子减3
atomic_fetch_or(&counter, 0x1);   // 原子按位或
atomic_fetch_and(&counter, ~0x1); // 原子按位与

4. 内存顺序（Memory Order）

指定原子操作的内存同步行为，控制指令重排和可见性：

atomic_store_explicit(&counter, 42, memory_order_release); // 写入释放
int val = atomic_load_explicit(&counter, memory_order_acquire); // 读取获取

常用选项：
• memory_order_relaxed：仅保证原子性，无同步/顺序约束。
• memory_order_acquire：本操作前的所有读写不会被重排到它之后。
• memory_order_release：本操作后的所有读写不会被重排到它之前。
• memory_order_seq_cst：严格顺序一致性（默认）。

5. 示例：线程安全的计数器

#include <stdatomic.h>
#include <stdio.h>
#include <threads.h>

atomic_int counter = 0;

int thread_func(void *arg) {
    for (int i = 0; i < 10000; i++) {
        atomic_fetch_add(&counter, 1);
    }
    return 0;
}

int main() {
    thrd_t t1, t2;
    thrd_create(&t1, thread_func, NULL);
    thrd_create(&t2, thread_func, NULL);
    thrd_join(t1, NULL);
    thrd_join(t2, NULL);
    printf("Counter: %d\n", counter); // 正确输出20000
    return 0;
}

6. 注意事项

1. 性能：原子操作比普通操作慢，仅在必要时使用。
2. 适用场景：简单共享变量（如标志、计数器），复杂逻辑仍需互斥锁。
3. 兼容性：需C11及以上编译器（如GCC -std=c11）。
4. 避免ABA问题：CAS操作需注意值被其他线程多次修改的情况。

7. 扩展知识

• 无锁编程：原子量是实现无锁数据结构的基础（如队列、栈）。
• 编译器屏障：atomic_signal_fence() 用于线程与信号处理函数间的同步。

通过合理使用原子量，可以高效解决多线程竞争问题，但需谨慎设计以避免逻辑错误。

数据结构——图

一、图的性质

　　•图的路径的定义是边序列，也可是点边序列（正规定义）：以下默认路径是简单路径（点边序列中边不重合的路径）。
　　•一个图有n个结点，若边数大于n-1条，则一定有环（首尾结点相同的路径）（记住即可）。
　　•生成子图是一个包含原图所有结点的子图。
　　•无向图的连通：
　　　两结点连通，即两结点之间有路径。
　　　一个图是连通图，即任意两个结点有路径。
　　　连通分量 = 极大连通子图 = 包含尽可能多的结点与边的连通子图。
　　　无向图成为连通图所需边最少：构成一条线或一个生成树——n-1条。
　　　无向图成为连通图所需边最多：成为完全图——n(n-1)/2条。
　　•有向图的强连通：
　　　两结点强连通，即两结点可相互到达。
　　　一个图是强连通图，即任意两个结点可以相互到达。
　　　强连通分量 = 极大强连通子图 = 包含尽可能多的顶点与边的强连通子图。
　　　有向图成为强连通图所需边最少：构成一个环——n条。
　　　有向图成为强连通图所需边最多：成为完全图——n(n-1)条。
　　•对于连通图，有生成树，该生成树是包含其所有结点的极小连通子图（极小是边极少但仍保持连通）。非连通图有生成森林。
　　•连通分量只能少结点，生成树只能少边。而“极大”、“极小”是描述边的，因此极大连通子图指连通分量，包含全部顶点的极小连通子图指生成树。

二、图的存储

　　图的存储分为四种方法。
1.邻接矩阵存储
　　•矩阵元素为边，要么为1或0，要么为无穷（也可以为0）或一个数。
　　•矩阵元素（i,j)为1则表明结点i与结点j之间有边（无向图）或从结点i到结点j有弧（有向图）：
　　　因此一个顶点的入度（有向图）为j作为其自身而固定，i从1到|V|的元素中1或非0常数的个数——逐行求和。
　　　因此一个顶点的出度（有向图）为i作为其自身而固定，j从1到|V|的元素中1或非0常数的个数——逐列求和。
　　　因此一个顶点的度（有向/无向图）为上述相加——十字求和。
　　　总结：入行出列。
　　•存储的空间复杂度为O(n)。

2.邻接表存储及其改进存储方式
　　•一个图通过邻接表等所有涉及链表的存储方式进行存储的结果都不唯一——链表次序可不同（不用深究矩阵等顺序表为什么不能改变顺序）
　　•无向图的邻接表存储的边冗余了一倍——导致边链表结点的总数必定是偶数。
　　•任何需要遍历整个图的邻接表的操作（删除结点、建立表、有向图记录结点入度）的时间复杂度为O(|V|+2|E|)（无向图）或O(|V|+|E|)（有向图）即结点的个数，包括数组结点与链表节点。
　　•十字链表与邻接多重表是邻接表的变体。十字链表用于有向图，邻接多重表用于无向图。
　　　十字链表解决入度难寻的问题：从结点结构firstout域出发的边链表为其出度链表（一行）；从结点结构firstin域出发的链表为其入度链表（一列）。
　　　邻接多重表解决冗余问题：从结构结构的firstedge出发，每一个边结点都会告诉你下一个下一个边结点的位置，但你需要判断该往ilink走还是该往jlink走。

三、图的遍历

　　•两种方式——BFS、DFS。

1.BFS：Breadth-First-Search。外层函数使用循环从visted数组首结点开始调用BFS主体函数，循环条件是数组项为0（未访问）。BFS主体函数将传入该函数的结点入队，每次出队一个所有其未访问的邻接结点（需要visited数组支持）。入队时访问或出队时访问均可，访问后将结点对应visited项置1。
　　•采用邻接表进行BFS遍历，所有的操作无非就是对图的所有结点与所有边操作一次。时间复杂度为O(|V|+|E|)。
　　•采用邻接矩阵进行BFS遍历，所有的操作无非就是对图的所有结点入队的同时搜索其邻接结点。时间复杂度为O(|V|*|V|)。

2.DFS：Depth-First-Search。外层函数使用循环从visted数组首结点开始调用DFS主体函数，循环条件是数组项为0（未访问）。DFS主体函数先访问该结点，置该结点的visited项为1。然后对其每个visited为0的邻接结点递归调用该DFS主体函数。

　　•不需要visited数组的条件很苛刻。无向图不可能不需要。有向图只有树形才不需要。
　　•深度优先搜索可以判断一个图有没有环。这需要维护一个全局parent数组。考虑一个结点访问完后对其邻居判断是否已被访问，若未访问则访问。现在新增：若已访问，则看该邻接结点是否为其双亲结点（其直接遍历前驱），若不是，那么有环。
　　•BFS生成树的树高为图的两个结点距离的最大值。DFS生成树的树高至少为图的两个结点的最大值。

四、最小（代价）生成树算法

　　•适用：无向连通图
　　•应用：连通各点的道路最短修筑距离

1.prim算法：选一个结点加入树开始，维护各个结点加入树的最小代价数组lowCost与是否已经加入树的状态数组isJoin。对剩下每一个结点，调用两个循环。一个循环用于找到加入树代价最小的结点，然后将该结点加入树，将该结点对应的isJoin表项置1。第二个循环用于更新lowCost数组，具体操作是只要比较每个不在树中的结点到刚刚加入树的结点的距离是否小于现有值，小于就改。因此对于|V|-1个结点，每个结点消耗O(|V|+|V|)，总的时间复杂度就是O(|V|^2)。不依赖边。

2.kruskal算法：先将所有边抹除导致每个结点自成一个集合。每次选一条权值最小的边并将边关联的两个集合合并，且边的两个关联节点调用并查集的查操作证明不属于同一个集合，重复操作直到所有结点都在一个集合中。因此总计外层循环次数与边数|E|正相关，每个外层循环内部需调用并查集的查操作，其循环次数与树高log|E|正相关，故总的时间复杂度为O(|E|log|E|)。

　　•两个算法每次都不保证每次循环一定会选最短的未选边，prim要求新选结点在树之外，kruskal要求新选边的两边不同属一个集合。

五、最短路径算法

　　•适用：BFS算法适用无权图，Dijkstra算法适用正权图（多为有向图，但可以是无向），Floyd算法适用没有总权值为负的回路的图（多为有向图，但可以是无向）。
　　•应用：BFS与Dijkstra算法用于求单源最短路径；Floyd算法直接给出任意两点的最短路径。

1.BFS算法：只需修改BFS主体函数。函数一开始就初始化路径长度数组dist除了源为0其余为无穷，每个结点i出队后将其所有邻接结点j入队时将每个邻接结点j的路径长度设置为该出队结点i的路径长度+1（dist[j] = dist[i] + 1）。

2.Dijkstra算法：基于贪心算法。使用final数组表明各结点是否已找到最短路径=是否已经走过，使用dist数组存储各结点到源点的最短路径，使用path数组记录每个结点到源点路径的第一前驱。

　　a.首先初始化dist为各结点到源点的边的权值，没有边则为∞。若各结点与源点有边，path为源点所在数组下标，否则为-1。
　　b.然后，挑没走过的（final为0）且距离最短(dist最小)的路走，走完后所处的点到源点的最短路径就定了（不可能绕到其他点再回来会比此路径更短）。将目前所处的点的final置1。
　　c.最后看看从这个点出发到没有走过的邻接点（final为0）是否会更近，更近则更新dist数组与path数组中该临界点所在的项。
　　d.重复bc直到走完全部结点或final值都为1。

　　•时间复杂度分析：总共要走|V|-1个结点，每走到一个结点处，要使用循环遍历其射出的弧修改dist数组与path数组，循环次数取决于该结点的射出的弧数|E|（邻接表）或总结点数|V|（邻接矩阵）。接下来还要一个循环遍历dist数组找到没走过的最小项。因此时间复杂度为O((|V|-1)x(|V|+|E|))或O((|V|-1)x(|V|+|V|))，但化简后都是O(|V|x|V|)。

3.Floyd算法：基于动态规划。采用一个方阵A，逐步以各顶点作为中转迭代A。

　　a.首先初始化一个nxn的矩阵，每个矩阵元素A(i)(j)为结点i到结点j的距离。
　　b.以k号结点作为中转(k=0,1,2...n-1)，遍历矩阵，若结点i到结点k再到结点j的距离较原A(i)(j)小(A(i)(k)+A(k)(j) < A(i)(j))，则将A(i)(j)置为A(i)(k)+A(k)(j)。

　　•时间复杂度分析：显而易见，O(|V|x|V|x|V|)。

六、AOV网扩扑排序、AOE网关键路径算法

　　•适用：有向无环图。AOV网=有向无环图，AOE网还要求只有一个源点，只有一个汇点。

1.AOV网拓扑排序——标准法：假设已经准备好indegree数组存储每个结点的度
　　a.初始化一个栈或队列，将原所有度为0的结点如栈，初始化已经输出的结点数count为0，初始化print数组记录先后。
　　b.开始循环，循环条件为栈非空。每次循环出栈一个结点并将该结点存储进print数组最前面没被存储的位置。将该结点所有射出的弧指向的结点的度-1，遍历该结点所有射出的弧指向的结点，若发现度为0的结点，压入栈中。
　　c.最后发现count小于图的结点数，则说明有回路（回路导致没有结点度为0），输出失败信息，则输出成功信息。
　　•排序算法若给的是outdegree则得到是逆拓扑序列。
　　•若求一个AOV网的全部拓扑序列，则需要注意的是存储空间（队列或栈或别的）中有多个结点，那么出队的顺序是任意的。做题时牢牢根据算法，每个步骤写成“X出XXX...入”，或“X出”（没有入的）。每次出的时候脑海中把相应边抹除。参考王道课后题p244 16题，慢下心来。
　　•选择题问谁是给定图的拓扑序列直接从选项入手，列出所有扩扑序列需要耗费大量时间。从前至后，删除每个结点与其边，若有个结点删除时发现其前驱没有被删，就错。
　　•一个有向图有拓扑序列与该有向图没有环与该有向图可以作为AOV网三者等价。
　　•有向图有有序扩扑序列可以推出有向图的邻接矩阵为三角阵（因为有序拓扑序列任两个结点排在前面必定编号小，而扩扑序列只有排在前面的指向排在后面的弧，没有排在后面的指向排在前面的弧，则所有弧都是小编号结点指向大编号结点，则该图的邻接矩阵为三角阵）。有向图的邻接矩阵是个三角阵，可以推出该有向图必定无环，拓扑序列必定存在。

2.AOV网拓扑排序——DFS法：假设已经给出一个度为0的点
　　从该度为0的结点开始，调用DFS函数。函数主体先递归访问其所有未被访问的邻接，然后再将其自身添加进一个数组前面。如此，得到的数组的顺序就是先最后的工程，最后才是一开始先完成的工程。最后将数组倒置即为扩扑序列。
　　•若最后不倒置则得到的是逆扩扑序列。

3.AOE网关键路径
　　（结点代表的）事件的最早发生时间：当每个活动能做就做时所有前面发生的最晚结束的活动结束的时候。（不能再早了，不然就抢先了）。
　　（结点代表的）事件的最迟发生时间：当每个活动能拖就拖时所有后面发生的最早开始的活动开始的时候。（不能再晚了，不然就来不及了）。
　　（弧代表的）活动的最早开始事件=弧的源头结点的最早发生时间。
　　（弧代表的）活动的最晚开始事件=弧的指向结点的最晚发生时间-该活动耗时。
　　•关键路径上各个结点发生时间固定。最早发生时间=最晚发生时间。
　　•关键路径算法：
　　　1.先对图进行扩扑排序与逆拓扑排序。
　　　2.利用扩扑序列，从源点开始，求得每个结点的最早发生时间。
　　　3.利用逆拓扑序列，从汇点开始，求得每个结点的最晚发生时间。
　　　4.最早与最晚发生时间相等的结点构成关键路径（可能多条）。
　　•AOE网关键路径算法能判断图是否有回路全依赖扩扑排序的count。
　　•选择题求一个AOV网关键路径时用瞪眼法。

高等数学重要定理总结

定理是证明题的关键，包括著名定理与小定理。

一、函数、极限与连续

1.最值定理：函数在一个闭区间内连续则必有最大值与最小值
2.有界性定理：函数在一个闭区间内连续则必有界
3.介值定理：函数在一个闭区间内连续且区间端点函数值不相等，则该闭区间内必有一点的函数值介于端点函数值之间
　　扩展：函数在一个闭区间内连续且区间端点函数值不相等，则该闭区间内必有一点的函数值介于该区间内的最大值与最小值之间（常与1共同使用）
4.零点定理：函数在一个闭区间内连续且区间端点函数值符号相反，则该闭区间内至少有一点的函数值为0
　　（可用于证明方程根的存在性）

5.极限的有界性：
　　-数列若收敛(n->∞的极限存在)则必有界
　　-函数若在一点处极限存在，则在该点去心邻域有界
6.极限的保号性：
　　-数列在n->∞时有一个正数极限，则肯定有一点之后的所有值都大于0，反推成立，反之亦然
　　-函数若在一点处有一个正数极限，则存在一个距离δ，在范围为该距离的去心邻域内的所有点函数值都大于0，反推成立，反之亦然

7.夹逼准则：略
8.单调有界准则：单调有界数列必有极限

二、导数、微分与中值定理

1.费马引理：可导函数在一点取极值，则该点导数为0
　　(因可导即左导=右导，而左导右导符号相反而得证)
2.罗尔中值定理：函数在闭区间连续，开区间可导，若在该区间两端点函数值相等，则区间内必有一点导数值为0
　　（由最值定理+费马引理证出，可用于证明方程根的存在性）
3.拉格朗日中值定理：函数在闭区间连续，开区间可导，则该区间内必有一点的导数值等于该区间端点连线的斜率
　　（由辅助函数——端点连线与函数值的差值，应用罗尔定理得到）
4.柯西中值定理：两函数在闭区间连续，开区间可导，则增量比值=一点处导数比值
　　（启发来源为拉格朗日中值定理的参数方程形式，证明由辅助函数——定理表达式全移到一边，应用罗尔定理得到）

三、不定积分与定积分

1.原函数存在定理：函数的连续闭区间上必有原函数
　　（导数存在要求Δy/Δx比值极限存在，极限存在要求左右极限相等，即导数处处不突变。只有连续函数才能成为导数）