总览（Glossary）

————————————————————————

一个有向图（directed graph, or simply digraph）是若干节点和有向边的集合。每条有向边有序地连接着一对节点。

————————————————————————

我们称一条有向边由节点对的第一个节点指向第二个节点。

图是若干节点(vertices)和若干连接这些节点的边(edge)组成的集合。

节点的名字不是十分重要，我们用 0 到 V-1 的数字来标记 V 个节点，用v-w表示节点v和节点w相连的一条边，w-v表示同一条边。

以上关于无向图的定义允许出现下面两种情况：1. 自循环：即一条边连接着一个节点和它自己。 2.平行边：两条边连接着相同的一对节点。

之前一直用的是MathTex来插入公式，不过，这个方式相当于插入了一张在线图片，显示效果不是很好。终于闲下来，有机会琢磨一下怎么用MathJax了。

我们用数组来存储符号表的键-值对，通过算术运算将键转换成数组的索引。当需要查找元素时，将待查找元素的键转换成数组索引，直接通过下标访问即可。这样的办法称为哈希（hashing）。

马踏棋盘问题又称Knight Tour Problem，指的是在一个n*n棋盘上，找出一条路径，可以使马不重复地踏遍整个棋盘的格子。对于每一步，最多有八个方向可以走。

陀螺仪可以用来测量物体的旋转状态。不像飞机、轮船等可以安装一个精密的陀螺仪，手机等电子设备由于体积小，只能使用微机械陀螺仪。微机械陀螺仪的原理和传统陀螺仪的原理是不一样的。

Shadowsocks

Shadowsocks Qt

Onedrive for win7

我们来研究一种符号表的实现————它结合了使用链表带来的插入元素的灵活性和使用顺序数组带来的查找元素的高效性，称为二叉搜索树。

————————————————————————

一个二叉搜索树是一个二叉树，每个节点都有一个可以比较的键，并满足以下约束条件：每个节点的键都比它左子树中所有节点的键大，都比它右子树中所有节点的键小

————————————————————————

为了方便查找，人们设计出符号表（symbol table）这样一个抽象数据类型：在其中存储信息（value），之后可以通过指明一个键（key）来访问这个信息。符号表有时候也可以称为字典，有时也可以称为索引。

符号表的主要目标是把一个值（value）与一个键（key）联系起来。用户可以插入 “键-值” 对（insert/put），也可以通过一个键来找到一个值（search/get）。除此之外，为方便使用，符号表还提供了其他一些方法。

很多应用要求我们把元素按顺序排列，但不一定是完整且严格的顺序，也不一定一次就排好。有时候，我们收集一些元素，找出他们中最大的那一个，然后再收集一些元素，找出此刻最大的一个。这时候，一个符合条件的数据结构应该支持下列两种操作：删除（找出）最大的元素，插入元素。这样的数据结构叫做 优先队列。

下面主要介绍优先队列的朴素实现和基于完全二叉树实现(heap based)，以及在后者基础上产生的一种排序算法——堆排序（heapsort）