1、哈夫曼算法及其应用一、问题描述给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼编码是一种根据哈夫曼树对文件进行编码的方式。哈夫曼编码是可变字长编码的一种。本次课程设计是对一个已建文本文件，统计该文件中各字符频率，对各字符进行 Huffman 编码，将该文件翻译成 Huffman 编码文件，再将 Huffman 编码文件翻译成原文件。压缩文件即读文件，统计文件中的字符个数，对文件进行哈夫曼编码和译码，并将编码译码后的字符存储在文件中。二、基本要求程序要求实现以下功能：1统计文本文件中各字符的出现次数（涉及读文件，统计
2、字符个数） ；2对文件中的字符进行哈夫曼编码，并存储入字符编码文件；3根据字符编码文件对文本文件内容进行编码；4根据字符编码文件和已编码文件的内容进行译码；5能够输出原文、编码表、文本文件编码、译文。3、测试数据In its medical literature, the Food and Drug Administration states that hot water comfortable enough for washing hands is not hot enough to kill bacteria, but is more effective than cold water b
3、ecause itremoves oils from the hand that can harbor bacteria.四、算法思想1、哈夫曼树建立算法：1）根据给定的 n 个权值 W1，W2，W3Wn 构成 n 棵二叉树的集合T1， T2， Tn，其中 Ti 中只有一个权值为 Wi 的根结点，左右子树均为空。2）在 F 中选取两棵根结点的权值最小的树作为左、右子树一构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。3）在 F 中删除这两棵中权值最小的树，同时将新得到的二叉树加入 F 中。4）重复2）3）直到 F 中仅剩一棵树为止，这棵树就是哈夫曼树。2、哈夫曼
4、编码算法：通过从哈夫曼树根结点开始，对左子树分配代码“1” ，右子树分配代码“0” ，一直到达叶子结点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。3、对文件字符编码算法：逐一读取文件中字符，在哈夫曼编码表查找对应字符，读取其编码并写入文件，如此循环直至结束。4、哈夫曼译码算法：根据编码用的哈夫曼树，从根结点出发，逐个读入电文中的二进制码；若代码为“1” ，则走左子树的根结点，否则走向右子树的根结点；一旦到达叶子结点，便译出代码所对应的字符。然后又重新从根结点开始继续译码，直到二进制电文结束。五、模块划分1Void InitHT(HuffmanT T) 初始化 H
5、uffman 树。2Void SelectMin(HuffmanT T, int n, int /字符int weight; /字符权重int lchild; /左子int rchild; /右子int parent; /双亲 THNODE;2、哈夫曼编码表的存储结构：typedef struct char ch; /存储字符char bitsMAX_C + 1; /字符编码位串 CodeNode;七、源程序/Huffman.cpp 源代码如下：#include #include #include #define MAX_C 256 /定义最大字符数#define MAX_N 512 /定义最
6、大 Huffman 节点个数#define N 50/*Huffman Tree 结构*/typedef struct char ch; /字符int weight; /字符权重int lchild; /左子int rchild; /右子int parent; /双亲THNODE;typedef THNODE HuffmanTMAX_N;/*Huffman 编码表结构*/typedef struct char ch; /存储字符char bitsMAX_C + 1; /字符编码位串CodeNode;typedef CodeNode HuffmanCodeMAX_C;HuffmanCode H;
7、/*全局变量*/int n; /指示待编译文件的字长char filename20;/*初始化 Huffman 树*/void InitHT(HuffmanT T) int i;for (i = 0; i 0)p1 = i;break;for (j = i + 1; j 0)p2 = j;break;for (i = 0; i Ti.weight) for (j = 0; j Tj.weight) /*加载文件*/void LoadHuffmanFile(HuffmanT T) unsigned int i;int j = 0;char c;int aMAX_C;FILE *fp;printf
8、(“Input file name: “);scanf(“%s“, filename);if (fp = fopen(filename, “rb“) = NULL) printf(“Cant open %sn“, filename);exit( 0 );for (i = 0; i = 0) /直到回溯到 Tc是树根位置 cd-start = (Tp.lchild = c) ? 0 : 1;c = p;strcpy(Hi.bits, /复制临时编码到编码表中/*对文件编码，将结果保存到 codefile.txt 中*/void EncodingHuffmanT(HuffmanT T, Huffm
9、anCode H) char c;FILE *in,*fp;int j,l;char encodefile20,tempMAX_C;if (in = fopen(filename, “rb“) = NULL) printf(“Read %s fail!n“, encodefile);exit(1);CharSetHuffmanEncoding(T, H);printf(“Input encode file name: “);gets( encodefile );if (fp = fopen(encodefile, “wb“) = NULL) printf(“Write %s fail!n“,
10、encodefile);exit(1);fread(fwrite(fseek(in, 0, SEEK_SET);fseek(fp, 0, SEEK_SET);while ( 1 )/( !feof( in ) fread(if (feof(in) break;for (j = 0; j 0)printf(“n“);if (Ti.weight 0) fprintf(fp, “%c:%d “, Ti.ch, Ti.weight);printf(“%c: %d “, Ti.ch, Ti.weight);fclose(fp);printf(“nLeaf/*打印 Huffman 编码表*/void Pr
11、intHuffmanH(HuffmanT T, HuffmanCode H) int i;FILE *fp;CharSetHuffmanEncoding(T, H);if (fp = fopen(“codeprint.txt“, “wb“) = NULL) printf(“Open codeprint.txt fail!n“);exit(1);for (i = 0; i 0) printf(“n“);printf(“%c: %sn“, Ti.ch, Hi.bits);fprintf(fp, “%c:%s “, Ti.ch, Hi.bits);fclose(fp);printf(“nHuffma
12、n tree code saved in codeprint.txt!nn“);/*主菜单*/void MainMenue() fflush( stdin );printf(“n* Main Menue *n“);printf(“* *n“);printf(“* 1. Load to be dealt file. *n“);printf(“* 2. Show Huffman code list. *n“);printf(“* 3. Show Huffman weight list. *n“);printf(“* 4. Encoding Huffman file. *n“);printf(“*
13、5. Decoding Huffman file. *n“);printf(“* 6. Exit. *n“);printf(“* *n“);printf(“*n“);/*主函数开始*/int main()int flag = 1;char ch10;HuffmanT T; /定义 Huffman 树HuffmanCode H; /定义 Huffman 编码表InitHT(T); /初始化 Huffman 树while ( flag ) MainMenue();printf(“Please input your choice(16): “);gets( ch );switch ( ch0 )case 1: CreatHT(T); break;case 2: PrintHuffmanH(T, H); break;case 3: PrintHuffmanT(T); break;case 4: EncodingHuffmanT(T, H); break;case 5: DecodingHuffmanT(T, H); break;case 6: exit(1);default: printf(“Input error!n“); break;return 0;八、测试情况程序的测试结果如下：建立哈夫曼树、打印编码表正确。打印权重表正确。
