Graph 数据结构的 C++ 实现

Graphs in Data structure (using C++) | Engineering Education (EngEd) Program | Section

https://www.section.io/engineering-education/graphs-in-data-structure-using-cplusplus/

编写仅使用一个数组而实现两个栈的例程

要求:

除非数组的每一个单元都被使用, 否则栈例程不能有溢出声明.

如何使用一个数组实现三个栈?

定义: 红黑树(Red Black Tree) 是一种具有下列着色规则的二叉查找树:

1. 每一个结点或者是红色, 或者是黑色. (可以 标记为 0 和 1)
2. 根结点是黑色的.
3. 红色结点如果有儿子, 那么它的子结点必须是黑色的.
4. 从任何一个结点到一个 NULL 指针的每一条路径都必须包含相同数目的黑色结点.

证明: 结点数为 $N$ 的红黑树的高度至多是 $2\log(N+1)$. 

References:

Mark Allen Weiss 著, 张怀勇 等译 《数据结构与算法分析(C++描述)》（第3版）,  人民邮电出版社.

许多库中的随机数生成器基于函数

\[
x_{i+1}\equiv (Ax_i+C)\mod (2^B-1)
\]

如果令 $A=48271$, $C=1$, $B=31$, 则有

\[
(48271\times 179424105+1)\mod (2^{31}-1)=179424105
\]

可以是用 Calculator 验证:

>> (48271*179424105+1)mod(2^31-1)
in> (48271*179424105+1)@(2^31-1)

out> 179424105

这说明, 如果种子(即初值) $x_0=179424105$, 则生成器将陷入周期为 1 的循环.

References:

Mark Allen Weiss 著, 张怀勇 等译《数据结构与算法分析C++描述》(第3版). P.333

汉诺塔问题

汉诺塔(Towers of Hanoi)问题来自大梵天创世的一个古老传说。在创世之日，有一座钻石宝塔（塔1），其上有64个金碟，所有碟子从大到小从塔底堆到塔顶，旁边还有另外两座钻石宝塔（塔2和塔3）。从创世之日起，婆罗门一直试图把塔1上的碟子移到塔2上去，不过要借助塔3。由于碟子非常重，所以一次只能移动一个碟子。另外，任何时候大碟子都不能压在小碟子上面。根据这个传说，等到婆罗门把盘子搬完了，世界末日也就到了。

/*
* 设塔 x 有 n 个碟子
*
*         -|-         |           |
*       --|--        |           |
*     ---|---       |           |
*   ----|----      |           |
* -----|-----     |           |
*        x           y           z
*
*
* Idea: 为了把最大的碟子移到塔 y 的底部, 必须把其余 n-1 个碟子移到塔 z
*       然后把最大的碟子移到塔 y. 接下来把塔 z 上的 n-1 个碟子移到塔 y.
*/

Reference:

Sartaj Sahni, Data Structures, Algorithms, and Applications in C++, Second Edition.
[美] 萨特吉.萨尼 著，王立柱、刘志红 译 《数据结构、算法和应用 C++ 语言描述》 机械工业出版社

十大经典排序算法动画，看我就够了！

https://cloud.tencent.com/developer/article/1377642

数据结构第三次作业

书本 P.30

Exer1.9

估计 \[\sum_{i=\lfloor N/2\rfloor}^{N}\frac{1}{i}\]

1.4  C++ 提供形如 #include filename 的语句, 它将 filename 读入并将其插入到 include 语句处. include 语句可以嵌套; 换句话说, 文件 filename 本身还可以包含 include 语句, 但是显然一个文件在任何链接中都不能包含它自己. 编写一个程序, 来读入一个文件, 并输出该文件被 include 语句修改后的内容.

Exercise 1.4  课本 P.29

课本: Mark Allen Weiss 著, 张怀勇 等译, 《数据结构与算法分析C++描述》（第3版） 

假设需要生成前 $N$ 个自然数的一个随机置换. 例如 $\{4,3,1,5,2\}$ 和 $\{3,1,4,5,2\}$ 是合法的置换, 但是$\{5,4,1,2,1\}$ 就不是置换.

这个程序通常用来模拟一些算法.

References:

Mark Allen Weiss 著 《数据结构与算法分析 C++ 描述》（第3版），张怀勇 等译.

高度为 $h$ 的 AVL 树, 其最少的结点数是多少?

[Hint]

高度为 $h$ 的 AVL 树, 其最少的结点数若记 $S(h)$, 则 $S(h)$ 有三部分组成: 1（根结点）, 左子树的最少结点数, 右子树的最少结点数.

由于 AVL 树的平衡条件是: 任意结点的左子树与右子树的高度之差的绝对值至多为 1. 因此如果左子树的最少结点数是 $S(h-1)$, 则右子树的最少结点数是 $S(h-2)$.

于是, 我们得到关于 $S(h)$ 的递推表达式:

\[
S(h)=S(h-1)+S(h-2)+1.
\]

这与 Fibonacci 的递推表达式非常类似, 仅相差一个常数 1.

试求出 $S(h)$ 的具体表达式.

P. 132  Ex 4.18