C++实现哈夫曼编码

2024-12-10 05:14:02

本文实例为大家分享了C++实现哈夫曼编码的具体代码，供大家参考，具体内容如下

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int Max = 300;

class tree{
 public:
 char s;
 int num;
 tree *left;
 tree *right;
 tree(){
  s= '!';
  num = 0;
  left = 0;
  right = 0;
 }
 tree(char a,int n,tree* p1,tree* p2){
  s = a;
  num = n;
  left = p1;
  right = p2;
 }
};

vector<tree *> open;

/*********************************
**中序遍历输出各节点及其哈夫曼编码
*********************************/
void inorder(tree *t,string s){
 if(t != 0){
 inorder(t->left,s+'0');
 if(t->s != '!')
  cout<<t->s<<":"<<s<<endl;
 inorder(t->right,s+'1');
 }
}

int main(){
 int a[Max];
 for(int i = 0;i < Max;i++)
 a[i] = 0;  //初始化数组
 string s;
 cout<<"请输入字符串：";
 cin>>s;

 vector<char> v;
 vector<char>::iterator vit;
 for(int i = 0;i < s.length();i ++){
 a[s[i]]++;  //确定每个字符出现的次数（频率）
 vit = find(v.begin(),v.end(),s[i]);
 if(vit == v.end()) //相同的字符只保留一个
  v.push_back(s[i]);
 }
 for(int i = 0;i < v.size();i ++){
 tree *n = new tree();
 n->s = v[i];
 n->num = a[v[i]];
 open.push_back(n); //存入open表中
 }

 /************************
 **
 **构造哈夫曼树
 **
 *************************/
 tree *root;
 while(open.size() != 1){
 tree *min1,*min2; //min1,min2是当前open表中num值最小的节点
 int sit1,sit2;
 min1 = open.front();
 sit1 = 0;
 for(int i = 0;i < open.size();i++){
  if(open[i]->num < min1->num){
  min1 = open[i];
  sit1 = i;
  }
 }
 open.erase(open.begin()+sit1);

 min2 = open.front();
 sit2 = 0;
 for(int i = 0;i < open.size();i++){
  if(open[i]->num < min2->num){
  min2 = open[i];
  sit2 = i;
  }
 }
 open.erase(open.begin()+sit2);

 tree *t = new tree('!',min1->num + min2->num,min1,min2); //构造新节点，左右指针指min1和min2
 open.push_back(t); //存入open表中
 root = t;
 }

 cout<<"它的哈夫曼编码为："<<endl;
 string s1 = "";
 inorder(root,s1);

 return 0;
}```

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

C++数据结构之文件压缩（哈夫曼树）实例详解

C++数据结构之文件压缩(哈夫曼树)实例详解概要: 项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压开发环境:windows vs2013 项目概述: 1.压缩 a.读取文件,将每个字符,该字符出现的次数和权值构成哈夫曼树 b.哈夫曼树是利用小堆构成,字符出现次数少的节点指针存在堆顶,出现次数多的在堆底 c.每次取堆顶的两个数,再将两个数相加进堆,直到堆被取完,这时哈夫曼树也建成 d.从哈夫曼树中获取哈夫曼编码,然后再根据整个字符数组来获取出现了得字符的编
C++实现哈夫曼树简单创建与遍历的方法

本文以实例形式讲述了C++实现哈夫曼树简单创建与遍历的方法,比较经典的C++算法. 本例实现的功能为:给定n个带权的节点,如何构造一棵n个带有给定权值的叶节点的二叉树,使其带全路径长度WPL最小. 据此构造出最优树算法如下: 哈夫曼算法: 1. 将n个权值分别为w1,w2,w3,....wn-1,wn的节点按权值递增排序,将每个权值作为一棵二叉树.构成n棵二叉树森林F={T1,T2,T3,T4,...Tn},其中每个二叉树都只有一个权值,其左右字数为空 2. 在森林F中选取根节点权值最小二叉树,
基于C++实现的哈夫曼编码解码操作示例

本文实例讲述了基于C++实现的哈夫曼编码解码操作.分享给大家供大家参考,具体如下: 哈夫曼编码是一个通过哈夫曼树进行的一种编码,一般情况下,以字符:'0'与'1'表示.编码的实现过程很简单,只要实现哈夫曼树,通过遍历哈夫曼树,这里我们从每一个叶子结点开始向上遍历,如果该结点为父节点的左孩子,则在字符串后面追加"0",如果为其右孩子,则在字符串后追加"1".结束条件为没有父节点.然后将字符串倒过来存入结点中. C++实现代码如下: #include<iostre
C++数据结构与算法之哈夫曼树的实现方法

本文实例讲述了C++数据结构与算法之哈夫曼树的实现方法.分享给大家供大家参考,具体如下: 哈夫曼树又称最优二叉树,是一类带权路径长度最短的树. 对于最优二叉树,权值越大的结点越接近树的根结点,权值越小的结点越远离树的根结点. 前面一篇图文详解JAVA实现哈夫曼树对哈夫曼树的原理与java实现方法做了较为详尽的描述,这里再来看看C++实现方法. 具体代码如下: #include <iostream> using namespace std; #if !defined(_HUFFMANTREE_H
C++实现哈夫曼树算法

如何建立哈夫曼树的,网上搜索一堆,这里就不写了,直接给代码. 1.哈夫曼树结点类:HuffmanNode.h #ifndef HuffmanNode_h #define HuffmanNode_h template <class T> struct HuffmanNode { T weight; // 存储权值 HuffmanNode<T> *leftChild, *rightChild, *parent; // 左.右孩子和父结点 }; #endif /* HuffmanNode
解析C++哈夫曼树编码和译码的实现

一．背景介绍: 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 二．实现步骤: 1.构造一棵哈夫曼树 2.根据创建好的哈夫曼树创建一张哈夫曼编码表 3.输入一串哈夫曼序列,输出原始字符三．设计思想: 1.首先要构造一棵哈夫曼树,哈夫曼树的结点结构包括权值,双亲,左右孩子:假如由n个字符来构造一棵哈夫曼树,则共有结点2n-1个:在构造前,先初始化
C++ 哈夫曼树对文件压缩、加密实现代码

在以前写LZW压缩算法的时候,遇到很多难受的问题,基本上都在哈夫曼编码中解决了,虽然写这代码很费神,但还是把代码完整的码出来了,毕竟哈夫曼这个思想确实很牛逼.哈夫曼树很巧妙的解决了当时我在LZW序列化的时候想解决的问题,就是压缩后文本的分割.比如用lzw编码abc,就是1,2,3.但这个在存为文件的时候必须用分割符把1,2,3分割开,非常浪费空间,否则会和12 23 123 产生二义性.而哈夫曼树,将所有char分布在叶节点上,在还原的时候,比如1101110,假设110是叶节点,那么走到110
C++实现Huffman的编解码

Huffman编码主要是通过统计各元素出现的频率,进而生成编码最终达到压缩的目的. 这里是Huffman树中节点的结构. typedef struct Tree { int freq;//频率 int key;//键值 struct Tree *left, *right; Tree(int fr=0, int k=0,Tree *l=nullptr, Tree *r=nullptr): freq(fr),key(k),left(l),right(r){}; }Tree,*pTree; 首先用一个
C++实现哈夫曼树编码解码

本文实例为大家分享了C++实现哈夫曼树的编码解码,供大家参考,具体内容如下代码: #pragma once #include<iostream> #include<stack> using namespace std; #define m 20 stack<int> s; /*哈夫曼树结点类HuffmanNode声明*/ template<class T> class HuffmanNode { private: HuffmanNode<T>
JS实现的哈夫曼编码示例【原始版与修改版】

本文实例讲述了JS实现的哈夫曼编码.分享给大家供大家参考,具体如下: 原始版 function cal(str) { if (typeof str !== 'string' || str.length < 1) { return; } var map = {}; var i = 0; while(str[i]) { map[str[i]] ? map[str[i]]++ : (map[str[i]] = 1); i++; } return map; } function sort(map) {
C语言实现哈夫曼编码

本文实例为大家分享了C语言实现哈夫曼编码的具体代码,供大家参考,具体内容如下代码来自于<小甲鱼C++快速入门> 主程序main.cpp #include "stdafx.h" #include <stdlib.h> #include "huffman.h" int main() { htTree *codeTree = buildTree("I love wwwwwwwwwFishC.com!");//建立哈夫曼树 hl
C++实现哈夫曼编码

本文实例为大家分享了C++实现哈夫曼编码的具体代码,供大家参考,具体内容如下 #include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; int Max = 300; class tree{ public: char s; int num; tree *left; tree *right; tree(){ s= '!'; num =
用R语言实现霍夫曼编码的示例代码

可读性极低,而且其实也没必要用R语言写,图个乐罢了 p=c(0.4,0.2,0.2,0.1,0.1)###输入形如c(0.4,0.2,0.2,0.1,0.1)的概率向量,即每个待编码消息的发生概率 p1=p###将概率向量另存,最后计算编码效率要用 mazijuzhen=matrix(,nrow=length(p),ncol=length(p)-1)###码字矩阵:第i行对应向量p的第i个分量所对应的那个待编码消息的编码后的码字 group=matrix(c(1:length(p),rep(NA
C语言实现BMP图像处理(哈夫曼编码)

哈夫曼(Huffman)编码是一种常用的压缩编码方法,是 Huffman 于 1952 年为压缩文本文件建立的.它的基本原理是频繁使用的数据用较短的代码代替,较少使用的数据用较长的代码代替,每个数据的代码各不相同.这些代码都是二进制码,且码的长度是可变的. 下面给出具体的 Huffman 编码算法: (1) 首先统计出每个符号出现的频率,上例 S0 到 S7 的出现频率分别为 4/14,3/14,2/14,1/14,1/14,1/14,1/14,1/14. (2) 从左到右把上述频率按从小到大的
利用Python和C语言分别实现哈夫曼编码

目录 1.C语言实现 1.1代码说明 1.2运行结果 2.Python实现 2.1代码说明 2.2运行结果 1.C语言实现 1.1代码说明 a 创建双向链表: 在创建哈夫曼树的过程中,需要不断对结点进行更改和删除,所以选用双向链表的结构更容易 '''C #include <stdlib.h> #include <stdio.h> #include <windows.h> //哈夫曼树结构体,数据域存储字符及其权重 typedef struct node { char
Java利用哈夫曼编码实现字符串压缩

赫夫曼编码基本介绍 1) 赫夫曼编码也翻译为哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法 2) 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一. 3) 赫夫曼编码广泛地用于数据文件压缩.其压缩率通常在 20%-90%之间 4) 赫夫曼码是可变字长编码(VLC)的一种.Huffman 于 1952 年提出一种编码方法,称之为最佳编码在通信领域中几种信息处理方式的区别(以字符串" i like like like java do you li
如何用Java实现啥夫曼编码

大家可能会想,程序和第三方提供了很多压缩方式,何必自己写压缩代码呢?不错,如GZIP这样的压缩工具很多,可是在某些情况下(如文本内容小且字符不重复),GZIP压缩后会比原始文本还要大.所以在某些特殊情况下用自己的压缩方式可以更优. 大家可能早已忘记了在学校学习的哈夫曼知识,可以先在百度百科了解一下哈夫曼知识:http://baike.baidu.com/view/127820.htm 哈夫曼思想:统计文本字符重复率,求出各字符权值,再构造出一颗最优二叉树(又称哈夫曼树),然后给每个叶子结点生成一

C++实现哈夫曼编码

相关推荐

随机推荐