主要内容：
设计一个哈夫曼树，建立函数输入二叉树，并输出哈夫曼树。实现哈夫曼树的初始化并打印，进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。同时，在此基础上对算法的时间复杂度进行分析并进行优化。
基本要求：
1、运行时，由用户输入来初始化字符集大小和相应用字符
2、输入一个要加密的字符串，将其加密。
3、设计哈夫曼树的解码，输出解密字符串。
4、哈夫曼树算法的存储结构;
主要参考资料：
[1] 李春葆.数据结构教程(第3版)[M].北京：清华大学出版社.2009.
[2] 谢弗.数据结构与算法分析(C++版.第3版)[M].北京：电子工业出版社.2003
[3]陈守礼.算法与结构C语言版[M].西安.机械工业出版社.2007
[4] 严蔚敏、吴伟民.《数据结构》（C语言版）.清华大学出版社.2007
[5] 谭浩强.《C++程序设计》.清华大学出版社.2015
[6]Stanley B.LippmanBarbara E.Moo JoseeLaJolie，《C++ Primer》.人民邮电出版社.2006
完 成 期 限： 2022 年 12 月 13 日
指导教师签名：
课程设计人签名：
摘要
在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程序的执行效率。因此，我们需要寻找一种最佳判定树，即哈夫曼树，来高效地存储、处理数据。本课程设计主要进行哈夫曼树的建立，通过此设计充分理解哈夫曼树的原理，同时也为哈夫曼编码奠定基础。哈夫曼编码属于变长编码，也是一种压缩优化型的编码方式。而哈夫曼树的建立是哈夫曼编码的前提，哈夫曼编码可以起到数据压缩的作用，提高程序的执行效率。哈夫曼编码是将明文转变成暗文，比如将一串字符转化成01010001..形式的暗文。而译码则是将暗文转变成明文，比如将01010001转化成有意义的字符串。
哈夫曼树存储结构有顺序存储和链式存储，顺序存储利用数组完成，链式存储利用指针来完成。本实验要了解字符集中，每个字符相关的使用频度，来完成解码的实现。同时，尽可能降低代码的时间复杂度和空间复杂度。
关 键 词: 哈夫曼树;存储结构;哈夫曼编码；哈夫曼解码
目录
摘要
目录
1 概述
1.1 课程设计目的
1.2 预备知识
1.3 实训的内容和要求
2 需求分析
2.1 系统目标
2.2 功能分析
2.3 开发环境
3 总体设计
3.1 系统功能模块图
3.2系统总流程图
3.3 功能详细分析 4
4 详细设计 6
4.1创建哈夫曼树 6
4.2创建编码表 9
4.3解码 13
5 程序运行 15
5.1源程序 15
5.2程序运行结果28
心得体会 30
参考文献 31
1 概述
1.1 课程设计目的
本课程设计目的不仅仅在于建立函数输入二叉树，输出得到哈夫曼树，并且通过二叉树结构实现哈夫曼树和译码。实现哈夫曼树的初始化并打印，在此基础上对算法的时间复杂度进行分析并进行优化。
1.2 预备知识
运用到的知识(1)初始化：能够让用户输入字符和相应字符的频度来初始化，并建立哈夫曼树;（2）建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码进行输出，打印哈夫曼编码表;（3）译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。
运用哈夫曼算法的相关知识解决问题。以用户输入的字符作为需要编码的字符集合，每个字符对应的频度则作为该字符的权值，构造一棵哈夫曼编码树，规定哈弗曼编码树的左分支代表0，右分支代表1，则从根结点到每个叶子结点所经过的路径组成的0和1的序列为需要加密字符的编码。
1.3 实训的内容和要求
实训内容：用户输入需要编译的字符和该字符的权值;构造哈夫曼算法,设计一个数组H保存哈夫曼树中各结点的信息;数组H初始化，将所有结点的孩子域和双亲域的值初始化为-1;数组H的前n个元素的权值给定值;调用select函数选择权值最小的根结点进行合并，其下标分别为i1，i2;将二叉树i1，i2合并为一棵新的二叉树;共进行n-1次合并，直到剩下一棵二叉树，这棵二叉树就是哈夫曼树;用户输入需要编译的字符和该字符的权值;建立函数输入二叉树，并输出哈夫曼树，实进而实现哈夫曼树的应用。要求：完成基本要求前提下，尽可能得对算法进行改进，提高运算效率。
2 需求分析
2.1 系统目标
通过用户输入编译字符和字符的权值来构造哈夫曼算法，初始、定值、合并，最后输出哈夫曼树。通过利用二叉树结构实现哈夫曼编码，并且对数据进行存储结构设计：采用静态的三叉链表存放。
2.2 功能分析
存储结构：算法设计头指针数组存储哈夫曼编码串，字符型指针用来存放临时的编码串；从叶子节点开始向上倒退，若其为它双亲节点的左孩子则编码标0，否则标1；直到根节点为止，最后把临时存储编码复制到对应的指针数组所指向的内存中。重复，直到所有的叶子节点都被编码完。同时，实验中设计一个结构体Element保存哈夫曼树中各结点的信息。
实验内容时间复杂度在输出哈夫曼树后，用以下函数来判断分析算法思想：Select函数，时间复杂度O(n);Reverse函数，时间复杂度O(n);HuffmanTree函数，构造哈夫曼树，时间复杂度O(n!);CreateCodeTable函数，构造和输出哈夫曼编码表，时间复杂度O(n);Decode函数，解码，时间复杂度O(n)。Select函数，时间复杂度O(n)。
2.3 开发环境
Microsoft Visual Studio2019
3 总体设计
3.1 系统功能模块图
主函数：由main函数开始往下三个分支，第一个是初始化然后创建哈夫曼，第二个创建哈夫曼编码表然后CreateCodeTable函数，第三个是译码然后Decode函数。
3.1功能模块图
3.2系统总流程图
算法的运行结果按系统总流程图来展示出来
3.2总流程图
3.3功能详细分析
函数功能分析：Select函数，目的是选择出权值最小的两个节点，并且这两个节点是未选择过的，也就是他的父母节点是不知道的（在我们这里定义的也即为0），通过i1，i2分别来返回两个最小的和次小的节点 ，select函数直接决定了哈夫曼树结构 ； Reverse函数，将字符串倒置，采用reverse函数将其逆序回来，存入编码数组； HuffmanCode函数，构造哈夫曼树，储存哈夫曼树编码；CreateCodeTable函数，构造和输出哈夫曼树编码；Decode函数，解码通过采用从根结点出发，一个字符依次查找对应的编码。而解码过程也是如此，可以根据输入的01字符串，从根节点出发，根据左0右1的原则，进行解码，输出数据。
4 详细设计
4.1创建哈夫曼树
a.输入需要编译的字符和该字符的权值（即其字母的频度）。
b.构造用户哈夫曼算法。设计一个数组H保存哈夫曼树中各结点的信息。
c.数组H初始化，将所有结点的孩子域和双亲域的值初始化为-1。
d.数组H的前n个元素的权值给定值。
e.调用select函数选择权值最小的根结点进行合并，其下标分别为i1，i2。
f.将二叉树i1，i2合并为一棵新的二叉树。
g.共进行n-1次合并，直到剩下一棵二叉树，这棵二叉树就是哈夫曼树。
函数实现：
int Select(Element H[],int i) //选择两个最小的
{
intmin=11000;
int min1;
for(intk=0;k<i;k++)
{
if(H[k].weight<min&& H[k].parent==-1)
{
min=H[k].weight;
min1=k;
}
}
H[min1].parent=1;
returnmin1;
}
void HuffmanTree(Element H[],int w[],int n) //构造哈夫曼树
{
inti1=0,i2=0;
for(inti=0;i<2*n-1;i++)
{
H[i].lchild=-1;
H[i].parent=-1;
H[i].rchild=-1;
}
for(intl=0;l<n;l++)
{
H[l].weight=w[l];
}
for(intk=n;k<2*n-1;k++)
{
inti1=Select(H,k);
inti2=Select(H,k);
if(i1>i2)
{
inttemp;
temp=i1;
i1=i2;
i2=temp;
}
H[i1].parent=k;
H[i2].parent=k;
H[k].weight=H[i1].weight+H[i2].weight;
H[k].lchild=i1;
H[k].rchild=i2;
}
}
4.2创建编码表
a.根据已经创建的哈夫曼树创建编码表。
b.从叶子结点开始判断。
c.如果当前叶子结点的双亲不是根结点，并且是其双亲的左孩子，则编码为‘0’，否则为‘1’。
d.然后往上对其双亲进行判断，重复操作，直到每个字符编码完毕。
e.将已经完成的编码调用reserve函数进行倒置。
f.按照“下标n，权值weight，左孩子LChuld，右孩子RChild，双亲parent，字符char，编码code”的顺序输出编码表。
数实现：
void Reverse(char c[]) //将字符串倒置
{
int n=0;
char temp;
while(c[n+1]!='\0')
{
n++;
}
for (inti=0;i<=n/2;i++)
{
temp=c[i];
c[i]=c[n-i];
c[n-i]=temp;
}
}
void CreateCodeTable(Element H[],HCode HC[],intn) //输出哈弗曼编码表
{
HC=newHCode[n];
for (inti=0;i<n;i++)
{
HC[i].data=H[i].ch;
int ic=i;
int ip=H[i].parent;
int k=0;
while(ip!=-1)
{
if (ic==H[ip].lchild) //左孩子标'0'
HC[i].code[k]='0';
else
HC[i].code[k]='1'; //右孩子标'1'
k++;
ic=ip;
ip=H[ic].parent;
}
HC[i].code[k]='\0';
Reverse(HC[i].code);
}
cout<<setiosflags(ios::left)
<<setw(5)<<"n"
<<setw(12)<<"weight"
<<setw(12)<<"LChild"
<<setw(12)<<"RChild"
<<setw(12)<<"parent"
<<setw(12)<<"char"
<<setw(12)<<"code"
<<endl;
for(i=0;i<2*n-1;i++)
{
if(i<n)
{
cout<<setiosflags(ios::left)
<<setw(5)<<i
<<setw(12)<<H[i].weight
<<setw(12)<<H[i].lchild
<<setw(12)<<H[i].rchild
<<setw(12)<<H[i].parent
<<setw(12)<<HC[i].data
<<setw(12)<<HC[i].code
<<endl;
}
else
cout<<setiosflags(ios::left)
<<setw(5)<<i
<<setw(12)<<H[i].weight
<<setw(12)<<H[i].lchild
<<setw(12)<<H[i].rchild
<<setw(12)<<H[i].parent
<<setw(12)<<"\\0"
<<setw(12)<<"\\0"
<<endl;
}
}
4.3解码
a.用户输入要解码的二进制字符串，建立一个字符数组存储输入的二进制字符。
b. 创建一个指向待解码的字符串的第1个字符的指针。
c. 读取每一个字符。设置一个根结点的指针，从根结点开始判断。
d. 若字符为‘0’，则指向哈夫曼树当前结点的左孩子。
e. 若字符为‘1’，则指向当前结点的右孩子。
f. 直到指针指向的当前结点的左孩子为-1时，输出符合的字母。
g. 输出解码结果。
函数实现：
void Decode(Element H[],HCode HC[],int n,char *s) //解码函数
{
cout<<"解码数据为：";
inti=2*(n-1); //根结点
while(*s!='\0')
{
if(*s=='0')
i=H[i].lchild;
else
i=H[i].rchild;
if(H[i].lchild==-1)
{
cout<<H[i].ch;
i=2*n-2;
}
s++;
}
cout<<endl;
}
5 程序运行
5.1源程序：
#include<iostream>
#include<string>
#include<iomanip>
using namespacestd;
struct Element
{
charch;
intweight;
intlchild, rchild, parent;
};
struct HCode
{
chardata;
charcode[100];
};
intSelect(Element H[], int i) //选择两个最小的
{
intmin = 11000;
intmin1;
for(intk = 0; k < i; k++)
{
if(H[k].weight < min && H[k].parent == -1)
{
min = H[k].weight;
min1 = k;
}
}
H[min1].parent = 1;
returnmin1;
}
voidReverse(char c[]) //将字符串倒置
{
intn = 0;
chartemp;
while(c[n + 1] != '\0')
{
n++;
}
for(inti = 0; i <= n / 2; i++)
{
temp = c[i];
c[i] = c[n - i];
c[n - i] = temp;
}
}
voidHuffmanTree(Element H[], int w[], int n) //构造哈夫曼树
{
inti1 = 0, i2 = 0;
for(inti = 0; i < 2 * n- 1; i++)
{
H[i].lchild = -1;
H[i].parent = -1;
H[i].rchild = -1;
}
for(intl = 0; l < n; l++)
{
H[l].weight = w[l];
}
for(intk = n; k < 2 * n- 1; k++)
{
inti1 = Select(H, k);
inti2 = Select(H, k);
if(i1 > i2)
{
inttemp;
temp = i1;
i1 = i2;
i2 = temp;
}
H[i1].parent = k;
H[i2].parent = k;
H[k].weight = H[i1].weight + H[i2].weight;
H[k].lchild = i1;
H[k].rchild = i2;
}
}
voidCreateCodeTable(Element H[], HCode HC[], int n) //输出哈弗曼编码表
{
HC= new HCode[n];
for(inti = 0; i < n; i++)
{
HC[i].data = H[i].ch;
intic = i;
intip = H[i].parent;
intk = 0;
while(ip != -1)
{
if(ic == H[ip].lchild) //左孩子标'0'
HC[i].code[k] = '0';
else
HC[i].code[k] = '1'; //右孩子标'1'
k++;
ic = ip;
ip = H[ic].parent;
}
HC[i].code[k] = '\0';
Reverse(HC[i].code);
}
cout <<setiosflags(ios::left)
<<setw(5) << "n"
<<setw(12) << "weight"
<<setw(12) << "LChild"
<<setw(12) << "RChild"
<<setw(12) << "parent"
<<setw(12) << "char"
<<setw(12) << "code"
<<endl;
for(inti = 0; i < 2 * n- 1; i++)
{
if(i < n)
{
cout <<setiosflags(ios::left)
<<setw(5) <<i
<<setw(12) << H[i].weight
<<setw(12) << H[i].lchild
<<setw(12) << H[i].rchild
<<setw(12) << H[i].parent
<<setw(12) << HC[i].data
<<setw(12) << HC[i].code
<<endl;
}
else
cout <<setiosflags(ios::left)
<<setw(5) <<i
<<setw(12) << H[i].weight
<<setw(12) << H[i].lchild
<<setw(12) << H[i].rchild
<<setw(12) << H[i].parent
<<setw(12) << "\\0"
<<setw(12) << "\\0"
<<endl;
}
}
voidDecode(Element H[], HCode HC[], int n, char* s) //解码函数
{
cout << "解码数据为：";
inti = 2 * (n- 1); //根结点
while(*s!= '\0')
{
if(*s== '0')
i = H[i].lchild;
else
i = H[i].rchild;
if(H[i].lchild == -1)
{
cout << H[i].ch;
i = 2 * n- 2;
}
s++;
}
cout <<endl;
}
intmain()
{
ElementH[20];
HCodeHC[20];
intn;
intselect;
while(1)
{
cin >>select;
if(select == 0) break;
switch(select) {
case1:
{
cout <<endl;
cout << "请输入字符集大小：";
cin >>n;
cout <<endl;
chars;
HCodeHC[20];
inte[20];
for(intt = 0; t < n; t++)
{
cout << "请输入第" <<t + 1 << "个字符：";
cin >>s;
H[t].ch = s;
HC[t].data = H[t].ch;
cout << "请输入该字符的权值：";
cin >>e[t];
cout <<endl;
}
HuffmanTree(H, e, n);
break;
}
case2:
CreateCodeTable(H, HC, n);
break;
case3:
{
cout <<endl;
cout << "请输入解码数据：";
chars[200] = { '\0'};
cin >>s;
Decode(H, HC, n, s);
break;
}
default:
cout << "没有此选项,请重新选择！" <<endl;
}
}
5.2运行截图
选择1运行截图
选择2运行截图
选择3运行截图
心得体会
通过这次实验，我进一步增强了对于哈夫曼算法的理解。明白了构建哈夫曼树的关键在于找最小树﹔在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。而哈夫曼编码的算法实质就是每次两个最小的相邻数相加，直到只剩一个数为止。把过程中所有的和加起来，较难处理的点就是每次加完了要保证下次相加的必须是最小的两个数。同时，对本次存储结构采用的三叉链表存放，也有了更加深刻的理解。其主要的算法思想：头指针数组存储哈夫曼编码串，字符型指针用来存放临时的编码串；从叶子节点开始向上倒退，若其为它双亲节点的左孩子则编码标0，否则标1；直到根节点为止，最后把临时存储编码复制到对应的指针数组所指向的内存中。重复，直到所有的叶子节点都被编码完。
与之对应的哈夫曼解码是，读取按顺序读取文件中的字符使用次数、原文件字符长度、哈夫曼编码长度、哈夫曼编码。和编码步骤一样，通过字符使用次数构建哈夫曼树。再根据哈夫曼树，对哈夫曼编码进行解码，把其解码出来的内容写入原文件字符大小的动态数组中。简单来说哈夫曼编码是将明文转成暗文，哈夫曼译码是将暗文转成明文。同时，通过查阅资料我对哈夫曼树有了更好的认识，在实验过程中掌握了哈夫曼树的结构，将有关哈夫曼树的相关理论与实际相结合。在一次次编写程序不断调试纠错的过程中，我对调试技巧有了更好的掌握。分析问题，解决问题也更加的全面。在实验过程中，我遇到了许多难点，比如：统计字符的权值等。为此，我不断的练习解决问题，也锻炼了实际操作时的动手能力。
参考文献
[1] 严蔚敏、吴伟民.《数据结构》（C语言版）.清华大学出版社.2007
[2] 谭浩强.《C++程序设计》.清华大学出版社.2015
[3]Stanley B.LippmanBarbara E.Moo JoseeLaJolie，《C++ Primer》.人民邮电出版社.2006
[4] 李春葆.数据结构教程(第3版)[M].北京：清华大学出版社.2009.
[5] 谢弗.数据结构与算法分析(C++版.第3版)[M].北京：电子工业出版社.2003
[6] 陈守礼.算法与结构C语言版[M].西安.机械工业出版社.2007
用百度学术
[7] 滕秀花.算法与数据结构.《高教学刊》2021
[8] KennethA.Reek.《C和指针》.人民邮电出版社.2008
[9] 张颖江、胡燕.《C语言程序设计》.科学出版社.1998
[10] 张霞、张海云.计算机操作系统原理.北京：中国电力出版社.2012