1、需求分析
1.1、问题阐述
利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道) ,每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。
1.2、基本要求
一个完整的系统应具有以下功能;
(1) I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。
(2) E:编码(Encoding).利用以建好的哈夫曼树(如不在内存,则从文件hfm'Tree中读入) ,对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。
(3)D:译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。
(4) P:印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上.每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。
(5) T:印哈夫曼树(Tree printing) 。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。
1.3、测试数据
(1)利用教科书例6-2的数据测试程序:
(2)用下表给出的字符集和权重建立哈夫曼树,并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE”。
字符 |
空格 |
A |
B |
C |
D |
E |
F |
G |
H |
频度 |
186 |
64 |
13 |
22 |
32 |
103 |
21 |
15 |
47 |
字符 |
I |
J |
K |
L |
M |
N |
O |
P |
Q |
频度 |
57 |
1 |
5 |
32 |
20 |
57 |
63 |
15 |
1 |
字符 |
R |
S |
T |
U |
V |
W |
X |
Y |
Z |
频度 |
48 |
51 |
80 |
23 |
8 |
18 |
1 |
16 |
1 |
2、设计概要
利用数组开到2*n-1的内存来存储哈夫曼树,然后利用文件流的操作读取、保存文件来实现各个功能。
3、详细设计
- 对于I初始化操作,从终端读取字符集大小n和n个字符,n个权值,然后开数组2*n-1,遍历n到2*n-1 ,每次查询数组0-N中没有双亲的结点的最小和次小结点作为该结点的左、右子节点。以此建立哈夫曼树,然后将哈夫曼树的各个数据存储进hfmTree.txt文件中。
- 对于E编码操作,利用建立好的哈夫曼树,首先进行各个字符的二进制码的编写,代码中利用了递归的算法,每次都对结点进行二进制编码赋值,然后递归左子树加个“0”,右子树则加个“1”,这样便生成了每个结点的二进制编码串了,然后读入文件ToBETran.txt文件中的数据,遍历数据中每一个字符,对每个字符代表的二进制编码存进Code File.txt文件中,便成功完成了编码。
- 对于D 译码操作,读取Code File.txt文件中的数据,定义一个pi=2*n-2(代表根节点),然后遍历数据,如果该数据为‘0’,则pi = hfmtree[pi].lchild,等于它的左子树的结点,否则pi 就等于它的右子树的结点,如果此时pi刚好为叶子节点,那么可以直接输出pi结点代表的字符,同时将pi再次赋值为2*n-2。最后便完成了所有数据的译码,并且存储进TextFile.txt文件。
- 对于P印代码文件操作,首先读取出CodeFile文件中的数据,然后以每行50个输出,代码设置了一个pi=1,在循环中pi与一直加1,如果pi%50==0就输出u按行符,并且将换行好的数据存放进CodePrin.txt文件中。
- 对于T打印哈夫曼树操作,我们利用了二位字符数组存放字符,首先全部赋值为空格,其次利用前序遍历哈夫曼树,将结点用‘o’存进二维数组中,最终我们可以以直观的形似看到这棵树,然后再输出它的前序遍历结果即可。
4、用户手册
输入I、E、D、P、T、Q进行不同的操作。
5、测试数据
①对测试数据(1)的测试结果:
1.当输入I时会初始化输入字符集和频率并建立哈夫曼树,同时将哈夫曼树的数据保存进hfmTree.txt文件中。(代码会自动将频度换成权重)
2.输入E时,会创建二进制哈夫曼编码,并且从ToBetran文件中读取的正文进行编码,然后将编码存放于CodeFile文件。(测试的ToBetran文件为:“ABBCAAEFGH”)。结果完全正确!
3.当输入D时,会对CodeFile文件中的二进制编码进行译码,译码后,将结果存进TextFile文件中。如图,译码的结果和我们文件中的样例完全一致,说明结果正确!
4.当输入P时,进行打印编码操作,将CodeFile文件中的数据以50一行在终端进行显示,然后存储进CodePrin文件,结果以50一行输出在终端,并且已经存进了CodeFile文件中,结果正确!
5.当输入T时,系统会打印哈夫曼树:这里以‘o’作为结点,更加的美观,便于观看,同时输出它的前序遍历结果。如图:结果正确。
6.当输入Q时,直接退出:
②对测试数据(2)的测试结果:
1.当输入I时会初始化并建立哈夫曼树,同时将哈夫曼树的数据保存进hfmTree.txt文件中。
2.输入E时,会创建二进制哈夫曼编码,并且从ToBetran文件中读取的正文进行编码,然后将编码存放于CodeFile文件。(测试样例提供的ToBetran文件为:“THIS PROGRAM IS MY FAVORITE”)。结果完全正确!
3.当输入D时,会对CodeFile文件中的二进制编码进行译码,译码后,将结果存进TextFile文件中。如图,译码的结果和我们文件中的样例完全一致,说明结果正确。
4.当输入P时,进行打印编码操作,将CodeFile文件中的数据以50一行在终端进行显示,然后存储进CodePrin文件,结果以50一行输出在终端,并且已经存进了CodeFile文件中,结果正确!
5.当输入T时,系统会打印哈夫曼树:这里以‘o’作为结点,更加的美观,便于观看,同时输出它的前序遍历结果。由于数据过多,打印出来在终端自动换行了,所以利用小的数据进行对打印操作的测试,利用(A B C D E)权重为:(3 2 4 5 7);如图:结果正确。
6.当输入Q时,直接退出:
- 附录
源程序文件名清单:
CodeFile.txt
CodePrin.txt
hfmTree.txt
TextFile.txt
ToBetran.txt
哈夫曼编译码器.cpp
哈夫曼编译码器.exe
5、源代码
//
// Created by stu_kk on 2022/4/16.
//
#include<bits/stdc++.h>
using namespace std;
int n = 0;
char word[10001];//
int wei[10001];//权重
typedef struct HuffmanTree{
char pi;
int weight;
int parent,lchild,rchild;
}Tree;
string code[10000];
//初始化操作
Tree *hftree;
void crearteTree(int n){
hftree= (Tree*) malloc(sizeof(Tree)*(2*n-1));
for(int i = 0;i<n;i++){
hftree[i].pi = word[i];
hftree[i].weight = wei[i];
hftree[i].parent = hftree[i].lchild = hftree[i].rchild = -1;
}
for(int i = n;i<2*n-1;i++){
hftree[i].parent = -1;
hftree[i].pi = '$';
int min = 1000000;//最小
int cmin = 1000000;//次小
int mpi = -1;
int cmpi = -1;
for(int j = 0;j<i;j++){
if(hftree[j].parent == -1) {
if (hftree[j].weight < min) {
if(min < cmin){
cmin = min;
cmpi = mpi;
}
min = hftree[j].weight;
mpi = j;
}
else {
if (hftree[j].weight < cmin) {
cmin = hftree[j].weight;
cmpi = j;
}
}
}
}
hftree[i].weight = cmin+min;
hftree[i].lchild = mpi;
hftree[i].rchild = cmpi;
hftree[mpi].parent = i;
hftree[cmpi].parent = i;
}
}
void Init(){
cout<<"输入的是(1.权重)还是(2.字符出现频率)"<<endl;
int is1;
cin>>is1;
if(is1 == 1){
cout<<"输入字符集大小:";
cin>>n;
cout<<"输入"<<n<<"个字符集:(如果输入的是空格,请用'.'表示)";
for(int i = 0;i<n;i++){
cin>>word[i];
}
cout<<"输入"<<n<<"个字符集的权重:";
for(int i = 0;i<n;i++){
cin>>wei[i];
}
}
else{
cout<<"输入字符集大小:";
cin>>n;
cout<<"输入"<<n<<"个字符集:(如果输入的是空格,请用'.'表示)";
for(int i = 0;i<n;i++){
cin>>word[i];
}
cout<<"输入"<<n<<"个字符集的出现频率:";
for(int i = 0;i<n;i++){
double as;
cin>>as;
wei[i] = as * 100;
}
};
cout<<"输入数据成功,正在创建哈夫曼树......."<<endl;
crearteTree(n);
cout<<"创建哈夫曼树成功,下面输出该哈夫曼树的参数。"<<endl;
cout<<"结点i"<<"\t字符"<<"\t权值"<<"\t双亲"<<"\t左孩子"<<"\t右孩子"<<endl;
for(int i = 0;i<2*n-1;i++){
cout<<i<<"\t"<<hftree[i].pi<<"\t"<<hftree[i].weight<<"\t"<<hftree[i].parent<<"\t"<<hftree[i].lchild<<"\t"<<hftree[i].rchild<<endl;
}
FILE *fp;
if((fp = fopen("hfmTree.txt","w")) == NULL){
cout<<"打开文件失败"<<endl;
}
//数据存进hfmTree.txt文件
for(int i = 0;i<2*n-1;i++){
fprintf(fp,"%d ",i);
fwrite(&word[i],1,1,fp);
fprintf(fp," %d ",hftree[i].weight);
fprintf(fp,"%d ",hftree[i].parent);
fprintf(fp,"%d ",hftree[i].lchild);
fprintf(fp,"%d ",hftree[i].rchild);
}
fclose(fp);
cout<<"哈夫曼树创建成功并且存入文件hfmTree.txt中了!!!"<<endl;
}
//初始化操作
//EEEEEEEEEEEEEEE编码编码
void bianma(Tree *tree,int pi,string s){//递归编码
code[tree[pi].pi] = s;
if(tree[pi].lchild != -1)
bianma(tree,tree[pi].lchild,s+"0");
if(tree[pi].rchild != -1)
bianma(tree,tree[pi].rchild,s+"1");
}
void E(){//编码
bianma(hftree,2*n-2,"");
cout<<"二进制码生成成功,编码结果为:"<<endl;
cout<<"结点i"<<"\t字符"<<"\t权值"<<"\t编码"<<endl;
for(int i = 0;i<n;i++){
cout<<i<<"\t"<<hftree[i].pi<<"\t"<<hftree[i].weight<<"\t"<<code[hftree[i].pi]<<endl;
}
cout<<"接下来读取ToBetran文件的正文并且进行编码:"<<endl;
FILE *fp = fopen("ToBetran.txt","r");
char mp[1001];
int po = 0;
while(1){
char di = fgetc(fp);
if(di == EOF)
break;
mp[po++] = di;
}
fclose(fp);
string s = mp;
cout<<mp<<"的编码为: ";
string ans = "";
for(int i = 0;i<po;i++){
if(mp[i]==' '){
mp[i] = '.';
}
cout<<code[mp[i]];
ans += code[mp[i]];
}
cout<<endl;
cout<<"将编好的码存进CodeFile.txt中"<<endl;
FILE *p = fopen("CodeFile.txt","w");
char nnp[ans.length()];
for(int i = 0;i<ans.length();i++){
nnp[i] = ans[i];
}
fwrite(nnp,sizeof(nnp),1,p);
fclose(p);
cout<<"编好的码存进CodeFile.txt成功!!!"<<endl;
}
//EEEEEEEEEE编码编码
void Menu(){
cout<<"---------------哈夫曼编码器/译码器----------------"<<endl;
cout<<" I:初始化并创建哈夫曼树 E:编码 "<<endl;
cout<<" D:对二进制码进行译码 P:打印编码 "<<endl;
cout<<" T:哈夫曼树 Q:退出 "<<endl;
cout<<"-----------------------------------------------"<<endl;
}
void D(){
cout<<"先将CodeFile文件中的二进制编码取出:"<<endl;
FILE *p = fopen("CodeFile.txt","r");
char ch[10001] ;
int po = 0;
while(true){
char as = fgetc(p);
if(as == EOF)
break;
ch[po++] = as;
}
cout<<"CodeFile文件中的二进制编码为:"<<ch<<endl;
cout<<"接着对二进制编码进行翻译:"<<endl;
cout<<ch<<"的翻译结果为:";
int pi = 2*n-2;
string ans = "";
for(int i =0;i < po;i++){
if(ch[i] == '0'){
pi = hftree[pi].lchild;
}
else{
pi = hftree[pi].rchild;
}
if(hftree[pi].lchild == -1 && hftree[pi].rchild == -1){
if(hftree[pi].pi == '.'){
ans+=' ';
}
else
ans+=hftree[pi].pi;
pi = 2*n-2;
}
}
cout<<ans<<endl;
cout<<"将其存进TextFile文件中"<<endl;
FILE *fp = fopen("TextFile.txt","w");
for(int i = 0;i<ans.length();i++)
fprintf(fp,"%c",ans[i]);
fclose(fp);
cout<<"数据存进TextFile文件成功!"<<endl;
}
//DDDDDDDDDDD
//PPPPPPP
void P(){
cout<<"将CodeFile文件中的数据以50一行在终端进行显示,然后存储进CodePrin文件:"<<endl;
FILE *cf = fopen("CodeFile.txt","r");
FILE *cp = fopen("CodePrin.txt","w");
char temp;
fscanf(cf,"%c",&temp);
for(int i = 1;!feof(cf);i++){
cout<<temp;
fputc(temp,cp);
fscanf(cf,"%c",&temp);
if(i%50 == 0) {
cout << endl;
fputc('\n',cp);
}
}
cout<<endl;
cout<<"存储进CodePrin文件成功!"<<endl;
}
//PPPPPP
//TTTTTTTT
char mp[151][151];
void prin(int l,int r,int num,int ceng){
mp[l][r] = hftree[num].weight;
if(hftree[num].lchild !=-1){
prin(l+1,r - (ceng - l - 1),hftree[num].lchild,ceng);
}
if(hftree[num].rchild !=-1){
prin(l+1,r + (ceng - l - 1),hftree[num].rchild,ceng);
}
}
int findchenshu(int pi){//递归计算层数
if(pi == -1){
return 0;
}
int lnum = findchenshu(hftree[pi].lchild) + 1;
int rnum = findchenshu(hftree[pi].rchild) + 1;
return max(lnum,rnum);
}
void out(int pi){
if(pi == -1){
return ;
}
cout<<hftree[pi].pi<<"\t"<<hftree[pi].weight<<endl;
out(hftree[pi].lchild);
out(hftree[pi].rchild);
}
void T(){
cout<<"打印哈夫曼树:"<<endl;
int num = 2*n-2;
memset(mp,' ',sizeof(mp));//先都存为空格
int cengshu = findchenshu(2*n-2);//计算层数
cout<<"测试:层数为:"<<cengshu<<endl;
int zhongjian = 1;
for(int i = 1;i<=cengshu;i++){
zhongjian *= 2;
}
zhongjian--;
prin(0,zhongjian/2,num,cengshu);
for(int i = 0;i<zhongjian;i++){
bool is = true;
for(int j = 0;j<zhongjian;j++){
if(mp[i][j] == ' '){
cout<<mp[i][j];
}
else{
is = false;
cout<<'o';
}
}
cout<<endl;
if(is){
break;
}
}
cout<<"输出成功,其中,该树的先序遍历为:"<<endl;
cout<<"字符"<<"\t"<<"权重"<<endl;
out(2*n-2);
cout<<"哈夫曼树打印完毕"<<endl;
}
//TTTTTTTTT
int main(){
while(true){
char choose;//选择什么操作
Menu();//显示菜单
cout<<"请输入你想要进行的操作"<<endl;
cin>>choose;
switch (choose) {
case 'I':
Init();
break;
case 'E'://c创建二进制哈夫曼编码,并且从ToBetran文件中读取的正文进行编码,然后存放于CodeFile文件
E();
break;
case 'D'://对CodeFile文件中的二进制编码进行译码。
D();
break;
case 'P':
P();//将CodeFile文件中的数据以50一行在终端进行显示,然后存储进CodePrin文件
break;
case 'T':
T();//打印哈夫曼树
break;
case 'Q':
exit(0);
default:
break;
}
}
return 0;
}
其中,一些文件为:
ToBetran.txt文本中的数据为:文章来源:https://www.toymoban.com/news/detail-434813.html
THIS PROGRAM IS MY FAVORITE
三个月前写的了,如果有问题的话,就直接联系我要一些文件。 文章来源地址https://www.toymoban.com/news/detail-434813.html
到了这里,关于数据结构与算法(C语言版)---哈夫曼编译码器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!