史蒂芬の电台

动漫

1 篇文章

笔记

38 篇文章

题解

0 篇文章

2026-03-08 2k 字 9 分钟

哈夫曼树的设计与实现

什么是哈夫曼树各位了解文件压缩吗？它是怎么做到的呢？我们都会在这一节进行探讨。给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树（Huffman Tree）啥叫带权路径长度达到最小？就是树中所有的叶结点的权值乘上其到根结点根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）这里我们分别将叶子结点ABCD都赋予一个权值，我们来尝试计算一下，计算公式如下： $$WPL = \sum_{i=1}^{n} \big( value(i) \times depth(i) \big)

2026-03-06 2k 字 8 分钟

平衡二叉树的设计与实现

什么是平衡二叉树利用二叉查找树，我们在搜索某个值的时候，效率会得到巨大提升。但是虽然看起来比较完美，也是存在缺陷的，比如现在我们依次将下面的值插入到这棵二叉树中： 120 15 13 8 6 3 在插入完成后，我们会发现这棵二叉树竟然长这样：其说它是一棵二叉树，不如说就是一个链表，如果这时我们想要查找某个结点，那么实际上查找的时间并没有得到任何优化，直接就退化成线性查找了。所以，二叉查找树只有在理想情况下，查找效率才是最高的，而像这种极端情况，就性能而言几乎没有任何的提升。我们理想情况下，这样的效率是最高的：所以，我们在进行结点插入时，需要尽可能地避免这种一边倒的情况，这里就需要

2026-03-04 1.5k 字 6 分钟

二叉查找树的设计与实现

什么是二叉查找树二叉查找树本质就是通过二分搜索的方法来快速查找二叉查找树也叫二叉搜索树或是二叉排序树，它具有一定的规则：左子树中所有结点的值，均小于其根结点的值。右子树中所有结点的值，均大于其根结点的值。二叉搜索树的子树也是二叉搜索树。一棵二叉搜索树长这样：查找值为15的结点：从根结点18开始，因为15小于18，所以从左边开始找。接着来到10，发现10比15小，所以继续往右边走。来到15，成功找到。实际上，我们在对普通二叉树进行搜索时，可能需要挨个进行查看比较，而有了二叉搜索树，查找效率就大大提升了，它就像我们前面的二分搜索那样。因为二叉搜索树要求比较严格，所

2026-03-02 2.6k 字 11 分钟

线索化二叉树的设计与实现

线索化二叉树我们知道一棵二叉树实际上可以由多个结点组成，每个结点都有一个左右指针，指向其左右孩子。我们在最后也讲解了二叉树的遍历，包括前序、中序、后序以及层序遍历。只不过在遍历时实在是太麻烦了，我们需要借助栈来帮助我们完成这项遍历操作。一棵二叉树的某些结点会存在NULL的情况，我们可以利用这些为NULL的指针，将其线索化为某一种顺序遍历的指向下一个按顺序的结点的指针，这样我们在进行遍历的时候，就会很方便了。线索化的规则为：结点的左指针，指向其当前遍历顺序的前驱结点。结点的右指针，指向其当前遍历顺序的后继结点。在线索化之后，G的指向情况如下：这样，G原本两个为NULL的指针就

2026-03-01 4.3k 字 17 分钟

二叉树的设计与实现(树的开篇)

树与森林树的介绍树是一种全新的数据结构，它就像一棵树的树枝一样，不断延伸。一棵树就像下面这样连接：可以看到，现在一个结点下面可能会连接多个节点，并不断延伸，就像树枝一样，每个结点都有可能是一个分支点，延伸出多个分支，从位于最上方的结点开始不断向下，而这种数据结构，我们就称为树（Tree)，不能与其他分支上的结点相交我们一般称位于最上方的结点为树的根结点（Root）因为整棵树正是从这里开始延伸出去的。每个结点连接的子结点数目（分支的数目），我们称为结点的度（Degree），而各个结点度的最大值称为树的度。每个结点延伸下去的下一个结点都可以称为一棵子树（SubTree）比如结

