【数据结构实验】哈夫曼树

【数据结构实验】哈夫曼树

简介：

为一个信息收发站编写一个哈夫曼码的编/译码系统。文末贴出了源代码。

需求分析

1. 完整的系统需要具备完整的功能，包含初始化、编码、译码、印代码文件和印哈夫曼树，因此需要进行相应的文件操作进行配合。
2. 哈夫曼树的字符集和频度可以从文件中读入，也可以让用户手动输入，应当给予用户足够的选择。
3. 测试数据（附后）。

概要设计

1. 抽象数据类型树的定义如下：

ADT BinaryTree{数据对象D：D是具有相同特性的数据元素集合。数据关系R：如D=Ф，则R=Ф，称BinaryTree为空二叉树；如D≠Ф，则R={H}，H是如下二元关系：
（1） 在D中存在唯一的称为根的数据元素root,它在关系H下无前驱；
（2）如D-{root}≠Ф,则存在D-{root}={D1,Dr},且D1∩Dr=Ф;
（3）如D1≠Ф,则D1中存在唯一元素x1,1>∈H,且存在D1上的关系H1∈H；如Dr≠Ф，则Dr中存在唯一的元素xr，r>∈H,且存在Dr上的关系Hr包含于H；H={1>,r>,H1,Hr}；
（4） (D1,{H1})是一棵符合本定义的二叉树，称为根的右子树。
基本操作 P：
InitBiTree(&T)                      操作结果：构造空二叉树T.
DestroyBiTree(&T);                    初始条件：二叉树T存在。
操作结果：销毁二叉树T.
CreateBiThrTree(&T);
操作结果：先序构造二叉树T,Ltag和RTag初始置为Link.
PreOrderTraverse(T );
初始条件：二叉树T存在。
操作结果：先序递归遍历T。
InOrderTraverse(T);
初始条件：二叉树T存在。
操作结果：中序递归遍历T。
PostOrderTraverse(T);
初始条件：二叉树T存在。
操作结果：后序递归遍历T。
InOrderThreading(&ThrT, T);
初始条件：二叉树T存在。
操作结果：建立头结点ThrT,并调用InThreading(T);函数。
InThreading(T);
初始条件：二叉树T存在。
操作结果：中序线索化二叉树T;
InOrderTrasverse_Thr(T);
初始条件：二叉树T存在。
操作结果：中序扫描线索化的二叉树。
}ADT BinaryTree

2. 主程序

int main()
{初始化；do{接受命令；处理命令；}while(“命令”！=“退出”)
}

2. 调用关系
   本程序共有七个模块，调用关系简单。主函数模块可以调用任意模块，在编码和译码模块，在哈夫曼树不存在的情况下允许调用读取哈夫曼树模块。

详细设计

1. 哈夫曼树的类型

typedef struct
{unsigned int weight;  //权重char alpha;   //字母int number;  //编号unsigned int parent,lchild,rchild; //左右孩子和双亲
}HTNode,*HuffmanTree;   //哈夫曼树结点和指针类型
typedef char** HuffmanCode;  //哈夫曼编码类型

2. 哈夫曼树的基本操作如下

void Select(HuffmanTree HT, int end, int *s1, int *s2);
//构建哈夫曼树子函数，筛选权重最小的项 
int GetHuffmanRoot(HuffmanTree HT);
//返回树根节点下标 
Status HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, char* alpha,int *w, int n);
//构建哈夫曼树
Status saveTreeFrequent(HuffmanTree HT, HuffmanCode HC,int length);
//保存权重 
Status Encoding(HuffmanTree &HT,HuffmanCode &HC,int length);
//编码 
Status read(char *alpha,int *frequent,int length);
//读取字符及其权重 
Status Decoding(HuffmanTree HT,HuffmanCode HC,int length);
//解码 
Status Print();//印码
Status writeTree(HuffmanTree HT,unsigned root,int level,FILE *fs);
//画树子函数 
Status PrintTree(HuffmanTree HT,unsigned root,int level);
//画树

