哈弗曼编码的实现.doc

如何实现哈夫曼编码一、编码 【题目描述】 给定一篇用于通信的英文电文，统计该电文中每个字符出现的频率，按频率左小右大的方法为这些字符建立哈夫曼(Huffamn)树，并编出每个字符的哈夫曼树码，输出该电文的哈夫曼码译文。【输入】 输入文件huffman.in是一篇用于通信的英文电文。【输出】 输出文件huffman.out输出该电文的哈夫曼码译文。【输入输出样例1】 huffman.in huffman.outaaccdddbacbcddddddd011011000011101001100010001111111【数据限制】2=英文电文字符数=10000000统计以上abcd出现的个数。a:3b:2 c:4 d:10构造出哈夫曼树a:011 b:010 c:00 d:1下面主要通过两个结构体数组来实现：struct node1 int w, lch, rch, parent;ht2*N0-1+1;数组下标1234567父节点的数组下标parent0000左孩子节点的数组下标lch0000右孩子节点的数组下标rch0000权值w32410-数组下标1234567父节点的数组下标parent55000左孩子节点的数组下标lch00002右孩子节点的数组下标rch00001权值w324105-.。数组下标1234567父节点的数组下标parent5567670左孩子节点的数组下标lch0000256右孩子节点的数组下标rch0000134权值w324105919struct node2char ch;/对应的字符abcdint start;/编码的起始位置 注意这个编码是倒着的 所以这里用startint codeN0;/这个是编码数组hcN0+1;大概图如下面下面给出大家想要的程序部分view plaincopy to clipboardprint?/#includestdio.h /#includestring.h #include #include constintN0=10;constintN=100;constintINF=1000000;structnode1intw,lch,rch,parent;ht2*N0-1+1;structnode2charch;intstart;intcodeN0;hcN0+1;intn,root;/n为叶子的个数 voidreadData()charch;intnum256=0;n=0;freopen(huffman.in,r,stdin);/读文本文件 while(ch=getchar()!=EOF)numch+;for(inti=0;i=255;i+)if(numi)n+;htn.w=numi;hcn.ch=i;voidselect1(intt,int*s1,int*s2)/用两个数来记录没有在树上的最小的两个值，从而进一步生成树。 intw1,w2;w1=w2=INF;for(inti=1;i=t;i+)if(hti.parent=0)if(hti.ww1)w2=w1;*s2=*s1;w1=hti.w;*s1=i;elseif(hti.ww2)w2=hti.w;*s2=i;voidcreateHufTreeHuCode()inti,s1,s2;intchild,parent;root=2*n-1;for(i=n+1;i=root;i+)select1(i-1,&s1,&s2);hti.w=hts1.w+hts2.w;hti.lch=s1;hti.rch=s2;hts1.parent=hts2.parent=i;for(i=1;i=n;i+)child=i;while(child!=root)parent=htchild.parent;if(htparent.lch=child)hci.codehci.start+=0;elsehci.codehci.start+=1;child=parent;voidtxt2code()inti,j,m;charch1N+1=0;freopen(huffman.in,r,stdin);for(intk=1;kN+1;k+)scanf(%c,&ch1k);for(j=1,i=1;i=0;m-)printf(%d,hcj.codem);j=1;intmain()readData();createHufTreeHuCode();freopen(huffman.out,w,stdout);txt2code();return0;二、译码【题目描述】 给定2个输入文件，第1个输入文件是用于通信的英文电文，统计该电文中每个字符出现的频率，按频率左小右大的方法为这些字符建立哈夫曼(Huffamn)树，并编出每个字符的哈夫曼树码；第2个输入文件是已经按第1个输入文件的英文电文编好的哈夫曼码，输出该哈夫曼码的对应的英文电文。【输入】 第1个输入文件为huffman.in是用于通信的英文电文, 第2个输入文件codeToTxt.in是已经按第1个输入文件编好的哈夫曼码。【输出】 输出文件codeToTxt.out输出codeToTxt.in文件内容的英文电文。【输入输出样例1】 huffman.in codeToTxt.incodeToTxt.outaaccdddbacbcddddddd011111011000011101001100010001111adddaccdddbacbcdddd【数据限制】2=英文电文字符数=10000000view plaincopy to clipboardprint?#include #include constintN0=10;constintN=100;constintINF=1000000;structnode1intw,lch,rch,parent;ht2*N0-1+1;structnode2charch;intstart;intcodeN0;hcN0+1;intn,root,num256;voidreadData()charch;n=0;freopen(huffman.in,r,stdin);while(ch=getchar()!=EOF)numch+;/同时得到了两个东西，一个是字符，一个是个数 for(inti=0;i=255;i+)if(numi)n+;htn.w=numi;/个数 hcn.ch=i;/字符 voidselect1(intt,int*s1,int*s2)intw1,w2;w1=w2=INF;for(inti=1;i=t;i+)if(hti.parent=0)if(hti.ww1)w2=w1;*s2=*s1;w1=hti.w;*s1=i;elseif(hti.ww2)w2=hti.w;*s2=i;voidcreateHufTreeHuCode()inti,s1,s2;intchild,parent;root=2*n-1;for(i=n+1;i=root;i+)select1(i-1,&s1,&s2);hti.w=hts1.w+hts2.w;hti.lch=s1;hti.rch=s2;hts1.parent=hts2.parent=i;for(i=1;i=n;i+)child=i;while(child!=root)parent=htchild.parent;if(htparent.lch=child)hci.codehci.start+=0;elsehci.codehci.start+=1;child=parent;voidcode2txt()charch=0;inti=root;freopen(codeToTxt.in,r,stdin);freopen(codeToTxt.out,w,stdout);while(ch=getch