大数据的结构实验报告材料-文件资料压缩

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

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

3、子结点的信息，由此可采用如下数据结构。1. 使用结构体数组统计词频，并存储: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编码表三

4、、算法设计1. 读取文件，获得字符串void read_file(char const *file_name, char *ch)FILE *in_file = Fopen(file_name, "r");unsigned int flag = fread(ch, sizeof(char), N, in_file);if(flag = 0)printf("%s读取失败 n", file_name);fflush(stdout);printf("读入的字符串是: %snn", ch);Fclose(in_file);int len =

5、strlen(ch);精彩文档实用标准文案chlen-1 = '0'2. 统计叶子结点的字符和权值并存储void CreateLeaf(char ch, int *ch_len, LeafNode leaves, int *leaf_num)int len,j,k;int tag;*leaf_num=0;/叶子节点个数/ 统计字符出现个数 , 放入 CWfor(len=0; chlen!='0' len+)/遍历字符串chtag=1;for(j=0; j<len; j+)if(chj=chlen)tag=0;break;if(tag)/ *leaf_num

6、 =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;/字符串长度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.weig

7、ht;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(;j<=i-1;j+)if(!htj.parent)s1=hts1.weight>htj.weight?j:s1;hts1.parent=i;hti.

8、LChild=s1;for(j=1;j<=i-1;j+)if(!htj.parent)break;s2=j; /找到第二个双亲为零的结点for(;j<=i-1;j+)if(!htj.parent)s2=hts2.weight>htj.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;FILE *HufTree = Fopen("HufTree

9、.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.paren

10、t,(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");4. 读取哈夫曼树至新的结构体数组void read_HufTree(Huffman ht) /记得从 1 开始存储int i = 1, j;精彩文档实用标准文案FILE *HufTree = Fopen(&qu

11、ot;HufTree.dat", "r");while(fscanf(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("

12、;已从 HufTree.dat读取哈弗曼树n");5. 根据哈夫曼树生成每个叶子结点的编码voidCrtHuffmanNodeCode(Huffmanht,char ch,HuffmanCode code_of_leaf,LeafNodeweight, int m, 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-1wh

13、ile(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 *)malloc(n-start)*sizeof(char);strcpy(code_of_leafi,&cdstart);/将 二 进 制 字 符 串 拷 贝 到 指 针 数 组code_of_leaf中free(c

14、d);/释放 cd 内存6. 保存每个叶子结点的信息voidsave_HufCode(Huffmanht,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, code_of_leaf, leaves, ch_len, leaf_num); /叶子结精彩文档实用标准文案点的编码printf("n每个叶子

15、节点的前缀码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 code_of_leaf)

16、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(Hu

17、fCode);printf("已从 HufCode.txt读取每个叶子节点信息n");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;i<ch_len;i+)for(k=1;k<=leaf_num;k+) /* 从 weightk.c 中查找与 chi 相等的下标 K*/ if(chi=leavesk.c)break

18、;code_of_chi=(char *)malloc(leavesk.num)*sizeof(char);strcpy(code_of_chi,code_of_leafk); /拷贝二进制编码9. 保存字符串的编码信息 ( 压缩 )FILE *Fopen(char const *filename, char const *mode)FILE *idlist;idlist = fopen(filename, mode);if(idlist = NULL)perror(filename);exit(EXIT_FAILURE);else精彩文档实用标准文案return idlist;10. 解码并

19、保存到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(i<m)p=2*n-1;/从父亲节点向下遍历直到叶子节点for(j=0;hcij!='0'j+)if(hcij='0')p=htp.LChild;elsep=htp.RCh

20、ild;printf("%c",wp.c); /*打印原信息 */fputc(wp.c, str2);i+;Fclose(str2);printf("n已将解压得到的字符串保存至str2.txtn");11. 释放 huffman 编码内存void FreeHuffmanCode(HuffmanCode h1, HuffmanCode h2, HuffmanCode hc, int leaf_num, int ch_len)int i;for(i=1;i<=leaf_num;i+)/释放叶子结点的编码free(h1i);free(h2i);for(

21、i=0;i<ch_len;i+) /释放所有结点的编码free(hci);四、运行测试与分析及运行界面1. 文件 str1.txt内容：精彩文档实用标准文案2. 运行程序，读取文件3. 统计叶子节点的权值4. 根据权值生成哈夫曼树，保存至HufTree.dat，并用新的结构体数组读取哈夫曼树5.HufTree.dat内容精彩文档实用标准文案6. 根据哈夫曼树生成叶子节点的前缀码，保存至HufCode.txt，之后用新的结构体数组读取HufCode.txt7.HufCode.txt内容精彩文档实用标准文案8. 根据前缀码生成哈夫曼编码，保存至CodeFile.dat9.CodeFile.d

22、at内容精彩文档实用标准文案10根据 CodeFile.dat解压，获得原字符串，并保存至str2.txt11.str2.txt内容精彩文档实用标准文案五、实验收获与思考通过使用哈夫曼树实现文件压缩，使我充分理解哈夫曼树的构造方法以及实际应用，巩固了课堂知识， 同时认识到自己的不足。在编程中发现问题，通过查询求助解决问题，使我不断地我加深数据结构的学习。六、附录 ( 原程序 )#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 100#define M 2*N-1typedef

23、char *HuffmanCode2*M;/haffman编码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 *l

24、eaf_num) int len,j,k;int tag;*leaf_num=0;/叶子节点个数/ 统计字符出现个数 , 放入 CWfor(len=0; chlen!='0' len+)/遍历字符串chtag=1;for(j=0; j<len; 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

25、*leaf_num.weight+;/权值累加*ch_len=len;/字符串长度/ 创建 HuffmanTreevoid 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+

26、1;i<=2*n-1;i+)精彩文档实用标准文案for(j=1;j<=i-1;j+)if(!htj.parent)break;s1=j; /找到第一个双亲为零的结点for(;j<=i-1;j+)if(!htj.parent)s1=hts1.weight>htj.weight?j:s1;hts1.parent=i;hti.LChild=s1;for(j=1;j<=i-1;j+)if(!htj.parent)break;s2=j; /找到第二个双亲为零的结点for(;j<=i-1;j+)if(!htj.parent)s2=hts2.weight>htj.w

