一、编程目的
（1）学习和理解树和二叉树的概念、特点和相关知识，理解和掌握二叉树的遍历操作的原理和方法；掌握二叉树的常用存储结构以及C++类的实现方法。
（2）学习最优二叉树的概念，理解和掌握哈夫曼算法的原理，掌握基于哈夫曼算法构造最优二叉树的方法；学习和掌握基于最优二叉树的哈夫曼编码方法。
（3）学会通过分析应用需求，结合理论知识来设计合理的数据结构与有效的求解算法；能够通过查找和学习技术资料、文档来掌握需用到的编程知识、技术；能够综合运用所学知识，利用开发环境提供的调试工具对程序进行调试，完成程序的开发、测试和完善。
二、26字母频率表
英文字母字符集及使用频率
字母 | 英语中出现的频率 | 字母 | 英语中出现的频率 | 字母 | 英语中出现的频率 | 字母 | 英语中出现的频率 |
a | 8.167% | h | 6.094% | o | 7.507% | u | 2.758% |
b | 1.492% | i | 6.966% | p | 1.929% | v | 0.978% |
c | 2.782% | j | 0.153% | q | 0.095% | w | 2.360% |
d | 4.253% | k | 0.772% | r | 5.987% | x | 0.150% |
e | 12.702% | l | 4.025% | s | 6.327% | y | 1.974% |
f | 2.228% | m | 2.406% | t | 9.056% | z | 0.074% |
g | 2.015% | n | 6.749% |
三、代码实现
#include#include#includeusing namespace std;
struct huff
{
double weight;
int parent, lch, rch;
char cha;
};
struct code
{
char cd[25];
int start;
};
void input(huff hufftree[],char alpha[],double weight[])//初始化哈夫曼树，权值先全部赋0，再将频率录入
{
for (int i = 0;i< 51;i++)
hufftree[i].cha = '_';
for (int i = 0;i< 26;i++)
hufftree[i].cha= alpha[i];
for (int i = 0;i< 51;i++)
hufftree[i].weight = 0;
for (int i = 0;i< 26;i++)
hufftree[i].weight = weight[i];
for (int i = 0;i< 51;i++)
{
hufftree[i].parent = -1;
hufftree[i].lch = -1;
hufftree[i].rch = -1;
}
}
void buildtree(huff hufftree[])
{
int i, k, lnode, rnode;double mina, minb;
for (i = 26;i< 51;i++)//从第一个结点开始，确定其孩子结点
{
mina = minb = 100;lnode = rnode = 0;//100和0只是初始化值，无特殊含义，取100是确保高于任意字母的频率，因为所有字母的频率和是100
for (k = 0;k< 51&&hufftree[k].weight!=0;k++)//每一次遍历整个hufftree，将已经找到双亲结点的和尚未被使用的结点剔除，比较剩余结点
{
if (hufftree[k].parent == -1)//没找到双亲结点
{
if (hufftree[k].weight< mina)//每一轮后mina都会变为100，此时基本第一个进来的k就会执行这个if语句
{
minb = mina;//如果后续有更小的权，原先在mina的数据便会被移动到minb，暂时变为第二小
rnode = lnode;
mina = hufftree[k].weight;
lnode = k;
}
else if (hufftree[k].weight< minb)//看看新的权值会不会替代成为第二小
{
minb = hufftree[k].weight;
rnode = k;
}//遍历整个hufftree后，此时mina和minb上都已经确定好这一轮的最小和次小，准备赋值给这一轮对应的未使用结点
}
}
hufftree[lnode].parent = i;//确定双亲
hufftree[rnode].parent = i;
hufftree[i].weight = hufftree[lnode].weight + hufftree[rnode].weight;//确定未使用结点的权
hufftree[i].lch = lnode;//确定未使用结点的孩子
hufftree[i].rch = rnode;
}//循环直到按照哈夫曼算法确定每个结点的值，构造完成
}
void createcode(huff hufftree[],code alphac[])
{
int i, f, c;
code hc{};
for(i=0;i<26;i++)//26次循环，确定26个字母
{
hc.start = 26;
c = i;
f = hufftree[i].parent;
while (f != -1)
{
if (hufftree[f].lch == c)hc.cd[hc.start--] = '0';
else hc.cd[hc.start--] = '1';
c = f;
f = hufftree[f].parent;//向上再找一级，逆向从后向前储存
}
hc.start++;//读取时有用，确定长度
alphac[i] = hc;//储存
}
}
void display(code alphac[],huff hufftree[])
{
int i, j;
cout<< "********* 欢迎使用哈夫曼编码程序 *************"<< endl;
cout<< "********* 26字母表字符集对应哈夫曼编码如下： *************"<< endl;
for(i=0;i<26;i++)
{
cout<< hufftree[i].cha<< " ";
for (j = alphac[i].start;j<= 26;j++)
cout<< alphac[i].cd[j];//正向读取
cout<< endl;
}
cout<< "************* 请输入接下来的操作： *************"<< endl;
cout<< "************ 1.将单词翻译为哈夫曼编码 ********************"<< endl;
cout<< "************ 2.将哈夫曼编码翻译为单词 ********************"<< endl;
cout<< "请选择："<< endl;
}
void fromwordstohuff(code alphac[], huff hufftree[])
{
int eye = 0;
cout<< "请输入你想编译的单词："<< endl;
char input[1000];
cin >>input;
cout<< input<< "的编码为：" ;
for (int i = 0;input[i] != '\0';i++)
{
char temp = input[i];
for (int k = 0;k< 26;k++)
{
if (temp == hufftree[k].cha)
{
for (int j = alphac[k].start;j<= 26;j++)
cout<< alphac[k].cd[j];//正向读取
eye++;
}
}
}
if (eye< strlen(input))
{
cout<< endl;
cout<< "您输入的单词中或含非法字符，已过滤，请您留意！"<< endl;//鲁棒性容错
}
cout<< endl;
}
void fromhufftowords(code alphac[], huff hufftree[],char code[])
{
cout<< "该编码对应单词为：" ;
int i, j;
struct array { char storecode[10]; };
array array1[26];
for (i = 0;i< 26;i++)
{
int q = 0;
for ( j = alphac[i].start;j<= 26;j++)
{
array1[i].storecode[q] = alphac[i].cd[j];
q++;
}
array1[i].storecode[q] = '\0';
//cout<< array1[i].storecode<< endl;（调试用）
}
int tt=0;//用于暂存i值
char codecmp[1000];//构造用于比较的字符串
int z;
int w = 0;
for (int i = 0;code[i] != '\0';)
{
int key=1;//用于判断是否跳出for循环
//cout<< w;w++;system("pause");（调试用）
tt = i;
for (z = 0;code[i] != '\0';z++)
{
codecmp[z] = code[i];
i++;
}//完成拷贝
codecmp[z++] = '\0';//加入截止符号
i = tt;
int len=0;
int k = 0;
for (;k< 26&&key==1;k++)
{ int d;
for (d = 0; codecmp[d] != '\0';)
{
if (codecmp[d] == array1[k].storecode[d])
{
d++;
if (array1[k].storecode[d] == '\0')//判断哈夫曼代码是否和字符集有相同的段落
{
cout<< hufftree[k].cha;//如果有，输出该字符
key = 0;//调整key，使得对于该字符的循环停止，重新从k=0开始，避免k继续往下加
len = strlen(array1[k].storecode);
}
}
else break;
}
}
if (k == 26 && key == 1)
{
cout<< "<——本条提示前为成功编译的字母，但此后存在哈夫曼码输入错误,请检查后重新输入"<< endl;
break;
}
i = i + len;
key = 1;//重调key值是下一次正常进入循环
}
}
int main()
{
int w; int t;
char alpha[26] = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };
double weight[26] = { 8.167,1.492, 2.782,4.253,12.702,2.228,2.015,6.094,6.966,0.153,0.772,4.025,2.406,6.749,7.507,1.929,0.095,5.987,6.327,9.056,2.758,0.978,2.360,0.150,1.974,0.074 };
huff hufftree[51];
code alphac[26];
input(hufftree, alpha, weight);
buildtree(hufftree);
createcode(hufftree, alphac);
display(alphac, hufftree);//字母表、权值表、哈夫曼树和储存哈夫曼码的结构数组的建立
while(1)
{
cin >>t;
w = t;
int guard = 0;
switch(w)
{
case 1: fromwordstohuff(alphac, hufftree);break;
case 2: cout<< "请输入哈夫曼码："<< endl;
char code[1000];
cin >>code;
for (int check = 0;code[check] != '\0';check++)
{
if (code[check] != '0' && code[check] != '1')
{
cout<< "请输入二进制数字,请重试"<< endl;
guard = 1;
break;
}
}
if (guard == 1) { break; }
fromhufftowords(alphac, hufftree,code);cout<< endl;break;
case 3: exit(1);
default: cout<< "请输入一个合理的选项"<< endl;
}
cout<< endl;
cout<< "************* 请输入接下来的操作： *************"<< endl;
cout<< "************ 1.将单词翻译为哈夫曼编码 ********************"<< endl;
cout<< "************ 2.将哈夫曼编码翻译为单词 ********************"<< endl;
cout<< "************ 3.退出程序 ********************"<< endl;
cout<< "请选择："<< endl;
}
} 四、运行结果
1、初始化
2、将单词编码为哈夫曼编码
3、将哈夫曼码编译为单词
五、结语
源代码很少调用函数，编程习惯也很糟糕，因为笔者对c++已经非常生疏，但觉得这个功能很有意思，所以还是磕磕绊绊写出来了一堆非常低效低级的代码，有的地方甚至非常冗余，源代码看着乐就好啦！
笔者过于小白，如果觉得有任何错漏和不足，恳请批评指正笔者，笔者感激不尽！
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
