Name1e5s

故事要从今天中午一位同学提到了这个问题开始……

简介

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

对于并查集，主要有如下操作：

1. 合并两个集合（“并”）

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

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

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

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

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

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

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

练习

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

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

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 指针表示），要么左右孩子都指向一颗二叉树。

• 基础篇

• 实践篇

• 应用篇（一）

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

• 基础篇

• 实践篇

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

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

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

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

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

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

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

链表基础

复习：数组

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

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

1
2
3
4
5
6
7
8

void ArrayTest(void) {
    int fuc[100]; // 定义数组

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

    printf("%d\n",fuc[0]);
}

原文来自：C PUZZLES, Some interesting C problems

本文文末有笔者的答案。

注意：原文中原作者和笔者使用的环境均为 linux + gcc，笔者的答案亦以此为准。