>> hex2decimal(0x7ffc000000000000)
out> 9222246136947933184

>> decimal2binary(9222246136947933184)
out> 111111111111100000000000000000000000000000000000000000000000000

------------------------

0111,1111,1111,1100;00000000,00000000;00000000,00000000;00000000,00000000

定义符号位 SIGN_BIT 为64位无符号整数0x8000000000000000

#define SIGN_BIT ((uint64_t)0x8000000000000000)

#define QNAN     ((uint64_t)0x7ffc000000000000)

定义 QNAN 是64位无符号整数

判断是否是数

#define IS_NUMBER(value)    (((value) & QNAN) != QNAN)

即凡是不以0x7ffc开头的都不是NUBMER,  以0x7ffc开头的都是obj

//     QNAN=0x7ffc000000000000
//TAG_FALSE=0x0000000000000010
// TAG_TRUE=0x0000000000000011
//FALSE_VAL=0x7ffc000000000010
// TRUE_VAL=0x7ffc000000000011

(SIGN_BIT | QNAN)

1111,1111,1111,1100;00000000,00000000;00000000,00000000;00000000,00000000

取反

0000,0000,0000,0011;11111111,11111111,11111111,11111111,11111111,11111111

#define AS_OBJ(value) \
    ((Obj*)(uintptr_t)((value) & ~(SIGN_BIT | QNAN)))

AS_OBJ() 函数就是将 value 和上面的值  0x3ffffffffffff 作与运算

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版），张怀勇 等译.