huffman编码译码实现文件的压缩与解压文档格式.docx

1、2.1.1 字符的统计用结构体huffchar来存放文件字符的信息。其中有文件中不同字符出现的种类Count、字符data。struct huffchar/存放读入字符的类； int Count;/字符出现的个数； char data;/字符；;函数实现： bool char_judge（char c）/判断字符出现的函数； void char_add（char c）/添加新出现的字符； void read_file_count（） /文件的读取2.1.2 huffman树节点的设计用结构体huff_tree来存储结点信息，其中有成员频率weight、父亲节点parent、左儿子节点lchil

2、d、右儿子节点rchild。struct huff_tree/huffman树结点定义； int parent; int lchild; int rchild; int weight; void creathuffman（） /构造huffman树的函数 2.2构造huffman编码 2.2.1 huffman编码的设计 用结构体huffcode来存储每个字符的编码。其中有编码数组bits、起始编码start、频数count、编码对应的字符 c。struct huffcode/结构体 string bits100;/存放解码； int start;/ int count;/频数 string

3、c;/存放字符； void huffmancode（）/编码函数 2.3 压缩文件与解压文件的实现 将压缩的文件根据huffman树进行编码，存入新的文件（huffman1.txt）中，将huffman.txt按照huffman编码对应的字符解压回来，但是这样的文件是压缩不了的，当时用了一个30kb的文件压缩后竟然成了119kb，导致这样的问题是因为一个字符对应几个二进制数字，然而一个二进制文字也是占一个字节，这就导致了压缩后的文件变大。处理的方法将huffman1.txt文件中的二进制编码7位7位的存成一个ascII值存入新的文件，这样就实现了真正打压缩。解压的时候将文件中的ascII值重新

4、弄成二进制，不够7位的前边补0，例如ascII值为99的二进制位100011这是6位的ascII码所以再前边补一个0那么99的二进制就变成0100011。接下来就利用huffman编码将这个文件重新译码过来。 void code_huffman_file（）/编码后的二进制码存入文件 void code_file_out（）/将编码过的文件恢复； void evaluating（）/比较文件压缩的比例 void change（）/将二进制编码变成ascII码 void yichu（）/将ascII翻译成二进制码恢复文件三、执行效果 本算法有一个初始文件为huffman.txt。为一篇小说，大小

5、为32KB 3.1界面 3.2每个字符的编码3.3操作部分3.4文件效果huffman为初始文件大小为30KB，huffman1为二进制编码文件大小为130KB，huffman2文件为解压后的文件大小为30KB，huffman3.为真正压缩后的文件大小为19KB，huffman为huffman3文件解压后的文件大小为30KB，与huffman文件内容相同。标记的文件就是压缩后的huffman3文件。四、源程序：#include fstreamstringiomanipcstdioalgorithmqueueusing namespace std;string remfile3100000;/存

6、放原文件字符的数组；char strstr1500000;int remcount=0;/记录元素个数；float bitecount=0;/记录二进制码的个数；/*/struct huffchar/存放读入字符的类；int Count=1;/记录huff数组中字符实际出现的个数；huffchar huff1000;/类的对象；/*文件读入部分和统计字符出现的频率*/bool char_judge（char c）/判断字符出现的函数； for（int i=1;i=Count;i+） if（huffi.data=c）huffi.Count+;return true;/如果出现过，出现的频数加1；

7、 return false;void char_add（char c）/添加新出现的字符； huffCount.data=c; huffCount+.Count+;/个数增加，/文件的读取void read_file_count（） char c; ifstream infile; infile.open（huffman.txt）;/打开huffman.txt文件； if（!infile）/检查文件是否打开。 cerr不能打开 huffman.txt文件;/输出文件未打开的标志。 exit（0）; cout读入的文件中的内容为：endl; while（c=infile.get（）!=EOF）

8、remfile+remcount=c;char_judge（c） char_add（c）;/*文件读入和统计字符出现频率部分结束*/*/*构造huffman树程序部分*/ int sum;/huffman树中结点的个数； huff_tree huffman1000;void creathuffman（）/构造huffman树的函数 int min1,min2;/指示权值最小； int loc1,loc2;/指向权值最小的两个数的位置；=sum; /对huffman树的结点进行初始化； huffmani.parent=0; huffmani.lchild=0; huffmani.rchild=0

