哈夫曼编码算法实现完整版

数据结构哈夫曼编码实验报告

一、实验目的：

通过哈夫曼编、译码算法的实现，巩固二叉树及哈夫曼树相关知识的理解掌握，训练学生运用所学知识，解决实际问题的能力。

二、实验内容：

已知每一个字符出现的频率，构造哈夫曼树，并设计哈夫曼编码。

1、从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。

2、打印每一个字符对应的哈夫曼编码。

3、对从终端读入的字符串进行编码，并显示编码结果。

4、对从终端读入的编码串进行译码，并显示译码结果。

三、实验方案设计：

（对基本数据类型定义要有注释说明，解决问题的算法思想描述要完整，算法结构和程序功能模块之间的逻辑调用关系要清晰，关键算法要有相应的流程图，对算法的时间复杂度要进行分析）

1、算法思想：

（1）构造两个结构体分别存储结点的字符及权值、哈夫曼编码值：

（2）读取前n个结点的字符及权值，建立哈夫曼树：

（3）根据哈夫曼树求出哈夫曼编码：

2、算法时间复杂度： （1）建立哈夫曼树时进行n到1次合并，产生n到1个新结点，并选出两个权值最小的根结点：O（n²）；

（2）根据哈夫曼树求出哈夫曼编码：O（n²）。

（3）读入电文，根据哈夫曼树译码：O（n）。

四、该程序的功能和运行结果：

（至少有三种不同的测试数据和相应的运行结果，充分体现该程序的鲁棒性）

1、输入字符A，B，C，D，E，F及其相应权值16、12、9、30、6、3。

2、输入字符F，E，N，G，H，U，I及其相应权值30、12、23、22、12、7、9。

3、输入字符A，B，C，D，E，F，G，H，I，G及其相应权值19、23、25、18、12、67、23、9、32、33。

哈夫曼编码python

一、什么是哈夫曼编码？

哈夫曼编码（Huffman Coding）是一种可变长度编码（Variable

Length Code），它可以将不同长度的字符编码成等长的二进制串，从而实现数据压缩的目的。哈夫曼编码是由David A. Huffman在1952年发明的，它是一种贪心算法，可以得到最优解。

二、哈夫曼编码原理

1.字符频率统计

在进行哈夫曼编码之前，需要先统计每个字符出现的频率。通常使用一个字典来存储每个字符和其出现的次数。

2.构建哈夫曼树

根据字符出现频率构建一个二叉树，其中频率越高的字符离根节点越近。构建过程中需要用到一个优先队列（Priority Queue），将每个节点按照频率大小加入队列中，并将队列中前两个节点合并为一个新节点，并重新加入队列中。重复这个过程直到只剩下一个节点，即根节点。

3.生成哈夫曼编码

从根节点开始遍历哈夫曼树，在遍历过程中，左子树走0，右子树走1，直到叶子节点。将路径上经过的0和1分别表示为0和1位二进制数，并把这些二进制数拼接起来，就得到了该字符的哈夫曼编码。

三、哈夫曼编码Python实现

下面是一个简单的Python实现：

1.字符频率统计

```python

from collections import Counter

def get_char_frequency(text):

"""统计每个字符出现的频率"""

return Counter(text)

```

2.构建哈夫曼树

```python

import heapq

class HuffmanNode:

def __init__(self, char=None, freq=0, left=None, right=None):

self.char = char

self.freq = freq

self.left = left

长 春 大 学 课程设计纸

共 24 页 第 1 页

┊

┊

┊

┊

┊

┊

┊

┊

┊

┊

┊

┊

┊

装

┊

┊

┊

┊

┊

订

┊

┊

┊

┊

┊

线

┊

┊

┊

┊

┊

┊

┊

┊

┊

┊

┊

┊

┊ 目 录

目 录 ................................................ 1

1 课程设计的目的和意义 .................................. 2

2 需求分析 .............................................. 3

3 系统设计 .............................................. 4

(1)设计思路及方案 .................................... 4

(2)模块的设计及介绍 .................................. 4

(3)主要模块程序流程图 ................................ 6

4 系统实现 ............................................. 10

(1)主调函数 ......................................... 10

(2)建立HuffmanTree .................................. 10

(3)生成Huffman编码并写入文件 ........................ 13

(4)电文译码 ......................................... 14

5 系统调试 ............................................. 16

c语言哈夫曼树的构造及编码

一、哈夫曼树概述

哈夫曼树是一种特殊的二叉树，它的构建基于贪心算法。它的主要应用是在数据压缩和编码中，可以将频率高的字符用较短的编码表示，从而减小数据存储和传输时所需的空间和时间。

二、哈夫曼树的构造

1. 哈夫曼树的定义

哈夫曼树是一棵带权路径长度最短的二叉树。带权路径长度是指所有叶子节点到根节点之间路径长度与其权值乘积之和。

2. 构造步骤

(1) 将待编码字符按照出现频率从小到大排序。

(2) 取出两个权值最小的节点作为左右子节点，构建一棵新的二叉树。

(3) 将新构建的二叉树加入到原来排序后队列中。

(4) 重复上述步骤，直到队列只剩下一个节点，该节点即为哈夫曼树的根节点。

3. C语言代码实现

以下代码实现了一个简单版哈夫曼树构造函数：

```c

typedef struct TreeNode {

int weight; // 权重值

struct TreeNode *leftChild; // 左子节点指针

struct TreeNode *rightChild; // 右子节点指针

} TreeNode;

// 构造哈夫曼树函数

TreeNode* createHuffmanTree(int* weights, int n) {

// 根据权值数组构建节点队列，每个节点都是一棵单独的二叉树

TreeNode** nodes = (TreeNode**)malloc(sizeof(TreeNode*) *

n);

for (int i = 0; i < n; i++) {

nodes[i] = (TreeNode*)malloc(sizeof(TreeNode));

nodes[i]->weight = weights[i];

nodes[i]->leftChild = NULL;