二零拾肆

我们之前已经接触过了二叉树的递归遍历和非递归遍历。 但是发现无论是哪种遍历方式，都离不开创建一个栈。 那么…有没有不需要栈的遍历方式？ 当然有，只是比较麻烦——这次我们来聊聊线索二叉树。 引 我们知道，对于任何一棵二叉树，总是会有很多指向NULL的空指针域。经过简单的推理计算就可以得出：一棵拥有n个结点的二叉树，会有n+1个空指针域。 这些空指针域，白白放着也是浪费，为什么不把它们利用起来，让它们按照遍历次序指向下一个结点？ 这样一来，对于各种不同的遍历方式，我们可以将空指针域指向不同的方向，从而构造出各种二叉树。一般来说，我们将左空指针指向当前结点的上一个结点（也称为前驱结点）；将右空指针指向当前结点的下一个结点（也称为后继结点）。我们将这些符合定义的树统称为线索二叉树（Threaded BinaryTree）。 图片源于百度百科 线索二叉树 由于线索二叉树针对不同的遍历方式有不同的结构，我无法一一列举出来介绍，这次我就先介绍一下较为典型的中序线索二叉树。 中序线索二叉树 基本结点 虽然线索二叉树也是一棵二叉树，但它的结点结构还是与普通的二叉树有些许差别的。 想象一下 ...

上一周我们已经实现了一棵自己的二叉树。 我们知道，对于我们学过的数据结构，不论链表或是矩阵，都有其独特的遍历方式，以方便我们在其中处理数据。 那二叉树有没有呢？当然有，而且有三种主要的遍历方式。 我们这次就来聊聊二叉树的前序遍历、中序遍历和后序遍历。 遍历 所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。 对于二叉树的每个结点元素，我们可以将其本身记为N（Node），左子树与右子树分别记为L与R。 这样一来，对于每个结点我们就有六种遍历方式：NLR，LNR，LRN，NRL，RNL，RLN（其实就是对这三个字母的全排列）。我们可以将这六种分为三类：先遍历N的（NLR和NRL）、在中间遍历N的（LNR和RNL）与最后遍历N的（LRN和RLN），对于每类中的两种，其实只是L与R次序的问题，所以我们一般只考虑先L后R（反正反过来也是同样的原理）。 以上，我们便可以得出三种最典型的遍历方式：前序遍历(NLR) 、中序遍历(LNR) 与后 ...

这次我们终于摆脱了丑陋的黑框框控制台，进入了Windows图形界面编程的时代。 先从一个比较简单的程序入手吧！ ——高仿MSPaint画板程序 前期准备 实验要求 2.4 构造属于你的专属画图程序，可参考系统自带的绘图板； 需求分析 对于画图程序，自然少不了一个交互界面。所以从前熟悉的命令台窗口就发挥不了用处了，我们需要踏入一块新的领域——窗体应用。 对于一个最基础的画板来说，我们需要实现： 图片的打开 图片的保存 简单的画笔工具 简单的橡皮工具 清屏功能 额外可以实现的功能： 直线工具 椭圆形工具 矩形工具 更改画笔颜色 更改画笔粗细 话不多说，直接进入正题。 实验环境 虽然Visual Studio和VS Code都可以用来编写C#程序，但由于微软的Visual Studio提供了图形化界面，使得我们可以更轻易地绘制窗体，所以本次实验我们选用VS2019来进行操作。 在实验开始之前，先创建一个新项目，并选择Windows窗体应用(.NET Framework) ，点击创建。 实验过程 控件选择 对于画板的主题，由于要进行图片的显示与修改，我们选择Picture ...

