电子科技大学-计算机学院-软件开发环境实验-李林教学班-霍夫曼编码压缩解压缩

1、/huffmaneunction. hinclude <stdio. h>#dofinc max_node_num 512typcdcf struct int bitnuin; int parent; int lchild; int rchild; int weight;/bool code1024 ;/每个字符的编码最大支持1024个单位长度bool* code;int codelength;bool isleaf;int floor;huffmannode;class iiuffmanfunctionprivate:bool bi t (char c, int num); lo

2、ng getfilesize(file* stream);bool ini tia 1 izclluffmantrce(iluffmannodc* huffmantrce, const char* sourceei lc); bool dcstroylluffmantrce (lluffmannodc* huffmantrce);int stat ist icsofhuffmannodes (：iuf finannode* huffmantree, char* sourcefi le);bool gctfirstandsecondminnode(int* firstminnode, int*

3、secondminnodc, const huffmannode*huffmantree, const int* issigned);bool gcneratelluffinancodc(huffmannode* huffmantrcc, const int index);bool sethuffmanh1oor(hufrmannode* huffmantree, const int index);int generatehuffmantree(lluffmannode* huffmantree, int* issigned);int generateeilecodc(const kuffma

4、nnodc* huffmantree,const char* sourceeile, bool*filecode):bool createcompressfile(const char* destfile,const bool* filecode, int filecodelength);public:bool compressfile(char* sourcefile, char* destfile); bool uncompressfile (char* sourcefile, char* destfile):huffmanfunctiono ;"huffmanfunctiono

5、 ;；/ stdafx.h :标准系统包含文件的包含文件, /或是经常使用怛不常更改的 /特定于项目的含文件 /ttpragma once#include <stdio. h>#includc <tchar. h>includestring, h ttinclude "huffmanfunction. h"/ todo:在此处引用程序耑耍的其他尖文件/ huffmanclass. cpp :定义控制台应用程序的入口点。 /#includc "stdafx. h" int main(int argc,char *argv)if (a

