数据结构实验报告4文件压缩教程.doc

数据结构与程序设计实验 实 验 报 告 课程名称数据结构与程序设计实验课程编号0906550实验项目名称 文件压缩学号2014061221年级2014姓名马攀专业计算机科学与技术学生所在学院计算机学院指导教师杨静实验室名称地点21B276 哈尔滨工程大学 实验报告四 实验课名称：数据结构与程序设计实验实验名称：文件压缩班级：学号：姓名： 时间：2016.04.21一、问题描述 哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。 ? 统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树， 并将该哈夫曼树保存到文件HufTree.dat 中。 ? 根据哈夫曼树（保存在HufTree.dat 中）对每个字符进行哈夫曼编码，并 将字符编码保存到HufCode.txt 文件中。 ? 压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。 ? 解压：将CodeFile.dat 文件利用哈夫曼树译码解压，恢复为源文件。 二、数据结构设计 由于哈夫曼树中没有度为1的结点，则一棵树有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。 1.使用结构体数组统计词频，并存储: typedef struct Node{ int weight; //叶子结点的权值 char c; //叶子结点 int num; //叶子结点的二进制码的长度 }LeafNode[N]; 2.使用结构体数组存储哈夫曼树: typedef struct{ unsigned int weight;//权值 unsigned int parent, LChild, RChild; }HTNode,Huffman[M+1]; //huffman树 3.使用字符指针数组存储哈夫曼编码表： typedef char *HuffmanCode[2*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 == 0){ printf(%s读取失败\n, file_name); fflush(stdout); } printf(读入的字符串是: %s\n\n, ch); Fclose(in_file); int len = strlen(ch); ch[len-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; ch[len]!=\0; len++){//遍历字符串ch[] tag=1; for(j=0; jlen; j++){ if(ch[j]==ch[len]){ tag=0; break; } } if(tag){// *leaf_num =0 不用 leaves[++*leaf_num].c=ch[len]; leaves[*leaf_num].weight=1; for(k=len+1; ch[k]!=\0; k++)//在之后的字符串中累计权值 if(ch[len]==ch[k]) 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=