本站首页 收藏本站
广告位联系

APP正在开发中...
返回顶部
您的位置： 主页 > 软件编程 > C#教程 >

收藏
分享到

C++实现哈夫曼树算法的介绍

C#教程 来源：互联网搜集 作者：秩名 发布时间：2020-04-27 21:10:43 人浏览
摘要

如何建立哈夫曼树的，网上搜索一堆，这里就不写了，直接给代码。 1.哈夫曼树结点类：HuffmanNode.h ? 1 2 3 4 5 6 7 8 9 10 #ifndef HuffmanNode_h #define HuffmanNode_h template class T struct HuffmanNode { T weight; // 存储权值 HuffmanNodeT *leftC

如何建立哈夫曼树的，网上搜索一堆，这里就不写了，直接给代码。

1.哈夫曼树结点类：HuffmanNode.h

?
1
2
3
4
5
6
7
8
9
10
#ifndef HuffmanNode_h
#define HuffmanNode_h
 
template <class T>
struct HuffmanNode {
 T weight; // 存储权值
 HuffmanNode<T> *leftChild, *rightChild, *parent; // 左、右孩子和父结点
};
 
#endif /* HuffmanNode_h */
 

2.哈夫曼树最小堆：HuffmanMinHeap.h

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#ifndef HuffmanMinHeap_h
#define HuffmanMinHeap_h
 
#include "HuffmanNode.h"
#include <iostream>
using namespace std;
 
const int DefaultSize = 100;
 
template <class T>
class MinHeap {
public:
 MinHeap(); // 构造函数
 ~MinHeap(); // 析构函数
 void Insert(HuffmanNode<T> *current); // 插入
 HuffmanNode<T> *getMin(); // 获取最小结点
private:
 HuffmanNode<T> *heap; // 动态数组存储最小堆
 int CurrentSize; // 目前最小堆的结点数
 void ShiftUp(int start); // 向上调整
 void ShiftDown(int start, int m); // 下滑
};
 
// 构造函数
template <class T>
MinHeap<T>::MinHeap() {
 heap = new HuffmanNode<T>[DefaultSize]; // 创建堆空间
 CurrentSize = 0;
}
 
// 析构函数
template <class T>
MinHeap<T>::~MinHeap() {
 delete []heap; // 释放空间
}
 
// 插入
template <class T>
void MinHeap<T>::Insert(HuffmanNode<T> *current) {
 if(CurrentSize == DefaultSize) {
  cout << "堆已满" << endl;
  return;
 }
 // 把current的数据复制到“数组末尾”
 heap[CurrentSize] = *current;
 // 向上调整堆
 ShiftUp(CurrentSize);
 CurrentSize++;
}
 
// 获取最小结点并在堆中删除该结点
template <class T>
HuffmanNode<T> *MinHeap<T>::getMin() {
 if(CurrentSize == 0) {
  cout << "堆已空!" << endl;
  return NULL;
 }
 HuffmanNode<T> *newNode = new HuffmanNode<T>();
 if(newNode == NULL) {
  cerr << "存储空间分配失败！" << endl;
  exit(1);
 }
 *newNode = heap[0]; // 将最小结点的数据复制给newNode
 heap[0] = heap[CurrentSize-1]; // 用最后一个元素填补
 CurrentSize--;
 ShiftDown(0, CurrentSize-1); // 从0位置开始向下调整
 return newNode;
}
 
// 向上调整
template <class T>
void MinHeap<T>::ShiftUp(int start) {
 // 从start开始，直到0或者当前值大于双亲结点的值时，调整堆
 int j = start, i = (j-1)/2; // i是j的双亲
 
 HuffmanNode<T> temp = heap[j];
 while(j > 0) {
  if(heap[i].weight <= temp.weight)
   break;
  else {
   heap[j] = heap[i];
   j = i;
   i = (j - 1) / 2;
  }
 }
 heap[j] = temp;
}
 
