月度归档:2016年05月

弱冠有感

102920-106

倘若将人生的每十年看做一个阶段,那么每过一个阶段就应该问自己一个问题:我学到了什么?以十年这个刻度来回首一个阶段,究竟有哪些事还能值得再提起来?这样看来,人生天地之间,真若白驹过隙,沧海一粟。

继续阅读

数学意义上的图包含两个要素,即顶点集V与边集E,可以形象的表示为 G=(V; E),其中顶点数(vertex)n=|V|,边数(edge/arc)e=|E|。另外,同一条边的两个顶点,彼此邻接(adjacency),同一顶点自我邻接,构成自环(self-loop)。不含自环,即为简单图(simple graph),对于非简单图(non-simple),这里暂不讨论。顶点与其所属的边,彼此关联(incidence),与同一顶点关联的边数称为(degree/valency)。形象地说,所谓邻接关系就是顶点与顶点之间的关系,而关联关系则是顶点与边之间的关系。进一步对图进行分类,若邻接顶点u和v的次序无所谓,则(u, v)为无向边(undirected edge),进而,所有边均无方向的图,即无向图(undigraph)。反之,有向图(digraph)中均为有向边(directed edge),u、v分别称作边(u, v)的(tail)、(head)。无向边、有向边并存的图,称作混合图(mixed graph)。因为有向图通用性更强,故本文主要针对有向图介绍相关结构及算法。 继续阅读

二叉树

树是特殊的图,\(T= \left ( V,E \right )\),节点数|V|=n,边数|E|=e。指定任一节点r∈V作为根后,T即称作有根树(rooted tree)。若:T1, T2, …, Td为有根树,则:T=((∪Vi)∪{r}, (∪Ei)∪{<r, ri>|1≤i≤d})也是,相对于T,Ti称作以ri为根的子树(subtree rooted at ri),记作Ti=subtree(ri)。ri称作r的孩子(child),ri之间互称兄弟(sibling),r为其父亲(parent),d=degree(r)为r的(出)(degree)。可归纳证明:,故在衡量相关复杂度时,可以n作为参照。若指定Ti作为T的第i棵子树,ri作为r的第i个孩子,则T称作有序树(ordered tree)。

列表

列表(list)是采用动态储存策略的典型结构,其中的元素称作节点(node),各节点通过指针或引用彼此联接,在逻辑上构成一个线性序列。如L = {a0, a1, a2, …, an-1}。相邻节点彼此互成前驱(predecessor)或后继(successor),前驱或后继若存在,则必然唯一,这也是线性结构的重要特征,没有前驱/后继的唯一节点称作(first/front)/(last/rear)节点。向量支持循秩访问(call-by-rank)的方式,根据数据元素的秩,可在O(1)时间内直接确定其物理地址,既然同属线性序列,列表固然也可通过秩来定位节点,即从头/尾端出发,沿后继/前驱引用,然而,此时的循秩访问成本过高,已不合时宜,因此,应改为循位置访问(call-by-position)的方式,亦即,转而利用节点之间的相互引用,找到特定的节点。

继续阅读

向量

C/C++语言中,数组A[]中的元素与[0, n)内的编号一一对应,反之,每个元素均由(非负)编号唯一指代,并可直接访问,即A[i]的物理地址 = A + i*s, s为单个元素占用的空间量,故亦称作线性数组(linear array)。向量是数组的抽象与泛华,由一组元素按线性次序封装而成,各元素与[0, n)内的(rank)一一对应,我们也称其为循秩访问(call-by-rank);向量操作、管理维护更加简化、统一与安全,元素类型可灵活选取,便于定制复杂数据结构。

继续阅读