2026-02-27 1.2k 字 5 分钟

队列的设计与实现

什么是队列栈中元素只能栈顶出入，它是一种特殊的线性表，同样的，队列（Queue）也是一种特殊的线性表。秉承先来后到的原则，队列中的元素只能从队尾进入，只能从队首出去，也就是说，入队顺序为1、2、3、4，那么出队顺序也一定是1、2、3、4，所以队列是一种先进先出（FIFO，First In, First Out）的数据结构。顺序表队列想要实现队列也是很简单的，也可以通过两种线性表来实现，我们先来看看使用顺序表如何实现队列，假设一开始的时候队列中有0个元素，队首和队尾一般都初始都是-1这个位置：此时有新的元素入队了，队尾向后移动一格（+1），然后在所指向位置插入新的元素：之后都

2026-02-27 1k 字 5 分钟

栈的设计与实现

什么是栈栈（Stack）是一种特殊的线性表，它只能在表尾进行插入和删除操作，就像下面这样：我们一般只在一端进行插入和删除，依次插入1，2，3，4后，如果进行删除操作，将会是4，3，2，1的顺序进行删除：底部称为栈底，顶部成为栈顶，所有操作只能在栈顶进行，先进后出，下面的元素想要进行操作需要让上面的元素先出去接着我们要来讲下栈的两个操作： pop：出栈操作，从栈顶取出一个元素。 push：入栈操作，向栈中压入一个新的元素。我们先按照顺序表(也可以用链表)来编写： 123456789typedef int E;struct Stack { E * array;

2026-02-26 1.2k 字 5 分钟

双链表和循环链表的设计与实现

什么是双向链表单链表，通过这样的链式存储，我们不用再像顺序表那样一次性申请一段连续的空间，而是只需要单独为结点申请内存空间，同时在插入和删除的速度上也比顺序表轻松。不过有一个问题就是，如果我们想要操作某一个结点，比如删除或是插入，那么由于单链表的性质，我们只能先去找到它的前驱结点，才能进行。并且双向链表从前从后都可遍历为了解决这种查找前驱结点非常麻烦的问题，我们可以让结点不仅保存指向后续结点的指针，同时也保存指向前驱结点的指针：这样我们无论在哪个结点，都能够快速找到对应的前驱结点，就很方便了，这样的链表我们成为双向链表（双链表）首先定义好结构体 123456789typedef

2026-02-25 1.8k 字 7 分钟

链表设计与实现

什么是链表链表不同于顺序表，但是得记住顺序表是随机排序，链表的空间不是连续的，而顺序表是连续的。它通过指针来连接一个个分散的节点，虽然物理上不相邻，但是在逻辑上是相邻的。顺序表他不如链表，本质还是用数组来存的链表本身分为带头结点的链表和不带头结点，戴头结点的链表就是会有一个头指向后续的整个链表，但是头结点不存放数据。而不带头结点的链表就像上面那样，第一个节点就是用来存放数据的结点，一般设计链表都会采用带头结点的结构，因为操作更加方便。那么我们先来写一个链表: 12345678typedef int E;struct ListNode { E element;

2026-02-24 2.7k 字 9 分钟

蓦然回首——藤本树致所有创作者的一份情书

蓦然回首——藤本树致所有创作者的一份情书内容藤本树，你是我的精神病人在讨论藤本树的作品前，先让我们讨论下这个精神病人吧（笑）。《电锯人公安篇》在2020年10月14日完结的时候，我才意识到藤本树是一个天才，为什么粉丝们总是说藤本树是一位“精神病人”，我想这是对藤本树的嘉奖，他的作品并没有迎合大众趋势，而是以自己所愿表达出自己所想——以超乎读者想象的方式。藤本树早期短篇作品并不出众，藤本树在《藤本树短篇集》中《预言中的那由多》的随笔中写到：“编剧总是说我画不出具有特点的角色，所以我创作了那由多。”藤本树对那由多的爱其实延续到了《电锯人》，玛奇玛死后再次重生的样子就和那由多一模一样。