当前位置：首页 > 编程日记 > 正文

huffman树和huffman编码

编程日记 2024-08-01 13:30:00

不知道为什么，我写的代码都是又臭又长。

直接上代码：

#include <iostream>
#include <cstdarg>
using namespace std;
class Node{
public:int weight;int parent, lChildren, rChildren;Node(int weight, int parent, int lChildren, int rChildren):weight(weight), parent(parent), lChildren(lChildren), rChildren(rChildren){}void printNode(){cout<<"weight = "<<weight<<", ";cout<<"parent = "<<parent<<", ";cout<<"lChildren = "<<lChildren<<", ";cout<<"rChildren = "<<rChildren<<endl;}
};class Tree{Node **nodes;char** huffmanCodec;int length,rPos;int mNum;/**给Tree实例增加Node。***/void addNode(Node *node){if(!node){cout<<"addNode中，指针为NULL"<<endl;return;}for(int i = 0; i < length; i++){if(node == nodes[i])//如果存在了就不必加到里面了。。return;}nodes[length++] = node;}/**从数组array中找到最小的两个数值，赋给v1和v2***/void findSmallest2ValueInArray(int *array, int length, int *v1, int *v2, int *v1Pos, int *v2Pos){int t = 0;for(int i = 0; i < length; i++){if(array[i] < 0)continue;++t;if(t == 1){*v1 = array[i];*v1Pos = i;}else if (t == 2){*v2 = array[i];*v2Pos = i;}else{if(*v1 > array[i]){if(*v1 < *v2){*v2 = *v1;*v2Pos = *v1Pos;}*v1 = array[i];*v1Pos = i;}else if(*v2 > array[i]){*v2 = array[i];*v2Pos = i;}}}}/***从当前Tree中找到给定node的下标。生成huffman编码用的。***/int findNodePosViaNode(Node *node){for(int i = 0; i < length; i++){if(nodes[i] == node){return i;}}return -1;}/***从当前Tree中找到给定Weight的node的下标, 并且该node没有parent。生成树结构用的。***/int findNodePosViaWeight(int value, bool isForParent, bool isTheSameWeightNode){for(int i = 0; i < length; i++){if(nodes[i]->parent == -1 && nodes[i]->weight == value && !isForParent && !isTheSameWeightNode){return i;}}return -1;}/***从头至尾找到叶子结点。***/int findHuffmanNodePos(){static int mark;//默认初始化为0for(int i = mark; i < length; i++){if(nodes[i]->lChildren == -1 && nodes[i]->rChildren == -1){mark = i + 1;return i;}}return -1;}/***初始化node***/Node* getNode(Node *node, int value, int parent, int lChildren, int rChildren, bool isForParent, bool isTheSameWeightNode){//最后一个参数，解决这种情况，如果v1是20，//并且v1已经在树中了，然后v2也是20.//这时候要求v2要new一个新的节点。if(node){cout<<"getNode中，指针未初始化为NULL"<<endl;return NULL;}int pos = findNodePosViaWeight(value, isForParent, isTheSameWeightNode);if(pos != -1){node = nodes[pos];}else{node = new Node(value, parent, lChildren, rChildren);}return node;}/***把一个数组初始化为全是-1的数组。***/void initArray2Zero(int *array, int length){for(int i = 0; i < length; i++){array[i] = -1;}}/***打印一个int数组*/void printIntArray(int *array, int length){cout<<"[";for(int i = 0; i < length - 1; i++){cout<<array[i]<<", ";}cout<<array[length - 1]<<"]"<<endl;}/***for debug*/void debug(int i){cout<<"debug "<<i<<endl;}/***根据huffman树生成huffman编码。*/char** generateHuffmanCodec(int num){int topIndex = 0;huffmanCodec = new char*[num];//分配空间for(int i = 0; i < num; i++){int index = 0;char *data = new char[num + 1];//每一个节点的存储单位int thisPos = findHuffmanNodePos();Node *currentNode = nodes[thisPos];while(currentNode->parent != -1){Node *currentParent = nodes[currentNode->parent];if(thisPos == currentParent->lChildren){//0data[index++] = '0';}else if(thisPos == currentParent->rChildren){//1data[index++] = '1';}else{//X, never in.data[index++] = 'X';}thisPos = currentNode->parent;currentNode = currentParent;}data[index] = '\0';huffmanCodec[topIndex++] = data;}return huffmanCodec;}public:/***创造一棵树。***/void makeTree(int num, ...){int weightArray[num];initArray2Zero(weightArray, num);va_list list;va_start(list, num);for(int i = 0; i < num; i++){weightArray[i] = va_arg(list, int);}va_end(list);printIntArray(weightArray, num);//debugint debug_x = 100;while(true){int v1 = -1, v2 = -1, v1Pos = -1, v2Pos = -1;findSmallest2ValueInArray(weightArray, num, &v1, &v2, &v1Pos, &v2Pos);if(v1 == -1 || v2 == -1){cout<<"v1或v2至少有一个是-1, 没被赋值"<<endl;break;}Node *node1 = NULL;node1 = getNode(node1, v1, -1, -1, -1, false, false);addNode(node1);//如果已经存在就不必add。Node *node2 = NULL;node2 = getNode(node2, v2, -1, -1, -1, false, v1 == v2);//万一v1和v2相等，如果不加这个force，那么本来有2个权值相等的节点，就会少添加到树中一个。addNode(node2);Node *parent = NULL;parent = getNode(parent, v1 + v2, -1, -1, -1, true, false);//最后这个参数，在于判断是否是寻找的是parent。如果是parent，那么就算树中已经存在了相同节点，但是也要new一个新节点。//因为树中的节点不是已经有了孩子 就是叶子节点了。都不能做parent了，所以要重新生成。addNode(parent);node1->parent = findNodePosViaNode(parent);node2->parent = node1->parent;parent->lChildren = findNodePosViaNode(node1);parent->rChildren = findNodePosViaNode(node2);weightArray[v1Pos] = -1;weightArray[v2Pos] = v1 + v2;printIntArray(weightArray, num);//debug}mNum = num;generateHuffmanCodec(num);        }/***打印huffman树***/void printTree(){for(int i = 0; i < length; i++){cout<<"pos = "<<i<<", ";nodes[i]->printNode();//cout<<findHuffmanNodePos()<<endl;}}/***打印哈夫曼编码*/void printHuffman(){cout<<"------huffman codec begin-----\n";for(int i = 0; i < mNum; i++){cout<<huffmanCodec[i]<<endl;}cout<<"------huffman codec end-----\n";}/***构造函数与析构函数*/Tree(): nodes(new Node*[100]), huffmanCodec(NULL), length(0), rPos(-1), mNum(0){//为何是int呢？因为我想数组中存储的是Node*,是一个指针，指针应该可以用int来存储。}~Tree(){cout<<"析构"<<endl;delete []nodes;if(huffmanCodec) delete []huffmanCodec;}
};int main(){Tree *tree = new Tree;tree->makeTree(8, 5, 29, 7, 8, 14, 23, 3, 11);tree->printTree();tree->printHuffman();delete tree;
}

书上的例子才30行代码，我写了300行，为什么会这样呢，挺奇怪的，估计还是修炼不够。得努力！

https://www.dkcj.cn/info/12356.html

react 监听组合键_投资组合中需要的5个React项目

react 监听组合键Youve put in the work and now you have a solid understanding of the React library.您已经完成工作，现在对React库有了扎实的了解。 On top of that, you have a good grasp of JavaScript and are putting its most helpful features to use …

编程日记2024/08/01 13:20:00

Unity 单元测试(PLUnitTest工具)

代码测试的由来上几个星期上面分配给我一个装备系统,我经过了几个星期的战斗写完90%的代码. 后来策划告诉我需求有一定的改动,我就随着策划的意思修改了代码. 但是测试(Xu)告诉我装备系统很多功能都用不上了. Xu: 我有300多项测试用例,现在有很多项都无法运行了. 你修改了部分…

编程日记2024/08/01 13:10:00

Best Time to Buy and Sell Stock II

题目： Say you have an array for which the i th element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multipl…

编程日记2024/08/01 13:00:00

求给定集合的幂集

数据结构中说这个问题可以用类似8皇后的状态树解法。把求解过程看成是一棵二叉树，空集作为root，然后遍历给定集合中的元素，左子树表示取该元素，右子树表示舍该元素。然后，root的左右元素分别重复上述过程。就形成…

编程日记2024/08/01 12:50:00

angular 命令行项目_Angular命令行界面介绍

angular 命令行项目Angular is closely associated with its command-line interface (CLI). The CLI streamlines generation of the Angular file system. It deals with most of the configuration behind the scenes so developers can start coding. The CLI also has a l…

编程日记2024/08/01 12:40:00

oracle-imp导入小错filesize设置

***********************************************声明*********************************************************************** 原创作品，出自 “深蓝的blog” 博客。欢迎转载，转载时请务必注明出处。否则追究版权法律责任。表述有错误之处&#xf…

编程日记2024/08/01 12:30:00

CentOS 7 下用 firewall-cmd / iptables 实现 NAT 转发供内网服务器联网

自从用 HAProxy 对服务器做了负载均衡以后，感觉后端服务器真的没必要再配置并占用公网IP资源。而且由于托管服务器的公网 IP 资源是固定的，想上 Keepalived 的话，需要挤出来 3 个公网 IP 使用，所以更加坚定了让负载均衡后端服务器…

编程日记2024/08/01 12:20:00

八皇后的一个回溯递归解法

解法来自严蔚敏的数据结构与算法。代码如下： #include <iostream> using namespace std; const int N 8;//皇后数 int count 0;//解法统计 int a[N][N];//储存值的数组const char *YES "■"; const char *NO "□"; //const char *Y…

编程日记2024/08/01 12:10:00

即时编译和提前编译_即时编译说明

即时编译和提前编译Just-in-time compilation is a method for improving the performance of interpreted programs. During execution the program may be compiled into native code to improve its performance. It is also known as dynamic compilation.即时编译是一种提…

编程日记2024/08/01 12:00:00

bzoj 2588 Spoj 10628. Count on a tree （可持久化线段树）

Spoj 10628. Count on a tree Time Limit: 12 Sec Memory Limit: 128 MBSubmit: 7669 Solved: 1894[Submit][Status][Discuss]Description 给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点…

编程日记2024/08/01 11:50:00

.Net SqlDbHelper

using System.Configuration; using System.Data.SqlClient; using System.Data;namespace ExamDAL {class SqHelper{#region 属性区// 连接字符串private static string strConn;public static string StrConn{get{return ConfigurationManager.ConnectionStrings["Exam&…

编程日记2024/08/01 11:40:00

C语言的一个之前没有见过的特性

代码： #include <stdio.h>int test(){int a ({int aa 0;int bb 1;int cc 2;if(aa 0 && bb 1)printf("aa %d, bb %d\n", aa, bb);//return -2;cc;});return a; }int main(){typeof(4) a test();printf("a %d\n", a); } …

编程日记2024/08/01 11:30:00

如何构建顶部导航条_如何构建导航栏

如何构建顶部导航条导航栏 (Navigation Bars) Navigation bars are a very important element to any website. They provide the main method of navigation by providing a main list of links to a user. There are many methods to creating a navigation bar. The easiest…

编程日记2024/08/01 11:20:00

SPSS聚类分析：K均值聚类分析

SPSS聚类分析：K均值聚类分析一、概念：（分析-分类-K均值聚类） 1、此过程使用可以处理大量个案的算法，根据选定的特征尝试对相对均一的个案组进行标识。不过，该算法要求您指定聚类的个数。如果知道&#xff…

编程日记2024/08/01 11:10:00

[ 总结 ] nginx 负载均衡及缓存

操作系统：centos6.4 x64 前端使用nginx做反向代理，后端服务器为：apache php mysql 1. nginx负载均衡。 nginx编译安装（编译安装前面的文章已经写过）、apache php mysql 直接使用yum安装。 nginx端口：80…

编程日记2024/08/01 11:00:00

中国剩余定理(孙子定理)的证明和c++求解

《孙子算经》里面的"物不知数"说的是这样的一个题目：一堆东西不知道具体数目，3个一数剩2个，5个一数剩3个，7个一数剩2个，问一共有多少个。书里面给了计算过程及答案：70*2 21*3 15*2 -105*2 2…

编程日记2024/08/01 10:50:00

osi七层网络层_OSI层速成课程

osi七层网络层介绍 (Introduction) Have you ever wondered how data is sent through the network from one machine to another? If yes, then the Open System Interconnected model is what you are looking for.您是否曾经想过如何通过网络将数据从一台机器发送到另一台机…

编程日记2024/08/01 10:40:00

KMP算法求回溯数组的步骤

KMP算法到底是什么原理就不说了，各种资料上讲的明明白白，下面我就如何用代码来实现做一下说明和记录. KMP的核心思想就是，主串不回溯，只模式串回溯。而模式串匹配到第几位时失配，要回溯多少，由模式串本身来…

编程日记2024/08/01 10:30:01

【.Net】vs2017 自带发布工具 ClickOnce发布包遇到的问题

一、遇到的问题在安装了vs2017 社区版（Community）之后想打包安装程序（winform） 还是想用之前的 installshield来打包发现居然打不了，在官网查了 installshield不支持社区版（Community）&…

编程日记2024/08/01 10:20:00

windows平台，开发环境变量配置

1.打开我的电脑--属性--高级--环境变量 JAVA配置环境变量变量名：JAVA_HOME 变量值：C:\Program Files\Java\jdk1.7.0 变量名：CLASSPATH 变量值：.;%JAVA_HOME%\lib\dt.jar;%JAVA_HOME%\lib\tools.jar; 变量名：Path 变…

编程日记2024/08/01 10:10:00

如何编写可测试的代码哈利勒的方法论

Understanding how to write testable code is one of the biggest frustrations I had when I finished school and started working at my first real-world job. 当我完成学业并开始从事第一份现实世界的工作时，了解如何编写可测试的代码是我最大的挫败之一。 T…

编程日记2024/08/01 10:00:00

【Java入门提高篇】Day6 Java内部类——成员内部类

内部类是什么，简单来说，就是定义在类内部的类（一本正经的说着废话）。一个正经的内部类是长这样的： public class Outer {class Inner{} } 这是为了演示而写的类，没有什么luan用，可以看到Inner类…

编程日记2024/08/01 09:50:00

POJ 1001(高精度乘法 java的2种解法)

方法1: import java.math.BigDecimal; import java.util.Scanner; public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);while(sc.hasNext()){String d sc.next();int z sc.nextInt();BigDecimal bd new BigDecimal(d);BigDeci…

编程日记2024/08/01 09:40:00