简洁高效的内存池 数据结构

简洁高效的内存池

之前两篇文章剖析了 SGI STL 的空间配置器,果然在 STL 面前,几乎所有代码都是三流水准。 今天我们借鉴 STL 空间配置器的思想,设计一个简洁的内存池,只分配固定大小内存。 它用一个链表管理...
阅读全文
有向图的单源最短路径

有向图的单源最短路径

单源最短路径 给定一个带权有向图G=(V,E),其中每条边的权是一个实数。另外,还给定V中的一个顶点,称为源。现在要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路径上各边权之和。这个问题通...
阅读全文
无向图的最小生成树

无向图的最小生成树

连通图由N个顶点组成,生成树必须含有N个顶点、N-1条边。 只能用连通图的边来构造最小生成树 只能恰好用N-1条边来联结图中的顶点 选用的这N-1条边不能构成回路 构造最小生成树的方法,Kruskal...
阅读全文
图的广度优先遍历

图的广度优先遍历

基本思想 从图中某个顶点V0出发,并访问此顶点; 从V0出发,访问V0的各个未曾访问的邻接点W1,W2,…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点; 重复步骤2,直到全部顶...
阅读全文
图的深度优先遍历

图的深度优先遍历

之前一篇文章介绍了图的存储,我们再来了解一下图的深度优先遍历是怎么回事。 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,...
阅读全文
平衡搜索树之红黑树

平衡搜索树之红黑树

什么是红黑树 红黑树是一棵二叉搜索树,它在每个节点上增加了一个存储位来表示节点的颜色,可以是Red或Black。通过对任何一条从根到叶子节点路径上的颜色来约束,红黑树保证最长路径不超过最短路径的两倍,...
阅读全文
逆序打印链表 链表

逆序打印链表

题目:输入一个单链表的头指针,从尾到头逆序打印出每个结点的值。 定义链表结点: 我们先完成链表的PushBack 再写一个Remove函数 回到逆序打印链表的问题上,由于是单链表所以只能从前向后遍历,...
阅读全文
实现哈希桶的迭代器 哈希

实现哈希桶的迭代器

上一篇文章介绍了哈希表闭散列实现,这篇文章我们分析一下处理哈希表冲突的另一种方法——开链法。也就是我们常说的哈希桶,同时我们会实现一个哈希桶的简易版迭代器。 同样的使用散列函数完成哈希地址的映射,我们...
阅读全文
图的存储

图的存储

图的定义 图是另一种非线性结构,由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构。 Graph = (V, E); V = {x|x是顶点集合}; E = {<x,y> | ...
阅读全文