哈夫曼编码/译码器整套代码（历史博客有详细解读）：

---

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define Max 100                     //最大叶子结点个数//定义哈夫曼树的结点
typedef struct {char data;     //数据域float weight;    //权值域int parent;    //双亲域int LChild;    //左孩子域int RChild;    //右孩子域
}Huffnode;
Huffnode* ht;//定义编码的结点
typedef struct {char cd[Max];                //cd[]存放哈夫曼编码int start;
}Huffcode;
Huffcode* hc;//菜单
void Menu()
{printf("*****************************************\n");printf("*                                       *\n");printf("*          哈夫曼编/译码系统            *\n");printf("*                                       *\n");printf("*****************************************\n");printf("*            1.调用已初始化的           *\n");printf("*            2.手动初始化               *\n");printf("*            E(e).编码                  *\n");printf("*            D(d).译码                  *\n");printf("*            P(p).打印代码文件          *\n");printf("*            T(t).打印哈夫曼树          *\n");printf("*            Q(q).退出                  *\n");printf("*****************************************\n");printf("请键入操作：");
}//输入结点信息
void Input() {void Hfmtree(Huffnode * ht);void Huffcoding(Huffnode * ht);FILE* fp;int i, n;printf("enter elem number:");scanf_s("%d", &n);ht = (Huffnode*)malloc((2 * n) * sizeof(Huffnode));if (ht == NULL) {printf("wrong!");exit(0);}ht[0].weight = n;for (i = 1; i <= n; i++) {char a = getchar();printf(" %d elem data and weight(中间用空格隔开):", i);scanf_s("%c%f", &ht[i].data, 1, &ht[i].weight);}Hfmtree(ht);Huffcoding(ht);if ((fp = fopen("D:\\hfm\\hfmtree.txt", "w")) == NULL) {printf("Open file hfmtree.txt error!\n");exit(0);}fputs("初始化如下：\n", fp);fprintf(fp, "%f\n", ht[0].weight);for (int i = 1; i <= ht[0].weight; i++)fprintf(fp, "%c%f\n", ht[i].data, ht[i].weight);fclose(fp);printf("\n\n\n初始化已完成，已存入hfmtree.txt文件中！\n");
}//初始化带权结点
void Init() {void Hfmtree(Huffnode * ht);void Huffcoding(Huffnode * ht);FILE* fp;ht = (Huffnode*)malloc((2 * Max) * sizeof(Huffnode));if (ht == NULL) {printf("wrong!");exit(0);}ht[0].weight = 26;ht[1].data = 'A'; ht[1].weight = 64;ht[2].data = 'B'; ht[2].weight = 13;ht[3].data = 'C'; ht[3].weight = 22;ht[4].data = 'D'; ht[4].weight = 32;ht[5].data = 'E'; ht[5].weight = 103;ht[6].data = 'F'; ht[6].weight = 21;ht[7].data = 'G'; ht[7].weight = 15;ht[8].data = 'H'; ht[8].weight = 47;ht[9].data = 'I'; ht[9].weight = 57;ht[10].data = 'J'; ht[10].weight = 1;ht[11].data = 'K'; ht[11].weight = 5;ht[12].data = 'L'; ht[12].weight = 32;ht[13].data = 'M'; ht[13].weight = 20;ht[14].data = 'N'; ht[14].weight = 57;ht[15].data = 'O'; ht[15].weight = 63;ht[16].data = 'P'; ht[16].weight = 15;ht[17].data = 'Q'; ht[17].weight = 1;ht[18].data = 'R'; ht[18].weight = 48;ht[19].data = 'S'; ht[19].weight = 51;ht[20].data = 'T'; ht[20].weight = 80;ht[21].data = 'U'; ht[21].weight = 23;ht[22].data = 'V'; ht[22].weight = 8;ht[23].data = 'W'; ht[23].weight = 18;ht[24].data = 'X'; ht[24].weight = 1;ht[25].data = 'Y'; ht[25].weight = 16;ht[26].data = 'Z'; ht[26].weight = 1;Hfmtree(ht);Huffcoding(ht);if ((fp = fopen("D:\\hfm\\hfmtree.txt", "w")) == NULL) {printf("Open file hfmtree.txt error!\n");exit(0);}fputs("初始化如下：\n", fp);fprintf(fp, "%f\n", ht[0].weight);for (int i = 1; i <= ht[0].weight; i++)fprintf(fp, "%c%f\n", ht[i].data, ht[i].weight);fclose(fp);printf("\n\n\n初始化已完成，已存入hfmtree.txt文件中！\n");
}//创建哈夫曼树
void Hfmtree(Huffnode* ht) {float n, m1, m2;int i, k, x1, x2;                    /*m1为最小权值，x1为其对应的下标；m2为次小权值，x2为其对应的下标*/n = ht[0].weight;        /*ht[0].weight存放的是字符数*/for (i = 1; i <= 2 * n - 1; i++)ht[i].parent = ht[i].LChild = ht[i].RChild = 0;       /*对所有的ht[]的parent、LChile、RChild域进行初始化*/for (i = n + 1; i <= 2 * n - 1; i++) {          /*创建非叶结点，构建哈夫曼树*/m1 = m2 = 10000;     /*初始值赋的大一些*/x1 = x2 = 0;for (k = 1; k <= i - 1; k++)          /*k为可进行比较的结点的下标；在ht[1]~ht[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋给x1、x2*/if (ht[k].parent == 0)if (ht[k].weight < m1) {m2 = m1;x2 = x1;m1 = ht[k].weight;x1 = k;}else if (m1 < ht[k].weight < m2) {m2 = ht[k].weight;x2 = k;}ht[i].weight = ht[x1].weight + ht[x2].weight;ht[x1].parent = i; ht[x2].parent = i;ht[i].LChild = x1; ht[i].RChild = x2;}
}//创建哈夫曼编码
void Huffcoding(Huffnode* ht) {char d[Max];float n;int i, start, c, p;n = ht[0].weight;hc = (Huffcode*)malloc(Max * sizeof(Huffcode));          //分配当前编码的工作空间if (hc == NULL) {printf("wrong!\n");exit(0);}for (i = 1; i <= n; i++) {                                             //h[i]start = n;       //初始化编码起始指针c = i;               //从叶子结点开始向上倒推p = ht[i].parent;while (p != 0) {--start;                       //从右向左逐位存放编码,首先放结束符if (ht[p].LChild == c)d[start] = '0';elsed[start] = '1';c = p;p = ht[p].parent;}hc[i].start = start;for (int k = start; k < n; k++) {hc[i].cd[k] = d[k];}}
}//编码函数
void Encoding() {FILE* fp, * fp1;int i, m = 0;char a;char in[Max];char in1[Max];char out[Max * Max];if ((fp = fopen("D:\\hfm\\ToBeTran.txt", "a+")) == NULL) {printf("Open file ToBeTran.txt error!\n");exit(0);}if ((fp1 = fopen("D:\\hfm\\CodeFile.txt", "w")) == NULL) {printf("Open file ToBeTran.txt error!\n");exit(0);}//判断ToBeTran.txt是否为空if (fgetc(fp) == EOF) {printf("ToBeTran.txt文件为空\n请在相应位置打开文件输入\n\n");exit(0);}else {printf("成功读取ToBeTran.txt文件\n");}fseek(fp, 0L, SEEK_SET);         //定位到文件开始处fgets(in, Max, fp);int n = (int)strlen(in);for (i = 0; i < n; i++)for (int j = 1; j <= ht[0].weight; j++)if (in[i] == ht[j].data) {for (int k = hc[j].start; k < ht[0].weight; k++) {out[m++] = hc[j].cd[k];}}for (i = 0; i < m; i++)fprintf(fp1, "%c", out[i]);printf("\n\n\n编码结束，结果已存入CodeFile.txt文件中！\n");fclose(fp);fclose(fp1);
}//译码函数
void Decoding() {FILE* fp, * fp1;int i, j, n, k, x, m, w;char out[Max];char in[Max * Max];if ((fp = fopen("D:\\hfm\\CodeFile.txt", "r")) == NULL) {printf("Open file CodeFile.txt error!\n");exit(0);}if ((fp1 = fopen("D:\\hfm\\TextFile.txt", "w")) == NULL) {printf("Open file TextFile.txt error!\n");exit(0);}fgets(in, Max * Max, fp);if ((int)strlen(in)) {printf("成功读取CodeFile.txt文件\n");}n = (int)strlen(in);i = 0; m = 0;while (i < n) {for (j = 1; j <= ht[0].weight; j++) {x = hc[j].start;for (k = x, w = i; k < ht[0].weight; k++, w++)if (in[w] != hc[j].cd[k])break;if (k >= ht[0].weight) {out[m++] = ht[j].data;break;}}i = w;}for (i = 0; i < m; i++)fprintf(fp1, "%c", out[i]);printf("\n\n\n译码结束，结果已存入TextFile.txt文件中！\n");fclose(fp);fclose(fp1);
}//打印编码
void Print()
{FILE* fp, * fp1;int i = 0;int j = 0;char in[Max * Max];printf("代码文件为:\n");if ((fp = fopen("D:\\hfm\\CodeFile.txt", "r")) == NULL) {printf("Open file CodeFile.txt error!\n");exit(0);}if ((fp1 = fopen("D:\\hfm\\CodePrin.txt", "w")) == NULL) {printf("Open file CodePrin.txt error!\n");exit(0);}fgets(in, Max * Max, fp);int n = (int)strlen(in);for (; i < n; i++) {printf("%c", in[i]);fprintf(fp1, "%c", in[i]);j++;}printf("\n\n\n\n代码文件已存入CodePrin.txt文件中\n");fclose(fp);fclose(fp1);
}//打印树
int DEPTH = 0;
void PreOrderTraverse(FILE* fp, int k) {int i;if (ht[k].RChild != 0) {DEPTH++;PreOrderTraverse(fp, ht[k].RChild);DEPTH--;}for (i = 0; i <= DEPTH; i++) {printf("    ");fprintf(fp, "        ");}printf("%f\n", ht[k].weight);fprintf(fp, "%f\n", ht[k].weight);if (ht[k].LChild != 0) {DEPTH++;PreOrderTraverse(fp, ht[k].LChild);DEPTH--;}if (ht[k].LChild == 0 && ht[k].RChild == 0)return;return;}
void TreePrinting() {FILE* fp;if ((fp = fopen("D:\\hfm\\TreePrint.txt", "w")) == NULL) {printf("Open file TreePrint.txt error!\n");exit(0);}printf("哈夫曼树凹入表：\n");PreOrderTraverse(fp, ht[0].weight * 2 - 1);printf("\n\n\n\n凹入表已写入TreePrint.txt文件中\n");fclose(fp);
}//释放空间
void Free() {free(ht);free(hc);
}//主函数
int main() {char select;while (1) {Menu();scanf_s("%c", &select, 1);switch (select) {case '1':Init(); break;case '2':Input(); break;case 'e':case 'E':Encoding(); break;case 'd':case 'D':Decoding(); break;case 'p':case 'P':Print(); break;case 't':case 'T':TreePrinting(); break;case 'q':case 'Q':Free(); exit(1);default:printf("Input error!\n");}int x = getchar();}
}