实验五 哈夫曼树的设计及实现
一、实验目的
1. 掌握哈夫曼树的构造算法，理解二叉树的应用；
2. 掌握哈夫曼编码的构造算法。
二、实验内容
输入一串字符串，根据给定的字符串中字符出现的频率建立相应的哈夫曼树，构造哈夫曼编码表，在此基础上可以对压缩文件进行压缩（即编码）。
已知字符串中出现的字符为A、B、C、D、E、F、G、H，其相应的权值为
7、19、2、6、32、3、21、10。
三、实验提示
此实验内容即要求实现主教材的案例5.1，具体实现可参考算法5.10和算法5.11。首先，读入一行字符串，统计每个字符出现的频率；然后，根据字符出现的频率利用算法5.10建立相应的哈夫曼树；最后，根据得到的哈夫曼树利用算法5.11求出每个字符的哈夫曼编码。
源代码：
程序所需头文件及结构体的定义：
#include<iostream>
#include <stdlib.h>
#include<string.h>
#include<fstream>
using namespace std;
typedef struct{
int weight;
char ch;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;输入一串字符串并计算其各字符的权值函数，并用文件打印存储，用于哈夫曼树的构建：
void WeightCulate(string str,int &n){
int i=0,k=0,flag=0,sum=0;
n=1;
char CharOp[26];
int CharWeight[26];
for(i=1;i<=26;i++){
CharWeight[i]=0;
}
ofstream outfile("权值打印.txt");
i=0;
while(str[i]!='\0'){//输入一串字符串并统计不重复的字符及其出现次数
if(i==0){
CharOp[n]=str[i];
CharWeight[n]+=1;
}
else{
for(k=1;k<=n;k++){
if(str[i]==CharOp[k]){
CharWeight[k]+=1;
flag=1;
break;
}
}
if(flag==0){
n+=1;
CharOp[n]=str[i];
CharWeight[n]+=1;
}
}
i+=1;
flag=0;
}
for(i=1;i<=n;i++){
outfile.put(CharOp[i]);
outfile<<CharWeight[i]<<endl;;
}
outfile.close();
}选择parent为0且权值最小的两科树，并记作s1，s2：
void Select(HuffmanTree& HT, int n, int& s1, int& s2){//选择权值最小的两棵树进行合并
int min,i;
for(i=1;i<=n;i++){
if(HT[i].parent == 0){
min=i;
break;
}
}
for (i=min+1;i<=n;i++){
if (HT[i].parent==0&&HT[i].weight<HT[min].weight)
min = i;
}
s1 = min;//左孩子s1
for(i=1;i<=n;i++){
if(HT[i].parent==0&&i!=s1){
min=i;
break;
}
}
for(i=min+1;i<=n;i++){
if(HT[i].parent==0&&HT[i].weight<HT[min].weight&&i!= s1)
min=i;
}
s2=min; //右孩子s2
}建立哈夫曼树，并用文件对字符及其权值进行输入：
void CreatHuffmanTree(HuffmanTree &HT,int n,int choose){
int m,i,s1,s2;
if(n<=1) return;
m=2*n-1;
HT=new HTNode[m+1];
for(i=1;i<=m;++i){
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
i=1;
fstream file;//文件输入
if(choose==1){
file.open("字符权值.txt");
if(!file)
cout<<"[----错误！未找到字符权值文件----]"<<endl;
}
else if(choose==2){
file.open("权值打印.txt");
if(!file)
cout<<"[----错误！未找到字符权值文件----]"<<endl;
}
while(!file.eof()){
file>>HT[i].ch>>HT[i].weight;
i++;
}
for(i=n+1;i<=m;++i){
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;
}
cout<<"[------哈夫曼树已成功建立！------]"<<endl;
}打印哈夫曼树：
void print(HuffmanTree HT,int n){
int i,m;
m=2*n-1;
cout<<"[--------------哈夫曼树为:>--------------]"<<endl;
cout<<"下标 权值 父结点 左孩子 右孩子"<<endl;
for(i=1;i<=m;i++)
{
cout<<i<<" "<<HT[i].weight<<" "<<HT[i].parent<<" "<<HT[i].lchild<<" "<<HT[i].rchild<<endl;
}
}对各字符进行哈夫曼编码：
typedef char **HuffmanCode;
//生成哈夫曼编码
void HuffCoding(HuffmanTree& HT, HuffmanCode& HC, int n)
{
HC = (HuffmanCode)malloc(sizeof(char*)*(n + 1)); //开n+1个空间，因为下标为0的空间不用
char* code = (char*)malloc(sizeof(char)*n); //辅助空间，编码最长为n(最长时，前n-1个用于存储数据，最后1个用于存放'\0')
code[n - 1] = '\0'; //辅助空间最后一个位置为'\0'
for (int i = 1; i <= n; i++)
{
int start = n - 1; //每次生成数据的哈夫曼编码之前，先将start指针指向'\0'
int c = i; //正在进行的第i个数据的编码
int p = HT[c].parent; //找到该数据的父结点
while (p) //直到父结点为0，即父结点为根结点时，停止
{
if (HT[p].lc == c) //如果该结点是其父结点的左孩子，则编码为0，否则为1
code[--start] = '0';
else
code[--start] = '1';
c = p; //继续往上进行编码
p = HT[c].parent; //c的父结点
}
HC[i] = (char*)malloc(sizeof(char)*(n - start)); //开辟用于存储编码的内存空间
strcpy(HC[i], &code[start]); //将编码拷贝到字符指针数组中的相应位置
}
free(code); //释放辅助空间
cout<<"[-----已完成对各字符的编码！-----]"<<endl;
}
输出各字符及其编码：
void CodeOutput(HuffmanTree HT,HuffmanCode HC,int n){
int i;
for(i=1;i<=n;i++){
cout<<"字符"<<HT[i].ch<<"的编码为："<<HC[i]<<endl;
}
cout<<"[---已输出所有字符及其编码！---]"<<endl;
}输入一串字符串并对其进行哈夫曼编码：
void StringCode(HuffmanTree& HT,HuffmanCode& HC,int n,string str){
int i=0,k,flag;
while(str[i]!='\0'){
flag=0;
for(k=1;k<=n;k++){//字符匹配
if(HT[k].ch==str[i]){
if(i==0) cout<<"字符串"<<str<<"的哈夫曼编码为";
cout<<HC[k];
flag=1;
}
}
if(flag==0) cout<<"字符"<<str[i]<<"编码失败！";
i++;
}
cout<<endl;
}菜单函数：
void menu1(){
cout<<"[----------------------------------------请选择操作！----------------------------------------]"<<endl;
cout<<"[1.以字符为A、B、C、D、E、F、G、H,其相应的权值为7、19、2、6、32、3、21、10,开始创建哈夫曼树！]"<<endl;
cout<<"[----------------------------2.输入一串字符并计算其权值开始实验！----------------------------]"<<endl;
}
void menu2(){
cout<<"[----------请选择操作！----------]"<<endl;
cout<<"[--------1.打印哈夫曼树！--------]"<<endl;
cout<<"[-------2.对字符进行编码！-------]"<<endl;
cout<<"[-----3.输出各字符及其编码！-----]"<<endl;
cout<<"[4.输入一串字符串并对其进行编码！]"<<endl;
cout<<"[----------0.退出程序！----------]"<<endl;
}主函数：
int main(){
HTNode *HT;
HuffmanCode HC;
int n,i,choose;
string str;
menu1();
cin>>choose;
if(choose==1) n=8;
if(choose==2){
cout<<"[--------开始创建哈夫曼树！--------]"<<endl;
cout<<"[请输入一串字符，我们将计算其权值！]"<<endl;
cin>>str;
WeightCulate(str,n);
cout<<"[----------打印字符及其权值文件完成！----------]"<<endl;
}
CreatHuffmanTree(HT,n,choose);
menu2();
cin>>choose;
while(choose){
switch(choose){
case 1:print(HT,n);break;
case 2:HuffCoding(HT,HC,n);break;
case 3:CodeOutput(HT,HC,n);break;
case 4:cout<<"[-------请输入一串字符串！-------]"<<endl;
cin>>str;
cout<<"[------------已输入！------------]"<<endl;
StringCode(HT,HC,n,str);break;
}
cout<<"[----------请选择操作！----------]"<<endl;
cin>>choose;
}
cout<<"[----------感谢您的使用！----------]"<<endl;
return 0;
} 输入文件“字符权值.txt”：
(注：文件的格式应为ANSI,否则会导致乱码）
运行结果：
运行结果2：
（注：权值打印文件为这次运行中出现的各字符及其出现次数！）
给出该实验内容实现的分析研究过程的描述：
（1）数据结构和其存储结构的选择理由和类型描述；
（2) 哈夫曼树的构造、设计过程和结果：
（3）哈夫曼编码的构造、设计过程和结果：文章来源：https://www.toymoban.com/news/detail-485100.html
（4）效率分析：文章来源地址https://www.toymoban.com/news/detail-485100.html
到了这里，关于数据结构实验五：哈夫曼树的设计及实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
