首页 > 2017年6月

哈夫曼编码

毕业多年发现写业务写废了,需要重新捡回算法。 概念 哈夫曼编码是利用哈夫曼树生成的编码方式,其特点是编码长度最短,常用于数据压缩。哈夫曼树是带权路径总长度最小的树,又称为最优二叉树,所谓最优二叉树是指所有叶子节点的带权路径和最小的树。树中一个节点的带权路径就是该点的权值乘以其到根节点的距离。 即: WPL = W1 * L1 + W2 * L2 + ... + Wn * Ln 生成 从节点集合S中取出权值最小的两个节点a,b作为左右子节点建立二叉树T,并从S中删除a,b 将二叉树T的根节点重新加入集合S,其权值为a,b权值相加 重复前两步操作直至集合S为空,此时得到的二叉树即为...

C++构造函数与析构函数的一些特殊用法

最近提及C++的构造函数与析构函数的一些特性引发了一些思考,不如写篇文章记录下过程。 关键字: C++,构造函数,析构函数,虚函数,纯虚函数,私有函数 构造函数是否可以是私有函数 之前单纯从理论上思考,一个类实例化必然要通过构造函数来产生实例,所以一个类的构造函数如果是私有的,将无法从外部实例化。至此思路都是没有问题的,但是发现自己忘记了一种情况:类的static公有函数可以在没有实例化时即可使用,它自然也能访问到类的私有成员。 所以,类的构造函数可以是私有的,可以通过static静态函数来创建实例。基于这个思路,我们可以在该静态函数中增加一些操作来管理该类的实例化。例如,我们可以通...

STL模板不同类型在内存分布与效率上的差别

最近发现虽然一直在使用STL,但从来没有好好的去了解对比过,所以决定系统的学习与归纳下STL相关知识。 关键字: vector,list,map,set,unordered_map,unordered_set Vector Vector在内存上的分布是采用一段连续内存来存储,进行插入操作时如果内存不足则会malloc申请一块新的内存并将当前数据memcpy复制到新内存中并free释放原内存。但是在有些实现中通过一些算法来分析申请新内存并舍弃旧内存的效率,当效率底下时会通过使用链表连接两块内存来存储数据,当然这部分对外是不透明的,外部使用时只会看到Vector是一整块内存空间。 对Ve...

最新文章

最近回复