27、eight?j:s2;hts2.parent=i;hti.RChild=s2;hti.weight=hts1.weight+hts2.weight;/权值累加/ 生成每个叶子结点的编码voidCrtHuffmanNodeCode(Huffmanht,char ch,HuffmanCode code_of_leaf,LeafNodeweight, int m, 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; /c

28、d串每次从末尾开始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 *)malloc(n-start)*sizeof(char);精彩文档实用标准文案strcpy(code_of_leafi,&cdst

29、art);/将 二 进 制 字 符 串 拷 贝 到 指 针 数 组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;i<ch_len;i+)for(k=1;k<=leaf_num;k+) /* 从 weightk.c 中查找与 chi 相等的下标 K*/ if(chi=leave

30、sk.c)break;code_of_chi=(char *)malloc(leavesk.num)*sizeof(char);strcpy(code_of_chi,code_of_leafk); /拷贝二进制编码FILE *Fopen(char const *filename, char const *mode)FILE *idlist;idlist = fopen(filename, mode);if(idlist = NULL)perror(filename);exit(EXIT_FAILURE);elsereturn idlist;void Fclose(FILE *file)if(f

31、close(file) != 0)perror("fclose");exit(EXIT_FAILURE);file = NULL;void read_file(char const *file_name, char *ch)FILE *in_file = Fopen(file_name, "r");unsigned int flag = fread(ch, sizeof(char), N, in_file);if(flag = 0)printf("%s读取失败 n", file_name);fflush(stdout);精彩文档实用标

32、准文案printf("读入的字符串是: %snn", ch);Fclose(in_file);int len = strlen(ch);chlen-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

33、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, "%d | %d | %d | %d | %dn",i,(ht)i.weight,(ht)i.parent,

34、(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(HufTree, "%d | %d | %d | %d | %dn",&j,&(ht)i.weight),&(ht)i.paren

35、t),&(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");voidsave_HufCode(Huffmanht,char *ch,HuffmanCode code_of_leaf,LeafNode leaves,int ch_len, int leaf_num)int i

36、;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:

37、 %sn", leavesi.c, code_of_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 = st

38、rlen(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");void save_CodeFile(char *ch, HuffmanCode code_of_leaf, HuffmanCode code_of_ch, LeafNode leaves, int lea

39、f_num, int ch_len)FILE *CodeFile = Fopen("CodeFile.dat", "a");CrtHuffmanCode(ch, code_of_leaf, code_of_ch, leaves, leaf_num, ch_len); /字符串的编码printf("n字符串的编码 : "); /打印字符串的编码int i;for(i=0; i<ch_len; i+)printf("%s",code_of_chi);fputs(code_of_chi, CodeFile);Fcl

40、ose(CodeFile);printf("n字符串的哈弗曼编码已保存至CodeFile.datn");/ 解码并保存到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(i<m)p=2*n-1;/从父亲节点向下遍历直到叶子节点for(j=0;hcij!='0'j+)if(hcij='0')p=htp.LChild;elsep=htp.RChil