6、rgc!=4)printf ("输入不合法1<); return 0;elsehuffmanfunction* function = new huffmanfunctiono ; if (!strcmp(argv1, -c")function->comprcsseiic(argv2,argv3); else if (! strcmp (argv 1,function->uncompressfile(argv2, argv3);elseprintf (输入不合法n)； return 0;return 1;#include "huffman卜unct

7、ion.h"include <stdio. h>include <stdlib. h>huffman function: : i luf f maneunct i on ()huffnianfunct ion:、lluffmanfunct ion 0/获得字符的某一位bool huffmanfunclion: : bi t (char c, int rium)return (c&(l«num) >>num;/获得文件人小long huffnicineunction: :getfilesize(file* stream)long c

8、urpos, length; curpos = ftoil (stream): fscck(stream, 0,seek_end): length = ftel1 (stream): fseek(stream, curpos, seek_set); return length;bool huffmanfunct ion: ini tializehuffmcintree(huffmannode* huffmantree, const char* sourcefile) file* file = fopen(sourcefile, rb"); if (file = null)return

9、 false;long size = getfilesize(file);/获得 source 的文件人小 fclose(file);for (int i=0;imax_node_mjm;i+)huffmantreeti. code = (bool*)rnalloc (size):/动态生成编码数组huffmantrccti. weight = 0;huf'f'mantrcci. floor = 0;huffniantreci. codclength = 0;huf fnicintree i. parent = -1;huffmantreci. lchiid = -1; huf

10、fmantreeti. rchild = -1; huffmantreei. isleaf = false;return true:bool iiuffmanfunction:destroyiluffinantree(iiuffmannode* huffmantree)for(int i =0;i<max_node_num;i+)free(huffmantreei. code);return true;/返回的是文件中字符的数量int huffmanfunction:statislicsofhuffmannodes(huffmannode* huffmantree, char* sour

11、cefile)int count = 0;file* file = fopon(sourccpilc, rb);/读取字符，统计词频int index;while(index = fgetc(file)!=e0f)huffmantreeindex. wcight+; count+;huffmantreeindex. isleaf = true;fclosc(fi1c): return count:bool huffmanfunction:getfirstandsecondminnodc(int*irstminnode, int* secondminnode, const huffmannode

12、* huffmantree, const int* issigned)int firstminnum = 10000; int secondminnum = 10000;for (int i=0;i<max_n0de_num;i+)if (issigncdi =0&&liuffmantreci. weight>0&&liuffmantrcci. weight<first.minnum)*secondminnode = *fi rstminnode;secondminnum = fi rstminnum;*f?irstiinnode = i:fi

13、rstminnum 二 hufiniantreei. weight;elseif (issignedi =0&&huffmantreei weight>o&&huffmantreei. weight<secondminnum) *sccondminnode = i;secondminnum = huffmanti'cci. weight;return true;bool huffmcineunclion:generatehuffmancodechuffmcinnode* huffmantree, const int index)/如果是根节点

14、，直接返回if (huffmantrceindcx. floor = 0)return true;c l sc int parent 二 huffmantreeindex, parent;generatehuffmancodc (huf fmantrec, parent) ;/先牛成父 p点的 codefor (int i=0; i<huffmantree parent, floor; i+)/把父节点的 code 复制至 lj index 节点 huffmantreeindex. codei = huffmantreeparent. codei; huffmantreeindex. c

15、odelength+;/根据是左了节点还是右了节点生成codeint codclcngth = huffmantreeindex. codolcngth;if (huffmantreeparent, lchild =二 index)huffmantreeindex. codecodelength =0;else if (huffmantreeparent. rchi1d = index)hu f fmant reei ndex. codecodelength = 1;huffmantreeindex. codelength+;return true;bool huffmanfunct ion:

16、 :sethuffmanfloor (huffmcinnode* huffmantree, const int index) if(index<0|index>=maxjode num)return false;elseif (huffmantreeindex, floor > 0)int parent = huirmantreeindex.parent;huffmantreeindex, floor = hui'finantreeparent, floor + 1;sethuffmanfloor(huffmantrcc, huffmantrccindex. lchi

17、ld); sethuffmanfloor(huffmantrce, huffmantrccindex. rchi1d); return true;/返回的足根节点的索引int iluffmanfunction:generatehuffmantree(iluffmannode* huffraantree, int* issigned) /先统计有多少个初始叶子节点int nodecount = 0;for(int i-0;i<=255;i+)if (huifinantree i. weight>0)nodecount+;)/pj 生成 huff man 树int ptr = 256;

18、/ptr指向下一个可用节点 while(nodecount1)/获得第一小和第二小fl.未挂载的节点int firstminnode，secondminnode;getfirstandsecondminnode (&firstminnode, &secondminnode, huitniaritree, issigned);/给父节点赋值huffmantreeptr. weight = huffnkintreefirstminnode. weight + huffmantreesecondminnode. weight;huffmantreeptr. lchild = firs

19、tminnode; huffmantrccptr. rchiid = secondminnode;/给第一小节点赋值huf fmantree first.minnodej. floor = l;/floor 赋 1 和根节点区别 huffmantreefirstminnode. parent = ptr;/给第二小节点赋值huf fmantree secondminnode. floor = l;/flooi赋 1 和根节点区别 hufimantreesecondminnode. parent = ptr;i ssi gncdf i rstmi nnode = 1; issignedsecon

20、dminnode = 1; ptr+;nodecount-；/生成每个节点的层数sethuffmanfloor (tinf fmantree, ptr-1);/再生成huff man编码for(int i_0;i<256;i+)if(hucfmantreei. isleaf)generatekuf fmancodc (huri'mantree, i);return plr-1;)/返冋的是文件编码的长度int huffmanl;unction: :gcneratefi 1 ccodc(const iluffmannode* huffmemtrcc, const char* sou

21、rccfi1c, bool* fi1ccodc)int count = 0;file* file = fopen(sourcefile, rb"); if(file = null)return 0;int byte;while (byte = fgetc(file)!=e0f)for (int i =0;i <huffmantrccbyte. codelength;i+)filecodecount+ = huffmantreebyte codei:fclose(file): return count; bool iluffnianb'unction: :creatcco

22、mpressei lc(const char* dcstl'i ic, const bool* fi iccodc, int fi lccodclcngth)file* file = fopen(destfile, "wb"); int byte;for (int i=0;i<fi1ccodclcngth;)byte = 0;for (int j=7; j>=0; j)if(i=filecodelength)break;>byte += filecodeij; i+;fputc(byte, file):fclose(file); return tr

23、ue;bool iluffmanfunction: comprosspi 1 c (char* sourccfi 1c, char* dcst.fi lc)/定义-个哈夫曼树和表示节点是否已挂载的数组 huffmannode huffmantreemax node num; int issigncdmax_node_nlm = 0;/初始化huff man树i f (! ini tial izehuffmantree (huf fmcintree, sourcehi le)printf ("初始化错误什"); return false;/统计词频int bytenum =

24、statisticsofhuffmannodes(huffmantree，sourcefile); if (!bytcnum)printf ("统计词频错误n"); return false;/生成huff man编硏int roottndex = generatchuffmantree(huffmantree, issigncd): if (!rootlndex)printf ("生成哈夫曼编码错误n"); return false;/生成文件编码bool* filecode =(boo 1*)ma 11oc(8*bytcnum);int fileco

25、delength = generatepilecode(huffmantree, sourcefile, filecode): huffmantree01. bitnum = filecodelength; if (filecodelength = 0)printf ("生成文件编码错误1<); return false;if (!createconipressei le(destfi 1 e, fi 1 ecode, filecodelength)printf f生成压缩文件错误rf); return false;free(filecode);file* file = fop

26、en(huffmantree，'vb)；fwri te (huffmantree, s i zcof (1 luff mannode), maxxodenum, file); fclose(file):if (! destroyhuf fmcintree (huffmcintree)printf ("不能释放资源"); return false;return true;bool huffmanfunction: :uncompressfi lc(char* sourcci;i 1 c, char* dcstei le) huffmannode huffmantreemax_node_num;p'll卜:氺 file = fopen(huffmantree，rb)；fread(huffmantree, sizcof(huffmannode), max_node_num, file);fcl