路径和路径长度
:从树中的一个节点到达另外一个节点的之间的分支为路径,其长度为路径长度。树的路径长度定义为从根节点开始到达每一个节点的路径长度之和。
权值
:节点的权值为该节点在所有节点中占的比重,拿一个文本文件来说,某个字符的节点权重即为该字符出现的次数与该文本文件中所有字符出现的次数的比值。
带权路径长度
:树中某个节点的带权路径长度为该节点的路径长度与该节点的权重的乘积。一颗树的带权路径长度(WPL)为该树中的所有叶节点的带权路径长度之和。
带权路径长度最小的树二叉树即为哈夫曼树(最优二叉树)!
1.根据给定的n个权值,构成n棵二叉树的集合:F = {T1,T2,T3,T4,…}。其中每棵二叉树中只有一个带权值为Wi的根节点,其左右孩子都为空。
2,在F中选取两棵权值最小的树,作为一个新节点的左右子树,构造出一课新的二叉树,且置新的树的权值为两棵左右子树的权值之和。
3,在F中删除这两棵左右子树,并将新的二叉树加入F中。
4,重复2,3过程,直到F只含有一棵二叉树。(这里即为树中根节点)
/* 哈夫曼树节点 */
typedef struct _haffman {
char data; //用来存放节点字符的数据域
int weight; //权重
struct _haffman *leftChild; //左孩子节点
struct _haffman *rightChild; //右孩子节点
}HaffNode;
宏定义
#define MAX_SIZE 256 //编码数量
#define HALF_MAX 128 //一半的数量
#define ASCII_SIZE 128 //ASCII码的数量
定义一些需要用到的全局变量
/* 以顺序结构存储的树节点--编码解码的字符映射表 --即存储原数据*/
HaffNode node[MAX_SIZE];
/* 用来保存所有左孩子节点--为总节点数的一半 */
HaffNode left[HALF_MAX];
/* 用来保存所有右孩子节点 --为总节点数的一半*/
HaffNode right[HALF_MAX];
/** 创建一个二维数组,用来保存每一个叶节点的编码 */
char code[MAX_SIZE][HALF_MAX];
/* 构造哈夫曼树
@param node 哈夫曼树的根节点
@param length 节点数组的长度
*/
void CreatHaffmanTree(HaffNode * node, int length)
{
if (length <= 0)
{
printf("长度为0,无法创建哈夫曼树!\n");
return;
}
SortHaffmanNode(node, length); //先进行节点权值的排序
HaffNode parent; //构建一个以node数组最后两个节点组成的父节点
left[length - 1] = node[length - 1]; //权重最小的节点
right[length - 1] = node[length - 2]; //权重第二小的节点
parent.weight = left[length - 1].weight + right[length - 1].weight; //累加权重
parent.leftChild = &left[length - 1]; //左孩子指向相对小的值
parent.rightChild = &right[length - 1]; //右孩子指向相对更大的值
node[length - 2] = parent; //将倒数第二个替代为parent节点,数组长度 - 1,递归创建哈夫曼树
CreatHaffmanTree(node, length - 1); //递归,并且长度自动减一,每一次都会进行一次重新排序。
}
实现构造哈夫曼树前需要先将节点数组的权重进行排序,即为上述SorHaffmanNode();函数,这里我使用的是冒泡排序的方法进行排序。
以下是其代码实现:
/* 哈夫曼树的排序 --使用冒泡排序
*@param node 节点数组
* @param length 节点的数量
*/
void SortHaffmanNode(HaffNode * node, int length)
{
HaffNode tempNode;
for (int i = 0; i < length - 1; i++)
{
for (int j = 0; j < length - i - 1; j++)
{
if (node[j].weight < node[j + 1].weight) //根据权重比较来排序--从大到小
{
tempNode = node[j];
node[j] = node[j + 1];
node[j + 1] = tempNode;
}
}
}
}
过程:从根节点出发,左支的编码为0,右支的编码为1.直到叶节点结束,其编码即为该节点数据的编码。每一次遍历都重新从根节点出发重新遍历。
代码实现:
/**
* 创建一个编码函数
* @param node 哈夫曼树节点数组
* @param tempnode 编码后的字符数组
* @param index 当前操作节点数组的下标
*/
void Coding(HaffNode * node, char * tempnode, int index)
{
if (!node) return;
if (node->leftChild == NULL || node->rightChild == NULL)
{
//使用字符数组,将编码形式保存
tempnode[index] = '\0'; //字符串结束的标志
strcpy(code[node->data - 0], tempnode); //这里叶节点的值使用的是字母,可以使用ASCII码的形式确认存储的位置,也可以用强制类型转换
}
tempnode[index] = '0'; //左支路的编码为0
Coding(node->leftChild, tempnode, index + 1); //先递归调用左支路,
tempnode[index] = '1'; //右支路的编码为1
Coding(node->rightChild, tempnode, index + 1); //再递归调用右支路
}
过程:对于一段由编码0/1构成的二进制文件,在同个树而言,重第一个开始,遇到0则访问左子树,遇到1则访问右子树。直到该节点没有了左右节点为止,即这段01字符即可解码为该叶子节点所对应的字符。
代码实现
/** 解码过程 -- flag 0/1 来表示往哪边走,左走0,右走1 */
HaffNode *Unziped(HaffNode *node, int flag)
{
if (flag == 1)
return node->rightChild; //右子树
else if(flag == 0)
return node->leftChild; //左子树
return NULL;
}
下面是所有的代码实现:
main.c
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#include "HaffmanTree.h"
#include <string.h>
/**
进行哈夫曼树编码的过程
1,打开文件,进行文件的字符读取,并进行哈夫曼编码,将压缩的数据保存另外一个文件ziped.txt中
2,解码文件,对二进制文件进行解码,将解码的结果保留在另外一个文件result.txt中
*/
int main() {
//保存到二进制文件中的无符号字符,即解码过后对应的字符,这里即为00000000
unsigned char saveChar = 0;
//中间变量
unsigned char tempchar = 0;
printf("使用哈夫曼树实现文件的压缩,(只支持ASCII字符)\n");
//以只读的形式打开文本文件,该文件就是要进行压缩的源文件
FILE * inputFile = fopen("input.txt", "r");
//以二进制的形式写入该文本文件,相当于压缩包
FILE * zipedFile = fopen("ziped.txt","wb");
//文件中保存的字符个数,源文件
int fileLength = 0;
//定义一个 数组,用来保存每个ASCII码的权重
int asciicount[128] = {
0};
//保留读取到的字符
char readChar;
while ((readChar = fgetc(inputFile)) != EOF) {
//逐个读取字符,并累加
fileLength++;
//将读取到的字符作为下标,统计每个字符出现的次数
asciicount[readChar - 0]++;
}
//字符种类计数器
int cnt = 0;
for (int i = 0; i < 128; i++) {
if(asciicount[i] != 0) {
//统计节点的数量,即文件中出现多少种字符
node[cnt].data = i;
// 将字符出现的次数当成权重
node[cnt].weight = asciicount[i];
//节点数量累加
cnt++;
}
}
CreatHaffmanTree(node, cnt); //创建哈夫曼树
char tempcode[10]; //编码的值 0/1
Coding(node, tempcode, 0); //编码,从零开始
cnt = 0; //计数器置零
fseek(inputFile, 0L, 0); //将文件定位于文件头,偏移0个字节长度
int zipedLength = 0;
while ((readChar = fgetc(inputFile)) != EOF) {
//逐位将编码保存到文件中
for (int i = 0; i < strlen(code[(int)readChar]); i++) {
saveChar |= (code[(int)readChar][i] - '0'); //将saveChar的最后一位赋值为0/1
cnt++; //累加计数器
if (cnt == 8) {
//如果计数累加到8,8位一个字符,则写入文件
//在文件中写入一个unsigned char 大小的字符
fwrite(&saveChar, sizeof(unsigned char), 1, zipedFile);
cnt = 0;
saveChar = 0;
zipedLength++; //压缩文件字符大小累加,方便算出压缩比
} else {
//saveChar的值左移一位,为下次给最低位赋值做好准备
saveChar <<= 1;
}
}
}
if (cnt < 8) {
//处理不足8个字符的情况
saveChar <<= (8 - cnt);
cnt = 0;
saveChar = 0;
fwrite(&saveChar, sizeof(unsigned char), 1, zipedFile);
zipedLength++;
}
fclose(inputFile);
fclose(zipedFile);
printf("文件压缩成功,请在文件夹中查看以压缩的文件\n");
printf("源文件的字符个数:%d,压缩后文件的个数:%d %.2lf\n", fileLength, zipedLength, (double)zipedLength / fileLength);
//哈夫曼树的解码过程
zipedFile = fopen("ziped.txt", "rb");
FILE * resultFile = fopen("result.txt", "w");
cnt = 0; //计数器清零
HaffNode * currNode = &node[0];
while (fread(&readChar, sizeof(unsigned char), 1, zipedFile)) {
if (fileLength == 0)
break;
//遍历readChar中的每个二进制
for (int i = 0; i < 8; i++) {
tempchar = readChar & 128; //取readChar的最高128为10000000
tempchar >>= 7; //每一次右移7位
readChar <<= 1; //最高位已经被取了,所以在进行移动
currNode = Unziped(currNode, tempchar - 0);
//判断叶节点
if (currNode->leftChild == NULL || currNode->rightChild == NULL) {
fprintf(resultFile, "%c", currNode->data);
cnt++;
currNode = &node[0]; //每一次遍历都需从根节点开始
}
}
}
fclose(inputFile);
fclose(resultFile);
printf("解码成功,请查看文件;result.txt");
system("pause");
return 0;
}
Haffman.h
#pragma warning(suppress : 4996)
/*
哈夫曼树的顺序存储
哈夫曼树编码的压缩文件的主要思路
1,读取某个文本文件,统计各个字符出现的个数,作为权重
2,构建哈夫曼树,生成每个字符对应的编码,将编码保存到压缩文件中
3,文件解压缩,实际就是将压缩文件翻译过来,然后在保存在解压缩文件中的过程
@autor 小机
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 256 //编码数量
#define HALF_MAX 128 //一半的数量
#define ASCII_SIZE 128 //ASCII码的数量
/* 哈夫曼树节点 */
typedef struct _haffman {
char data; //用来存放节点字符的数据域
int weight; //权重
struct _haffman *leftChild; //左孩子节点
struct _haffman *rightChild; //右孩子节点
}HaffNode;
/* 以顺序结构存储的树节点--编码解码的字符映射表 --即存储原数据*/
HaffNode node[MAX_SIZE];
/* 用来保存所有左孩子节点--为总节点数的一半 */
HaffNode left[HALF_MAX];
/* 用来保存所有右孩子节点 --为总节点数的一半*/
HaffNode right[HALF_MAX];
/** 创建一个二维数组,用来保存每一个叶节点的编码 */
char code[MAX_SIZE][HALF_MAX];
/* 哈夫曼树的排序 --使用冒泡排序的方法*/
void SortHaffmanNode(HaffNode * node, int length);
/* 构造哈夫曼树
@param node 哈夫曼树的节点数组
@param length 节点数组的长
*/
void CreatHaffmanTree(HaffNode * node, int length);
/**
* 创建一个编码函数
* @param node 哈夫曼树节点数组
* @param tempnode 编码后的字符数组
* @param index 当前操作节点数组的下标
*/
void Coding(HaffNode * node, char * tempnode, int index);
/** 解码过程 -- flag 0/1 来表示往哪边边的树枝走,左走0,右走1 */
HaffNode *Unziped(HaffNode *node, int flag);
Haffman.c
#include "HaffmanTree.h"
/* 哈夫曼树的排序 --使用冒泡排序*/
void SortHaffmanNode(HaffNode * node, int length) {
HaffNode tempNode;
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - i - 1; j++) {
if (node[j].weight < node[j + 1].weight) {
//根据权重比较来排序--从大到小
tempNode = node[j];
node[j] = node[j + 1];
node[j + 1] = tempNode;
}
}
}
}
/* 构造哈夫曼树
@param node 哈夫曼树的根节点
@param length 节点数组的长度
*/
void CreatHaffmanTree(HaffNode * node, int length) {
if (length <= 0) {
printf("长度为0,无法创建哈夫曼树!\n");
return;
}
// 先排序
SortHaffmanNode(node, length);
//构建一个以node数组最后两个节点组成的父节点
HaffNode parent;
//权重最小的节点
left[length - 1] = node[length - 1];
//权重第二小的节点
right[length - 1] = node[length - 2];
parent.weight = left[length - 1].weight + right[length - 1].weight; //累加权重
//左孩子指向相对小的值
parent.leftChild = &left[length - 1];
//右孩子指向相对更大的值
parent.rightChild = &right[length - 1];
//将倒数第二个替代为parent节点,数组长度 - 1,递归创建哈夫曼树
node[length - 2] = parent;
//递归,并且长度自动减一
CreatHaffmanTree(node, length - 1);
}
/**
* 创建一个编码函数
* @param node 哈夫曼树节点数组
* @param tempnode 编码后的字符数组
* @param index 当前操作节点数组的下标
*/
void Coding(HaffNode * node, char * tempnode, int index) {
if (!node) return;
if (node->leftChild == NULL || node->rightChild == NULL) {
//使用字符数组,将编码形式保存
tempnode[index] = '\0'; //字符串结束的标志
//这里叶节点的值使用的是字母,可以使用ASCII码的形式确认存储的位置,也可以用强制类型转换
strcpy(code[node->data - 0], tempnode);
}
tempnode[index] = '0'; //左支路的编码为0
Coding(node->leftChild, tempnode, index + 1); //先递归调用左支路,
tempnode[index] = '1'; //右支路的编码为1
Coding(node->rightChild, tempnode, index + 1); //再递归调用右支路
}
/** 解码过程 -- flag 0/1 来表示往哪边走,左走0,右走1 */
HaffNode *Unziped(HaffNode *node, int flag) {
if (flag == 1)
return node->rightChild; //右子树
else if(flag == 0)
return node->leftChild; //左子树
return NULL;
}
注意上面程序只能编码ASCII码的文件,如果文件中有中文字符的存在会存在乱码的情况,默认输入文件为input.txt,压缩文件为ziped.txt,解压文件为result.txt
文章浏览阅读4.6k次。有时在使用非自己搭建的环境平台时会需要查看系统信息,尤其是系统中编译过多个内核时,我们有时会需要当前使用的是哪个版本的内核。因此,一些查看系统版本以及内核版本信息的命令也是需要掌握的。 对于虚拟化环境而言首先要了解的是其VMM,也称为Hypervisor的版本,例如Xen,我们需要了解它的版本,其信息保存在/sys/hypervisor路径下,执行ls /sys/hyperv_hypervisor版本查询
文章浏览阅读263次。---SOAP绑定组件 o 通过ActiveSOAP提供基于StAX(XML流处理API)的对SOAP栈的支持 o对基于JAXP的Web服务客户端调用、 服务宿主提供支持,并且支持多种协议方式 o 使用反射支持POJO对象的部署。 o 支持Java SOAP附件API和Apache Axis o 通过XFire SOAP栈集成POJO对象支持 o 集成..._servicemix esb
文章浏览阅读3.9k次,点赞42次,收藏32次。共同学习,加入粉丝群哈喽大家好,我是iecne,本期为大家带来的是CPP/C++【游戏引擎Easy2D】炫酷动画来这学,动画入门之位移动画,构造函数让节点执行动画。包教包会,快来看看吧!引擎支持 Visual Studio 2013 及以上版本,如果你使用的是较低版本的 VS,那么你需要考虑一下更新你的编译器了什么是动画直接修改节点的属性会立即生效,体现不出时间的概念,也没有渐变的效果。想让一个精灵执行一段连贯的动画,需要用到 Action 动画类。动画分为普通动画和组合动画。_easy2d 人物移动
文章浏览阅读1.7k次。我是在安装使用Date Picker这个插件时报的这个错Error: EPERM: operation not permitted, rename 'C:\Users\tad\.config\configstore\cordova-config.json.670455402' -> 'C:\Users\tad\.config\configstore\cordova-config.jso..._用fs eperm: operation not permitted, rename
文章浏览阅读1.5k次,点赞4次,收藏16次。一、网站1、http://msdn.microsoft.com/zh-CN/微软的官方网站,C#程序员必去的地方。那里有API开发文档,还有各种代码、资源下载。2、http://social.msdn.microsoft.com/Forums/zh-CN/home微软msdn论坛。定位于微软技术的传播和技术问题的解决,是学习微软技术的好去处。3、https://referenc..._c#学习网站
文章浏览阅读2.2k次。前言本篇博客所写的算法对应于吴恩达教授的机器学习教程里的多元伯努利事件模型的朴素贝叶斯。多元伯努利事件模型的Python代码#!/usr/bin/env python# -*- coding: utf-8 -*-# @Time : 2018/9/415:55# @Author : DaiPuWei# E-Mail : [email protected]#..._python手写实现伯努利贝叶斯分类器
文章浏览阅读956次,点赞2次,收藏11次。FICO模块: FB01创建会计凭证:BAPI_ACC_DOCUMENT_POST 检查会计凭证:BAPI_ACC_DOCUMENT_CHECK FB02修改会计凭证:FI_ITEMS_MASS_CHANGE FB08冲销会计凭证:BAPI_ACC_DOCUMENT_REV_POST FS00创建总账科目:GL_ACCT_MASTER_SAVE AS01创建固定资产:BAPI_FIXEDASSET_CREATE1 AS02更改固定资产转移:BAPI_FIXEDASSET_CHANGE._sap me01 me04货源清单 bapi
文章浏览阅读220次。在`JSONHandler`中,我们定义了几个核心组件:- **JSON Parser (JSON 解析器)**:负责读取和解析JSON数据。- **JSON Writer (JSON 写入器)**:负责将JSON数据写入文件或其他输出流。- **JSON Manipulator (JSON 操作器)**:提供了一系列方法来修改、查询和操作JSON数据。这三个组件是`JSONHandler`的基石,它们确保了数据的正确读取、写入和操作。
文章浏览阅读543次。Algorithm Gossip: 阿姆斯壮数_actan算法 c++
文章浏览阅读429次。本篇文章的主要主要讲述的是对PHP导出的海量数据进行优化,具有一定的参考价值,有需要的朋友可以看看。导出数据量很大的情况下,生成excel的内存需求非常庞大,服务器吃不消,这个时候考虑生成csv来解决问题,cvs读写性能比excel高。测试表student 数据(大家可以脚本插入300多万测数据。这里只给个简单的示例了)SET NAMES utf8mb4;SET FOREIGN_KEY_CHECK..._php大数据优化
文章浏览阅读905次。有道云笔记如何保存网页 有道笔记保存页面教程网页剪报功能支持哪些浏览器?IE,360安全,Firefox,Chrome,搜狗,遨游等主流浏览器。不能收藏网页,原因是没有安装浏览器剪报插件:②点击如下图部门网页剪报”立即体验“。③在弹出”有道云笔记网页剪报“网页对话框,点击如下图”添加到浏览器“。④然后在弹出”确认新增扩展程序“网页对话框中,点击”添加“即可。⑤现在,在浏览器右上角多了一个标记,只需..._有道云笔记装扩展
文章浏览阅读63次。转自:http://www.jeasyui.net/tutorial/23.html本实例演示如何取得选中行数据。数据网格(datagrid)组件包含两种方法来检索选中行数据:getSelected:取得第一个选中行数据,如果没有选中行,则返回 null,否则返回记录。getSelections:取得所有选中行数据,返回元素记录的数组数据。创建数据网格(DataGrid)<..._easyui 获取table选中的一行的值