哈夫曼编码译码
哈夫曼树和字符编码对应你都弄完了，得到是如a :01 b :101对应关系，通过这个关系直接将像“asdsdfdfg”直接转换为“01110101”这样二进制编码。译码的时候，读取二进制编码，先读取一位，然后在关系表中查找该二进制数对应的字符，如果没有找到，继续读取二位，然后继续在关系表中查找该二位二进制对应的字符。如此循环，知道找到字符位置，然后将二进制数替换为相应的字符，知道所有的数都替换完为止。
注释非常详细，希望对你有所帮助！
#ifndef Huffman_Tree_h
#define Huffman_Tree_h
#endif
#include
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode, * HuffmanTree; //存储赫夫曼树的结点类型
typedef char * * HuffmanCode; //用于存储字符集中各个字符相应的赫夫曼编码
void strcpy(char *S1,char *S2){ //将字符串S2复制到S1
int i = 0;
while( S2[i] != '\0' ){
S1[i] = S2[i];
i++;
}
S1[i] = '\0';
}
void Select(HuffmanTree HT,int t,int &s1,int &s2){ //在HT[1]到HT[t-1]中找出权值最小的两个S1和S2
int i = 1;
s1 = s2 = 0;
HT[0].weight = 65535;
while( i <= t ){ //遍历查找权值最小的结点S1
if( HT[i].parent == 0 && HT[i].weight < HT[s1].weight )
s1 = i;
i++;
}
i = 1;
while( i <= t ){ //遍历查找除S1外权值最小的结点S2
if( i != s1 && HT[i].parent == 0 && HT[i].weight < HT[s2].weight )
s2 = i;
i++;
}
}
int HuffmanCoding( HuffmanTree &HT,HuffmanCode &HC,int *w,int n){ //根据各个字符的权值构造赫夫曼树HT，将对应的赫夫曼编码存储在HC中
int s1,s2,m,i,start;
unsigned int c,f;
HTNode * p;
char *cd;
if( n <= 1 ) return 0;
m = 2 * n - 1; //赫夫曼树的总结点树为m
HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); //申请存储赫夫曼树的空间
for(p = HT + 1, i = 1; i <= n; ++i, ++p, ++w){ //将各个叶子结点的weight赋以相应的权值，parent,lchild,rchild均赋为0
p->weight = *(w+1);
p->parent = p->lchild = p->rchild = 0;
}
for( ; i <= m; ++i, ++p ){ //将各个非叶子结点的weight,parent,lchild,rchild均赋为0
p->weight = p->parent = p->lchild = p->rchild = 0;
}
for( i = n + 1; i <= m; ++i ){ //构造赫夫曼树，给各个非叶子结点赋值
Select(HT, i - 1, s1, s2);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //申请空间，用于存储指向存储各个字符相应赫夫曼编码的字符数组的指针
cd = (char *)malloc(n * sizeof(char)); //申请用于求赫夫曼编码
cd[n - 1] = '\0'; //编码结束符
for( i = 1; i <= n; ++i){ //逐个字符求赫夫曼编码
start = n -1; //编码在数组cd[]中的最前位置
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[]数组的start位置到n-1位置复制给HC[i]
}
free(cd); //释放空间
return 1;
}
以上为第一部分
#include
#include
#include "Huffman_Tree.h"
#define Yes 1 //当程序已经调用过初始化赫夫曼树的InitHuff_T()函数，或已从htfTree文件读取过，则将Init_Mode置为Yes，否则为No
#define No 0
void InitHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[],int &n ){ //初始化赫夫曼数，要求用户输入字符和相应权值
int i = 1,w[100],tem,j;
char a[20];
FILE *save;
printf("请输入编码字符集的大小n:");
scanf("%d",&n); //获取用户输入的字符集个数
while( i <= n ){ //获取用户输入的字符和相应权值，分别存储在ch[]和w[]数组中
printf("请输入第%d个字符和该字符的权值w:",i);
fflush(stdin);
scanf("%c%d",&ch[i],&w[i]);
i++;
}
ch[i] = '\0';
HuffmanCoding(HT,HC,w,n); //根据用户的输入，生成赫夫曼数及各个字符相应的赫夫曼编码，分别存在HT树和HC中
if(( save = fopen("htfTree","w")) == NULL ){ //打开用于存储赫夫曼树的文件
printf("Open file fail......
");
exit(0);
}
tem = n; //接下来的14行是将字符集大小转换成字符形式写入到文件中
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = n;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
printf("%d
",n); //向屏幕输出字符集大小n
fputc('
',save);
for( i = 1; i <= n; i++ ){ //分别向文件和屏幕输出各个字符和相应的赫夫曼编码
fputc(ch[i],save); printf("%c",ch[i]);
fputc('',save);
fputs(HC[i],save); printf("%s
",HC[i]);
fputc('
',save);
}
for(i = 1; i <= 2 * n - 1; i++ ){ //将赫夫曼树各个结点的parent,lchild,rchild分别写入到文件中
tem = HT[i].parent; //将i结点的parent转换成字符并写入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc(' ',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i].parent;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc(' ',save);
}
tem = HT[i].lchild; //将i结点的lchild转换成字符并写入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc(' ',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i].lchild;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc(' ',save);
}
tem = HT[i].rchild; //将i结点的rchild转换成字符并写入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc('
',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i].rchild;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc('
',save);
}
}
fclose(save);
}
void Encoding(HuffmanTree &HT, HuffmanCode &HC, char ch[]){ //根据赫夫曼编码将用户指定的文件中的字符编成相应的编码,并将所得编码存储到用户指定文件
FILE *ToBeTran,*CodeFile;
char ToBeTran_Name[100],CodeFile_Name[100]; //存储用户指定文件的文件名
int i;
char c;
printf("请输入所要进行编码的文件的文件名:");
scanf("%s",ToBeTran_Name); //获得所要进行编码的文件的文件名
if(( ToBeTran = fopen(ToBeTran_Name,"r")) == NULL ){ //打开文件
printf("Open file fail......
");
exit(0);
}
printf("请输入编码后编码表示的信息所存储到的文件的文件名:");
scanf("%s",CodeFile_Name); //获得编码后编码表示的信息所存储到的文件的文件名
if(( CodeFile = fopen(CodeFile_Name,"w")) == NULL ){ //打开文件
printf("Open file fail......
");
exit(0);
}
c = fgetc(ToBeTran); //从文件读取一个字符
while( c != EOF ){ //对文件中的各个字符进行编码，直至文件结尾
i = 1;
while( c != ch[i] && ch[i] != '\0' ) //在ch[]数组中查找从文件读取的字符
i++;
if(ch[i] == '\0'){ //未找到，c不在ch[]数组中，c无法被识别，程序出错，退出
printf("字符%c无法识别，程序将退出。
",c);
exit(0);
}
fputs(HC[i],CodeFile); //若找到，则将c相应的赫夫曼编码写入到文件中
printf("%s",HC[i]); //将c相应的赫夫曼编码输出到屏幕
c = fgetc(ToBeTran); //读入文件中的下一个字符
}
printf("
");
fclose(ToBeTran);
fclose(CodeFile);
}
void Decoding(HuffmanTree HT, char ch[] , int n){ //对指定的存储由赫夫曼编码表示的信息的文件进行译码，翻译成相应的字符表示，并存储到指定文件
int p,i = 1;
char code[1000],c;
char CodeFile_Name[100],TextFile_Name[100]; //存储用户指定文件的文件名
p = 2 * n - 1;
FILE *CodeFile,*TextFile;
printf("请输入所要译的文件名:");
scanf("%s",CodeFile_Name); //获得所要译的文件的文件名
if(( CodeFile = fopen("CodeFile","r")) == NULL ){ //打开文件
printf("Open file fail......
");
exit(0);
}
printf("请输入译后的字符存储到的文件的文件名:");
scanf("%s",TextFile_Name); //获得译后的字符存储到的文件的文件名
if(( TextFile = fopen(TextFile_Name,"w")) == NULL ){ //打开文件
printf("Open file fail......
");
exit(0);
}
c = fgetc(CodeFile);
while( c != EOF ){
code[i] = c;
i++;
c = fgetc(CodeFile);
}
code[i] = '\0'; //从文件读取字符，存储在code[]数组中
i = 1;
while ( code[i] != '\0' && p != 0 ){ //对数组code[]中的赫夫曼编码进行译码
if ( code[i] == '0' )
p=HT[p].lchild; //进入左分支
else
p = HT[p].rchild; //进入右分支
if (!HT[p].lchild&& !HT[p].rchild){ //进入叶子结点
fputc(ch[p], TextFile); //将相应的字符写入到文件中
printf("%c",ch[p]); //将相应的字符输出到屏幕
p = 2 * n - 1; //重新从树根出发进行译码
}
i++;
}
printf("
");
}
void ReadHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[], int &n){ //从文件读取赫夫曼树
FILE *htfTree;
char c[100],ch1;
int i,j,t;
if(( htfTree = fopen("htfTree","r")) == NULL ){ //打开存有赫夫曼树信息的文件
printf("Open file fail......
");
exit(0);
}
fgets(c,10,htfTree); //获取赫夫曼树叶子结点个数的字符串表示形式
i = 0; //以下6行将字符串形式转换成整数形式
while( c[i] != '
' )
i++;
n = 0;
for( j = 0; j < i; j++ )
n = 10 * n + c[j] - '0'; //求出叶子结点数n
HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //申请HC空间
HT = (HuffmanTree)malloc((2 * n) * sizeof(HTNode)); //申请赫夫曼树存储空间
i = 1;
while( i <= n ){
ch[i] = fgetc(htfTree); //读取字符集中的一个字符
HC[i] = (char *)malloc((10)*sizeof(char)); //申请用于存储读取到的字符集中的字符的赫夫曼编码的空间
fgetc(htfTree); //将‘’输出
ch1 = fgetc(htfTree); //读取赫夫曼编码，存储在相应的HC[i][]数组里
int j = 0;
while( ch1 != '
' ){
HC[i][j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HC[i][j] = '\0';
i++;
}
ch[i] = '\0';
i = 0;
while( i < 2 * n - 1 ){ //读取赫夫曼树的各个结点的parent,lchild,rchild.并赋值到赫夫曼树HT中
ch1 = fgetc(htfTree); //读取parent的字符串形式,存储在c[]中，并将其转换成整数形式，赋给HT[i].parent
j = 0;
while( ch1 != ' ' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1].parent = 0;
for( t = 0; t < j; t++ )
HT[i+1].parent = 10 * HT[i+1].parent + c[t] - '0';
ch1 = fgetc(htfTree); //读取lchild的字符串形式，并将其转换成整数形式，赋给HT[i].lchild
j = 0;
while( ch1 != ' ' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1].lchild = 0;
for( t = 0; t < j; t++ )
HT[i+1].lchild = 10 * HT[i+1].lchild + c[t] - '0';
ch1 = fgetc(htfTree); //读取rchild的字符串形式，并将其转换成整数形式，赋给HT[i].rchild
j = 0;
while( ch1 != '
' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1].rchild = 0;
for( t = 0; t < j; t++ )
HT[i+1].rchild = 10 * HT[i+1].rchild + c[t] - '0';
i++;
}
}
int main(){
HuffmanTree HT;
HuffmanCode HC;
char ch[100]; //用于存储字符集
int n,Init_Mode = No; //n为字符集的大小，Init_Mode = No 表示内存中没有赫夫曼树的信息
char mode; //让用户选择不同的操作
printf("请输入你要选择的功能
");
printf("I -- 初始化E -- 编码
");
printf("D -- 译码 Q -- 退出程序
");
scanf("%c",&mode); //获得用户选择的操作
while( mode != 'Q' && mode != 'q' ){ //当用户输入不为Q或q时，执行相应操作
switch(mode){
case 'I' :
InitHuff_T(HT,HC,ch,n);
Init_Mode = Yes;
break;
case 'i' :
InitHuff_T(HT,HC,ch,n);
Init_Mode = Yes;
break;
case 'E' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Encoding(HT,HC,ch);
Init_Mode = Yes;
break;
case 'e' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Encoding(HT,HC,ch);
Init_Mode = Yes;
break;
case 'D' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Decoding(HT,ch,n);
Init_Mode = Yes;
break;
case 'd' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Decoding(HT,ch,n);
Init_Mode = Yes;
default :
printf("您的输入有错，请重新选择.
");
}
printf("请输入你要选择的功能
");
printf("I -- 初始化E -- 编码
");
printf("D -- 译码 Q -- 退出程序
");
fflush(stdin);
scanf("%c",&mode); //让用户继续选择相应的操作，直至用户选择退出
}
return 0;
}
树- 哈夫曼树及其应用 - 哈夫曼编码 (二)
依次读人文件的二进制码，从哈夫曼树的根结点(即T[m- 1])出发，若当前读人0，则走向左孩子，否则走向右孩子。一旦到达某一叶子T[i]时便译出相应的字符H[i].ch。然后重新从根出发 继续译码，直至文件结束。文件的编码和解码算法【参见练习】。lishixinzhi\/Article\/program\/sjjg\/201311\/23862 ...
哈夫曼树 3位固定长度编码是什么?
所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。[3]2、哈夫曼译码 在通信中，若将字符用哈夫曼编码形式发送出去，对方接收到编码后，将编码还原成字符的过程，称为哈夫曼译码。[4]...
...根据字符出现频率构建赫夫曼树 的赫夫曼编码译码c++程序阿
void HuffmanCoding(HuffmanCode HC[], int w[], int n) \/\/ w存放n个字符的权值(均>0),构造哈夫曼树HT, 并求出n个字符的哈夫曼编码HC { int i, j; char *cd; int start; if (n<=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); \/\/ 0号...
什么是哈夫曼编码和译码
哈夫曼编码 http:\/\/baike.baidu.com\/view\/95311.htm 译码 http:\/\/baike.baidu.com\/view\/189742.htm
霍夫曼编码压缩比编码效率怎么算
霍未曼编码通常采用两次扫描的办法，第一次扫描得到统计结果，第二次扫描进行编码。霍夫曼编码具有一些明显的特点：1) 编出来的码都是异字头码，保证了码的唯一可译性。2) 由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。3) 编码长度不统一，硬件实现有难度。4) 对不同...
哈夫曼编码和译码系统 数据结构实验题目 急求!!!
\/\/初始化哈夫曼树 for(i=1;i<=n;i++){ ht[i].weight =w[i].weight;ht[i].parent=0;ht[i].LChild=0;ht[i].RChild=0;} for(i=n+1;i<=2*n-1;i++){ ht[i].weight=0;ht[i].parent=0;ht[i].LChild=0;ht[i].RChild=0;} for(i=n+1;i<=2*n-1;i++){ for(...
哈夫曼编码是否会产生二义性,为什么?
哈夫曼编码不会产生二义性。因为，在哈夫曼树中，每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径中，每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径，从而保证了译码的非二义性。
设计要求是对输入的一串电文字符实现赫夫曼编码,再对赫夫曼编码生成的代...
include<stdio.h> include<stdlib.h> define N 100 struct node \/\/用于表示赫夫曼树的节点 { int num;\/\/表示叶子节点的序号 int v;\/\/表示权值（频率）struct node*parent;\/\/指向父亲节点 int type;\/\/1表示左儿子，2表示右儿子 struct node*next;\/\/用于该节点未成为赫夫曼树节点时的连接 }...
设计一个哈夫曼编码\/译码系统,对一个文本文件中的字符进行哈夫曼编码...
我给你个差不多的，你自己修改一下就可以用了 \/***Huffman编码和译码***\/ include<stdio.h> include<malloc.h> include<string.h> include<stdlib.h> typedef struct { int weight;char ch;int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef struct { char ch;char *chs;}HuffmanCode;ty...
求文档: 对某一文档中的字符按照其出现概率进行哈夫曼编码及译码
\/* 哈夫曼编码*\/ include "graphics.h"include "stdlib.h"include "Stdio.h"include "Conio.h"define MAX 53 char bmfile[10];char a[100];typedef struct {char c,s[10];}MM;MM mm[53];typedef struct \/*以数组存储哈夫曼树时的结点类型*\/ {char ch;int w,lcd,rcd,pt; \/*...
桂鸣润燥： 说明: 叶子节点:＂a＂,＂e＂,＂r＂,＂t＂,＂d＂,＂f＂,对应权重为8,4,6,3,1,1 测试数据 strtest1=＂01011101111100011＂ #include ＂stdafx.h＂ #include <stdio.h> #include <string.h> #define N 50 //叶子结点数/ #define M 2*N-1 //树中结点总数...
乳源瑶族自治县18064525357： .哈夫曼树、编码、译码 - ？
桂鸣润燥： 生成哈夫曼树的代码如下: #define INT_MAX 10000 #define ENCODING_LENGTH 1000 #include ＂stdio.h＂ #include ＂string.h＂ #include ＂malloc.h＂ typedef enum{none,left_child,right_child} Which;//标记是左孩子还是右孩子 ...
乳源瑶族自治县18064525357： 哈夫曼编码译码 - ？
桂鸣润燥： 什么叫N—S流程图?#include#include#includeint m,s1,s2;typedef struct { unsigned int weight; unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表...
乳源瑶族自治县18064525357： 什么是哈夫曼编码和译码 - ？
桂鸣润燥： 哈夫曼编码http://baike.baidu.com/view/95311.htm译码http://baike.baidu.com/view/189742.htm
乳源瑶族自治县18064525357： 哈夫曼树编码与译码 - ？
桂鸣润燥： #define INT_MAX 10000 #define ENCODING_LENGTH 1000 #include ＂stdio.h＂ #include ＂string.h＂ #include ＂malloc.h＂ typedef enum{none,left_child,right_child} Which;//标记是左孩子还是右孩子 typedef char Elemtype; typedef struct ...
乳源瑶族自治县18064525357： 哈夫曼编码和译码 - ？
桂鸣润燥： #include<iostream.h> #include<iomanip.h> #include<string.h> #include <windows.h> typedef struct{ int weight; int parent,lchild,rchild; char data; }HTNode,*HuffmanTree; //*HuffmanTree既是指针也是数组,用来存放树枝 typedef char **HuffmanCode...
乳源瑶族自治县18064525357： 哈夫曼编码与译码 - ？
桂鸣润燥： 什么叫N—S流程图?#include<string.h> #include<stdlib.h> #include<stdio.h>int m,s1,s2;typedef struct {unsigned int weight;unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 typedef char *HuffmanCode;...
乳源瑶族自治县18064525357： Huffman编码与译码, - ？
桂鸣润燥： #include <stdlib.h> #include <iostream.h> #include <stdio.h> #include <string.h>#define OVERFLOW -1typedef struct {char letter;int weight;int parent;int lchild;int rchild; }HTNode,*HuffmanTree;typedef char * *HuffmanCode;void Select(...
乳源瑶族自治县18064525357： 哈夫曼编码/译码器编程 - ？
桂鸣润燥： #include #include #define M 10000 //定义字符串最大长度#define N 128 //定义叶子节点个数 typedef struct node //定义哈夫曼树节点结构体 { int weight; struct node *LChild,*RChild,*Parent; //分别指向该节点的左孩子,右孩子,和双亲节点 struct ...
乳源瑶族自治县18064525357： 哈夫曼译码算法 - ？
桂鸣润燥： C++的 #include#include #include #include ofstream outstuf; #define MAXBIT 50 // 哈夫曼编码的最大长度 #define MAXVALUE 50 // 最大权值 #define MAXLEAF 50 // 哈夫曼树中叶子结点个数 #define MAXNODE MAXLEAF*2-1 //树中结点总数 //...
