#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 TNode{ Elemtype letter; int weight; int parent; Which sigh; char *code; }HTNode,*HuffmanTree; int n; char coding[50];//储存代码 char str[ENCODING_LENGTH];//保存要翻译的句子 void InitTreeNode(HuffmanTree &HT){//初始前N个结点,后M-N个结点置空 int i;int w;char c; int m=2*n-1; HuffmanTree p; HT=(HuffmanTree)malloc((m)*sizeof(HTNode)); printf("input %d database letter and weight",n); p=HT; getchar(); for (i=1;i<=n;i++){ scanf("%c%d",&c,&w); p->code='\0'; p->letter=c; p->parent=0; p->sigh=none; p->weight=w; p++; getchar(); } for (;i<=m;i++,p++){ p->code='\0'; p->letter=' '; p->parent=0; p->sigh=none; p->weight=0; } }//INITTREENODE void Select(HuffmanTree HT,int end,int *s1,int *s2){//在0~END之间,找出最小和次小的两个结点序号,返回S1,S2 int i; int min1=INT_MAX; int min2; for (i=0;i<=end;i++){//找最小的结点序号 if (HT[i].parent==0&&HT[i].weight<min1){ *s1=i; min1=HT[i].weight; } } min2=INT_MAX; for(i=0;i<=end;i++){//找次小结点的序号 if (HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight){ *s2=i; min2=HT[i].weight; } } } void HuffmanTreeCreat(HuffmanTree &HT){//建立HUFFMAN树 int i;int m=2*n-1; int s1,s2; for(i=n;i<m;i++){ Select(HT,i-1,&s1,&s2); HT[s1].parent=i; HT[s2].parent=i; HT[s1].sigh=left_child; HT[s2].sigh=right_child; HT[i].weight=HT[s1].weight+HT[s2].weight; } }
void HuffmanTreeCode(HuffmanTree HT){//HUFFMAN译码 int i; char *temp; temp=(char *)malloc(n*sizeof(char)); temp[n-1]='\0'; int p;int s; for (i=0;i<n;i++){ p=i; s=n-1; while (HT[p].parent!=0){//从结点回溯,左孩子为0,右孩子为1 if (HT[p].sigh==left_child) temp[--s]='0'; else if (HT[p].sigh==right_child) temp[--s]='1'; p=HT[p].parent; } HT[i].code=(char *)malloc((n-s)*sizeof(char));//分配结点码长度的内存空间 strcpy(HT[i].code,temp+s); printf("%s\n",HT[i].code); } } void GetCodingSen(char *sencence){//输入要编码的句子 int l; gets(sencence); l=strlen(sencence); sencence[l]='\0'; } void HuffmanTreeEncoding(char sen[],HuffmanTree HT){//将句子进行编码 int i=0;int j; while(sen[i]!='\0'){ for(j=0;j<n;j++){ if (HT[j].letter==sen[i]) //字母吻合则用代码取代 {strcat(coding,HT[j].code); break; } } i++; if (sen[i]==32) i++; } printf("\n%s",coding); } void HuffmanTreeDecoding(HuffmanTree HT,char code[]){//HUFFMAN译码过程,将代码翻译为句子 char sen[100]; char temp[50]; char voidstr[]=" "; int i;int j; int t=0;int s=0; for(i=0;i<strlen(code);i++){ temp[t++]=code[i]; for(j=0;j<n;j++){ if (strcmp(HT[j].code,temp)==0){//代码段吻合 sen[s]=HT[j].letter;s++; strcpy(temp,voidstr);//将TEMP置空 t=0; break; } } } printf("\n%s",sen); }
void main(){ HTNode hnode; HuffmanTree huff; huff=&hnode; printf("input the letter for coding number\n"); scanf("%d",&n); InitTreeNode(huff); HuffmanTreeCreat(huff); HuffmanTreeCode(huff); GetCodingSen(str); HuffmanTreeEncoding(str,huff); HuffmanTreeDecoding(huff,coding); } |
相关推荐
这个代码是用C/C++实现哈夫曼编码并将编码输出。 文本为操作者输入,,对各字符进行频率统计,然后进行哈夫曼编码,并将编码结果输出,同时可求得平均码长。
哈夫曼编码实现文本文件的压缩,可作为数据压缩作业的参考
哈夫曼树与哈夫曼编码 建立哈夫曼树并计算哈夫曼编码
详细描述了哈夫曼树的构造方法,同时推广到三元哈夫曼编码,并用C语言于VC++上实现
要求对一段数据序列进行哈夫曼编码,使得平均码长最短,输出各元素编码和编码后的数据序列。 ①组成序列的元素是[0-9]这10个数字,每个数字其对应的4位二进制数表示。比如5对应0101,9对应1001。 ②输入数据序列的...
哈夫曼编码课程设计,我要让所以人都知道写一个哈夫曼编码树便不是难事。
利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传输数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向...
这是那个用c语言来实现的哈夫曼编码程序,可以对输入的数据进行相应的编码……
哈夫曼编码(Huffman Coding),是一种熵编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般...
压缩文件即读文件,统计文件中的字符个数,对文件进行哈夫曼编码和译码,并将编码译码后的字符存储在文件中。 完成功能的详细说明: 1.统计文本文件中各字符的频率(涉及读文件,统计字符个数); 2.对文件中的...
利用哈夫曼编码思想,设计对一个文本文件(.txt)中的字符进行哈夫曼编码,生成编码压缩文件(.txt),并且还可将压缩后的文件进行解码还原为原始文本文件(.txt)。 实现的功能: (1)压缩:实现对文件的压缩,生成...
c语言实现哈夫曼编码,并求平均码长 c语言实现哈夫曼编码,并求平均码长
摘 要:哈夫曼编码是一种数据编码方式,以哈夫曼树——即最优二叉树,用带权路径长度最小的二叉树,对数据进行重编码,经常应 用于数据压缩。在计算机信息处理中,“哈夫曼编码”是一种一致性编码法(又称“熵编码法...
哈夫曼编码是一种无损的高效的压缩方法。对文本文件进行哈夫曼编码,使用计算信源熵打开一个文件进行概率计算,然后将输出的 submit.txt 文件用哈夫曼编码打开,之后就会对文本文件中出现的字符进行哈夫曼编码。
用MATLAB实现哈夫曼编码的例程-Huffman.rar 用MATLAB实现哈夫曼编码的例程(以子函数形式给出), NORM2HUFF 哈夫曼编码器 对于输入向量, NORM2HUFF 返回向量的哈夫曼编码后的码串。
哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方式,其压缩率通常在20%—90%之间。哈夫曼编码算法是通过使用字符在文件中出现的频率表来构造最优前缀码的贪心算法。所谓前缀码,即是任一字符的编码都不是其他...
用C++进行哈夫曼编码计算信源熵及编码效率 统计各种概率
数据结构课程设计,实现哈夫曼编码,译码,打印哈夫曼树
基于概率的哈夫曼编码C语言程序,能对txt文件中的诗句给予其对应的编码
通过编写利用哈夫曼算法实现的文件编码解码小工具,可加深对哈夫曼算法的理解,以及编码的熟练度。本人的小工具仅针对英文大小字母及 ' '\n' ' ' 字符针对性的进行了哈夫曼编码,若想实现中文及各种支持语言的编码,...