哈弗曼树-VC++6.0版.docx

哈弗曼树源代码：#include #include #include #define N 255#define M 2*N - 1 /* 运行成功标记 */int ok = 0; /* 保存原文件名 */char file20 = 0; /* 哈夫曼树节点类型 */typedef struct int data; /* 字符值 */ int weight; /* 权重 */ int parent; /* 双亲结点 */ int lchild; /* 左孩子结点 */ int rchild; /* 右孩子结点 */Tree; /* 哈夫曼编码类型 */typedef struct /* 存放哈夫曼码 */ char cdN; int start;Code; /* 生成节点及编码数组 */Tree htM;Code hcdN; /* 函数声明 */int cmp(const void*, const void*);int NumberOfChar();void Reset();void InputFile();void Encode(int);void Decode(int);void OutputFile(int);void PrintHuffmanCode(int);void CreateHT(int);void CreateHCode(int); /* 主函数 */int main() int x = 0; int n = 0; char ch; while(1) system(cls); printf(1. 读入原文件n); printf(2. 在屏幕上打印哈夫曼代码表n); printf(3. 编码原文件n); printf(4. 解码原文件n); printf(5. 退出n); printf(Input 1-5:); scanf(%d, &x); switch(x) case 1: Reset(); InputFile(); if (ok) /* 排序使得有效字符在前面 */ qsort(ht, N, sizeof(Tree), cmp); /* 记下有效字符的个数 */ n = NumberOfChar(); CreateHT(n); CreateHCode(n); OutputFile(n); system(pause); break; case 2: system(cls); if (ok) PrintHuffmanCode(n); else printf(原文件尚未读入!n); system(pause); break; case 3: system(cls); if (ok) Encode(n); else printf(原文件尚未读入!n); system(pause); break; case 4: system(cls); if (ok) Decode(n); else printf(原文件尚未读入!n); system(pause); break; case 5: return 0; default: /* 防止输入错误序号，刷新缓冲区 */ fflush(stdin); return 0; /* 快速排序比较函数 */int cmp(const void *a ,const void *b) return (*(Tree *)a).weight (*(Tree *)b).weight ? 1 : -1; /* 统计有效的字符数量 */int NumberOfChar() int i, num = 0; for (i = 0; i 0) num+; return num; /* 初始化哈夫曼树 */void Reset() int i; for (i = 0; i M; i+) hti.weight = 0; hti.parent = -1; hti.lchild = -1; hti.rchild = -1; /* 读入文件内容 */void InputFile() FILE *fp; char ch; system(cls); printf(请输入原文件名:); fflush(stdin); scanf(%s, file); /* 打开原文件 */ if (fp = fopen(file, rt) = NULL) printf(找不到原文件 %s!n, file); ok = 0; system(pause); return; /* 读入字符并处理权重 */ while (fscanf(fp, %c, &ch) != EOF) htch.data = ch; htch.weight+; /* 关闭文件指针 */ fclose(fp); printf(原文件 %s 读入成功!n, file); ok = 1; /* 编码 */void Encode(int n) int i, k; char ch; FILE *fp1, *fp2; /* 利用哈夫曼代码表进行编码 */ if (access(Huffman_Code.txt,0) != 0) printf(找不到代码表 Huffman_Code.txt !n); return; /* 打开要编码的原文件 */ if (fp1 = fopen(file, rt) = NULL) printf(找不到原文件 %s !n, file); return; /* 生成编码文件 */ if (fp2 = fopen(Encode.txt, wt+) = NULL) printf(编码文件 Encode.txt 创建失败!n); return; /* 一个字符一个字符替换 */ while (fscanf(fp1, %c, &ch) != EOF) for (i = 0; i n; i+) if (hti.data = ch) for (k = hcdi.start; k = n; k+) fprintf(fp2, %c, hcdi.cdk); /* 关闭文件指针 */ fclose(fp1); fclose(fp2); printf(编码成功，结果在 Encode.txt 中!n); /* 解码 */void Decode(int n) int i, k; char ch; FILE *fp1, *fp2; /* 打开要解码的文件 */ if (fp1 = fopen(Encode.txt, rt) = NULL) printf(找不到编码文件 Encode.txt!n); return; /* 生成解码文件 */ if (fp2 = fopen(Decode.txt, wt+) = NULL) printf(解码文件 Decode.txt 创建失败!n); return; /* 利用哈夫曼树解码 */ i = 2 * n - 2; while (fscanf(fp1, %c, &ch) != EOF) if (ch = 0) i = hti.lchild; else i = hti.rchild; /* 找到叶子节点为止 */ if (hti.lchild = -1) fprintf(fp2, %c, hti.data); /* 继续从根节点开始查找 */ i = 2 * n - 2; /* 关闭文件指针 */ fclose(fp1); fclose(fp2); printf(解码成功，结果在 Decode.txt 中!n); /* 输出哈弗曼编码到文件 */void OutputFile(int n) FILE *fp; int i, k; /* 生成哈夫曼代码表文件 */ if (fp = fopen(Huffman_Code.txt, wt+) = NULL) printf(代码表文件 Huffman_Code.txt 创建失败!n); return; /* 将内存里的东西写入文件 */ for (i = 0; i n; i+) fprintf(fp, %d , hti.data); for (k = hcdi.start; k = n; k+) fprintf(fp, %c, hcdi.cdk); if (i n - 1) fprintf(fp, n); /* 关闭文件指针 */ fclose(fp); printf(代码表文件 Huffman_Code.txt 生成成功!n); /* 打印哈夫曼编码到屏幕 */void PrintHuffmanCode(int n) int i, k; printf(ASCII t Char t HuffmanCoden); for (i = 0; i n; i+) printf(%d t %c t , hti.data, hti.data); for (k = hcdi.start; k = n; k+) printf(%c, hcdi.cdk); printf(n); /* 构造哈夫曼树 */void CreateHT(int n) int i, k ,lmin, rmin; int min1, min2; /* 一共有2n-1个节点 */ for (i = n; i 2 * n - 1; i+) /*lmin和rmin为最小权重的两个节点置*/ min1 = min2 = 0x7FFFFFFF; lmin = rmin = -1; for (k = 0; k = i - 1; k+) /*只在尚未构造二叉树的节点中查找*/ if (htk.parent = -1) if (htk.weight min1) min2 = min1; rmin = lmin; min1 = htk.weight; lmin = k; else if (htk.weight min2) min2 = htk.weight; rmin = k; /* 修改2个小权重节点的双亲 */ htlmin.parent = i; htrmin.parent = i; /* 修改双亲的权重 */ hti.weight = htlmin.weight + htrmin.weight; /* 修改双亲的孩子 */ hti.lchild = lmin; hti.rchild = rmin; /* 得到哈夫曼编码 */void CreateHCode(int n) int i, f, c; Code hc; /* 根据哈夫曼树求哈夫曼编码 */ for (i = 0; i n; i+) hc.start = n; c =