弱冠有感

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);向量操作、管理维护更加简化、统一与安全,元素类型可灵活选取,便于定制复杂数据结构。

继续阅读

从C到C++

C++是C语言的扩展和超集,也是现今程序设计语言中最为复杂的一员,要熟练地掌握和运用C++,没有十年半载的时间是不大可能的,但是这篇文章我只是想简单的讨论一下C++相比于C扩展的地方以及不同之处,以便于从C快速的进阶到C++,为之后的C++版数据结构做准备,与C相同的地方将不再赘述,但要注意,这些只是简单的了解,并不能算是真正的学会。会用一门编程语言实现“HelloWorld”并不等于就掌握了这门编程语言。

继续阅读

结构、联合与枚举

C语言除了提供基本的数据类型外,还提供了其他一些高级的数据类型,这其中自然包括结构(struct)、联合(union)与枚举(enum)。所谓结构就是一个复合的数据类型,在里面可以有很多各种类型的成员,然后用一个整体去表达多个集合在一起的数据。而联合和结构基本相同,唯一的区别就是联合中的成员使用的是同一个存储空间。最后,枚举实际上就是把常量符号化组合起来。 继续阅读

指针庶事

有人说指针是C语言的精髓,但精髓可不是容易掌握的,特别是指针与数组、字符串、结构体和数据结构等的结合,往往会使许多新手摸不着头脑,这篇文章我将把我所掌握的一些基本知识好好地梳理一遍,也算是“温故而知新”吧!

继续阅读

谈谈域名那些事

倘若你想要建一个自己的网站或者像我这样的独立博客,无论是在开始还是结束,总要涉及到“域名”这个东西,面对如今这个互联网的世界,域名在我们的生活中是必不可少的,最熟悉的东西往往越值得去研究。

继续阅读