xiaogang1014

摘要： C++的函数重载意味着函数名和返回值类型相同，但是参数个数和/或类型不同。在编译过程中编译器一般会把各个参数的类型连接到函数名内组成新的函数名，以区分各个重载函数。 C语言不支持函数重载。但是有时候虽然实参和形参个数不同，编译和连接都能通过，甚至没有告警。这可能会给后续的运行带来严重和难以调试的问题 阅读全文

摘要： 18.1 B树的定义 18.2 B树的基本操作 与一棵二叉搜索树一样，可以在从树根到叶子这个单程向下过程中将一个新的关键字插入B树中。为了做到这一点，当沿着树向下查找新的关键字所属位置时，就分裂沿途遇到的每个满结点（包括叶节点本身）。如分裂一个满的根，首先要让根成为一个新的空根结点的孩子。树的高度因 阅读全文

摘要： 17.1 聚合分析 用来确定一个n个操作的序列的总代价的上界T(n). 由n个push，pop，multi-pop组成的操作序列。依赖于push 二进制计数器递增 A[0]每次都翻转，A[1]每两次翻转一次，A[2]每两次翻转一次... 17.2 核算法 较早操作的余额（overcharge）作为预 阅读全文

摘要： 通常用于最优化问题，我们做出一组选择来达到最优解。每步都追求局部最优。对很多问题都能求得最优解，而且速度比动态规划方法快得多。 16.1 活动选择问题 按结束时间排序，然后选择兼容活动。 定理16.1 考虑任意非空子问题Sk，令am是Sk中结束时间最早的活动，则am在Sk的某个最大兼容活动子集中。 阅读全文

摘要： 通常用来解决最优化问题。在做出每个选择的同时，通常会生成与原问题形式相同的子问题。当多于一个选择子集都生成相同的子问题时，动态规划技术通常就会非常有效。其关键技术就是对每个这样的子问题都保存其解，当其重复出现时即可避免重复求解。 分治：划分为互不相交的子问题，递归求解子问题，再将他们的解组合起来。 阅读全文

摘要： gcc -g 如果不打开-g或者-ggdb(GDB专用)调试开关，GCC编译时不会加入调试信息，因为这会增大生成代码的体积。GCC采用了分级调试，通过在-g选项后附加数字1、2或3来指定在代码中加入调试信息量。 级别1（-g1）不包含局部变量和与行号有关的调试信息，只能用于回溯跟踪和堆栈转储之用。[ 阅读全文

摘要： 第十二章 二叉搜索树 >=左子树的所有key，<=右子树的所有key 在一棵高度为h的二叉搜索树上，动态集合上的操作SEARCH,MINIMUM,MAXIMUM,SUCCESSOR,PREDECESSOR,INSERT和DELETE可以在O(h)时间内完成。 h>=（lgn向下取整） 和快速排序算法 阅读全文

摘要： 第十章 基本数据结构 栈：可由数组表示 队列：可由数组表示 指针和对象：可由多数组表示。可用栈表示free list 有根数： 二叉树：左右孩子 分支无限制：左孩子右兄弟表示法 第十一章 散列表 数组：为每个元素保留一个位置 散列表：用于实际存储关键字比全部可能关键字少很多时，比如字典操作 解决散列 阅读全文

摘要： 9.1 最小值和最大值 同时求最小值和最大值，总的比较次数至多为3*[n/2]。只要成对处理数据即可。 9.2 期望为线性时间的选择算法 使用分治算法和快速算法用到的随机选择pivot。假设数据都不相同。 RANDOMIZED-SELECT(A, p, r, i) //从数组A的下标段p到r找第i大 阅读全文

摘要： 第六章 堆排序 最小堆和最大堆：近似的完全二叉树 A[parent(i)]<=A[i]或者A[parent(i)]>=A[i] 建堆复杂度O(n) 排序O(nlgn) 实际应用中，快速排序一般优于堆排序。可用于优先队列等。 在一个包含n个元素的堆中，所有优先队列的操作均可在O(lgn)时间内完成。 阅读全文