9、; huffmani.weight=0; for（int ii=1;iiCount;ii+）/将权值赋给huffman.weight; huffmanii.weight=huffii.Count; sum=2*Count-3;for（int j=Count;jj+） loc1=loc2=0;/权值最小的 min1=min2=2000000; for（int k=1;k=j-1;k+）/求权值最小的两个地址； if（huffmank.parent=0） if（huffmank.weight=min1） min2=min1;min1=huffmank.weight; loc2=loc1;loc1=

10、k; else=min2） min2=huffmank.weight;loc2=k;/将求出的两个权值最小的结点合并为新的结点，并将新的结点存入数组中 huffmanloc1.parent=j; huffmanloc2.parent=j; huffmanj.lchild=loc1; huffmanj.rchild=loc2; huffmanj.weight=huffmanloc1.weight+huffmanloc2.weight;/*构造huffman树的程序部分结束*/*huffman编码开始*/struct huffcode/结构体huffcode hcode100;void huffm

11、ancode（）/编码函数 int rem,p;int count1=0; for（int y=1;yy+） /编码部分； rem=y; hcodey.start=sum; hcodey.c=huffy.data; p=huffmany.parent; while（p!=0） if（huffmanp.lchild=rem）hcodey.bits+count1=0 else hcodey.bits+count1=1 rem=p; p=huffmanp.parent; hcodey.count=count1; count1=0;字符以及其编码： for（int t=1;tt+）/输出所编的码；字符

12、hcodet.c；编码： int r=hcodet.count; while（r）hcodet.bitsr-;/*/ string str;void code_huffman_file（） ofstream fp;请输入文件名endlstr; fp.open（str.c_str（）;fp）/检查文件是否打开。不能打开 str0;k-） fphcodei.bitsk;bitecount+; break; fp.close（）;/*编码并将编码存入文件部分结束*/string s1;/void code_file_out（）/将编码过的文件恢复； ifstream fp1;/编码文件； ofstr

13、eam fp2;/解压缩文件； fp1.open（str.c_str（）;fp1）/检查文件是否打开。 char inchar;huffman2.txt该文件用来存放解压后的文件s1; fp2.open（s1.c_str（）;fp2）/检查文件是否打开。不能打开s1inchar; if（inchar=）ptr=huffmanptr.rchild;/查找相应编码对应huffman树中的位置， else ptr=huffmanptr.lchild; if（huffmanptr.rchild=0&huffmanptr.lchild=0）/判断是否为叶子结点； fp2huffptr.data;ptr=

14、sum;/是叶子结点，将该结点的对应字符输入到文件中； 请检查原文件与解压缩文件 /cout*请检查*/*解压缩文件部分结束*/void evaluating（） float y1; y1=bitecount/7/remcount*100;压缩比例是：y1%string s2;/压缩文件2名int tot=0;void change（）输入文件名用来存放压缩后的文件例如huffman3.txts2; char inchar,ch; fp2.open（s2.c_str（）;s2 int t=0,f=0,s; /char a8; while（!fp1.eof（） s=inchar- t*=2; t

15、+=s; f+; if（f=7） ch=t; t=0; fp2ch; strstrtot+=ch; f=0; strstrtot=0 fp1.close（）; fp2.close（）;string s3;/文件解压2名queues;string s4;void yichu（） fp1.open（s2.c_str（）;输入文件名用来存放解压后的文件例如huffman4.txts3; fp2.open（s3.c_str（）;s3 int inchar; int i=0;s.empty（）s.pop（）;tot;） if（s.size（）=0;i-） ai=num%2;num/=2; for（int

16、 i=0;7; /ch=ai+ s.push（ai）; inchar=s.front（）; s.pop（）; if（inchar=1）ptr=huffmanptr.rchild; if（huffmanptr.lchild=0&huffmanptr.rchild=0）/判断是否为叶子结点；/printf（*int main（） * * 数据结构课程设计 * * Huffman树文件压缩 * * * * * * * /system（pause read_file_count（）;一共有Count个字符 creathuffman（）; huffmancode（）;*模拟压缩* code_huffman_file（）; code_file_out（）;*真正的压缩*