📄 赫夫曼编码.cpp
字号:
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
#define N 30
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode, *HuffmanTree;
typedef char * * HuffmanCode;
void Select(HuffmanTree &HT,int a,int &s1, int &s2) //在HT[1...i-1]中选择parent为0且weight最小得两个结点，其序号分别为s1,s2
{
for(int j=1;j<=a;++j) //s1的开始定位
if(!HT[j].parent)
{
s1=j;
break;
}
for(int k=1;k<=a;++k) //s2的开始定位
if((!HT[k].parent) && (k!=s1))
{
s2=k;
break;
}
for(int l=s1;l<=a;++l) //s1确定为最小的
{
if(!HT[l].parent)
if(HT[l].weight<HT[s1].weight)
s1=l;
}
for(int r=s1;r<=a;++r) //s2确定为除了s1最小的
{
if(s1==s2)
for(int k=s2+1;k<=a;++k)
{
if((!HT[k].parent) )
{
s2=k;
break;
}
}
if((!HT[r].parent) &&(r!=s1))
if(HT[r].weight<HT[s2].weight)
s2=r;
}
}
void HuffmanCoding(HuffmanTree &HT ,HuffmanCode &HC, int *w, int n)
{
//int *w 是一个数组，用来存放所有叶子节点的权值 存放叶子节点的个数
HTNode *p;
int m,i,start,f; //m记录总的节点数
int s1,s2;
char *cd;
unsigned int c;
if(n<=1) return;
m=2*n-1; //一棵有n个节点的赫夫曼树共有2n-1个节点
//从叶子到根逆向求每个字符的赫夫曼编码
HT =(HuffmanTree)malloc ((m+1)*sizeof(HTNode)); //0号单元未用 （相当于有一个头节点）
for(p=HT+1, i=1;i<=n;++i,++p,++w)
//*p={*w,0,0,0}; //先将前n个节点的权值信息输入
{
p->weight=*w;
p->lchild=p->parent=p->rchild=0;
}
for(;i<=m;++i,++p) //将其余节点的权值初始化为0
// *p={0,0,0,0};
p->weight=p->lchild=p->parent=p->rchild=0;
for(i=n+1;i<=m;++i)
{ //在HT[1..n]选择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);
}
//上面已经将赫夫曼树建好下面进行编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n个字符编码的头指针向量
cd=(char *)malloc (n*sizeof(char));
cd[n-1] ='\0'; //编码结束符(2n-1个结点的赫夫曼树的深度为n,则编码最长n-1)
for(i=1;i<=n;++i)
{
start=n-1; //编码结束位置
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //从叶子到根逆向求编码 f始终纪录当前结点的双亲结点的编号
if(HT[f].lchild==c) //f==0表示已经到根节点
cd[--start]='0';
else cd[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间
strcpy(HC[i],&cd[start]); // 从复制编码串到HC
}
free(cd);
}
int INCode(char *code,HuffmanCode &HC)
{
for(int i=1;i<=N;++i)
if(!strcmp(code,HC[i]))
return i;
return 0;
}
void main()
{
HuffmanTree HT;
HuffmanCode HC; //存放各个字符的赫夫曼编码
int weight[N];
/*
int num;
printf("\n请输入你要编码的节点的个数：");
scanf("%d",&num);
printf("\n\n请输入每个要编码字符的权值：");
for(int i=1;i<=num;++i)
{
scanf("%d", &weight[i-1]);
}
HuffmanCoding(HT ,HC, weight, num);
printf("\n\n下面输出编码的结果：\n"); //此步操作结束后i的值为num+1
for(i=1;i<=num;++i)
{
printf("%s\n",HC[i]);
}*/
for(int i=0;i<N;++i)
weight[i]=0; //先将权值数组初始化为0
FILE *fp1,*fp2,*fp3;
char ch,temp='a';
char word[30];
for(int k=0;k<N-4;k++)
{
word[k]=temp; //此数组的建立，使后面的编码输出非常方便
temp++;
}
word[26]=','; word[27]='.';
word[28]='!'; word[29]=' ';
if((fp1=fopen("D://yanggang.txt","r"))==NULL)
{
printf("\n文件1打开失败！\n");
exit(0);
}
else printf("\n文件1打开成功！\n");
ch=fgetc(fp1);
while(ch!=EOF)
{
switch(ch) //权值数组的前26个数存储各个英文字母的出现次数
{
case 'a': //后4个存储常用的英文标点
weight[0]++; break;
case 'b':
weight[1]++; break;
case 'c':
weight[2]++; break;
case 'd':
weight[3]++; break;
case 'e':
weight[4]++; break;
case 'f':
weight[5]++; break;
case 'g':
weight[6]++; break;
case 'h':
weight[7]++; break;
case 'i':
weight[8]++; break;
case 'j':
weight[9]++; break;
case 'k':
weight[10]++; break;
case 'l':
weight[11]++; break;
case 'm':
weight[12]++; break;
case 'n':
weight[13]++; break;
case 'o':
weight[14]++; break;
case 'p':
weight[15]++; break;
case 'q':
weight[16]++; break;
case 'r':
weight[17]++; break;
case 's':
weight[18]++; break;
case 't':
weight[19]++; break;
case 'u':
weight[20]++; break;
case 'v':
weight[21]++; break;
case 'w':
weight[22]++; break;
case 'x':
weight[23]++; break;
case 'y':
weight[24]++; break;
case 'z':
weight[25]++; break;
case ',':
weight[26]++; break;
case '.':
weight[27]++; break;
case '!':
weight[28]++; break;
case ' ':
weight[29]++; break;
} //switch
ch=fgetc(fp1);
}//while
fclose(fp1); //关闭原文件
for(int t=1; t<=N; t++)
{ //显示各个字符在要编码文件中出现的次数
printf(" %c :",word[t-1]);
printf(" %d ", weight[t-1]);
if(t%5==0)
printf("\n\n");
}
HuffmanCoding(HT ,HC, weight, N);
printf("\n\n经过赫夫曼编码后各个字符的编码是：\n"); // 显示各个字符的赫夫曼编码
for(int j=0;j<N;j++)
{
printf(" %c:",word[j]);
printf(" %s\n",HC[j+1]);
}
if((fp2=fopen("d://translating.txt","w+"))==NULL)
{
printf("\n文件2打开失败！\n");
exit(0);
}
else printf("\n文件2打开成功！\n");
if((fp1=fopen("d://yanggang.txt","r"))==NULL)
{
printf("\n文件1打开失败！\n");
exit(0);
}
else printf("\n文件1打开成功！\n");
ch=fgetc(fp1);
while(ch!=EOF)
{
switch(ch) //权值数组的前26个数存储各个英文字母的出现次数
{
case 'a': //后4个存储常用的英文标点
fputs(HC[1],fp2); break;
case 'b': //读原文件，同时将编码的结果写到fp2指向的文件中
fputs(HC[2],fp2); break;
case 'c':
fputs(HC[3],fp2); break;
case 'd':
fputs(HC[4],fp2); break;
case 'e':
fputs(HC[5],fp2); break;
case 'f':
fputs(HC[6],fp2); break;
case 'g':
fputs(HC[7],fp2); break;
case 'h':
fputs(HC[8],fp2); break;
case 'i':
fputs(HC[9],fp2); break;
case 'j':
fputs(HC[10],fp2); break;
case 'k':
fputs(HC[11],fp2); break;
case 'l':
fputs(HC[12],fp2); break;
case 'm':
fputs(HC[13],fp2); break;
case 'n':
fputs(HC[14],fp2); break;
case 'o':
fputs(HC[15],fp2); break;
case 'p':
fputs(HC[16],fp2); break;
case 'q':
fputs(HC[17],fp2); break;
case 'r':
fputs(HC[18],fp2); break;
case 's':
fputs(HC[19],fp2); break;
case 't':
fputs(HC[20],fp2); break;
case 'u':
fputs(HC[21],fp2); break;
case 'v':
fputs(HC[22],fp2); break;
case 'w':
fputs(HC[23],fp2); break;
case 'x':
fputs(HC[24],fp2); break;
case 'y':
fputs(HC[25],fp2); break;
case 'z':
fputs(HC[26],fp2); break;
case ',':
fputs(HC[27],fp2); break;
case '.':
fputs(HC[28],fp2); break;
case '!':
fputs(HC[29],fp2); break;
case ' ':
fputs(HC[30],fp2); break;
} //switch
ch=fgetc(fp1);
}//while
fclose(fp1);
fclose(fp2);
//至此编码结束，下面读已经编码好的文件再解码文件
char *code;
int codenum=2;
int location;
char str[N];
if((fp2=fopen("d://translating.txt","r"))==NULL)
{
printf("\n文件2打开失败！\n");
exit(0);
}
else printf("\n文件2打开成功！\n");
if((fp3=fopen("d://retranslating.txt","w+"))==NULL)
{
printf("\n文件3打开失败！\n");
exit(0);
}
else printf("\n文件3打开成功！\n");
code=fgets(str,codenum,fp2);
while(!feof(fp2))
{
//从已经编码的文件中读codenum-1个字符，
//直到代表的字符串是已经存在的编码
while(!INCode(code,HC))
{
fseek(fp2,-codenum+1L,1 );
codenum++;
code=fgets(str,codenum,fp2);
}
location=INCode(code,HC);
fputc(word[location-1],fp3);
codenum=2;
code=fgets(str,codenum,fp2);
}
fclose(fp2);
fclose(fp3);
}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -