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

《数据结构实验报告-文件压缩.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

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

3、，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。1.使用结构体数组统计词频，并存储:typedefstructNode{intweight;//叶子结点的权值charc;//叶子结点intnum;//叶子结点的二进制码的长度}LeafNode[N];2.使用结构体数组存储哈夫曼树:typedefstruct{unsignedintweight;//权值unsignedintparent,LChild,RChild;}HTNode,Huffman[M+1];//huffman树3.使用字符指针数组存储哈夫曼编

4、码表：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读取失败",file_name);fflush(stdout);}printf("读入的字符串是:%s",ch);Fclo

5、se(in_file);intlen=strlen(ch);ch[len-1]='';}2.统计叶子结点的字符和权值并存储voidCreateLeaf(charch[],int*ch_len,LeafNodeleaves,int*leaf_num){intlen,j,k;inttag;*leaf_num=0;//叶子节点个数//统计字符出现个数,放入CWfor(len=0;ch[len]!='';len++){//遍历字符串ch[]tag=1;for(j=0;j

6、;}}if(tag){//*leaf_num=0不用leaves[++*leaf_num].c=ch[len];leaves[*leaf_num].weight=1;for(k=len+1;ch[k]!='';k++)//在之后的字符串中累计权值if(ch[len]==ch[k])leaves[*leaf_num].weight++;//权值累加}}*ch_len=len;//字符串长度}3．创建HuffmanTree，并存储创建：voidCreateHuffmanTree(Huffmanht,LeafNodew,intn){inti,j;in

7、ts1,s2;//初始化哈夫曼树for(i=1;i<=n;i++){ht[i].weight=w[i].weight;ht[i].parent=0;ht[i].LChild=0;ht[i].RChild=0;}for(i=n+1;i<=2*n-1;i++){ht[i].weight=0;ht[i].parent=0;ht[i].LChild=0;ht[i].RChild=0;}for(i=n+1;i<=2*n-1;i++){for(j=1;j<=i-1;j++)if(!ht[j].parent)break;s1=j;//找到第一个双亲为零的结点fo

8、r(;j<=i-1;j++)if(!ht[j].parent)s1=ht[s1].weight>ht[j].weight?