2019年

用 Graphviz 绘制一棵漂亮的二叉树

起因

之前用 Rust 写了一个 AVL 树的实现,就很自然的想把树用可视化的图像画出来,在一波搜索过后,最后都指向了一位叫 Emden GansnerGraphviz 主要贡献者之一) 的大佬在 2010 年写的一段脚本,原作者是在邮件列表(链接1链接2)中回复别人的问题时提供的这段脚本,由于这个邮件列表原来的存档网站已经无法访问,现在能搜到的基本上都是别人对这段脚本引用,比如: stackoverflow

不过这个 gvpr 我实在是看不懂,所以我希望能够直接使用 dot 来绘制二叉树,这样在生成图像的时候就只需要使用 dot 命令行工具而不需要额外的脚本了。

尝试

但是事情看起来并没有那么简单,假如我们现在有一个文件 tree.dot

digraph G {
    node [shape=circle]
    edge [arrowhead=vee]
    8 -> 4
    4 -> 2
    2 -> 1
    2 -> 3
    4 -> 6
    6 -> 5
    6 -> 7
    8 -> 10
    10 -> 9
    10 -> 12
    12 -> 11
}

- 阅读剩余部分 -

用 Rust 实现一个 AVL 树

什么是 AVL 树以及 AVL 树的一些原理就不介绍了,我们直接讲如何用 Rust 来实现它。

结构体及 trait 定义

参考一般 AVL 树的实现,我定义了一个结构体 TreeNode 以及一个类型别名 AvlTreeNode

pub type AvlTreeNode<T> = Option<Box<TreeNode<T>>>;

#[derive(Clone, Debug)]
pub struct TreeNode<T: PartialOrd> {
    val: T,
    height: i32,
    left: AvlTreeNode<T>,
    right: AvlTreeNode<T>,
}

使用类型别名可以了少打几个字母以及好看一点。

还定义了一个 trait AvlTree

pub trait AvlTree<T: PartialOrd> {
    fn new(val: T) -> Self;
    fn height(&self) -> i32;
    fn insert(&mut self, val: T);
    fn delete(&mut self, val: T) -> Self;
}

- 阅读剩余部分 -

在 Arch Linux 下为 Windows 编译 Rust 程序

假设已经安装了 Rust 的工具链。

添加 x86_64-pc-windows-gnu target:

rustup target add x86_64-pc-windows-gnu

安装 mingw-w64 工具链:

pacman -S mingw-w64-crt mingw-w64-binutils mingw-w64-winpthreads mingw-w64-headers mingw-w64-gcc

设置链接器

~/.cargo/config 中加入以下内容:

[target.x86_64-pc-windows-gnu]
linker = "x86_64-w64-mingw32-gcc"

[target.i686-pc-windows-gnu]
linker = "i686-w64-mingw32-gcc"

- 阅读剩余部分 -

使用 svn 检出 GitHub 项目中的子目录

例如我们想检出 https://github.com/openwrt/packages 项目下的 net/nginx 子目录,但是不想把整个项目克隆下来。

可以利用 svn 来实现, svn 支持 --depth 选项,具体有 empty/files/immediates/infinity 四种参数,含义如下:

      depth-empty ------>  Updates will not pull in any files or
                           subdirectories not already present.
   
      depth-files ------>  Updates will pull in any files not already
                           present, but not subdirectories.
   
      depth-immediates ->  Updates will pull in any files or
                           subdirectories not already present; those
                           subdirectories' this_dir entries will
                           have depth-empty.
   
      depth-infinity --->  Updates will pull in any files or
                           subdirectories not already present; those
                           subdirectories' this_dir entries will
                           have depth-infinity.  Equivalent to
                           today's default update behavior.

1) 检出项目

svn co --depth=empty https://github.com/openwrt/packages/trunk packages

- 阅读剩余部分 -

循环冗余校验(CRC)算法入门

CRC 算法原理

CRC 算法的基本原理是将数据看作一个大数,与一个预定义的除数使用特殊的除法相除,所得的余数即为数据的 CRC 校验值。

生成多项式

算法的数学原理与多项式相关,用到的除法也基于多项式除法,预定义的除数也叫“生成多项式”,这里的多项式都是只有一个未知数并且各项系数只能是 0 或 1 的多项式(更多的信息可以参考维基百科:有限域算术,这里不多讲)。

我们以 CRC-4/ITU 为例,其生成多项式是 $x^4 + x + 1$,也即:

$$1x^4 + 0x^3 + 0x^2 + 1x^1 + 1x^0$$

如果我们令 $x = 2$,则多项式中每一项的系数可以看作一个二进制数的对应位,即 $(10011)_2$,是一个 5 位的二进制数,那么用它来做除数,最后可以得到 4 位的余数,也就是 CRC-4/ITU 中的 4。由此可见,生成多项式的首位必然是 1,在一般表示生成多项式的时候我们都省略最高位,再写成十六进制就是 0x03

模二多项式除法

我们先看多项式乘法:

$$ (x^4 + x^1 + x^0) \times (x^4 + x^3 + x^0) = x^8 + x^7 + x^4 + x^5 + x^4 + x^1 + x^4 + x^3 + x^0 $$

这里我们没有合并同类项,如果按照常规的方式合并同类项,即

$$ x^8 + x^7 + x^5 + 3x^4 + x^3 + x^1 + x^0 $$

那就是普通的多项式乘法;对于 CRC 算法,加减法采用模二运算,也就是最后的系数除以 2 取余数,不产生进位,所以最后的结果是:

$$ x^8 + x^7 + x^5 + x^4 + x^3 + x^1 + x^0 $$

- 阅读剩余部分 -