ZingLix 空间

单源最短路径算法

Single-source Shortest Paths

一、问题描述在图算法中，从某点开始，计算到其他点最短的路径是十分常见的问题，而这一问题有许多变种，本文着重于从某点开始到图中所有其他点的最短路径，称为单源最短路径问题（Single-source Shortest Paths）。二、特殊情况负权重的边在单源最短路径中，负权重的边并非不允许存在，但要求是不存在从源结点可以到达权重为负的环路。因为如果存在可以抵达的权重为负的环路...

Posted by ZingLix on June 15, 2018

有向无环图中的拓扑排序

Topological Sorting

一、什么是拓扑排序在一个较为复杂的任务中，我们往往选择将其分解为数个较为简单的分任务，然后依次完成。这些分任务之间，有些具有依赖关系，必须先完成某一个才可以完成接下去的任务。类似于在学校中，为了获得学位，必须将所有课程修完。而在学习数据结构前，必须先学完某一门编程语言。或是如下，算法导论中的一个例子。这是 Bumstead 教授每天穿衣服的次序图，必须先穿好某些衣服才能穿其他的。...

Posted by ZingLix on June 14, 2018

STL解析 —— priority_queue

Standard Template Library —— priority_queue

优先队列（priority queue）是一种队列，但是每次弹出的是优先级最高的元素，优先级可以有不同表现，比如在最小堆中是值最小的元素，而在最大堆中则是值最大的元素。关于其数据结构本身已有过详细讨论。 STL 中的优先队列 1 2 3 4 5 template< class T, class Container = std::vector<T>, ...

Posted by ZingLix on May 29, 2018

STL解析 —— heap

Standard Template Library —— heap

heap 又称二叉堆，是一个十分常用的数据结构，可以看成一个完全二叉树，但可以使用数组来实现。在这有过更详细的介绍。在 STL 中，heap 并不作为一个容器，而是在 algorithm 库中以算法的形式实现，并且都接受first和last两个参数，并要求其为随机迭代器（Random Access Iterator）。另外，这些函数都提供两个版本，一个通过 < 来比较，从而实...

Posted by ZingLix on May 27, 2018

STL解析 —— queue

Standard Template Library —— queue

队列（queue）是一种先进先出（First In First Out, FIFO）的数据结构。如上图所示，可以在最后添加元素，或者删除位于最前面的元素，而且只有对于首尾两个元素的访问权，所以并不可以对 queue 进行遍历的操作。综上，queue 提供如下关于操作元素的操作： push：在最后添加元素 pop：删除最前面的元素 front：获得最前面的元素 ...

Posted by ZingLix on May 15, 2018

STL解析 —— stack

Standard Template Library —— stack

栈（stack）是一个先进后出（First In Last Out, FILO）的数据结构，在这里有对栈的数据结构进行过详细的讨论。 stack 提供如下几个操作： push：将元素压入栈中 pop：将栈顶元素弹出 top：获得栈顶元素 empty：判断栈是否为空 size：获得栈中元素数量 STL 中的 stack 与利用栈顶元素及可以指向下一个元素的指...

Posted by ZingLix on May 8, 2018

STL解析 —— deque

Standard Template Library —— deque

vector 是 STL 中常用的一个容器，它可以在尾部快速添加和移除元素，但是在头部进行相关操作效率便十分糟糕。deque （双端队列）用于弥补 vector 的不足，在首尾两端都可以快速添加和删除，当然底层结构也有区别。底层数据结构与 vector 连续空间不同，deque 没有所谓容量的概念，因为它是动态地由多个连续空间组合而成。 deque 的结构类似于一个二维数组，左...

Posted by ZingLix on May 7, 2018

STL解析 —— 模板在traits技法中的应用

Standard Template Library —— template in traits

介绍在STL的实现中，traits技法是最核心的技术之一，其实现大量的运用到了模板这一特性，在Modern C++中引入的变长模板参数等等都为其实现创造了方便。以C++11标准中std::pointer_traits为例，如下是标准中非特化版本中成员类型和成员别名模板的定义。类型定义 poin...

Posted by ZingLix on April 21, 2018

STL解析 —— vector

Standard Template Library —— vector

vector 类似于传统的数组，是一种顺序容器，差别在于 vector 没有容量限制，在尾部新增元素有很好的性能。由于以顺序的方式存储，其迭代器为 random_access_iterator，支持快速随机访问，可以在 \(O(1)\) 的时间取得元素。底层数据结构 vector 底层数据结构为线性连续空间，但如果总正好是占用所有元素所需的空间，那么当频繁新增元素时，会频繁的申请新内存...

Posted by ZingLix on April 19, 2018

数据结构 - AVL 树

Data Structures - AVL Tree

介绍 AVL 树（Adelson-Velskii-Landis Tree）是平衡二叉搜索树的一种，可以看作是有附加条件的二叉搜索树，用以保证不会出现如下极端情况。之所以这么做是为了保证整棵树深度在 \(O(logN)\) ，从而使得插入和删除结点时不会因极端情况导致花费过长时间。AVL 树的要求是任何节点的左右子树高度相差不超过 1，如下图所示。仔细观察普通的二叉搜索树可...

Posted by ZingLix on April 16, 2018

ZingLix Blog