C++实现哈夫曼树编码解码
作者:qq_36795903 发布时间:2022-02-13 15:48:09
标签: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> * left;
HuffmanNode<T> * right;
T data;
int weight;
public:
HuffmanNode(){}
HuffmanNode(const T& item, HuffmanNode<T> * l, HuffmanNode<T> * r):data(item),left(l),right(r){}
HuffmanNode<T> * getLeft() { return left; }
void setLeft(HuffmanNode<T> * left) { this->left = left; }
HuffmanNode<T> * getRight() { return right; }
void setRight(HuffmanNode<T> * right) { this->right=right; }
T& getData() { return data; }
void setData(const T& item) { data = item; }
int getWeight() { return weight; }
void setWeight(int weight) { this->weight = weight; }
};
/*哈夫曼树类HuffmanTree声明*/
template<class T>
class HuffmanTree {
private:
HuffmanNode<T> * root;
T data[m];
int weight[m];
int count;
public:
HuffmanTree(HuffmanNode<T> * t=NULL):root(t){}
void CreateHuffmanTree();//创建哈夫曼树
HuffmanNode<T> * getRoot() { return root; }
void setRoot(HuffmanNode<T> * t) { root = t; }
void inputNodes();//输入各个结点的data和weight值
HuffmanNode<T> * deCode(HuffmanNode<T>*t,T item);
void showCode();
};
template<class T>
inline void HuffmanTree<T>::CreateHuffmanTree()
{
inputNodes();
HuffmanNode<T> ** H = new HuffmanNode<T>*[count];
HuffmanNode<T> * p1 = NULL, *p2 = NULL, * p,* t;
for (int i = 0; i < count; i++) {
H[i] = new HuffmanNode<T>();
H[i]->setData(data[i]);
H[i]->setWeight(weight[i]);
H[i]->setLeft(NULL);
H[i]->setRight(NULL);
}
for (int i = 0; i < count - 1; i++) {
p = new HuffmanNode<T>();
p1 = H[i];
p2 = H[i + 1];
p->setLeft(p1);
p->setRight(p2);
p->setWeight(p1->getWeight() + p2->getWeight());
//将新的结点插入结点数组中的合适位置,并将被合并的两个结点删除
t = p;
int j = i + 2;
while ( j < count &&H[j]->getWeight() < t->getWeight()) {
H[j - 1] = H[j];
j++;
}
H[j - 1] = t;
}
root = H[count - 1];
}
template<class T>
inline void HuffmanTree<T>::inputNodes()
{
int i = 0;
for (int j = 0; j < m; j++) {
data[j] = NULL;
weight[j] = 0;
}
while (cin >> data[i] >> weight[i]) {
i++;
}
count = i;
}
template<class T>
inline HuffmanNode<T>* HuffmanTree<T>::deCode( HuffmanNode<T> * t,T item)
{
HuffmanNode<T> * p, * q;
if(t==NULL)
return NULL;
if (t->getData() == item)
return t;
if ((p = deCode(t->getLeft(), item))!=NULL) {
s.push(0);
return p;
}
else if((q = deCode(t->getRight(), item))!=NULL){
s.push(1);
return q ;
}
}
template<class T>
inline void HuffmanTree<T>::showCode()
{
cout << root->getWeight() << endl;
cout << (root->getLeft())->getRight()->getData() << endl;
for (int i = 0; i < count; i++) {
cout << data[i] << "——";
deCode(root, data[i]);
while (!s.empty()) {
cout << s.top();
s.pop();
}
cout << endl;
}
}
测试程序:
#include<iostream>
#include"HuffmanTree.h"
using namespace std;
int main() {
HuffmanTree<char> * tree = new HuffmanTree<char>();
tree->CreateHuffmanTree();
tree->showCode();
system("pause");
return 0;
}
测试数据:
n 1
s 3
t 4
a 10
i 12
p 13
e 15
Ctrl+Z 回车结束输入
输入时权值由小到大排序…也可以在程序里加一个排序
结果:
来源:https://blog.csdn.net/qq_36795903/article/details/89916203
0
投稿
猜你喜欢
- 本文实例为大家分享了Android简单的自定义标题栏,供大家参考,具体内容如下android自定义控件向来都是开发者最头疼的,但是我们要有那
- 使用到的类:net.sf.json.JSONObject 使用JSON时,除了要导入JSON网站上面下载的json-lib-2.2
- 比如:int (*foo)(int arg),记住要和另一个指针函数区分开来,类似这样:int *foo(int arg).比如我们可以这样
- 窗口之间通信无非有两个方向,主窗口发送数据到副窗口,副窗口发送数据到主窗口。代码在最下面,先看一下解决的思路。首先是简单的主窗口传数据到副窗
- Java单例模式的实现,对java 单例模式的几种实现方法进行了整理:单例模式好多书上都是这么写的:public class SingleT
- SurfaceView和TextureView均继承于android.view.View与其它View不同的是,两者都能在独立的线程中绘制和
- 什么是fescar?关于fescar的详细介绍,请参阅fescar wiki。传统的2PC提交协议,会持有一个全局性的锁,所有局部事务预提交
- 完美地模仿了2048游戏,是根据网友的一个2048改的。Block.javaimport javax.swing.*;import java
- 1. 场景描述本节结合springboot2、springmvc、mybatis、swagger2等,搭建一个完整的增删改查项目,希望通过这
- 这个小游戏是我和我姐们儿的JAVA课程设计,也是我做的第一个JAVA项目,适合初学者,希望能帮到那些被JAVA课设所困扰的孩纸们~~~一、该
- //把txt清空 &n
- springboot 配置多个jndi数据源1.在application.properties中,添加jndi配置如下图2.新建dataSo
- Spring Data JPA 映射VO/DTO对象在项目开发中,时常需要根据业务需求来映射VO/DTO对象(这两个概念理解感觉很模糊- 。
- 一、什么是HTTP协议HTTP是hypertext transfer protocol(超文本传输协议)的简写,它是TCP/IP协议的一个应
- 前言在现实项目中,数据量一般都不小,如果一次性全部请求出来,肯定是影响性能,而且大量数据展示到页面上观感也不好。这时我们就需要用到分页,给定
- ReadWriteLock 和 ReentrantReadWriteLock介绍ReadWriteLock,顾名思义,是读写锁。它维护了一对
- 背景spring的profile大家都是用的溜的飞起~那么profile的组合如何使用呢???比如我们这样使用@Profile({"
- 本文列举了几个方法: 1. 使用java.math.BigDecimal &n
- 前言很久没有写关于 Spring 的文章了,最近在系统梳理 Dubbo 代码的过程中发现了 XML schema 这个被遗漏的知识点。由于工
- 本文所述实例实现WinForm自定义函数FindControl实现按名称查找控件的功能,在C#程序开发中有一定的实用价值。分享给大家供大家参