【数据结构】哈夫曼树实现编码译码
根据一段字符串中字符的个数 作为该字符的权值生成哈夫曼树。 然后根据生成的哈夫曼编码，对任意字符串实现编码，对任意二进制串实现译码。程序运行结果：1.程序
& & & &根据一段字符串中字符的个数 作为该字符的权值生成树。
& & & &然后根据生成的，对任意字符串，对任意二进制串。
程序运行结果：
1.程序主界面：
2.根据字符串 创建哈夫曼树及编码：
3.生成的编码表如下：
4.根据生成的哈夫曼编码对字符串编码：
5.生成的编码保存在文件中：
6.对二进制串：
哈夫曼树的生成和编码的常见，以及编码和译码函数
//_HuffmanTree_H
#ifndef _HuffmanTree_H
#define _HuffmanTree_H
typedef struct
unsigned int parent,lchild,
}HTNode,*HuffmanT
typedef char **HuffmanC
//这三个是哈夫曼树的生成
int min1(HuffmanTree t,int i);
//选出权值数组中最小的一个 ，，
void select(HuffmanTree t,int i,int *s1,int *s2);
//权值数组中最小的两个，，，并把临时数组对应位置改为1防止重复选择
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n);
//根据权值数组W，和元素个数N开辟，HC存放编码
void getWeightInfile(int *w);// 从MyTxt.TXT里读入字母，以字母个数为权值，，生成数组并返回
void bianMaInFile(HuffmanTree *p,HuffmanCode cd);
//根据编码.txt里面字母，找到对应的下标，在hc里面匹配编码
void yimaInFile(HuffmanTree *p);
数的根结点下标应该为2n-1。。。所以只需根据编码 0 1确定向左还是向右 最终直到=遇到有意义的字母停止
对指定文件的读和写
//myfile.h
#ifndef _MYFILE_H
#define _MYFILE_H
#define MY_STRMAX 100
void changMyTxtFile();
void showMyTxtFile();
void showBianMaFile();
void showYiMaFile();
void changBianMaFile();
//myfile.h
//HuffmanTree.c
#include &stdio.h&
#include &stdlib.h&
#include &string.h&
#include &HuffmanTree.h&
int min1(HuffmanTree t,int i)
{ /* 返回i个结点中权值最小的树的根结点序号，函数select()调用 */
unsigned int k=; /* 取k为不小于可能的值(无符号整型最大值) */
for(j=1;j&=i;j++)
if(t[j].weight&k&&t[j].parent==0) /* t[j]是树的根结点 */
k=t[j].weight,flag=j;
t[flag].parent=1; /* 给选中的根结点的双亲赋1，避免第2次查找该结点 */
void select(HuffmanTree t,int i,int *s1,int *s2)
{ /* 在i个结点中选择2个权值最小的树的根结点序号，s1为其中序号小的那个 */
*s1=min1(t,i);
*s2=min1(t,i);
if(*s1&*s2)
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) /* 算法6.12 */
{ /* w存放n个字符的权值(均&0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC */
int m,i,s1,s2,start,num=0;
unsigned c,f;
//开辟的 比元素个数多 因为后续生成的新子树要用到
*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用 */
for(p=*HT+1,i=1;i&=n;++i,++p,++w,++num)
(*p).weight=*w; //这部分是给确定的子树赋值，包括字母a-z 权值从数组中得出
(*p).ch=97+
else if(i==26)
(*p).ch=97+
else if(i&=52&&i&26)
(*p).ch=65+
else if(i==53)
(*p).ch=32;
else if(i==54)
(*p).ch='\n';
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
for(;i&=m;++i,++p)
(*p).parent=0;
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=(*HT)[s2].parent=i;
//这部分给后面要用到的新节点 初值
(*HT)[i].lchild=s1;
(*HT)[i].rchild=s2;
(*HT)[i].ch='!';
//他们存放的是!
所以可以判断此节点是否有意义
(*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].
//哈夫曼 编码 的求出
保存在HC里面（二维数组）
/* 从叶子到根逆向求每个字符的赫夫曼编码 */
*HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
/* 分配n个字符编码的头指针向量([0]不用) */
cd=(char*)malloc(n*sizeof(char)); /* 分配求编码的工作空间 */
cd[n-1]='\0'; /* 编码结束符 */
for(i=1;i&=n;i++)
{ /* 逐个字符求赫夫曼编码 */
start=n-1; /* 编码结束符位置 */
for(c=i,f=(*HT)[i].f!=0;c=f,f=(*HT)[f].parent)
/* 从叶子到根逆向求编码 */
if((*HT)[f].lchild==c)
cd[--start]='0';
cd[--start]='1';
(*HC)[i]=(char*)malloc((n-start)*sizeof(char));
/* 为第i个字符编码分配空间 */
strcpy((*HC)[i],&cd[start]); /* 从cd复制编码(串)到HC */
free(cd); /* 释放工作空间 */
void getWeightInfile(int *w)
pfr = fopen(&记录信息\\mytxt.txt&, &r&);//读取文件
if (pfr==NULL)
printf(&文件操作失败&);
while (!feof(pfr))
//直到文件读取完毕，每次读取一行
char str[256] = {0};
fgets(str, 256, pfr);//读取一行
while(str[i]!=0)
//如果这是个字母，那么对应数组的从0-25 发现一个 对应的值加加
实现计算文件中字母的个数
if(str[i]&='z' && str[i]&='a')
w[str[i]-97]++;
if(str[i]&='Z'&& str[i]&='A')
w[str[i]-65+26]++;
if(str[i]==' ')
w[26*2]++;
if(str[i]=='\n')
w[26*2+1]++;
fclose(pfr);
//文件用完要关闭
void bianMaInFile(HuffmanTree *p,HuffmanCode cd)
//HuffmanTree ptr=(*p)+1;
int count=1;
pfr = fopen(&记录信息\\mytxt.txt&, &r&);//读取文件
pfw = fopen(&记录信息\\编码.txt&,&w&);//写入文件
if (pfr==NULL || pfw==NULL)
printf(&文件操作失败&);
while (!feof(pfr))
char str[256] = {0};
fgets(str, 256, pfr);//读取一行
while(str[i]!=0)
if(str[i]&=122 && str[i]&=97)
num=str[i]-96;
else if(str[i]&=90 && str[i]&=65)
num=str[i]-64+26;
else if(str[i]==32)
else if(str[i]=='\n')
if(num!=-1)//就把cd里面的编码 输出到 编码.txt里面
if(count==1)
//fputs(cd[num], pfw);
fprintf(pfw,&%s\n&,cd[num]);
fclose(pfr);
fclose(pfw);
void yimaInFile(HuffmanTree *p)
char s[2]={0};
int i=0,num=107;
//51=2*26-1
pfr = fopen(&记录信息\\编码.txt&, &r&);//读取文件
pfw = fopen(&记录信息\\译码.txt&,&w&);//写入文件
if (pfr==NULL || pfw==NULL)
printf(&文件操作失败&);
while (!feof(pfr))
char str[255] = {0};
fgets(str, 255, pfr);
i=0;//读取一行
while(str[i]!=0)
while(str[i]!=0)
if((*p)[num].ch!='!')
//如果发现 左右移动找到了字母 立马退出 匹配下一个
if(str[i]=='0')
num=(*p)[num].
else if(str[i]=='1')
num=(*p)[num].
if((*p)[num].ch=='!' && str[i]!='\0')
printf(&因为编码不全,%d-%d个编码被舍掉\n&,n+1,i);
else if(str[i]!='\0')
s[0]=(*p)[num].
fputs(s, pfw);
fclose(pfr);
fclose(pfw);
//myfile.c
#include &stdlib.h&
#include &stdio.h&
#include &myfile.h&
#include &conio.h&
void changMyTxtFile()
int num=1;
pfw=fopen(&记录信息\\mytxt.txt&,&w&);
if (pfw==NULL)
printf(&文件操作失败&);
while(s=getchar(),s!=-1)
fprintf(pfw,&%c&,s);
fclose(pfw);
void showMyTxtFile()
pfr=fopen(&记录信息\\mytxt.txt&,&r&);
if (pfr==NULL)
printf(&文件操作失败&);
while (!feof(pfr))
char str[256] = {0};
fgets(str, 256, pfr);
puts(str);
fclose(pfr);
void showBianMaFile()
pfr=fopen(&记录信息\\编码.txt&,&r&);
if (pfr==NULL)
printf(&文件操作失败&);
while (!feof(pfr))
char str[256] = {0};
fgets(str, 256, pfr);
puts(str);
fclose(pfr);
void showYiMaFile()
pfr=fopen(&记录信息\\译码.txt&,&r&);
if (pfr==NULL)
printf(&文件操作失败&);
while (!feof(pfr))
char str[256] = {0};
fgets(str, 256, pfr);
puts(str);
fclose(pfr);
void changBianMaFile()
pfw=fopen(&记录信息\\编码.txt&,&w&);
if (pfw==NULL)
printf(&记录信息\\文件操作失败&);
while(s=getchar(),s!=-1)
fprintf(pfw,&%c&,s);
fclose(pfw);
#include &STDLIB.H&
#include &STDIO.H&
#include &HuffmanTree.h&
#include &myfile.h&
#define MYHFMNUM 26*2+2
HuffmanTree HT;
HuffmanCode HC;
int w[MYHFMNUM]={0},n=MYHFMNUM,i;
char s[MY_STRMAX]={0};
system(&color 3e&);
system(&cls&);
puts(&***********************************************&);
1.创建新的编码&);
puts(&***********************************************&);
puts(&输入想要的操作:&);
scanf(&%d&,&num);
switch(num)
system(&cls&);
//每次操作清理屏幕
puts(&输入一段字符串，会根据字符数累加权值，从而生成树&);
changMyTxtFile();
getWeightInfile(w);
HuffmanCoding(&HT,&HC,w,n);
pfw=fopen(&记录信息\\编码表.txt&,&w&);
if (pfw==NULL)
printf(&文件操作失败&);
fprintf(pfw,&
for(i=1;i&=n;i++) //把生成的
存在文件中 便于对照
fprintf(pfw,&%10s\t%c\t%2d\n&,HC[i],HT[i].ch,HT[i].weight);
fclose(pfw);
system(&pause&);
goto MENU;
{ system(&cls&);
puts(&输入要编码的字符串&);
changMyTxtFile();
bianMaInFile(&HT,HC);
showBianMaFile();
system(&pause&);
goto MENU;
{ system(&cls&);
puts(&输入要译码的二进制数字&);
changBianMaFile();
yimaInFile(&HT);
showYiMaFile();
system(&pause&);
//暂停一下
相当于getch
goto MENU;
case 4:return 0;
default:puts(&输入有误!&);system(&pause&);goto MENU;
你最喜欢的涓婁紶鍙戝竷
禄 浠庣粓绔??鍏ヨ?缂栫爜鐨勫瓧绗︿覆锛屽?鎵