结束了表结构的学习，我们终于迎来了二叉树。 这一次，我们从零开始，介绍一下树与二叉树的基本概念。 废话不多说，直接进入正题…… 树 在聊二叉树之前，我们要先聊一聊树结构。 基本概念 树结构，顾名思义，就是像树一般拥有层级的结构。看一看左边的文章目录（手机端可能看不到），这就是一种树结构；家族的族谱也是一种树结构。构造树结构，能让数据更富有层次性，在一些后续的算法中，也会频繁地用到树，可以说，树是一种特别重要的数据结构。 基本名词 对于我们来说，树是一种全新的数据结构。所以有一些名词需要先了解一下。 结点：树中的每一个元素。包含数据和指向其他结点的指针。 根结点：树中第一层的结点，图中为结点A。 子结点：某一结点的指针指向的结点。 父结点：指向某一结点的结点。 兄弟结点：与该结点拥有同一个父结点的结点。 结点的度：该结点拥有的子结点的个数。 叶结点：度=0的结点。 结点的层：根节点为第1层，第k层结点的子结点为k+1层。 树的深度(depth)：max(结点的层) 掌握了这些，我们就可以进入二叉树的学习了。 二叉树 二叉树，顾名思义，就是每个结点最多有两个子结点的树。换言 ...

本来这个栏目是专门记录我的课堂笔记的，但我课余时间一不小心又接触了一些课外的算法，不记下来吧，就怕忘掉；记下来，又不知道该放在哪个栏目。 最后决定跟这个学期的课堂笔记放在一起，当作一个额外的番外篇。 就专门记录一些零零散散的小算法吧！ 幂 求幂，是一个从刚开始接触编程就会学习的算法。在日常生活中也经常会用到。 然而，一开始我们只会接触到最基础的求幂算法：求x^n，便是进行n次循环，然后一次次乘以x。 1234567int power(int x, int n){ int ans = 1; for (int i = 0; i < n; i++) ans *= x; return ans;} 这个算法，说起来好像没有一点问题。写起来简单，理解起来也简单，就是运行的时候有点低效…… 为了不让我们的代码跑到猴年马月，我们引入了快速幂。 快速幂 设想一下，让你计算3^4，你会怎么算？ 是3*3=9；9*3=27；27*3=81这样的一次次算…… 还是3*3=9；9*9=81呢？ 想必大多数人都是用后者吧。 既然知道了34=(32)* ...

对于一把键盘来说，最重要的应该就是键轴了，它可以称得上是键盘的躯干，机械键盘独特的手感便来自于键轴。 江湖上广为流传的"黑轴适合打游戏，红轴适合文字工作"，我觉得并不恰当。 键轴的选择， 取决于你自己…… 基本概念 键轴（Switch），就是当你取下键帽后看到的那一个个小机关，也称为机械开关，通过手指的按压，实现通路，从而产生电信号。而这小小的机关中的弹簧与柱体，很大程度上影响了机械键盘的手感。 键轴主要分成两大类：段落轴与线性轴。 段落轴 顾名思义，段落轴就是有段落手感的轴。一般分为两段，按起来就像按圆珠笔的笔端一样。一部分人将其视为机械键盘的灵魂所在。 线性轴 没有段落手感，直上直下，干净利落。大概就像自动铅笔的笔端一样，只不过还要流畅一些。 两种轴体没有优劣之分，不过段落轴敲击起来更有节奏感，线性轴敲起来更加顺滑。两种轴体间的选择因人而异，如果实在不知道要选择什么，可以买一个试轴器来试一试手感。 其他概念 对于一个轴体的数据化评判，我们一般会引入以下参数： 触发行程：就是你按下去多深才会触发这个按键。 触底行程（也称总行程）：就是最深可以按 ...

