分类目录归档:数据结构与算法

计算几何(一)——凸包(Convex Hull)

凸包问题是计算几何(Computational Geometry)的一个重点,同样,如何构造凸包也是一个重要的研究方向,生活中许多问题都会用到构造凸包的知识,比如颜料混合,即如何从已有的颜料中通过混合得到未知的颜料。在这篇文章中,我将介绍5种重要的凸包构造算法,分别是极点算法极边算法增量式策略Jarvis MarchGraham Scan等,同时也将通过归约得到凸包构造算法时间复杂度的下界。

继续阅读

大话排序

伟大的计算机科学家D.E.Knuth曾指出,四分之一以上的CPU时间都用于执行同一类型的计算:按照某种约定的次序,将给定的一组元素顺序排列,比如将n个整数按通常的大小次序排成一个非降序列。这类操作统称排序(sorting)。

继续阅读

词典

词典(dictionary)这种数据结构在编程语言中很常见,比如Java中的HashMap与Hashtable、Python中的字典等等,一个键值对可以称为一个词条,即entry = (key, value),而映射(map)就是词条的集合,但其中各词条(的关键码)互异,词典与映射基本相同,但允许词条的(关键码)雷同,进一步,关键码之间可以定义全序关系的词典称为有序词典(sorted dictionary),映射和词典都是动态的,统称符号表(symbol table)。实现词典的重要技术便是散列(hash),与其说散列是一种技术,不如说散列是一种思想,它重点解决的问题是数据结构在空间效率上的提高,而依照散列思想所实现的数据结构的访问方式不妨称为寻值访问(call-by-value),这种方式更为自然,适用范围也更广泛。 继续阅读

数学意义上的图包含两个要素,即顶点集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);向量操作、管理维护更加简化、统一与安全,元素类型可灵活选取,便于定制复杂数据结构。

继续阅读