赫夫曼编码对文件进行压缩与解密
理论
赫夫曼树
先有赫夫曼树,才有赫夫曼编码。所以,首先简单详情一下什么是赫夫曼树。
假设一共五个叶子节点,分别是2、3、5、7、8
那么生成的赫夫曼树就是下面这样:
赫夫曼树.png
赫夫曼树也叫最优二叉树,它的每一个结点具备一个权值。权值越大的结点离根节点越近,这样子从根节点到每一个叶子结点的
所有带权路径的和(WPL)最小。假设叶子结点为 n, 则总结点数 = 2*n-1
由于:
叶子节点的度为 0,其余节点的度为2。
有:
(总结点数 – 叶子节点数)x 2 = 边数
又由于:
总结点数 – 1 = 边数
综上:
总结点数 = 2 x 叶子节点数 – 1按照叶子节点的数量和权值,以一种特定的规则,自下而上地建立一颗赫夫曼树。
可任意交换赫夫曼树中
兄弟结点的位置,带权路径和(WPL)不变。代码实现(具体见附加代码中的相关构造函数):
- 采用顺序结构来存储,也就是结构数组。
- 数组大小为二倍的结点数减一(2*n-1), 每个元素表示一个结点。
- 先录入 n 个叶子节点,再每次找到权值最小的两个无双亲的结点进行合并。
- 合并成的新结点加入到数组后面,直到生成2*n-1个元素
赫夫曼编码
对于字符串“ABACCDA”
以字符出现频率作为权值,则:
A: 3, B: 1,C: 2, D:1
建立赫夫曼树:
赫夫曼树2.png如图, 若从根结点,到叶子结点。每次向左为0,向右为1。如此每一个叶子节点都对应一个独一无二的编码,叫做赫夫曼编码。
A: 1
B: 000
C: 01
D: 001原字符串就变成了
1 000 1 01 01 001 1代码实现(介绍见附加代码):
对于每一个叶子节点,从叶节点开始,顺着结构中 parent 的下标,遍历到根节点。
期间假如当前节点是当前节点父节点的左儿子,字符串增加一个0
否则增加一个1
遍历到根节点时,将形成的字符串逆置strrev。
对于存储得到的字符串,可以用指针数组来存。char *huffmanCode[n];
应用
应用源码
- 先在桌面建立一个 txt 文本,文件里面阔以随意写一段文章(我这不支持对中文字符加密,你们阔以自行拓展)。
- 而后运行下面这段又臭又长的代码,输入路径文本所在路径,而后按照提醒进行操作就行了。
- 最终相同路径下会产生一个加密文件和一个解密后的文件。
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <windows.h>#include <limits.h>#define MAX 1e4char *HC[150];//指针数组,哈夫曼编码,按顺序对应哈夫曼树。int input_Data[150], number; //字符串的频率, 种类数char path[100]; //路径typedef struct Node{ char value; int weight; int lchild; int rchild; int parent;}HTNode, *HuffmanTree;HuffmanTree HT = NULL;void work(void); //输出交互界面void Coding(void); //对文件进行编码HuffmanTree build_Huffman_Tree(void);//建立哈夫曼树void Huffman_Coding(void); //建立哈夫曼编码HCvoid output_HC(void); //打印编码表void Encrypt(void); //生成加密文件void Decode(void); //生成解密文件23char* creat_Path(char *name); //生成路径名称int get_Min(HuffmanTree ht, int k);//得到前k个无父节点的最小权重节点int found_Char(char ch); //查找输入字符所对应的HC下标int Check(void); //将解密文件与源文件比较void Continue(void); //输出能否继续操作对话框intmain(){ printf("---------------欢迎进入文件编码与解码程序---------------\n"); printf(" ----by 方宁 20.05.09\n\n"); printf("请输入你所需要进行操作的文件路径:\n"); scanf("%s", path); //主函数中获取一次操作路径 work(); return 0;}//清屏,和重新调用主菜单voidContinue(void){ char str[5]; printf("能否继续进行操作?(yes/no)\n"); scanf("%s", str); if(strcmp(str, "yes") == 0){ system("cls"); work(); } else{ printf("欢迎您的使用,再见\n"); Sleep(1000); }}//对指定文件进行哈夫曼编码voidCoding(void){ FILE *fp = NULL; char ch; printf("\n文件读取中...\n"); fp = fopen( path, "r" ); if(fp == NULL){ printf("文件打开失败\n"); Sleep(1000); exit(-1); } //读取文件字符,计算权值 while( (ch = fgetc(fp)) != EOF){ if(input_Data[ch - '\0'] == 0) number++; input_Data[ch - '\0']++; } fclose( fp ); printf("文件读取成功!\n\n"); printf("正在建立哈夫曼树...\n\n"); HT = build_Huffman_Tree(); printf("哈夫曼树建立成功!\n\n"); printf("进行哈夫曼编码...\n\n"); Huffman_Coding(); printf("进行哈夫曼编码成功!\n\n"); printf("---------编码表---------\n"); output_HC(); printf("对文件进行加密...\n\n"); Encrypt(); printf("文件加密成功!\n\n");}//由叶子节点(n)建立哈夫曼树,结点数:2*n-1HuffmanTreebuild_Huffman_Tree(void){ int i , k = 0; int total = 2*number - 1; int min1, min2; HuffmanTree ht = NULL; ht = (HuffmanTree)malloc( 2*number*sizeof(HTNode) ); if(ht == NULL){ printf("ht malloc faild\n"); Sleep(1000); exit(-1); } for(i = 0; i < total; i++){ ht[i].parent = -1; ht[i].lchild = -1; ht[i].rchild = -1; ht[i].weight = 0; } for(i = 0; i < 150; i++){ if(input_Data[i] > 0){ ht[k].value = i + '\0'; ht[k++].weight = input_Data[i]; } } for(; k < total; k++) { min1 = get_Min(ht, k); min2 = get_Min(ht, k); ht[min1].parent = k; ht[min2].parent = k; ht[k].weight = ht[min1].weight + ht[min2].weight; ht[k].lchild = min1; ht[k].rchild = min2; } return ht;}intget_Min(HuffmanTree ht, int k){ int i = 0, min; while( ht[i].parent != -1) i++; min = i; i++; for(; i < k; i++) { if( ht[i].parent == -1 && ht[i].weight < ht[min].weight ) min = i; } ht[min].parent = -2; return min;}//建立哈夫曼编码,存储在指针数组中voidHuffman_Coding(void){ char str[number]; int p , i; int father; int current; //由叶子节点到根节点,产生路径串的逆strrev for(i = 0; i < number; i++) { father = HT[i].parent; current = i; p = 0; while( HT[current].parent != -1 ){ if( HT[father].lchild == current ) str[p++] = '0'; else str[p++] = '1'; current = father; father = HT[current].parent; } str[p] = '\0'; strrev(str); HC[i] = NULL; HC[i] = (char *)malloc( (strlen(str)+1)*sizeof(char) ); if(HC[i] == NULL){ printf("HC[%d] malloc faild\n", i); Sleep(1000); exit(-1); } //HC[0] = '\0'; strcpy(HC[i], str); }}voidoutput_HC(void){ int i; for(i = 0; i < number; i++) printf("'%c': %s\n", HT[i].value, HC[i]); /**调试打印哈夫曼树,无误 for(i = 0; i < number*2-1; i++){ if(i < number) printf("'%c': %s\n", HT[i].value, HC[i]); printf("%d. %d %d %d %d\n",i, HT[i].parent, HT[i].lchild, HT[i].rchild, HT[i].weight); } **/ putchar('\n');}//建立加密文件夹,将字符转化成哈夫曼码,写入文件voidEncrypt(void){ char ch; FILE *fp1 = NULL, *fp2 = NULL; //加密文件,原文件 fp1 = fopen( creat_Path("加密.txt"), "w+" ); if(fp1 == NULL){ printf("加密文件打开失败\n"); Sleep(1000); exit(-1); } fp2 = fopen( path, "r"); if(fp2 == NULL){ printf("原文件打开失败\n"); Sleep(1000); exit(-1); } while( (ch = fgetc(fp2)) != EOF ){ int i = found_Char(ch); if(i != -1) fputs(HC[i] , fp1); else fputc('#', fp1); //假如有找不到的字符,用输出#表示 } fclose(fp1); fclose(fp2);}int found_Char(char ch){ int i; for(i = 0; i < number; i++){ if(HT[i].value == ch) return i; } return -1;}//从根节点遍历到叶子节点作为一个字符解码结束voidDecode(void){ FILE *fp1, *fp2; int root = 2*number - 2; int current = root; char ch; printf("正在进行解码...\n"); fp1 = fopen( creat_Path("解密.txt"), "w+" ); if(fp1 == NULL){ printf("解密文件打开失败\n"); Sleep(1000); exit(-1); } fp2 = fopen( creat_Path("加密.txt"), "r" ); if(fp2 == NULL){ printf("加密文件打开失败\n"); Sleep(1000); exit(-1); } while( (ch = fgetc(fp2)) != EOF ) { if(ch == '0') current = HT[current].lchild; else if(ch == '1') current = HT[current].rchild; else continue; if(current < number){ fputc(HT[current].value, fp1); current = root; } } fclose(fp1); fclose(fp2); printf("解码成功\n"); Sleep(1000);}//选项三,比照源文件和解密后的文件能否一致intCheck(void){ FILE *fp_source, *fp_decode; char ch1, ch2; fp_source = fopen(path, "r"); fp_decode = fopen(creat_Path("解密"), "r"); while( (ch1 = fgetc(fp_decode)) != EOF ){ ch2 = fgetc(fp_source); if(ch1 != ch2){ printf("解密字符 '%c' 与原字符 '%c' 匹配错误\n", ch1, ch2); return 0; } } return 1; fclose(fp_source); fclose(fp_decode);}///操作主界面voidwork(void){ char ch; printf("\n请输入你要进行的操作:\n"); printf("1. 编码 2. 解码 3. 校验\n"); getchar(); scanf("%c", &ch); switch(ch) { case '1': Coding(); break; case '2': Decode(); break; case '3': printf("正在进行校验...\n"); if(Check()) printf("解密文件与源文件一致\n"); else printf("解密文件与源文件不一致\n"); Sleep(1000); break; default: printf("输入有误,程序结束\n"); Sleep(1000); return; } Continue();}//修改客户输入的路径,产生新的路径。char*creat_Path(char *name){ char *path2 = NULL; int p; path2 = (char *)malloc( 100*sizeof(char) ); path2[0] = '\0'; strcat(path2, path); p = strlen(path2) - 1; while( path2[p-1] != 92 ) p--; path2[p] = '\0'; strcat(path2, name); return path2;}运行结果截图
- 生成的加密文件内容,与源文件进行比照。
对文件进行赫夫曼编码图
- 对加密后的01文件,进行解密后,再与原文比照:
解码文件
说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 赫夫曼编码对文件进行压缩与解密
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 赫夫曼编码对文件进行压缩与解密