这是表结构部分的最后一篇文章，我们来聊一聊稀疏矩阵的压缩方法以及快速转置。 这部分需要一点线性代数的知识，如果没学过线性代数的话可以先跳过这部分，等学习完线性代数再回来阅读~ 矩阵 在编程语言中，矩阵其实可以看作一个二维数组，比如python的numpy中的矩阵，可以和二维数组自由地进行转换。 在C++中，我们虽然没有集成好的numpy库，但我们也可以自己实现一个矩阵。 123456vector<vector<int>> matrix({ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 8, 5, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {3, 0, 9, 0, 2, 0, 0, 0, 0, 0} ...

当老师讲到字符串的时候，必然会介绍字符串的匹配算法，我的老师也是。 但同我的老师一样，大多老师都只会介绍Brute-Force算法（暴力算法），需要O(nm)的时间复杂度。 然而，真的就没有更好的算法了吗？ 那必然不可能。我们这次就来聊聊这个精妙的字符串匹配算法——KMP算法。 串 想必能点开这篇笔记的朋友都对串很熟悉了吧… 如果不熟悉的话建议以后再回过头来看，KMP较难理解，不适合初学者。 串匹配 问题描述 给出一个主串（str）与一个模式串（pattern），编写一段程序找出模式串在主串中第一次出现的位置，若未能找到，返回-1。 例：主串为"aaaaa123333451234hhahan"，模式串为"1234"。观察到主串的第14位开始能与模式串匹配：“aaaaa123333451234hhahan”，返回13（数组下标从0开始，所以13对应第14位）。 问题分析（Brute-Force） 很显然，以一般人的思维都能想到，让程序像人脑一样进行逐位对比。先将模式串与主串对齐： 发现匹配失败，便将模式串后移，继续匹配： 很显然， ...

近几年，机械键盘不知怎么就登上了一系列外设中"鄙视链"的顶端，身边总有人想着买新的机械键盘。 正好，我对它也算略有了解。 我们这次来聊聊这一充满美感的工艺品——机械键盘。 机械键盘 单论发展历史来说，机械键盘算得上是老古董了。早在键盘出现的早期就诞生了机械键盘，经历了一段时间的繁盛后，由于物美价廉的薄膜键盘的出现，跌入了一段时间的低谷。然而，在近几年，不知是被潮流所引导，还是由于用户越来越追求极致的体验，机械键盘又逐渐火爆起来。 与薄膜键盘主要依靠电路不同，影响机械键盘好坏的部分主要在于机械元件。优秀的做工与设计使得这些机械元件变得十分昂贵，也决定了机械键盘昂贵的价格。 同时，比起薄膜键盘，机械键盘最大的特点大概就是更多键位的无冲（同时触发无冲突）了。薄膜键盘大多只能做到两三个键的无冲，而有的机械键盘甚至能做到全键无冲。 一把完整的机械键盘主要由：键盘、键轴、卫星轴/平衡杆、PCB板、外壳、（定位板）几个部分组成。可能看到这些名词你会一头雾水，没事，接下来我会尽量逐个介绍。这几个部分，都有不同厂家不同工艺的区别，一般来说：做得越好，价格也越贵。想要获得极致的体验 ...

这次聊一个比较有意思的算法，能够处理算术表达式的计算。 理解起来倒不是太难，只是不同于往常的思维方式，较为抽象。 做好准备，我们就开始吧。 算术表达式求值算法 问题描述 给定一行仅包含加减乘除括号与数字的表达式，求出结果。 如：输入(33+2)*2-4/2，输出68。 问题分析 第一眼看起来，好像也没什么难的，不就是python3中一句"print(eval(input()))"就能搞定的事情么。 但多想一想，好像又不太对？ 如果按顺序计算：33+2=35；35*2=70；70-4/2……要怎么才能让计算机知道需要先算4/2=2再计算70-2呢…… 就算把符号优先级告诉计算机，计算机也不一定懂分析啊…… 既然如此，不如直接把算式按计算顺序重排好了再交给计算机计算，由我们来完成分析优先级的部分。 要实现优先级的重排，我们要先引入一个概念： 逆波兰表达式 逆波兰表达式又叫做后缀表达式，是一种没有括号，并严格遵循“从左到右”运算的后缀式表达方法。 比如： 1 * 2 + ( 3 - 4 / 5 ) * 6，写作逆波兰表达式就变成了： 1 2 * 3 4 5 ...