实验目的：

(1) 掌握二叉树的定义；

(2) 掌握哈夫曼树和哈夫曼编码算法的实现。???

实验内容：

实现一个哈夫曼编码系统，系统包括以下功能：

(1) 字符信息统计：读取待编码的源文件SourceFile.txt，统计出现的字符及其频率。

附：SourceFile.txt文件内容为

U ARE THE BEST IN MY HEART

(2) 建立哈夫曼树：根据统计结果建立哈夫曼树。

(3) 建立哈夫曼码表：利用得到的哈夫曼树，将各字符对应的编码表保存在文件Code.txt中。

(4) 对源文件进行编码：根据哈夫曼码表，将SourceFile.txt中的字符转换成相应的编码文件ResultFile.txt。

实现提示：

(1) 字符信息统计：假设源文件SourceFile.txt中的字符只有大小写英文字母(同一个字母的大小写看作一个字符)，则字符统计算法的实现过程可以归纳为：先定义一个含有26个元素的整形数组，用来存储各个字母出现的次数，最后还要排除其中出现次数为0的数组元素。

(2) 建立哈夫曼树：参考教材算法5.10，补充函数Select的实现。

(3) 建立哈夫曼码表：参考教材算法5.11，将编译表HC中的内容写到文件Code.txt中。

(4) 对源文件进行编码：依次读入文件SourceFile.txt中的字符?c，在编码表?HC?中找到此字符，将字符c转换为编码表中存放的编码串，写入编码文件ResultFile.txt中，直到所有的字符处理完毕为止。

代码实现

#define _CRT_SECURE_NO_WARNINGS

#include

#include

#include

#include

#include

using namespace std;

typedef struct{

int weight;

int parent, lchild, rchild;

}HTNode, *HuffmanTree;

typedef char **HuffmanCode;

int a[24 + 1], b[24 + 1];

char c[24 + 1];

void Select(HuffmanTree &HT, int n, int &s1, int &s2){

for (int i = 1; i <= n; i++)

if (HT[i].parent == 0 && s1 == 0) { s1 = i; break; }

for (int i = 1; i <= n; i++)

if (HT[i].parent == 0 && HT[i].weight

for (int i = 1; i <= n; i++)

if (HT[i].parent == 0 && s2 == 0 && i != s1) { s2 = i; break; }

for (int i = 1; i <= n; i++)

if (HT[i].parent == 0 && HT[i].weight

}

void CreateHuffmanTree(HuffmanTree &HT, int n){

if (n <= 1) return;

int m = 2 * n - 1;//构造一棵哈夫曼树所需要的所有节点数

HT = new HTNode[m + 1];//m+1指从第一个结点开始，第0个结点不用

for (int i = 1; i <= m; i++){

HT[i].parent = 0;

HT[i].lchild = 0;

HT[i].rchild = 0;

}

for (int i = 1; i <= n; i++) HT[i].weight = b[i];//把字母出现的次数赋值给哈夫曼树的weight

for (int i = n + 1; i <= m; i++){

int s1 = 0, s2 = 0;

Select(HT, i - 1, s1, s2);

HT[s1].parent = i;

HT[s2].parent = i;

HT[i].lchild = s1;

HT[i].rchild = s2;

HT[i].weight = HT[s1].weight + HT[s2].weight;

}

}

void CreateHuffmanCode(HuffmanTree &HT, HuffmanCode &HC, int n){

HC = new char*[n + 1];

char *cd = new char[n];

cd[n - 1] = '\0';

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

int start = n - 1, c = i, f = HT[i].parent;

while (f){

--start;

if (HT[f].lchild == c) cd[start] = '0';

else cd[start] = '1';

c = f;

f = HT[f].parent;

}

HC[i] = new char[n - start];

strcpy(HC[i], &cd[start]);

}

delete cd;

}

int main(){

freopen("SourceFile.txt", "r", stdin);//打开输入文件

memset(a, 0, sizeof(a));

string str;

getline(cin, str);//接收文件的字符串并保存到str中

for (int i = 0; i

a[str[i] - 64]++;

int n = 0;

for (int i = 1, j = 1; i <= 24; i++)//统计有多少个不同的字母以及把没出现的字母去除掉

if (a[i] != 0){

n++;

b[j] = a[i];

c[j++] = i + 64;

}

HuffmanTree HT;

HuffmanCode HC;

CreateHuffmanTree(HT, n);

CreateHuffmanCode(HT, HC, n);

freopen("Code.txt", "w", stdout);

for (int i = 1; i <= n; i++)

cout << c[i] << ':' << HC[i] << endl;

freopen("ResultFile.txt", "w", stdout);

for (int i = 0; i

for (int j = 1; j <= n; j++){

if (str[i] == c[j]) cout << HC[j];

}

}

return 0;

}

Code.txt

A:000

B:0110

E:111

H:001

I:0111

M:1000

N:1001

R:010

S:1010

T:110

U:1011

ResultFile.txt

101100001011111000111101101111010110011110011000001111000010110

实验结果

原文：https://www.cnblogs.com/zhengyu-ahu/p/12038832.html