3. 源代码

/*头文件*/ 
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;/*宏定义*/
#define OK 1
#define TRUE 1
#define ERROR -1
#define FALSE -1/*哈夫曼树定义*/
typedef struct
{unsigned int weight;char alpha;int number;unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char** HuffmanCode;
typedef int Status;/*函数声明*/
void onScreen ();
void Select(HuffmanTree HT, int end, int *s1, int *s2);//构建哈夫曼树子函数，筛选权重最小的项 
int GetHuffmanRoot(HuffmanTree HT);//返回树根节点下标 
Status HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, char* alpha,int *w, int n);//构建哈夫曼树
Status saveTreeFrequent(HuffmanTree HT, HuffmanCode HC,int length);//保存权重 
Status Encoding(HuffmanTree &HT,HuffmanCode &HC,int length);//编码 
Status read(char *alpha,int *frequent,int length);//读取字符及其权重 
Status Decoding(HuffmanTree HT,HuffmanCode HC,int length);//解码 
Status Print();//印码
Status writeTree(HuffmanTree HT,unsigned root,int level,FILE *fs);//画树子函数 
Status PrintTree(HuffmanTree HT,unsigned root,int level);//画树 int main()
{/*定义变量，一定放在while外面*/ char userchoice;int judge,length,result;char *alpha;int *frequent;HuffmanTree HT=NULL;HuffmanCode HC=NULL;while(1){onScreen ();cin>>userchoice;while(userchoice!='I'&&userchoice!='E'&&userchoice!='D'&&userchoice!='P'&&userchoice!='T'&&userchoice!='Q'){cout<<"数据不合要求，请重新输入"<<endl;cin>>userchoice; }switch(userchoice){case 'I'://system("cls");cout<<"1.从文档读入字符和频度"<<endl;cout<<"2.终端输入字符和频度"<<endl;cin>>judge;if(judge==1){length=27;alpha=(char*)malloc(length*sizeof(char));frequent=(int*)malloc(length*sizeof(int));read(alpha,frequent,length);result=HuffmanCoding(HT, HC, alpha,frequent, length);if(result==OK){cout<<endl;cout<<"字符\t频度\n";for(int i=0;i<length;i++){cout<<alpha[i]<<"\t";cout<<frequent[i]<<"\n";}cout<<"\n建树操作成功"<<endl;}elsecout<<"\n建树操作失败"<<endl;}else if(judge==2){system("cls");cout<<"请输入字符的数量:"<<endl;cin>>length;while(length<=0) {cout<<"数据不合要求,请重新输入"<<endl;cin>>length; }alpha=(char*)malloc(length*sizeof(char));frequent=(int*)malloc(length*sizeof(int));for(int i=0;i<length;i++){cout<<"第"<<i+1<<"个字符是："<<endl;cin>>alpha[i];cout<<"它的权重是："<<endl;cin>>frequent[i];while(frequent[i]<=0) {cout<<"数据不合要求,请重新输入"<<endl;cin>>frequent[i]; }}result=HuffmanCoding(HT, HC, alpha,frequent, length);if(result==OK){cout<<endl;cout<<"字符\t频度\n";for(int i=0;i<length;i++){cout<<alpha[i]<<"\t";cout<<frequent[i]<<"\n";}cout<<"\n建树操作成功"<<endl;}elsecout<<"\n建树操作失败"<<endl;}break; case 'E'://system("cls");if(HC&&HT){result=Encoding(HT,HC,length);if(result==OK) cout<<"\n编码成功"<<endl;else cout<<"\n编码失败"<<endl;}else//哈夫曼树未建立 {cout<<"哈夫曼树未建立，从文件中读入哈夫曼树"<<endl; length=27;alpha=(char*)malloc(length*sizeof(char));frequent=(int*)malloc(length*sizeof(int));read(alpha,frequent,length);result=HuffmanCoding(HT, HC, alpha,frequent, length);;if(result==OK){cout<<endl;cout<<"字符\t频度\n";for(int i=0;i<length;i++){cout<<alpha[i]<<"\t";cout<<frequent[i]<<"\n";}cout<<"\n建树操作成功"<<endl;}elsecout<<"\n建树操作失败"<<endl;result=Encoding(HT,HC,length);if(result==OK) cout<<"\n哈夫曼树未建立，从文件中读入哈夫曼树,编码成功\n"<<endl;else cout<<"\n编码失败"<<endl;}break;case'D'://	system("cls");if(HT&&HC){result=Decoding(HT,HC,length);if(result==OK) cout<<"\n解码成功"<<endl;else cout<<"\n解码失败"<<endl;}else//哈夫曼树未建立 {cout<<"哈夫曼树未建立，从文件中读入哈夫曼树"<<endl; length=27;alpha=(char*)malloc(length*sizeof(char));frequent=(int*)malloc(length*sizeof(int));read(alpha,frequent,length);result=HuffmanCoding(HT, HC, alpha,frequent, length);;if(result==OK){cout<<endl;cout<<"字符\t频度\n";for(int i=0;i<length;i++){cout<<alpha[i]<<"\t";cout<<frequent[i]<<"\n";}cout<<"\n建树操作成功"<<endl;}elsecout<<"\n建树操作失败"<<endl;result=Decoding(HT,HC,length);if(result==OK) cout<<"\n哈夫曼树未建立，从文件中读入哈夫曼树,解码成功\n"<<endl;else cout<<"\n解码失败"<<endl;}break; case'P'://system("cls");result=Print();if(result==OK) cout<<"\n印代码文件成功"<<endl;else cout<<"\n印代码文件失败"<<endl;break; case'T'://	system("cls");if(!HT) {cout<<"树不存在"<<endl;break;}result=PrintTree(HT,GetHuffmanRoot(HT),0);if(result==OK) cout<<"\n画树成功"<<endl;else cout<<"\n画树失败"<<endl;break;case'Q':cout<<"感谢使用！"<<endl; return 0; }	}system("pause"); return 0;
}void onScreen()
{cout<<"-------------------------欢迎使用哈夫曼编译器----------------------------------"<<endl;cout<<"请选择需要进行的操作(输入相应字母)："<<endl;cout<<"I.初始化并建立哈夫曼树"<<endl;cout<<"E.利用哈夫曼树编码"<<endl;cout<<"D.利用哈夫曼树译码"<<endl;cout<<"P.印制代码文件"<<endl;cout<<"T.印制哈夫曼树"<<endl;cout<<"Q.退出程序"<<endl;
}Status read(char *alpha,int *frequent,int length)
{FILE *fp;char temp[50];if((fp=fopen("hfmTree.txt","r"))==NULL)cout<<"不能打开文件"<<endl;else{cout<<"打开文件hfmTree.txt成功"<<endl;int i=0;while((fscanf(fp,"%c\t%d\t%s\n", &alpha[i],&frequent[i],temp))!=EOF){i++;if(i>=length) break;}fclose(fp);cout<<"读入字符和频率成功"<<endl;} 
}void Select(HuffmanTree HT, int end, int *s1, int *s2)
{int min1, min2;//遍历数组初始下标为 1int i = 1;//找到还没构建树的结点while(HT[i].parent != 0 && i <= end) i++;min1 = HT[i].weight;*s1 = i;i++;while(HT[i].parent != 0 && i <= end)i++;//对找到的两个结点比较大小，min2为大的，min1为小的if(HT[i].weight < min1){min2 = min1;*s2 = *s1;min1 = HT[i].weight;*s1 = i;}else{min2 = HT[i].weight;*s2 = i;}//两个结点和后续的所有未构建成树的结点做比较for(int j=i+1; j <= end; j++){//如果有父结点，直接跳过，进行下一个if(HT[j].parent != 0){continue;}//如果比最小的还小，将min2=min1，min1赋值新的结点的下标if(HT[j].weight < min1){min2 = min1;min1 = HT[j].weight;*s2 = *s1;*s1 = j;}//如果介于两者之间，min2赋值为新的结点的位置下标else if(HT[j].weight >= min1 && HT[j].weight < min2){min2 = HT[j].weight;*s2 = j;}}
}Status HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, char* alpha,int *w, int n) 
{// 算法6.12// w存放n个字符的权值(均>0)，构造哈夫曼树HT，// 并求出n个字符的哈夫曼编码HCint i, j, m, s1, s2, start;char *cd;unsigned int c, f;if (n<=1) return ERROR;m = 2 * n - 1;HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));  // 0号单元未用for (i=1; i<=n; i++) { //初始化HT[i].weight=w[i-1];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;HT[i].alpha=alpha[i-1];HT[i].number=i;}for (i=n+1; i<=m; i++) { //初始化HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;HT[i].alpha='#';HT[i].number=i;}printf("\n哈夫曼树的构造过程如下所示：\n");printf("HT初态:\n  结点  alpha   weight  parent  lchild  rchild");for (i=1; i<=m; i++)printf("\n%4d%8c%8d%8d%8d%8d",i,HT[i].alpha,HT[i].weight,HT[i].parent,HT[i].lchild, HT[i].rchild);//  printf("    按任意键，继续 ...");//  getchar();printf("\nHT初态:\n  结点  alpha   weight  parent  lchild  rchild");for (i=n+1; i<=m; i++) {  // 建哈夫曼树// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，// 其序号分别为s1和s2。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;printf("\n\tselect: s1=%d   s2=%d\n", s1, s2);printf("  结点  alpha   weight  parent  lchild  rchild");for (j=1; j<=i; j++)printf("\n%4d%8c%8d%8d%8d%8d",j,HT[j].alpha,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);//printf("    按任意键，继续 ...");//  getchar();}/**/ //--- 从叶子到根逆向求每个字符的哈夫曼编码 ---cd = (char *)malloc(n*sizeof(char));    // 分配求编码的工作空间cd[n-1] = '\0';                         // 编码结束符。HC=(char**)malloc(n*sizeof(char*));for(i=1;i<=n;i++) HC[i] = (char *)malloc((n-start)*sizeof(char)); 	// 为第i个字符编码分配空间for (i=1; i<=n; ++i) {                  // 逐个字符求哈夫曼编码start = n-1;                          // 编码结束符位置for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent) // 从叶子到根逆向求编码{	if (HT[f].lchild==c) {start=start-1;cd[start] = '0';}else {start=start-1;//printf("\n%d",start);cd[start] = '1';}}strcpy(HC[i], &cd[start]);    // 从cd复制编码(串)到HC//	printf("\n%s",&cd[start]);// cout<<cd<<endl;}free(cd);   // 释放工作空间return OK;
} // HuffmanCodingStatus saveTreeFrequent(HuffmanTree HT, HuffmanCode HC,int length)
{FILE *fp;if((fp=fopen("hfmTree.txt","w+"))==NULL){cout<<"不能打开文件"<<endl;return ERROR;}else{cout<<"打开文件hfmTree.txt成功" <<endl;for(int i=1;i<=length;i++)fprintf(fp,"%c\t%d\t%s\n", HT[i].alpha,HT[i].weight,HC[i]);}fclose(fp);cout<<"保存哈夫曼树成功！"<<endl;return OK;	
}Status Encoding(HuffmanTree &HT,HuffmanCode &HC,int length)
{FILE *fp,*fs;if(!HC){int n=length;HC=(char**)malloc(n*sizeof(char*));int i;for(i=1;i<=n;i++) {HC[i] = (char *)malloc(10*sizeof(char)); }if((fp=fopen("hfmTree.txt","r"))==NULL){cout<<"不能打开文件hfmTree.txt"<<endl;return ERROR;}else{cout<<"打开文件hfmTree.txt成功"<<endl; int i=0;while((fscanf(fp,"%c\t%d\t%s\n", &HT[i].alpha,&HT[i].weight,HC[i]))!=EOF) {i++;if(i==length) break;}fclose(fp);cout<<"读入哈夫曼树成功！"<<endl;} 	}
//	for(int j=1;j<=length;j++) cout<<HC[j]<<endl;//准备好编码if((fp=fopen("ToBeTran.txt","r"))==NULL){cout<<"不能打开文件ToBeTran.txt"<<endl;return ERROR;} else{char temp;if((fs=fopen("CodeFile.txt","w+"))==NULL){cout<<"不能打开文件"<<endl;return ERROR;	}cout<<"打开文件ToBeTran.txt和成功"<<endl;cout<<"编码信息已存入CodeFile.txt,内容如下：\n"<<endl; while(fscanf(fp,"%c",&temp)!=EOF){if((temp>'Z'||temp<'A')&&(temp!=' ')){cout<<"\n\n出现不支持字符，编码中断"<<endl;return ERROR;}if(temp==' '){fprintf(fs,"%s ", HC[1]);printf("%s ", HC[1]);}else{int number=temp-'A'+2;fprintf(fs,"%s ", HC[number]);printf("%s ", HC[number]);}	}fclose(fp);fclose(fs);cout<<endl;}return OK;
}int GetHuffmanRoot(HuffmanTree HT)
{int i;for( i=1;;i++)if(HT[i].parent==0)break;return i;
}Status Decoding(HuffmanTree HT,HuffmanCode HC,int length)
{FILE *fp,*fs;char tempCode[20];char tempAlpha;if((fp=fopen("CodeFile.txt","r"))==NULL){cout<<"不能打开文件CodeFile.txt"<<endl;return ERROR;}else{if((fs=fopen("TextFile.txt","w+"))==NULL){cout<<"不能打开文件TextFile.txt"<<endl;return ERROR;}int Alphaposition;cout<<"打开文件CodeFile.txt和TextFile.txt成功"<<endl;cout<<"解码信息已存入TextFile.txt中，内容如下\n"<<endl; while((fscanf(fp,"%s",tempCode))!=EOF){unsigned int Alphaposition=GetHuffmanRoot(HT);for(int i=0,j=1;i<strlen(tempCode);i++){if(tempCode[i]=='0')Alphaposition=HT[Alphaposition].lchild;else if(tempCode[i]=='1')Alphaposition=HT[Alphaposition].rchild;else {cout<<"\n\n出现错误信息，解码中断\n";return ERROR;}	}tempAlpha=HT[Alphaposition].alpha;fprintf(fs,"%c",tempAlpha);printf("%c",tempAlpha); }cout<<endl;fclose(fp);fclose(fs);//关闭文件至关重要，不然下次再弄就出bug } return OK; 
}Status Print()
{FILE *fp,*fs;char tempCode[20];char tempAlpha;if((fp=fopen("CodeFile.txt","r"))==NULL){cout<<"不能打开文件CodeFile.txt"<<endl;return ERROR;}else{if((fs=fopen("CodePrin.txt","w+"))==NULL){cout<<"不能打开文件CodePrin.txt"<<endl;return ERROR;}cout<<"打开文件CodeFile.txt和CodePrin.txt成功"<<endl;cout<<"编码信息已存入CodePrin.txt中，内容如下：\n"<<endl;int Alphaposition;int count=0;while((fscanf(fp,"%s",tempCode))!=EOF){count+=strlen(tempCode);if(count>=50) {printf("\n");fprintf(fs,"\n");count=0; }printf("%s ",tempCode);fprintf(fs,"%s ",tempCode);}cout<<endl;fclose(fp);fclose(fs);//关闭文件至关重要，不然下次再弄就出bug cout<<"\n写入CodePrin.txt成功";} return OK; 
}Status writeTree(HuffmanTree HT,unsigned root,int level,FILE *fs)
{if(!HT) return ERROR;for(int i=1;i<level;i++){printf("\t");fprintf(fs,"\t");}fprintf(fs,"%c%d\n",HT[root].alpha,HT[root].number);printf("%c%d\n",HT[root].alpha,HT[root].number);if(root>27){writeTree(HT,HT[root].rchild, level+1,fs);writeTree(HT,HT[root].lchild, level+1,fs);}return OK;
}Status PrintTree(HuffmanTree HT,unsigned root,int level)
{if(!HT) return ERROR;FILE *fs;if((fs=fopen("TreePrint.txt","w+"))==NULL){cout<<"不能打开文件TreePrint.txt"<<endl;return ERROR;}cout<<"打开文件TreePrint.txt成功"<<endl; writeTree(HT,root,level,fs);fclose(fs);return OK;
}

设计和调试分析

1. 在调试HuffmanCoding函数时发现总是不能正确输出后十个字母相应的编码，耗费了大量时间，最终发现是malloc出现了问题。由于HC相当于二维数组，需要两次malloc，分别是

HC=(char**)malloc(n*sizeof(char*))

和

for(i=1;i<=n;i++) HC[i] = (char *)malloc((n-start)*sizeof(char))

但在最初漏掉了第一条语句，即使编译器不报错，HC所使用的空间也是非法的，自然导致了后续输出的问题。

2. 在进行保存等文件操作时，最初经常出现保存失败的情况。经过检查发现是漏掉了fclose()函数，在以后写代码的过程中，应牢记文件的打开与关闭操作必须成对出现。
3. 本算法的时间主要消耗在从结点中选择权值最小的两棵树根结点上，每构建一个非叶子结点都需要比较（i-1）次，构建n-1个非叶子结点总比较次数达到（3n-2）（n-1）/2,因此算法的时间复杂度为O（n2），空间复杂度为O（1）。

用户手册

1. 本程序的运行环境为windows10操作系统，执行文件为:哈夫曼树.exe；
2. 打开后显示文本方式的用户界面：
   -------------------------欢迎使用哈夫曼编译器--------------
   请选择需要进行的操作(输入相应字母)：
   I.初始化并建立哈夫曼树
   E.利用哈夫曼树编码
   D.利用哈夫曼树译码
   P.印制代码文件
   T.印制哈夫曼树
   Q.退出程序
   3. 输入I，初始化并建立哈夫曼树；输入E，利用哈夫曼树编码，如果哈夫曼树不存在，则可调用I；输入D，利用哈夫曼树译码。如果哈夫曼树不存在，则可调用I；输入P，印制代码文件；输入T，印制哈夫曼树；输入Q，退出程序。

测试结果

1. 输入I，初始化并建立哈夫曼树

字符    频度186    (此处为空格的=字符及其频度)
A       64
B       12
C       22
D       32
E       103
F       21
G       15
H       47
I       57
J       1
K       5
L       32
M       20
N       57
O       63
P       15
Q       1
R       48
S       51
T       80
U       23
V       8
W       18
X       1
Y       16
Z       1

2. 输入E，编码ToBeTran.txt中的文件，并将编码信息存入CodeFile.txt中，此时ToBeTran.txt中的内容为：

THIS IS MY FAVORITE PROGRAM

终端输出：

打开文件ToBeTran.txt和成功
编码信息已存入CodeFile.txt,内容如下：
1101 0001 0110 0011 111 0110 0011 111 110010 100011 111 110011 1010 1100000 1001 0010 0110 1101 010 111 100010 0010 1001 100001 0010 1010 110010
编码成功

3. 输入D，将CodeFile.txt中的编码解码并保存到TextFile.txt中，终端输出为：

打开文件CodeFile.txt和TextFile.txt成功
解码信息已存入TextFile.txt中，内容如下
THIS IS MY FAVORITE PROGRAM
解码成功

4. 输入P，将CodeFile.txt中的内容存入CodePrin.txt中，终端输出为：

打开文件CodeFile.txt和CodePrin.txt成功
编码信息已存入CodePrin.txt中，内容如下：
1101 0001 0110 0011 111 0110 0011 111 110010 100011 111
110011 1010 1100000 1001 0010 0110 1101 010 111 100010 0010 1001100001 0010 1010 110010
写入CodePrin.txt成功
印代码文件成功