根据一段字符串中字符的个数 作为该字符的权值生成哈夫曼树。
然后根据生成的哈夫曼编码，对任意字符串实现编码，对任意二进制串实现译码。
程序运行结果：
1.程序主界面：
2.根据字符串 创建哈夫曼树及编码：
3.生成的编码表如下：
4.根据生成的哈夫曼编码对字符串编码：
6.对二进制串译码：
结果：
代码：
//_HuffmanTree_H
#ifndef _HuffmanTree_H
#define _HuffmanTree_H
typedef struct
{
unsigned int weight;
char ch;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
//这三个是哈夫曼树的生成
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确定向左还是向右 最终直到=遇到有意义的字母停止
#endif //
对指定文件的读和写
//myfile.h #ifndef _MYFILE_H #define _MYFILE_H #define MY_STRMAX 100 void changMyTxtFile(); void showMyTxtFile(); void showBianMaFile(); void showYiMaFile(); void changBianMaFile(); #endif //myfile.h
//HuffmanTree.c #include <stdio.h> #include <stdlib.h> #include <string.h> #include "HuffmanTree.h" int min1(HuffmanTree t,int i) { /* 返回i个结点中权值最小的树的根结点序号，函数select()调用 */ int j,flag; unsigned int k=10000000; /* 取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次查找该结点 */ return flag; } void select(HuffmanTree t,int *s2) { /* 在i个结点中选择2个权值最小的树的根结点序号，s1为其中序号小的那个 */ int j; *s1=min1(t,i); *s2=min1(t,i); if(*s1>*s2) { j=*s1; *s1=*s2; *s2=j; } } void HuffmanCoding(HuffmanTree *HT,int n) /* 算法6.12 */ { /* w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC */ int m,i,s1,s2,start,num=0; unsigned c,f; HuffmanTree p; char *cd; if(n<=1) return; m=2*n-1; //开辟的空间 比元素个数多 因为后续生成的新子树要用到 *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 权值从数组中得出 if(i<26) (*p).ch=97+num; else if(i==26) { (*p).ch=97+num; num=-1; } else if(i<=52&&i>26) (*p).ch=65+num; 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].weight; } //哈夫曼 编码 的求出 保存在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].parent;f!=0;c=f,f=(*HT)[f].parent) /* 从叶子到根逆向求编码 */ if((*HT)[f].lchild==c) cd[--start]='0'; else 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) { FILE *pfr; int i=0; pfr = fopen("记录信息\\mytxt.txt","r");//读取文件 if (pfr==NULL) { printf("文件操作失败"); return ; } else { while (!feof(pfr)) //直到文件读取完毕，每次读取一行 { char str[256] = {0}; fgets(str,256,pfr);//读取一行 i=0; while(str[i]!=0) //如果这是个字母，那么对应数组的从0-25 发现一个 对应的值加加 实现计算文件中字母的个数 { if(str[i]<='z' && str[i]>='a') //97-122 65-90 32 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]++; i++; } } } fclose(pfr); } //文件用完要关闭 void bianMaInFile(HuffmanTree *p,HuffmanCode cd) { FILE *pfr; FILE *pfw; //HuffmanTree ptr=(*p)+1; int i; int num; int count=1; pfr = fopen("记录信息\\mytxt.txt","r");//读取文件 pfw = fopen("记录信息\\编码.txt","w");//写入文件 if (pfr==NULL || pfw==NULL) { printf("文件操作失败"); return ; } else { while (!feof(pfr)) { char str[256] = {0}; fgets(str,pfr);//读取一行 i=0; num=-1; while(str[i]!=0) { if(str[i]<=122 && str[i]>=97) //1-26 num=str[i]-96; else if(str[i]<=90 && str[i]>=65) //27-52 num=str[i]-64+26; else if(str[i]==32) num=53; else if(str[i]=='\n') num=54; if(num!=-1)//就把cd里面的编码 输出到 编码.txt里面 { if(count==1) count++; else //fputs(cd[num],pfw); fprintf(pfw,"%s\n",cd[num]); } i++; num=-1; } } fclose(pfr); fclose(pfw); } } void yimaInFile(HuffmanTree *p) { FILE *pfr; FILE *pfw; char s[2]={0}; int i=0,num=107; //51=2*26-1 2*54-1 int n; pfr = fopen("记录信息\\编码.txt","r");//读取文件 pfw = fopen("记录信息\\译码.txt","w");//写入文件 if (pfr==NULL || pfw==NULL) { printf("文件操作失败"); return ; } else { while (!feof(pfr)) { char str[255] = {0}; fgets(str,255,pfr); i=0;//读取一行 num=107; while(str[i]!=0) { n=i; while(str[i]!=0) { if((*p)[num].ch!='!') //如果发现 左右移动找到了字母 立马退出 匹配下一个 break; if(str[i]=='0') //0左1右 num=(*p)[num].lchild; else if(str[i]=='1') num=(*p)[num].rchild; i++; } if((*p)[num].ch=='!' && str[i]!='\0') printf("因为编码不全,%d-%d个编码被舍掉\n",n+1,i); else if(str[i]!='\0') { s[0]=(*p)[num].ch; fputs(s,pfw); } num=107; } } } fclose(pfr); fclose(pfw); }
//myfile.c #include <stdlib.h> #include <stdio.h> #include "myfile.h" #include <conio.h> void changMyTxtFile() { FILE *pfw; int s; int num=1; pfw=fopen("记录信息\\mytxt.txt","w"); if (pfw==NULL) { printf("文件操作失败"); return; } while(s=getchar(),s!=-1) { fprintf(pfw,"%c",s); } fclose(pfw); } void showMyTxtFile() { FILE *pfr; pfr=fopen("记录信息\\mytxt.txt","r"); if (pfr==NULL) { printf("文件操作失败"); return ; } else { while (!feof(pfr)) { char str[256] = {0}; fgets(str,pfr); //动态 遍历文件 puts(str); } } fclose(pfr); } void showBianMaFile() { FILE *pfr; pfr=fopen("记录信息\\编码.txt",pfr); puts(str); } } fclose(pfr); } void showYiMaFile() { FILE *pfr; pfr=fopen("记录信息\\译码.txt",pfr); puts(str); } } fclose(pfr); } void changBianMaFile() { FILE *pfw; int s; pfw=fopen("记录信息\\编码.txt","w"); if (pfw==NULL) { printf("记录信息\\文件操作失败"); return ; } while(s=getchar(),s); } fclose(pfw); }
//main.c #include <STDLIB.H> #include <STdio.H> #include "HuffmanTree.h" #include "myfile.h" #define MYHFMNUM 26*2+2 int main() { HuffmanTree HT; HuffmanCode HC; int w[MYHFMNUM]={0},n=MYHFMNUM,i; char s[MY_STRMAX]={0}; int num; system("color 3e"); //改颜色 MENU: system("cls"); puts("***********************************************"); puts(" 1.创建新的编码"); puts(" 2.编码"); puts(" 3.译码"); puts(" 4.退出"); puts("***********************************************"); puts("输入想要的操作:"); scanf("%d",&num); switch(num) { case 1: { FILE *pfw; system("cls"); //每次操作清理屏幕 puts("输入一段字符串，会根据字符数累加权值，从而生成树"); changMyTxtFile(); getWeightInfile(w); HuffmanCoding(&HT,&HC,w,n); pfw=fopen("记录信息\\编码表.txt","w"); if (pfw==NULL) { printf("文件操作失败"); return 0; } fprintf(pfw," 编码 字母 权值\n"); 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; } case 2: { system("cls"); puts("输入要编码的字符串"); changMyTxtFile(); bianMaInFile(&HT,HC); showBianMaFile(); system("pause"); goto MENU; } case 3: { system("cls"); puts("输入要译码的二进制数字"); changBianMaFile(); yimaInFile(&HT); showYiMaFile(); system("pause"); //暂停一下 相当于getch goto MENU; } case 4:return 0; default:puts("输入有误!");system("pause");goto MENU; } return 0; }
