-
CSAPP2 信息的表示和处理
介绍深入理解计算机系统第二章的家庭作业2.55#include <stdio.h>typedef unsigned char *byte_pointer;void show_bytes(byte_pointer start, size_t len) { size_t i; for (i = 0; i < len; i++) printf(" %.2x", start[i]); printf("\n");}void show_int(int ...…
-
CLRS25 所有结点对的最短路径问题
介绍 以表格形式表示输出，第u行第v列给出的是结点u到v的最短路径权重。 可以用V次单源最短路径问题，但是可以做得更好。 算法的输入是一个n * n的矩阵W，该矩阵代表的是一个有n个结点的有向图的权重。 PRINT-ALL-PAIRS-SHORTEST-PATH(T, i, j) if i == j print i elif Tij == NIL print "no path from "i "to" j" e...…
-
CLRS24 单源最短路径
介绍 广度优先搜索算法就是一个求取最短路径的算法，但该算法只能用于无权重的图。 在已知算法中，单结点对最短路径问题最坏情况下渐进运行时间和单源最短路径算法一样。 最短路径具有最优子结构：两个结点之间的一条最短路径包含其他的最短路径。 Dijkstra算法就是一个贪心算法，而Floyd-Warshall算法是一个动态规划算法(该算法能找出所有结点对之间的最短路径)。 如果有权重为负值的环路，则单源最短路径无定义(-INFINI...…
-
CLRS23 最小生成树
介绍 我们希望找到一个无环子集，既能够将所有的结点连接起来，又具有最小的权重。我们称这样的树为最小生成树。 本章介绍解决最小生成树问题的两种算法：Kruskal算法和Prim算法。如果使用普通的二叉堆，可以将两个算法的时间复杂度限制在O(ElgV)，使用斐波那契堆Prim算法的运行时间为O(E+VlgV)。这两种算法都是贪心算法。 23.1 最小生成树的形成 通用方法：在每遍循环之前，A是某棵最小生成树的一个子集。GENERIC-MST(G, w) A =...…
-
CLRS22 基本的图算法
介绍 本章介绍图的表示和图的搜索 图的搜索技巧是整个图算法领域的核心 22.1 图的表示 对于图G = (V, E)，有两种标准表示方法: 一种是邻接链表，另一种是邻接矩阵。分别适合稀疏图和稠密图。当图规模较小时，我们更倾向于使用邻接矩阵表示法。 对于有向图，所有邻接链表的长度和为E. 无向图为2E. 邻接链表表示法的鲁棒性很高，可以对其进行简单修改来支持许多其它的图变种。 无向图只需存储对角线及以上部分的邻接矩...…
-
CLRS21 用于不相交集合的数据结构
21.1 不相交集合的操作 一个不相交集合数据结构维护了一个不相交动态集的集合 {S1, S2, …, Sk}, 我们用一个代表来标识每个集合，它是这个集合的某个成员。 动态集合支持：MAKE-SET(x), UNION(x, y), FIND-SET(x) 用不相交集合数据结构确定无向图的连通分量 CONNECTED-COMPONENTS(G) for each vextex v in G.V MAKE-SET(v) fo...…
-
The Little Schemer
(defne lat?1 (lambda (l) (cond ((null? l) #t ) (( atom ? ( car l)) (lat? ( cdr l))) (else #f ))))(define insertR (lambda (new old lat) (cond ((null? lat) (quote ()))) else (cond ((eq? (car lat) old) ...…
-
CLRS20 van Emde Boas Tree
介绍 van Emde Boas 树支持优先队列操作以及一些其他操作，每个操作的最坏情况运行时间为O(lg lg n), 这种数据结构限制关键字必须为0~n-1的整数且无重复。 支持SEARCH, INSERT, DELETE, MINIMUM, MAXIMUM, SUCCESSOR, PREDECESSOR. 20.1 基本方法 本届讨论动态集合的几种存储方法。 直接寻址: INSERT, DELETE, MEMBER运行时间为O(1),...…
-
CLRS19 斐波那契堆
介绍 斐波那契堆支持一系列操作，这些操作构成了所谓的“可合并堆”。同时，斐波那契堆的一些操作可以在常数摊还时间内完成。操作 二叉堆(最坏情形) 斐波那契堆(摊还)MAKE-HEAP Θ(1) Θ(1)INSERT Θ(lgn) Θ(1)MINIMUM Θ(1) ...…
-
CLRS18 B树
介绍 B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。B树类似于红黑树，但他们在降低磁盘I/O操作数方面要更好一些。 一个B树的结点通常和一个完整磁盘页一样大，并且磁盘页的大小限制了一个B树结点可以含有的孩子个数。 一个分支因子为1001，高度为2的B树可以存储超过10亿个关键字。 18.1 B树的定义 B+树把所有卫星数据都存储在叶结点中，内部结点至存放关键字和孩子指针，因此最大化了内部节点的分支因子。 每个...…
-
CLRS17 摊还分析
介绍 在摊还分析中，我们求数据结构的一个操作序列中所执行的所有操作的平均时间，来评价操作的代价。它并不涉及概率，可以保证最坏情况下每个操作的平均性能。 介绍三种方法：聚合分析、核算法、势能法。 通过做摊还分析，通常可以获得对某种特定数据结构的认识，这种认识有助于优化设计。 17.1 聚合分析 利用聚合分析，我们证明对所有n，一个n个操作的序列最坏情况下花费总时间为T(n), 因此每个操作的摊还代价为T(n)/n 对任意n值，任...…
-
CLRS16 贪心算法
介绍贪心算法每一步都做出局部最优的选择，寄希望于这样的选择能得到全局最优解。贪心算法并不保证得到最优解，但对很多问题确实可以求得最优解。16.1 活动选择问题 虽然可以用动态规划方法求解活动选择问题，但并不需要这样做。相反，可以反复选择最早结束的活动，保留兼容活动，重复过程，直到不再有剩余。 贪心算法通常做出一个选择，然后求解剩下的那个子问题。 递归贪心算法：添加一个虚拟活动a0,其结束时间为f0=0方便初始化。 RECURSIVE-ACTIVITY...…
-
SICP5 Sequences and Coroutines
IntroductionIn this chapter, we introduce new constructs for working with sequential data that are designed to accommodate collections of unknown or unbounded length, while using limited memory. We also discuss how these tools can be used with a p...…
-
SICP4 Distributed and Parallel Computing
IntroductionIn this chapter, we turn to the problem of coordinating multiple computers and processors.Distributed Computing A distributed system is a network of autonomous computers that communicate with each other in order to achieve a goal....…
-
SICP3 The Structure and Interpretation of Computer Programs
Introduction It is no exaggeration to regard this as the most fundamental idea in programming, that an interpreter, which determines the meaning of expressions in a programming language, is just another program. In this chapter, we stu...…
-
CLRS15 动态规划
介绍 动态规划和分治方法相思，都是通过组合子问题的解来求解原问题。 动态规划适用于子问题重叠的情况。 动态规划通常用来求解最优化问题。15.1 钢条切割 钢条切割问题满足最优子结构：问题的最优解由相关子问题的最优解组合而成，这些子问题可以独立求解。CUT-ROD(p, n) if n == 0 return 0 q = -INFINITE for i = 1 to n q = max(q, p[i] + CUT-ROD(p, n-i))...…
-
CLRS14 数据结构的扩张
介绍经常需要通过存储额外信息的方法来扩张一种标准的数据结构，然后对这种数据结构，编写新的操作来支持所需要的应用。对数据结构的扩张并不总是简单直接的。14.1 动态顺序统计 本节介绍如何修改红黑树，使得可以在O(lgn)时间内确定任何顺序统计量。还将看到如何在O(lgn)时间内计算一个元素的秩。 红黑树每个结点饱含x.size = x.left.size + x.right.size + 1 OS-SELECT(x, i) r = x.left.size + ...…
-
CLRS13 红黑树
介绍red-black tree是许多平衡搜索树中的一种，可以保证最坏情况下基本动态集合操作的时间复杂度是O(lgn)13.1 红黑树的性质 红黑树是一棵二叉搜索树，它在每个结点上增加了一个存储位来表示结点颜色，RED或BLACK，它保证没有一条路径会比其它路径长出2倍。 一棵红黑树： 1、每个结点是红色的，或是黑色的 2、根结点是黑色的 3、每个叶结点是黑色的(NIL) 4、如果一个结点是红色的，它的两个child都是黑色的 ...…
-
CLRS12 二叉搜索树
12.1 什么是二叉搜索树 左子树关键字不大于x，右子树关键字不小于xINORDER-TREE-WALK(x) if x != NIL INORDER-TREE-WALK(x.left) print x.key INORDER-TREE-WALK(x.right) 练习12.1-1 For the set of keys {1, 4, 5, 10, 16, 17, 21}, draw binary search trees of heig...…
-
CLRS11 散列表
散列表 散列表是实现字典操作的一种有效数据结构 散列表是普通数组概念的推广 基本字典操作平均只需要O(1)时间 完全散列能在O(1)的最坏情况时间内完成关键字查找 11.1 直接寻址表(direct-address table)DIRECT-ADDRESS-SEARCH(T, k) return T[k]DIRECT-ADDRESS-INSERT(T, x) T[x.key] = xDIRECT-ADDRESS-DELETE...…
