20 岁,是学生

详解并查集(基础篇)

简介

并查集是一种树型的数据结构,用于处理一些不相交集(Disjoint Sets)的合并及查询问题。不相交集,顾名思义,就是交集为空集的一些集合。比如集合 {1,3,5} 和集合 {2,4,6} 就是不相交集。 {2,3,5} 和 {1,3,5} 就不是,因为他们的交集不是空集。该数据结构由Bernard A. Galler和Michael J. Fischer于1964年提出。

对于并查集,主要有如下操作:

  1. 合并两个集合(“并”)

  2. 判断两个元素是否属于同一个集合。(“查”)

2018-04-04 数据结构
Link

使用 C/C++ 模拟 defer 关键字

笔者在翻译完 这篇文章 以及同系列的下一篇文章(尚未发布…)后,受到了 ESR 大神的鼓舞,遂决定在寒假学习一下 Go 语言。在学习 Go 语言的过程中,觉着这语言和之前学到的 C/C++ ,Scheme 相比有着无法比较的简洁感。笔者尤其喜欢 defer 这一关键字的设计。于是就在今天尝试使用 C/C++ 模拟了下 defer 关键字。

                                                  ---- 某咸鱼的碎碎念
2018-04-01 Go
Link

详解二叉堆(基础篇)

堆(heap),又称为优先队列(priority queue)。尽管名为优先队列,但堆并不是队列。在队列中,我们可以进行的操作是向队列中添加元素和按照元素进入队列的选后顺序取出元素。而在堆中,我们不是按照元素进入队列的先后顺序,而是按照元素的优先级取出元素。

Linux 内核中的调度器会根据各个进程的优先级对程序的执行进行调度。在操作系统运行时,通常会有很多个不同的进程,优先级各不相同。在调度器的作用下,优先级高的进程被有限执行,优先级靠后的就只能等待。堆是实现这种调度器的一种很合适的数据结构(顺便提一下,现在的 Linux 内核的调度器使用的是基于红黑树的 CFS ,笔者以后会专门介绍)。

2018-03-29 数据结构
Link

详解 AVL 树(基础篇)

AVL 树是一种平衡二叉搜索树,得名于其发明者的名字( Adelson-Velskii 以及 Landis)。(可见名字长的好处,命名都能多占一个字母出来)。其递归定义如下:

  1. 左右子树的高度差小于等于 1。

  2. 其每一个子树均为 AVL 树。

基于这一句话,我们就可以进行判断其一棵树是否为二叉树了。

练习

2018-03-24 数据结构
Link

详解二叉树(基础与BST)

二叉树是一种树。这个树的每个节点都有不超过两个节点的孩子。我们通常将二叉树倒画,即将其根画在顶部,叶子画在最底部。一颗典型的二叉树表示如下:

现在给出二叉树的正式递归定义:

A binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.

二叉树要么是一颗空树(使用一个 NULL 指针表示),要么左右孩子都指向一颗二叉树。

2018-03-22 数据结构
Link

详解 C 语言链表(应用篇) -- 浅析 Linux kernel 中的 list.h 头文件(二)


注: 本文分析的为文章发布时最新的 Linux 内核源码。


2018-03-17 C
Link

详解 C 语言链表(应用篇) -- 浅析 Linux kernel 中的 list.h 头文件(一)

中国人有一句老话:“不入虎穴,焉得虎子。”这句话对于人们的实践是真理,对于认识论也是真理。离开实践的认识是不可能的。

                                             ---- 毛主席 《实践论》

计算机学科是一门实践性比较强的学科。这就意味着,搞计算机需要进行足够的实践。而回头看历史,计算机多年来的发展历程也是如此。人们从实践中发现理论,理论再指导新一轮的实践,循环往复,最终推动了技术的发展。

在前两篇文章中,我们讲述了基础的链表的实现方式。又留下了几个很有启发意义的习题,在本篇文章里面,我们来看简要地一下链表这一数据结构在 Linux 内核中的实际应用。

2018-03-17 C
Link

详解 C 语言链表(实践篇)

基础篇中,笔者介绍了一些链表的基本操作。在本文中,笔者整理了几个有关链表的问题供大家练习。练习的难度是递增的。前几道非常简单,后面就会愈加困难。答案会附在题目的后面。

注意:仅仅用眼睛看答案不会提升自己的水平,只有自己亲手实现,才算真正的学到了知识。在看答案之前,无论你自己有没有成功实现,都请务必确保你真的认真思考了。

优秀的程序员应该是能够将数据结构可视化的,因此他们能够很好的理解代码运行时内存的变化。链表的规整使得它很适合拿来做基本的可视化训练。在解决下面这些问题时,你可以尝试在纸上画出链表的结构进行模拟,最终使用代码将之表达起来。

2018-03-16 C
Link

详解 C 语言链表(基础篇)

链表基础

复习:数组

链表和数组的作用相同。都是用来存储数据。因此,使用数组和链表进行类比是一个不错的选择。

数组是很常用的数据结构。在多数语言中,我们都可以很容易的声明一个数组类型,并使用 [] 符号取出其中的元素。 C 语言的示例如下:

1
2
3
4
5
6
7
8
void ArrayTest(void) {
int fuc[100]; // 定义数组

// 数组操作
fuc[0] = 1;

printf("%d\n",fuc[0]);
}
2018-03-14 C
Link

NES 图像技术导引

介绍

红白机是一种价格亲民,功能强大的游戏设备,自 1983 年发行以来就造成了不小的轰动。通过使用定制设计的 PPU(Picture Processing Unit,图像处理单元)生成图像,红白机可以生成在当时给人们留下深刻印象的画面 —— 这些画面 就是在现在也不过时。但是,红白机最优秀的地方不只是图像的质量,还有就是它生成图像时对于内存的精简使用,它尽可能地使用较少的内存来生成画面。在如此节省内存的同时,任天堂却还为游戏的开发人员提供了大量强大易用的功能,这些功能使得红白机在同时代的古董游戏机中脱颖而出,成为一代经典。了解红白机使用的图像生成技术可以让我们了解并欣赏那个时代的程序员让人敬佩的技术实力,以及与现代游戏制作者打造精美图像时仅仅需要一些简单的操作即可的事实进行对比。

2018-03-01 NES
Link