详解二叉堆(基础篇)
堆(heap),又称为优先队列(priority queue)。尽管名为优先队列,但堆并不是队列。在队列中,我们可以进行的操作是向队列中添加元素和按照元素进入队列的选后顺序取出元素。而在堆中,我们不是按照元素进入队列的先后顺序,而是按照元素的优先级取出元素。
Linux 内核中的调度器会根据各个进程的优先级对程序的执行进行调度。在操作系统运行时,通常会有很多个不同的进程,优先级各不相同。在调度器的作用下,优先级高的进程被有限执行,优先级靠后的就只能等待。堆是实现这种调度器的一种很合适的数据结构(顺便提一下,现在的 Linux 内核的调度器使用的是基于红黑树的 CFS ,笔者以后会专门介绍)。
详解 AVL 树(基础篇)
AVL 树是一种平衡二叉搜索树,得名于其发明者的名字( Adelson-Velskii 以及 Landis)。(可见名字长的好处,命名都能多占一个字母出来)。其递归定义如下:
左右子树的高度差小于等于 1。
其每一个子树均为 AVL 树。
基于这一句话,我们就可以进行判断其一棵树是否为二叉树了。
详解二叉树(基础与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 指针表示),要么左右孩子都指向一颗二叉树。
详解 C 语言链表(实践篇)
在基础篇中,笔者介绍了一些链表的基本操作。在本文中,笔者整理了几个有关链表的问题供大家练习。练习的难度是递增的。前几道非常简单,后面就会愈加困难。答案会附在题目的后面。
注意:仅仅用眼睛看答案不会提升自己的水平,只有自己亲手实现,才算真正的学到了知识。在看答案之前,无论你自己有没有成功实现,都请务必确保你真的认真思考了。
优秀的程序员应该是能够将数据结构可视化的,因此他们能够很好的理解代码运行时内存的变化。链表的规整使得它很适合拿来做基本的可视化训练。在解决下面这些问题时,你可以尝试在纸上画出链表的结构进行模拟,最终使用代码将之表达起来。