// 向下调整
template <class T>
void MinHeap<T>::ShiftDown(int start, int m) {
 int i = start, j = 2 * i + 1; // j是i的左子女
 
 HuffmanNode<T> temp = heap[i];
 while(j <= m) {
  if(j < m && heap[j].weight > heap[j+1].weight)
   j++; // 选两个子女中较小者
  if(temp.weight <= heap[j].weight)
   break;
  else {
   heap[i] = heap[j];
   i = j;
   j = 2 * j + 1;
  }
 }
 heap[i] = temp;
}
 
 
#endif /* HuffmanMinHeap_h */
 

3.哈夫曼树实现：HuffmanTree.h

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#ifndef HuffmanTree_h
#define HuffmanTree_h
 
 
#include "HuffmanMinHeap.h"
#include "HuffmanNode.h"
 
template <class T>
class HuffmanTree {
public:
 HuffmanTree(); // 构造函数
 ~HuffmanTree(); // 析构函数
 void Create(T w[], int n); // 创建哈夫曼树
 void Merge(HuffmanNode<T> *first, HuffmanNode<T> *second, HuffmanNode<T> *parent); // 合并
 void PreOrder(); // 前序遍历Huffman树
private:
 HuffmanNode<T> *root; // 根结点
 void Destroy(HuffmanNode<T> *current); // 销毁哈夫曼树
 void PreOrder(HuffmanNode<T> *current); // 前序遍历Huffman树
};
 
// 构造函数
template <class T>
HuffmanTree<T>::HuffmanTree() {
 root = NULL;
}
 
// 析构函数
template <class T>
HuffmanTree<T>::~HuffmanTree() {
 Destroy(root); // 销毁哈夫曼树
}
 
// 销毁哈夫曼树
template <class T>
void HuffmanTree<T>::Destroy(HuffmanNode<T> *current) {
 if(current != NULL) { // 不为空
  Destroy(current->leftChild); // 递归销毁左子树
  Destroy(current->rightChild); // 递归销毁右子树
  delete current; // 释放空间
  current = NULL;
 }
}
 
// 创建哈夫曼树
template <class T>
void HuffmanTree<T>::Create(T w[], int n) {
 int i;
 MinHeap<T> hp; // 使用最小堆存放森林
 HuffmanNode<T> *first, *second, *parent = NULL;
 HuffmanNode<T>*work = new HuffmanNode<T>();
 
 if(work == NULL) {
  cerr << "存储空间分配失败！" << endl;
  exit(1);
 }
 for(i = 0; i < n; i++) {
  work->weight = w[i];
  work->leftChild = work->rightChild = work->parent = NULL;
  hp.Insert(work); // 插入到最小堆中
 }
 for(i=0; i < n-1; i++) { // 做n-1趟，形成Huffman树
  first = hp.getMin(); // 获取权值最小的树
  second = hp.getMin(); // 获取权值次小的树
  parent = new HuffmanNode<T>();
  if(parent == NULL) {
   cerr << "存储空间分配失败！" << endl;
   exit(1);
  }
  Merge(first, second, parent); // 合并
  hp.Insert(parent); // 重新插入到最小堆中
 }
 root = parent; // 根结点
}
// 合并
template <class T>
void HuffmanTree<T>::Merge(HuffmanNode<T> *first, HuffmanNode<T> *second, HuffmanNode<T> *parent) {
 parent->leftChild = first; // 左子树
 parent->rightChild = second; // 右子树
 parent->weight = first->weight + second->weight; // 父结点权值
 first->parent = second->parent = parent; // 父指针
}
 
// 前序遍历Huffman树
template <class T>
void HuffmanTree<T>::PreOrder() {
 PreOrder(root);
}
 
// 前序遍历Huffman树
template <class T>
void HuffmanTree<T>::PreOrder(HuffmanNode<T> *current) {
 if(current != NULL) {
  cout << current->weight << " "; // 访问当前结点数据
  PreOrder(current->leftChild); // 递归遍历左子树
  PreOrder(current->rightChild); // 递归遍历右子树
 }
}
#endif /* HuffmanTree_h */
 

4.测试：main.cpp

?
1
2
3
4
5
6
7
8
9
10
11
#include "HuffmanTree.h"
 
