数据结构实验报告-文件压缩

1、.数据结构与程序设计实验实 验 报 告课程名称数据结构与程序设计实验课程编号实验项目名称 文件压缩学号年级姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静实验室名称地点21B276哈尔滨工程大学实验报告四实验课名称：数据结构与程序设计实验实验名称：文件压缩班级：学号：姓名： 时间：2016.04.21一、问题描述 哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。l 统计待压缩的文本

2、文件中各字符的词频，以词频为权值建立哈夫曼树，并将该哈夫曼树保存到文件HufTree.dat 中。l 根据哈夫曼树（保存在HufTree.dat 中）对每个字符进行哈夫曼编码，并将字符编码保存到HufCode.txt 文件中。l 压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件Code。l 解压：将Code 文件利用哈夫曼树译码解压，恢复为源文件。二、数据结构设计 由于哈夫曼树中没有度为1的结点，则一棵树有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。1.使用结构体数

3、组统计词频，并存储: typedef struct Nodeint weight; /叶子结点的权值char c; /叶子结点int num; /叶子结点的二进制码的长度LeafNodeN;2.使用结构体数组存储哈夫曼树: typedef structunsigned int weight;/权值unsigned int parent, LChild, RChild;HTNode,HuffmanM+1; /huffman树3.使用字符指针数组存储哈夫曼编码表：typedef char *HuffmanCode2*M; /haffman编码表三、算法设计1.读取文件，获得字符串void read

4、_ const *, char *ch)FILE *in_file = Fopen(, r);unsigned int flag = fread(ch, sizeof(char), N, in_file);if(flag = 0)printf(%s读取失败n, );fflush(stdout);printf(读入的字符串是: %snn, ch);Fclose(in_file);int len = strlen(ch);chlen-1 = 0;2.统计叶子结点的字符和权值并存储void CreateLeaf(char ch, int *ch_len, LeafNode leaves, int *

5、leaf_num)int len,j,k;int tag;*leaf_num=0;/叶子节点个数/统计字符出现个数,放入CWfor(len=0; chlen!=0; len+)/遍历字符串ch tag=1;for(j=0; jlen; j+)if(chj=chlen)tag=0;break;if(tag)/ *leaf_num =0 不用leaves+*leaf_num.c=chlen;leaves*leaf_num.weight=1;for(k=len+1; chk!=0; k+)/在之后的字符串中累计权值if(chlen=chk)leaves*leaf_num.weight+;/权值累加*

