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

数据结构与程序设计实验实验报告课程名称数据结构与程序设计实验课程编号0906550实验项目名称文件压缩学号年级姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静实验室名称地点21B276哈尔滨工程大学实验报告四实验课名称：数据结构与程序设计实验实验名称：文件压缩班级：学号：姓名：时间：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);ch[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;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，并存储创建：voidCreateHuffmanTree(Huffmanht,LeafNodew,intn){inti,j;ints1,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;//找到第一个双亲为零的结点for(;j=i-1;j++)if(!ht[j].parent)s1=ht[s1].weightht[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].weightht[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(编号|权值|parent|LChild|RChild\n,HufTree);for(i=1;i=2*ln-1;i++){/*打印Huffman树的信息*/printf(%d\t%d\t%d\t%d\t%d\n,i,(ht)[i].weight,(ht)[i].parent,(ht)[i].LChild,(ht)[i].RChild);fprintf(HufTree,%d|%d|%d|%d|%d\n,i,(ht)[i].weight,(ht)[i].parent,(ht)[i].LChild,(ht)[i].RChild);}Fclose(HufTree);printf(哈弗曼树已保存至HufTree.dat\n);}4.读取哈夫曼树至新的结构体数组voidread_HufTree(Huffmanht){//记得从1开始存储inti=1,j;FILE*HufTree=Fopen(HufTree.dat,r);while((fscanf(HufTree,%d|%d|%d|%d|%d\n,&j,&((ht)[i].weight),&((ht)[i].parent),&((ht)[i].LChild),&((ht)[i].RChild)))==5){//printf(%d\t%d\t%d\t%d\n,(ht)[i].weight,(ht)[i].parent,(ht)[i].LChild,(ht)[i].RChild);i++;}Fclose(HufTree);printf(已从HufTree.dat读取哈弗曼树\n);}5.根据哈夫曼树生成每个叶子结点的编码voidCrtHuffmanNodeCode(Huffmanht,charch[],HuffmanCodecode_of_leaf,LeafNodeweight,intm,intn){inti,c,p,start;char*cd;cd=(char*)malloc(n*sizeof(char));cd[n-1]='\0';//末尾置0for(i=1;i=n;i++){start=n-1;//cd串每次从末尾开始c=i;p=ht[i].parent;//p在n+1至2n-1while(p){//沿父亲方向遍历,直到为0start--;//依次向前置值if(ht[p].LChild==c)//与左子相同,置0cd[start]='0';else//否则置1cd[start]='1';c=p;p=ht[p].parent;}weight[i].num=n-start;//二进制码的长度(包含末尾0)code_of_leaf[i]=(char*)malloc((n-start)*sizeof(char));strcpy(code_of_leaf[i],&cd[start]);//将二进制字符串拷贝到指针数组code_of_leaf中}free(cd);//释放cd内存}6.保存每个叶子结点的信息voidsave_HufCode(Huffmanht,char*ch,HuffmanCodecode_of_leaf,LeafNodeleaves,intch_len,intleaf_num){inti;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:%s\n,leaves[i].c,code_of_leaf[i]);fprintf(HufCode,%c:%s\n,leaves[i].c,code_of_leaf[i]);}Fclose(HufCode);printf(每个叶子节点的前缀码已保存至HufCode.txt\n);}7.读取每个叶子节点的信息到新的字符指针数组voidread_HufCode(HuffmanCodecode_of_leaf){inti=1;charc,tem[10];FILE*HufCode=Fopen(HufCode.txt,r);while((fscanf(HufCode,%c:%s\n,&c,tem))==2){intlen=strlen(tem);code_of_leaf[i]=(char*)malloc(len*sizeof(char));strcpy(code_of_leaf[i],tem);//printf(%c:%s\n,c,code_of_leaf[i]);i++;}Fclose(HufCode);printf(已从HufCode.txt读取每个叶子节点信息\n);}8.生成所有字符的编码voidCrtHuffmanCode(charch[],HuffmanCodecode_of_leaf,HuffmanCodecode_of_ch,LeafNodeleaves,intleaf_num,intch_len){inti,k;for(i=0;ich_len;i++){for(k=1;k=leaf_num;k++)/*从weight[k].c中查找与ch[i]相等的下标K*/if(ch[i]==leaves[k].c)break;code_of_ch[i]=(char*)malloc((leaves[k].num)*sizeof(char));strcpy(code_of_ch[i],code_of_leaf[k]);//拷贝二进制编码}}9.保存字符串的编码信息(压缩)FILE*Fopen(charconst*filename,charconst*mode){FILE*idlist;idlist=fopen(filename,mode);if(idlist==NULL){perror(filename);exit(EXIT_FAILURE);}else{returnidlist;}}10.解码并保存到str2.txtvoidTrsHuffmanTree(Huffmanht,LeafNodew,HuffmanCod