Questions in category: 数据结构 (Data Structure)
计算数学 >> 数据结构
<[1] [2] [3] [4] [5] >

1. Graph 数据结构的 C++ 实现

Posted by haifeng on 2022-05-04 09:26:46 last update 2022-05-04 09:26:46 | Answers (0) | 收藏


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/

2. [实验三] 编写仅使用一个数组而实现两个栈的例程

Posted by haifeng on 2021-04-21 15:48:34 last update 2021-04-21 16:11:43 | Answers (0) | 收藏


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

要求:

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

 

 

 

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

 

3. 红黑树

Posted by haifeng on 2021-03-19 12:05:00 last update 2021-03-19 12:06:37 | Answers (0) | 收藏


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

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

 

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

 

 


References:

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

4. 伪随机数生成器

Posted by haifeng on 2020-05-29 08:43:56 last update 2020-05-29 08:43:56 | Answers (0) | 收藏


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

\[
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

5. 汉诺塔(Towers of Hanoi)问题

Posted by haifeng on 2020-04-02 07:59:04 last update 2020-04-02 08:12:28 | Answers (0) | 收藏


汉诺塔问题

汉诺塔(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++ 语言描述》 机械工业出版社

6. 关于排序算法的动画

Posted by haifeng on 2020-03-30 20:05:38 last update 2020-03-30 20:06:04 | Answers (0) | 收藏


十大经典排序算法动画,看我就够了!

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

7. 估计 $\sum_{i=\lfloor N/2\rfloor}^{N}\frac{1}{i}$

Posted by haifeng on 2020-03-10 10:04:55 last update 2020-03-10 10:06:50 | Answers (0) | 收藏


数据结构第三次作业

书本 P.30

Exer1.9

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

8. Exercise 1.4

Posted by haifeng on 2020-02-27 08:48:59 last update 2020-02-27 08:48:59 | Answers (0) | 收藏


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

 


Exercise 1.4  课本 P.29

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

9. [Ex2.8]生成前$N$个数的一个随机置换

Posted by haifeng on 2019-03-14 11:46:13 last update 2019-03-14 11:46:13 | Answers (0) | 收藏


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

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

 


References:

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


 

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

Posted by haifeng on 2018-05-17 08:28:08 last update 2018-05-17 08:35:04 | Answers (0) | 收藏


高度为 $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

<[1] [2] [3] [4] [5] >