数据结构实验报告4文件压缩概要Word文档格式.docx

1、一、问题描述 哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。 统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，并将该哈夫曼树保存到文件HufTree.dat 中。 根据哈夫曼树（保存在HufTree.dat 中）对每个字符进行哈夫曼编码，并将字符编码保存到HufCode.txt 文件中。 压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。 解压：将C

2、odeFile.dat 文件利用哈夫曼树译码解压，恢复为源文件。二、数据结构设计 由于哈夫曼树中没有度为1的结点，则一棵树有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。1.使用结构体数组统计词频，并存储:typedef struct Node int weight; /叶子结点的权值 char c; /叶子结点 int num; /叶子结点的二进制码的长度LeafNodeN;2.使用结构体数组存储哈夫曼树:typedef struct unsigned int wei

3、ght;/权值 unsigned int parent, LChild, RChild;HTNode,HuffmanM+1; /huffman树3.使用字符指针数组存储哈夫曼编码表：typedef char *HuffmanCode2*M; /haffman编码表三、算法设计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

4、= 0） printf（%s读取失败n, file_name）; 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 *leaf_num） int len,j,k; int tag; *leaf_num=0;/叶子节点个数 /统计字符出现个数,放入CW for（len=0; chlen!= len+）/遍历字符

5、串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! k+）/在之后的字符串中累计权值 if（chlen=chk） leaves*leaf_num.weight+;/权值累加 *ch_len=len;/字符串长度3创建HuffmanTree，并存储创建：void CreateHuffmanTree（Huffman ht,LeafNode w,in

6、t 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;=2*n-1; hti.weight=0; for（j=1;jhtj.weight?j:s1; hts1.parent=i; hti.LChild=s1; s2=j; /找到第二个双亲为零的结点 s2=hts2.weights2; hts2.parent=i; hti.RChild=s2; hti.weight=hts1.weight+hts2.w

7、eight;存储：void save_HufTree（Huffman ht, LeafNode le, int ln） int i; FILE *HufTree = Fopen（HufTree.dat, a CreateHuffmanTree（ht, le, ln）;n哈夫曼树n编号 权值 parent LChild RChildn /fputs（编号|权值|parent|LChild|RChildn, HufTree）; i=2*ln-1; i+） /*打印Huffman树的信息*/%dt%dt%dt%dt%dn, i, （ht）i.weight, （ht）i.parent, （ht）i.L

8、Child, （ht）i.RChild）; fprintf（HufTree, %d | %d | %d | %d | %dn Fclose（HufTree）;哈弗曼树已保存至HufTree.datn4.读取哈夫曼树至新的结构体数组void read_HufTree（Huffman ht） /记得从1开始存储 int i = 1, j; while（fscanf（HufTree, , &j, &（ht）i.weight）, &（ht）i.parent）, &（ht）i.LChild）, &（ht）i.RChild） = 5） /printf（%dt%dt%dt%dn, （ht）i.weight,

9、 （ht）i.parent, （ht）i.LChild, （ht）i.RChild）; i+;已从HufTree.dat读取哈弗曼树n5.根据哈夫曼树生成每个叶子结点的编码 void CrtHuffmanNodeCode（Huffman ht, char ch, HuffmanCode code_of_leaf, LeafNode weight, int m, int n） int i,c,p,start; char *cd; cd=（char *）malloc（n*sizeof（char）; cdn-1=/末尾置0 start=n-1; /cd串每次从末尾开始 c=i; p=hti.pare

10、nt;/p在n+1至2n-1 while（p） /沿父亲方向遍历,直到为0 start-;/依次向前置值 if（htp.LChild=c）/与左子相同,置0 cdstart=0 else /否则置11 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（cd）;/释放cd内存6.保存每个叶子结点的信息vo

11、id save_HufCode（Huffman ht, char *ch, HuffmanCode code_of_leaf, LeafNode leaves, int ch_len, int leaf_num） FILE *HufCode = Fopen（HufCode.txt CrtHuffmanNodeCode（ht, ch, code_of_leaf, leaves, ch_len, leaf_num）; /叶子结点的编码n每个叶子节点的前缀码n /打印叶子结点的编码=leaf_num; i+）%c: %sn,leavesi.c, code_of_leafi）; fprintf（Huf

12、Code, , leavesi.c, code_of_leafi）; Fclose（HufCode）;每个叶子节点的前缀码已保存至HufCode.txtn7.读取每个叶子节点的信息到新的字符指针数组void read_HufCode（HuffmanCode code_of_leaf） int i=1; char c, tem10; while（fscanf（HufCode, , &c, tem） = 2） int len = strlen（tem）; code_of_leafi = （char *）malloc（len*sizeof（char）; strcpy（code_of_leafi, t

13、em）;, c, code_of_leafi）;已从HufCode.txt读取每个叶子节点信息n8.生成所有字符的编码 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;ch_len; for（k=1;kk+） /*从weightk.c中查找与chi相等的下标K*/ if（chi=leavesk.c） code_of_chi=（char *）malloc（leavesk

14、.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.解码并保存到str2.txtvoid TrsHuffmanTree（Huffman ht,

15、 LeafNode w, HuffmanCode hc, int n, int m） int i=0,j,p; FILE *str2 = Fopen（str2.txtn经解压得原文件中的字符串: while（im） p=2*n-1;/从父亲节点向下遍历直到叶子节点hcij!j+） if（hcij=） p=htp.LChild; else p=htp.RChild;%c,wp.c）; /*打印原信息*/ fputc（wp.c, str2）; Fclose（str2）;n已将解压得到的字符串保存至str2.txtn11.释放huffman编码内存void FreeHuffmanCode（Huffm

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

17、ode.txt内容8.根据前缀码生成哈夫曼编码，保存至CodeFile.dat9.CodeFile.dat内容10根据CodeFile.dat解压，获得原字符串，并保存至str2.txt11.str2.txt内容五、实验收获与思考 通过使用哈夫曼树实现文件压缩，使我充分理解哈夫曼树的构造方法以及实际应用，巩固了课堂知识，同时认识到自己的不足。在编程中发现问题，通过查询求助解决问题，使我不断地我加深数据结构的学习。六、附录（原程序）#include stdlib.hstring.h#define N 100#define M 2*N-1/haffman编码/huffman树/ 产生叶子结点的字符和权值 / 创建HuffmanTree / 生成每个叶子结点的编码 / 生成所有字符的编码