数据结构实验报告记录文件压缩————————————————————————————————作者：————————————————————————————————日期：数据结构与程序设计实验实验报告课程名称数据结构与程序设计实验课程编号0906550 实验项目名称文件压缩学号年级姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静实验室名称地点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;//叶子节点个数//统计字符出现个数,放入CWfor(len=0; ch[len]!='\0'; len++){//遍历字符串ch[]tag=1;for(j=0; j<len; 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<=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].weight>ht[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;//权值累加}}存储：void save_HufTree(Huffman ht, LeafNode le, int ln){int i;FILE *HufTree = Fopen("HufTree.dat", "a");CreateHuffmanTree(ht, le, ln);printf("\n哈夫曼树\n");printf("编号权值parent LChild RChild\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.读取哈夫曼树至新的结构体数组void read_HufTree(Huffman ht){ //记得从1开始存储int i = 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.根据哈夫曼树生成每个叶子结点的编码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));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.保存每个叶子结点的信息void save_HufCode(Huffman ht, char *ch, HuffmanCode code_of_leaf, LeafNode leaves, int ch_len, int leaf_num){int i;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.读取每个叶子节点的信息到新的字符指针数组void read_HufCode(HuffmanCode code_of_leaf){int i=1;char c, tem[10];FILE *HufCode = Fopen("HufCode.txt", "r");while((fscanf(HufCode, "%c: %s\n", &c, tem)) == 2){int len = 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.生成所有字符的编码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;i<ch_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(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, LeafNode w, HuffmanCode hc, int n, int m){int i=0,j,p;FILE *str2 = Fopen("str2.txt", "a");printf("\n经解压得原文件中的字符串: ");while(i<m){p=2*n-1;//从父亲节点向下遍历直到叶子节点for(j=0;hc[i][j]!='\0';j++){if(hc[i][j]=='0')p=ht[p].LChild;elsep=ht[p].RChild;}printf("%c",w[p].c); /*打印原信息*/fputc(w[p].c, str2);i++;}Fclose(str2);printf("\n已将解压得到的字符串保存至str2.txt\n");}11.释放huffman编码内存void FreeHuffmanCode(HuffmanCode h1, HuffmanCode h2, HuffmanCode hc, int leaf_num, int ch_len){int i;for(i=1;i<=leaf_num;i++){//释放叶子结点的编码free(h1[i]);free(h2[i]);}for(i=0;i<ch_len;i++) //释放所有结点的编码free(hc[i]);}四、运行测试与分析及运行界面1.文件str1.txt内容：2.运行程序，读取文件3.统计叶子节点的权值4.根据权值生成哈夫曼树，保存至HufTree.dat，并用新的结构体数组读取哈夫曼树5.HufTree.dat内容6.根据哈夫曼树生成叶子节点的前缀码，保存至HufCode.txt，之后用新的结构体数组读取HufCode.txt7.HufCode.txt内容8.根据前缀码生成哈夫曼编码，保存至CodeFile.dat9.CodeFile.dat内容10．根据CodeFile.dat解压，获得原字符串，并保存至str2.txt11.str2.txt内容五、实验收获与思考通过使用哈夫曼树实现文件压缩，使我充分理解哈夫曼树的构造方法以及实际应用，巩固了课堂知识，同时认识到自己的不足。