int main(int argc, const char * argv[]) {
 int arr[] = {7, 5, 2, 4};
 int len = sizeof(arr) / sizeof(arr[0]); // 数组长度
 HuffmanTree<int> tree; // Huffman树的对象
 
 tree.Create(arr, len); // 创建Huffman树
 tree.PreOrder(); // 前序遍历Huffman树
 return 0;
}
 

测试结果：
版权声明 : 本文内容来源于互联网或用户自行发布贡献，该文观点仅代表原作者本人。本站仅提供信息存储空间服务和不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权， 违法违规的内容， 请发送邮件至2530232025#qq.cn(#换@)举报，一经查实，本站将立刻删除。

您可能感兴趣的文章 :

原文链接 : https://blog.csdn.net/chuanzhouxiao/article/details/88427411
相关文章

  • WPF实现窗体亚克力效果的代码

    WPF实现窗体亚克力效果的代码
    WPF 窗体设置亚克力效果 框架使用大于等于.NET40。 Visual Studio 2022。 项目使用MIT开源许可协议。 WindowAcrylicBlur设置亚克力颜色。 Opacity设置透

  • C#非托管泄漏中HEAP_ENTRY的Size对不上解析

    C#非托管泄漏中HEAP_ENTRY的Size对不上解析
    一：背景 1. 讲故事 前段时间有位朋友在分析他的非托管泄漏时，发现NT堆的_HEAP_ENTRY的 Size 和!heap命令中的 Size 对不上，来咨询是怎么回事？
  • C#中ArrayList 类的使用介绍
    一：ArrayList 类简单说明 动态数组ArrayList类在System.Collecions的命名空间下，所以使用时要加入System.Collecions命名空间，而且ArrayList提供添加，

  • C#使用BinaryFormatter类、ISerializable接口、XmlSeriali

    C#使用BinaryFormatter类、ISerializable接口、XmlSeriali
    序列化是将对象转换成字节流的过程，反序列化是把字节流转换成对象的过程。对象一旦被序列化，就可以把对象状态保存到硬盘的某个位
  • C#序列化与反序列化集合对象并进行版本控制
    当涉及到跨进程甚至是跨域传输数据的时候，我们需要把对象序列化和反序列化。 首先可以使用Serializable特性。 1 2 3 4 5 6 7 8 9 10 11 12 13 14

  • C#事件中关于sender的用法解读

    C#事件中关于sender的用法解读
    C#事件sender的小用法 开WPF新坑了，看了WPF的炫酷界面，再看看winForm实在是有些惨不忍睹（逃）。后面会开始写一些短的学习笔记。 一、什么

  • 在C#程序中注入恶意DLL的方法

    在C#程序中注入恶意DLL的方法
    一、背景 前段时间在训练营上课的时候就有朋友提到一个问题，为什么 Windbg 附加到 C# 程序后，程序就处于中断状态了？它到底是如何实现
  • 基于C#实现一个简单的FTP操作工具
    实现功能 实现使用FTP上传、下载、重命名、刷新、删除功能 开发环境 开发工具： Visual Studio 2013 .NET Framework版本：4.5 实现代码 1 2 3 4 5 6 7

  • C#仿QQ实现简单的截图功能

    C#仿QQ实现简单的截图功能
    接上一篇写的截取电脑屏幕，我们在原来的基础上加一个选择区域的功能，实现自定义选择截图。 个人比较懒，上一篇的代码就不重新设计
  • C#实现线性查找算法的介绍
    线性查找，肯定是以线性的方式，在集合或数组中查找某个元素。 通过代码来理解线性查找 什么叫线性?还是在代码中体会吧。 首先需要一
推荐阅读
最新更新
友情链接
  • 本站所有内容来源于互联网或用户自行发布，本站仅提供信息存储空间服务，不拥有版权，不承担法律责任。如有侵犯您的权益，请您联系站长处理！
  • Copyright © 2017-2022 F11.CN All Rights Reserved. F11站长开发者网 版权所有 | 苏ICP备2022031554号-1 | 51LA统计