牛客网刷题总结—Day1
1.关于哈夫曼树
哈夫曼树也称最优二叉树,其n个叶子节点都是带有权值的,其节点的带权路径长度(n个叶子节点的权值*其到根节点的路径之和)最小的二叉树即为哈夫曼树。
一般的哈夫曼树不存在度为1的节点(除非在退化的情况下)
n个节点经过n-1一次合并最终成为拥有2n-1个节点的哈夫曼树
1.1 构建哈夫曼树
1>从n个带权的节点中选择最小的两个n1,n2构成一个子二叉树,并将其根的权值设为w(n1) + w(n2) = nw
2>再将n个带权节点删除n1和n2,而加入nw
3>再重复以上两步
1.2 哈夫曼编码
建立一棵哈夫曼树,规定其左孩子均对应于二进制的0、右孩子均定义为二进制的1—这就是一颗哈夫曼编码树
可以通过此树实现PFC编码(前缀无歧义编码—prefix-free code),每个字符对应着规定某个编码—如规定‘M’对应110等
只要所有字符都对应于叶节点,就不会产生歧义现象
可以通过哈夫曼编码实现文件的无损压缩或者解压等
根据某个字符出现的频率高低作为权重,频率高的其二进制码则短一些—相当于哈夫曼树中权重高的叶子节点到根节点路径短,频率低的二进制码则相对较长
其解码根据编码串如"11001111111001001"依次进行扫描,从根节点开始根据对应是0/1深入左/右子树进行,直至达到叶节点退出—根据此路径所扫描的码如110,对应'M'
由此再返回此树的根节点进行再次扫描—由此迭代至编码串遍历完毕
2.C++不能重载的运算符
1>"."类成员访问运算符 2>"::"域运算符 3>".*"类成员指针访问运算符 4>sizeof()运算符
注意:new/delete运算符是可以被重载的
3. c++调用基类虚函数是采用动态联编(动态绑定)
C++默认是采用函数和实现在编译阶段就进行绑定—即静态绑定
而涉及到多态时需要对虚函数设置一个virtual tablel存放函数指针
4.结构体中分配的位数
struct
mybitfields
{
unsigned
short
a : 4;
unsigned
short
b : 5;
unsigned
short
c : 7;
} test
void
main(
void
)
{
int
i;
test.a = 2;
test.b = 3;
test.c = 0;
i = *((
short
*)&test);
printf
(
"%d\n"
, i);
}
其中冒号表示分配了几位空间,即 a : 4,b : 5, c : 7; 且按照以下方式排列
根据main函数中对三值赋值结果来看其内存中的0/1分布为
地址值 位
0x11 0 0 1 0 (a) 0 0 0 1
0x12 1(b) 0 0 0 0 0 0 0(c)
或者
0 0 0 0 0 0 0(c)0 0 0 1 1(b) 0 0 1 0(a) 十进制的50或者十六进制的0x0032(每4位计算一次)
对test地址的数据进行short *强转 - short占两个字节即为50,再通过隐式的int转换变为0x00000032(50)
最新文章
- Android线程管理之ThreadPoolExecutor自定义线程池
- Python-02-基础
- Java开发基础
- 深入.net(数据类型)
- php函数获取文件名
- mysql中文乱码问题
- TDE与列级数据加密
- Huffman树与编码的简单实现
- CPU使用率
- POJ 3187 穷举
- Javascript学习3 - 语句
- 图片上传裁剪zyupload
- 1、搭建 maven 环境
- day 23 二十三、对象方法,类方法,封装,绑定方法
- 【建模应用】PLS偏最小二乘回归原理与应用
- jQuery学习笔记(一)
- (19)ThreadPoolExecutor线程池
- 潭州课堂25班:Ph201805201 mongo数据 库 第八课 (课堂笔记)
- 关于iOS开发常用的一些东西
- e640. 使一个组件可拖动