Posts

最近一直在学习 Rust 语言，深感它的学习曲线很陡峭，因此会写几篇博客记录一下学习进度。 本文主要参考了 Rust Course 和 Rust 标准库文档。 什么是迭代器 迭代器（iterator），是确使用户可在容器对象（container，例如链表或数组）上遍访的对象，设计人员使用此接口无需关心容器对象的内存分配的实现细节。 ...

华科宿舍的大门门禁用学生卡开，而每个寝室的门却只能使用钥匙打开。这就导致了每次出门都要带上学生卡和钥匙，每次回来都要先掏出卡，再掏出钥匙。这样实在是麻烦，因此我有了用校园卡就能打开宿舍门的想法。 ...

最近对脚本语言 Lua 很感兴趣，其一是因为它可以很方便地调用 C 语言库，其二是因为它是很多现代化工具的配置语言（比如 NeoVim ），另外 Lua 的源代码不是很长，因此研究学习难度会比其他语言更低。 ...

最近翻看了一下 《Vim使用技巧》 这本书，然后就发现我对 Vim 快捷键的了解很不深入。不过即使如此，我日常使用 Vim 写代码的效率也高于使用其他编辑器了，足见 Vim 模式之奇。 ...

之前使用git基本只是把它当作提交到 GitHub 上的工具，最多使用到的功能就是恢复误删的文件而已。 在我之前的git命令使用之中，基本上用的就是git clone、git add .、git commit -m以及git commit push。由于基本上是无脑add，因此.gitigore的文件书写比较重要。 ...

最近本来在看 CSAPP 后面的内容，但突然发现自己前面可能还有一些知识掌握不完全，因此做一下 Lab 检验一下。 准备工作 在 CSAPP 的官网上找到 Lab，下载 Self-Study Handout。 在下载目录下解压文件 tar -xf datalab-handout.tar 尝试执行自动测评脚本driver.pl结果发现没有32位环境，于是用dnf安装需要的库，折腾了一会发现还是不太行。请教了大佬 jyi2ya，他告诉我可以直接在makefile里面把编译条件改为-m64。 题目与题解 int 部分 bitXor 只用~和&实现^ ...

联创 Lab 组新人任务第一弹。 关于斐波那契堆 结构与特点 斐波那契堆是由一组最小堆有序树构成的。每个节点的度数为其子节点的数目。树的度数为其根节点的度数。 斐波那契堆中的树都是有根的但是无序。每个节点x包含指向父节点的指针p[x]和指向任意一个子结点的child[x]。x的所有子节点都用双向循环链表链接起来，叫做x的子链表。子链表中的每一个节点y都有指向它的左兄弟的left[y]和右兄弟的right[y]。如果节点y是x仅有的子节点，则left[y]=right[y]=y。 斐波那契堆中所有树的根节点也用一个双向循环链表链接起来。 使用一个指针指向斐波那契堆中最小元素。 斐波那契堆将操作尽可能地延后，它的插入是懒惰的，只有在不得不进行合并操作时才进行合并。在极端情况下，它甚至是一个长度很大的链表。 插入操作 将一个节点直接插入到根链表中，并比较键值的大小，如果新节点的键值小于原有节点的键值，就将斐波那契堆的指向最小节点的指针指向它。 ...

联创 Lab 组新人任务第一弹。 关于LLRB 定义 根节点是黑色的。 红色节点的儿子一定是黑色的。 任意节点到任意叶子的最短路径上都有相同数量的黑色节点。 黑色节点的儿子要么全是黑色，要么只有左儿子是黑色。 前三点与红黑树的性质相同，第四点为左偏红黑树的特殊性质，这导致了它的操作相对红黑树更加简单。 左偏红黑树也可以认为其相邻节点的边是有颜色的。 空节点的颜色认为是黑色。 插入操作 可以先就像向二叉查找树中插入节点一样操作，插入时将其颜色赋为红色。如果插入时是黑色，这会导致破坏了LLRB的平衡性质。 保持住了黑色平衡性质之后再来调整其他结构性质，要对连续两个红色节点、只有右儿子是红色节点进行旋转，对左右儿子都是红色的节点进行颜色翻转（拆分2-3-4树中的4-node）。 其操作可以是递归的，编写代码也将更加容易实现。 优先保持平衡性质的原因有：在一开始插入时保持平衡性质最容易实现（只需要给新节点赋红色），此时若优先考虑其他性质，会导致需要考虑的情况过多，而且在后续进行修补（旋转、颜色翻转）的时候不会破坏其平衡性质。 删除操作 依然优先考虑其平衡性质，删除的节点需要是红色的，因此思路就是先将需要删除的节点变成红色的。 此时需要考虑的是，如何将红色节点向下移动（向左下或右下）。当左右儿子都不是红色时也不用担心，可以通过颜色翻转实现，翻转后需要考虑移动的另一个方向是否会出现不满足左倾红黑树的情况，并对其进行修补。 由于LLRB的左偏特性，因此会出现想要向右下移动时，左儿子是红色而右儿子是黑色，因此需要对该节点进行右旋，让向右下的路径上出现红色。 当找到删除的目标节点后，如果是一个叶子节点，直接删去，如果是一个内部节点，便从它的右儿子的分支中找到最小节点与之替换，再删掉。 在向上返回的途中修补节点。 4 中判断是否为叶子节点不应该用它是否有左儿子来判断，而是用它是否有右儿子来判断，因为在前一步中有右旋操作。 ...