835 字 1 分钟

# 起因 最近看 GAMES104 课程听到 clang 的时候懵了一会，想了想以前是谷歌过的啊，为了避免忘记再次谷歌省点麻烦，故作了一点简单的整理。 这里只罗列我可能会用到且目前主流的编译器，非主流的几乎都是半死不活了，没必要了解。 # 编译器 # GCC 官网:gcc.gnu.org 支持架构：X86、ARM 支持系统：Linux 原本 GCC (GNU Compiler Collection) 就只是一个 C 编译器而已，只不过现在发展成一个支持多种语言的编译器套装了，而且名字还不一样。 # GCC 变种 - windows #...
3.2k 字 3 分钟

# 完结感想     ~~~~         ~~~~         ~~~~     耗时一年，我终于把这本《数据结构和算法分析 - C 语言描述》学完了，你说我学懂了没有？没有，完全没有！！！甚至可能前面都忘了，因为时间跨度太大了     ~~~~         ~~~~         ~~~~    ...
5.8k 字 5 分钟

# 第十一章 # 什么时候向一个二项队列进行连续 M 次撬入的花费少于 2M 个时间单位的时间？ 当插入的数量多于之前当前树的数量。 # 设建立一个有N=2k−1N=2^k-1N=2k−1 个元素的二项队列，交替进行 M 对 Insert 和 DeleteMin 操作。显然，每次操作花费0(log⁡N)0(\log{N})0(logN) 时简。为什么这与插入的Θ(1)\Theta (1)Θ(1) 摊还时间界不矛盾？ 尽管每次插入操作花费log⁡N\log{N}logN, 每次删除操作花费2log⁡N2\log{N}2logN, 虽然这与线性摊还时间相悖，但当NNN...
7.5k 字 7 分钟

# 证明贪婪算法可以将多处理器作业调度工作的平均完成时间最小化 假设 P 个处理器有均匀分的 N 分作业，则有最小调度时间C=∑k=1N(N=k+1)tikC=\sum_{k=1}^{N}(N=k+1)t_{ik}C=∑k=1N​(N=k+1)tik​; 若 P 个处理器有不均分的 N 份作业，这里假设所有处理器处理的总调度时间一致，则由小到大排序好后仍由最小平均完成时间。 # 设作业j1,j2,...jnj_1,j_2,...j_nj1​,j2​,...jn​ 为输人，其中的每一个作业都要花一个时间单位来完成。如果每个作业jij_iji​ 在时间限度ttt 内完成，那么将挣得did_idi​...
2.6k 字 2 分钟

# 给出一个算法求解最大生成树。这比求解最小生成树更难吗？ 将 Kruskal 算法生成最小生成树关于最小值选择比较的语句改成最大值比较即可，和求解最小生成树相比一样难度。 # 证明寻找割点的算法的正确性 假设存在一个矛盾，即非根节点aaa 和后代节点和正确的祖先节点没有正确的建立联系，因为存在这个矛盾且确实存在，因此存在寻找割点的算法的可能。 # 证明：在一个有向图的深度优先生成森林所有的交叉边都是从右到左的。 设(v,w)(v,w)(v,w) 为交叉边，当检查点www 时，标记，若点vvv 不是www 的后代，按照左右子树的规定，则应该是w−>vw ->...
4.3k 字 4 分钟

# 编写个程序执行对一个图的拓扑排序 拓扑排序简单的来说是求有向无环图的一条从顶点vvv 到顶点uuu 的路径。 拓扑排序参考链接/*----- -----| 1 | -> | 2 |----- ----- | \ /|\ \ / _\/ |----- ----- | 4 | | 3 |----- ----- / \ \ | | _\/ \|/----- ----- | 6 | -> | 5 |----- ----- */void Topological_Sort(Graph G){ /* * Create an array of in-degrees for...
3.9k 字 4 分钟

# 编写一个程序来确定路径压缩法和各种求并方法的效果。你的程序应该使用六种可能的方法处理一系列等价操作。 题意是叫你实现 2 种 find 操作和 3 种 union 操作，常规任意并查集初始化为 0，但灵巧求并算法的初始化为 - 1。测试数据可以用书上习题 8.1 的，还挺有用的。 void DisjSet_Init_0(DisjSet S){ for(int i = NumSets; i > 0; i--) S[i] = 0;}// it apply in DisjSet_Union_Size() and...
11k 字 10 分钟

# 设我们交换元素 A [i] 和 A [i+k], 它们最初是无序的。证明去掉的逆序最少为 1 个最多为 2k-1 个 若 N=1, 则只存在一个逆序数。 若 N=K, 则 A [i] 和 A [i+k] 各存在 K-1 的逆序数，且有一个重复，即 (A [i],A [i+k]), 总共 2K-1 个。 所以去掉的逆序最少为 1 个最多为 2k-1 个。 # 下述两种对图 7 一 4 所编写的希尔排序例程的修改影响最坏情形的运行时间吗？ # a. 如果 lncrement 是偶数，则在第 2 行前从减 1。 不会，希尔排序的一个重要特性是增量之间最好不要有公因子，即增量之间互素，原始增量排序...
7.9k 字 7 分钟

# 编写在二叉堆中进行上滤和下滤的例程 这是二叉堆的最重要操作步骤。 上滤波static int percolateUp(BinHeap H, BinHeapElementType X, int Pos){ int i; for(i= Pos;H->Elements[i/2]>X;i/=2) H->Elements[i] = H->Elements[i/2]; return i;}下滤波static int percolateDown(BinHeap H, BinHeapElementType LastElement, int...