6、ch_len=len;/字符串长度3创建HuffmanTree，并存储创建：void CreateHuffmanTree(Huffman ht,LeafNode w,int n)int i,j;int s1,s2;/初始化哈夫曼树for(i=1;i=n;i+)hti.weight =wi.weight;hti.parent=0;hti.LChild=0;hti.RChild=0;for(i=n+1;i=2*n-1;i+)hti.weight=0;hti.parent=0;hti.LChild=0;hti.RChild=0;for(i=n+1;i=2*n-1;i+)for(j=1;j=i-1;j

7、+)if(!htj.parent)break;s1=j; /找到第一个双亲为零的结点for(;jhtj.weight?j:s1;hts1.parent=i;hti.LChild=s1;for(j=1;j=i-1;j+)if(!htj.parent)break;s2=j; /找到第二个双亲为零的结点for(;jhtj.weight?j:s2;hts2.parent=i;hti.RChild=s2;hti.weight=hts1.weight+hts2.weight;/权值累加存储：void save_HufTree(Huffman ht, LeafNode le, int ln)int i;FI

8、LE *HufTree = Fopen(HufTree.dat, a);CreateHuffmanTree(ht, le, ln);printf(n哈夫曼树n);printf(编号 权值 parent LChild RChildn);/fputs(编号|权值|parent|LChild|RChildn, HufTree);for(i=1; i=2*ln-1; i+) /*打印Huffman树的信息*/printf(%dt%dt%dt%dt%dn, i, (ht)i.weight, (ht)i.parent, (ht)i.LChild, (ht)i.RChild);fprintf(HufTree

9、, %d | %d | %d | %d | %dn, i, (ht)i.weight, (ht)i.parent, (ht)i.LChild, (ht)i.RChild);Fclose(HufTree);printf(哈弗曼树已保存至HufTree.datn);4.读取哈夫曼树至新的结构体数组void read_HufTree(Huffman ht) /记得从1开始存储int i = 1, j;FILE *HufTree = Fopen(HufTree.dat, r);while(fscanf(HufTree, %d | %d | %d | %d | %dn,&j, &(ht)i.weight

10、), &(ht)i.parent), &(ht)i.LChild), &(ht)i.RChild) = 5)/printf(%dt%dt%dt%dn, (ht)i.weight, (ht)i.parent, (ht)i.LChild, (ht)i.RChild);i+;Fclose(HufTree);printf(已从HufTree.dat读取哈弗曼树n);5.根据哈夫曼树生成每个叶子结点的编码 void CrtHuffmanNodeCode(Huffman ht, char ch, HuffmanCode code_of_leaf, LeafNode weight, int m, int n

11、)int i,c,p,start;char *cd;cd=(char *)malloc(n*sizeof(char);cdn-1=0;/末尾置0for(i=1;i=n;i+)start=n-1; /cd串每次从末尾开始c=i;p=hti.parent;/p在n+1至2n-1while(p) /沿父亲方向遍历,直到为0start-;/依次向前置值if(htp.LChild=c)/与左子相同,置0cdstart=0;else /否则置1cdstart=1;c=p;p=htp.parent;weighti.num=n-start; /二进制码的长度(包含末尾0)code_of_leafi=(char

12、 *)malloc(n-start)*sizeof(char);strcpy(code_of_leafi,&cdstart);/将二进制字符串拷贝到指针数组code_of_leaf中free(cd);/释放cd内存6.保存每个叶子结点的信息void save_HufCode(Huffman ht, char *ch, HuffmanCode code_of_leaf, LeafNode leaves, int ch_len, int leaf_num)int i;FILE *HufCode = Fopen(HufCode.txt, a);CrtHuffmanNodeCode(ht, ch, c

13、ode_of_leaf, leaves, ch_len, leaf_num); /叶子结点的编码printf(n每个叶子节点的前缀码n); /打印叶子结点的编码for(i=1; i=leaf_num; i+)printf(%c: %sn,leavesi.c, code_of_leafi);fprintf(HufCode, %c: %sn, leavesi.c, code_of_leafi);Fclose(HufCode);printf(每个叶子节点的前缀码已保存至HufCode.txtn);7.读取每个叶子节点的信息到新的字符指针数组void read_HufCode(HuffmanCode

14、code_of_leaf)int i=1;char c, tem10;FILE *HufCode = Fopen(HufCode.txt, r);while(fscanf(HufCode, %c: %sn, &c, tem) = 2)int len = strlen(tem);code_of_leafi = (char *)malloc(len*sizeof(char);strcpy(code_of_leafi, tem);/printf(%c: %sn, c, code_of_leafi);i+;Fclose(HufCode);printf(已从HufCode.txt读取每个叶子节点信息n)

15、;8.生成所有字符的编码 void CrtHuffmanCode(char ch, HuffmanCode code_of_leaf, HuffmanCode code_of_ch, LeafNode leaves, int leaf_num, int ch_len)int i,k;for(i=0;ich_len;i+)for(k=1;k=leaf_num;k+) /*从weightk.c中查找与chi相等的下标K*/if(chi=leavesk.c)break;code_of_chi=(char *)malloc(leavesk.num)*sizeof(char);strcpy(code_o

16、f_chi,code_of_leafk); /拷贝二进制编码9.保存字符串的编码信息(压缩)FILE *Fopen(char const *, char const *mode)FILE *idlist; idlist = fopen(, mode);if(idlist = NULL)perror();exit(EXIT_FAILURE);elsereturn idlist;10.解码并保存到str2.txtvoid TrsHuffmanTree(Huffman ht, LeafNode w, HuffmanCode hc, int n, int m)int i=0,j,p;FILE *str

17、2 = Fopen(str2.txt, a);printf(n经解压得原文件中的字符串: );while(im)p=2*n-1;/从父亲节点向下遍历直到叶子节点for(j=0;hcij!=0;j+)if(hcij=0)p=htp.LChild;elsep=htp.RChild;printf(%c,wp.c); /*打印原信息*/fputc(wp.c, str2);i+;Fclose(str2);printf(n已将解压得到的字符串保存至str2.txtn);11.释放huffman编码内存void FreeHuffmanCode(HuffmanCode h1, HuffmanCode h2,

18、HuffmanCode hc, int leaf_num, int ch_len)int i;for(i=1;i=leaf_num;i+)/释放叶子结点的编码free(h1i); free(h2i); for(i=0;ich_len;i+) /释放所有结点的编码free(hci);四、运行测试与分析及运行界面1.文件str1.txt内容：2.运行程序，读取文件3.统计叶子节点的权值4.根据权值生成哈夫曼树，保存至HufTree.dat，并用新的结构体数组读取哈夫曼树5.HufTree.dat内容6.根据哈夫曼树生成叶子节点的前缀码，保存至HufCode.txt，之后用新的结构体数组读取HufC

19、ode.txt7.HufCode.txt内容8.根据前缀码生成哈夫曼编码，保存至Code9.Code内容10根据Code解压，获得原字符串，并保存至str2.txt11.str2.txt内容五、实验收获与思考 通过使用哈夫曼树实现文件压缩，使我充分理解哈夫曼树的构造方法以及实际应用，巩固了课堂知识，同时认识到自己的不足。在编程中发现问题，通过查询求助解决问题，使我不断地我加深数据结构的学习。六、附录(原程序)#include #include #include #define N 100#define M 2*N-1typedef char *HuffmanCode2*M;/haffman编码

20、typedef structunsigned int weight;/权值unsigned int parent, LChild, RChild;HTNode,HuffmanM+1;/huffman树typedef struct Nodeint weight; /叶子结点的权值char c; /叶子结点int num; /叶子结点的二进制码的长度LeafNodeN;/ 产生叶子结点的字符和权值 void CreateLeaf(char ch, int *ch_len, LeafNode leaves, int *leaf_num)int len,j,k;int tag;*leaf_num=0;

21、/叶子节点个数/统计字符出现个数,放入CWfor(len=0; chlen!=0; len+)/遍历字符串ch tag=1;for(j=0; jlen; j+)if(chj=chlen)tag=0;break;if(tag)/ *leaf_num =0 不用leaves+*leaf_num.c=chlen;leaves*leaf_num.weight=1;for(k=len+1; chk!=0; k+)/在之后的字符串中累计权值if(chlen=chk)leaves*leaf_num.weight+;/权值累加*ch_len=len;/字符串长度/ 创建HuffmanTree void Cre

22、ateHuffmanTree(Huffman ht,LeafNode w,int n)int i,j;int s1,s2;/初始化哈夫曼树for(i=1;i=n;i+)hti.weight =wi.weight;hti.parent=0;hti.LChild=0;hti.RChild=0;for(i=n+1;i=2*n-1;i+)hti.weight=0;hti.parent=0;hti.LChild=0;hti.RChild=0;for(i=n+1;i=2*n-1;i+)for(j=1;j=i-1;j+)if(!htj.parent)break;s1=j; /找到第一个双亲为零的结点for(

23、;jhtj.weight?j:s1;hts1.parent=i;hti.LChild=s1;for(j=1;j=i-1;j+)if(!htj.parent)break;s2=j; /找到第二个双亲为零的结点for(;jhtj.weight?j:s2;hts2.parent=i;hti.RChild=s2;hti.weight=hts1.weight+hts2.weight;/权值累加/ 生成每个叶子结点的编码 void CrtHuffmanNodeCode(Huffman ht, char ch, HuffmanCode code_of_leaf, LeafNode weight, int m

24、, int n)int i,c,p,start;char *cd;cd=(char *)malloc(n*sizeof(char);cdn-1=0;/末尾置0for(i=1;i=n;i+)start=n-1; /cd串每次从末尾开始c=i;p=hti.parent;/p在n+1至2n-1while(p) /沿父亲方向遍历,直到为0start-;/依次向前置值if(htp.LChild=c)/与左子相同,置0cdstart=0;else /否则置1cdstart=1;c=p;p=htp.parent;weighti.num=n-start; /二进制码的长度(包含末尾0)code_of_leaf

25、i=(char *)malloc(n-start)*sizeof(char);strcpy(code_of_leafi,&cdstart);/将二进制字符串拷贝到指针数组code_of_leaf中free(cd);/释放cd内存/ 生成所有字符的编码 void CrtHuffmanCode(char ch, HuffmanCode code_of_leaf, HuffmanCode code_of_ch, LeafNode leaves, int leaf_num, int ch_len)int i,k;for(i=0;ich_len;i+)for(k=1;k=leaf_num;k+) /*从

26、weightk.c中查找与chi相等的下标K*/if(chi=leavesk.c)break;code_of_chi=(char *)malloc(leavesk.num)*sizeof(char);strcpy(code_of_chi,code_of_leafk); /拷贝二进制编码FILE *Fopen(char const *, char const *mode)FILE *idlist; idlist = fopen(, mode);if(idlist = NULL)perror();exit(EXIT_FAILURE);elsereturn idlist;void Fclose(FI

27、LE *file)if(fclose(file) != 0)perror(fclose);exit(EXIT_FAILURE);file = NULL;void read_ const *, char *ch)FILE *in_file = Fopen(, r);unsigned int flag = fread(ch, sizeof(char), N, in_file);if(flag = 0)printf(%s读取失败n, );fflush(stdout);printf(读入的字符串是: %snn, ch);Fclose(in_file);int len = strlen(ch);chle

28、n-1 = 0;void save_HufTree(Huffman ht, LeafNode le, int ln)int i;FILE *HufTree = Fopen(HufTree.dat, a);CreateHuffmanTree(ht, le, ln);printf(n哈夫曼树n);printf(编号 权值 parent LChild RChildn);/fputs(编号|权值|parent|LChild|RChildn, HufTree);for(i=1; i=2*ln-1; i+) /*打印Huffman树的信息*/printf(%dt%dt%dt%dt%dn, i, (ht)i

29、.weight, (ht)i.parent, (ht)i.LChild, (ht)i.RChild);fprintf(HufTree, %d | %d | %d | %d | %dn, i, (ht)i.weight, (ht)i.parent, (ht)i.LChild, (ht)i.RChild);Fclose(HufTree);printf(哈弗曼树已保存至HufTree.datn);void read_HufTree(Huffman ht) /记得从1开始存储int i = 1, j;FILE *HufTree = Fopen(HufTree.dat, r);while(fscanf(

30、HufTree, %d | %d | %d | %d | %dn,&j, &(ht)i.weight), &(ht)i.parent), &(ht)i.LChild), &(ht)i.RChild) = 5)/printf(%dt%dt%dt%dn, (ht)i.weight, (ht)i.parent, (ht)i.LChild, (ht)i.RChild);i+;Fclose(HufTree);printf(已从HufTree.dat读取哈弗曼树n);void save_HufCode(Huffman ht, char *ch, HuffmanCode code_of_leaf, Leaf

31、Node leaves, int ch_len, int leaf_num)int i;FILE *HufCode = Fopen(HufCode.txt, a);CrtHuffmanNodeCode(ht, ch, code_of_leaf, leaves, ch_len, leaf_num); /叶子结点的编码printf(n每个叶子节点的前缀码n); /打印叶子结点的编码for(i=1; i=leaf_num; i+)printf(%c: %sn,leavesi.c, code_of_leafi);fprintf(HufCode, %c: %sn, leavesi.c, code_of_

32、leafi);Fclose(HufCode);printf(每个叶子节点的前缀码已保存至HufCode.txtn);void read_HufCode(HuffmanCode code_of_leaf)int i=1;char c, tem10;FILE *HufCode = Fopen(HufCode.txt, r);while(fscanf(HufCode, %c: %sn, &c, tem) = 2)int len = strlen(tem);code_of_leafi = (char *)malloc(len*sizeof(char);strcpy(code_of_leafi, tem

33、);/printf(%c: %sn, c, code_of_leafi);i+;Fclose(HufCode);printf(已从HufCode.txt读取每个叶子节点信息n);void save_Code *ch, HuffmanCode code_of_leaf, HuffmanCode code_of_ch, LeafNode leaves, int leaf_num, int ch_len)FILE *CodeFile = Fopen(Code, a);CrtHuffmanCode(ch, code_of_leaf, code_of_ch, leaves, leaf_num, ch_l

34、en); /字符串的编码printf(n字符串的编码: ); /打印字符串的编码int i;for(i=0; ich_len; i+)printf(%s,code_of_chi);fputs(code_of_chi, CodeFile);Fclose(CodeFile);printf(n字符串的哈弗曼编码已保存至Coden);/解码并保存到str2.txtvoid TrsHuffmanTree(Huffman ht, LeafNode w, HuffmanCode hc, int n, int m)int i=0,j,p;FILE *str2 = Fopen(str2.txt, a);printf(n经解压得原文件中的字符串: );while(im)p=2*n-1;/从父亲节点向下遍历直到叶子节点for(j=0;hcij!=0;j+)if(hcij=0)p=htp.LChild;elsep=htp.RChild;printf(%c,wp.c); /*打印原信息*/fputc(wp.c, str2);i+;Fclose(str2);printf(n已将解压得到