数据结构实验报告记录文件压缩2————————————————————————————————作者：————————————————————————————————日期：3数据结构与程序设计实验实验报告课程名称数据结构与程序设计实验课程编号0906550实验项目名称文件压缩学号年级姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静实验室名称地点21B276哈尔滨工程大学4实验报告四实验课名称：数据结构与程序设计实验实验名称：文件压缩班级：学号：姓名：时间：2016.04.21一、问题描述哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，并将该哈夫曼树保存到文件HufTree.dat中。根据哈夫曼树（保存在HufTree.dat中）对每个字符进行哈夫曼编码，并将字符编码保存到HufCode.txt文件中。压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。解压：将CodeFile.dat文件利用哈夫曼树译码解压，恢复为源文件。二、数据结构设计由于哈夫曼树中没有度为1的结点，则一棵树有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。1.使用结构体数组统计词频，并存储:typedefstructNode{intweight;//叶子结点的权值charc;//叶子结点intnum;//叶子结点的二进制码的长度}LeafNode[N];2.使用结构体数组存储哈夫曼树:typedefstruct{unsignedintweight;//权值unsignedintparent,LChild,RChild;}HTNode,Huffman[M+1];//huffman树3.使用字符指针数组存储哈夫曼编码表：typedefchar*HuffmanCode[2*M];//haffman编码表三、算法设计1.读取文件，获得字符串voidread_file(charconst*file_name,char*ch){FILE*in_file=Fopen(file_name,"r");unsignedintflag=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);intlen=strlen(ch);5ch[len-1]='\0';}2.统计叶子结点的字符和权值并存储voidCreateLeaf(charch[],int*ch_len,LeafNodeleaves,int*leaf_num){intlen,j,k;inttag;*leaf_num=0;//叶子节点个数//统计字符出现个数,放入CWfor(len=0;ch[len]!='\0';len++){//遍历字符串ch[]tag=1;for(j=0;jht[j].weight?j:s1;ht[s1].parent=i;ht[i].LChild=s1;for(j=1;j<=i-1;j++)if(!ht[j].parent)break;s2=j;//找到第二个双亲为零的结点for(;j<=i-1;j++)if(!ht[j].parent)s2=ht[s2].weight>ht[j].weight?j:s2;ht[s2].parent=i;ht[i].RChild=s2;ht[i].weight=ht[s1].weight+ht[s2].weight;//权值累加}}存储：voidsave_HufTree(Huffmanht,LeafNodele,intln){inti;FILE*HufTree=Fopen("HufTree.dat","a");CreateHuffmanTree(ht,le,ln);printf("\n哈夫曼树\n");printf("编号权值parentLChildRChild\n");//fputs("编号|权值|p...
