数据结构课程设计报告哈夫曼树.doc

计算机科学学院数据结构课程设计题 目：基于哈夫曼树的文献压缩/解压程序学生姓名：林华学 号：专 业：计算机科学与技术班 级：12级（2）班 指导教师姓名及职称：陈明 讲师 起止时间： 2023 年 3 月 2023 年 4 月1 需求分析1.1课题背景及意义近年来，随着计算机技术的发展，多媒体计算机技术、计算机网络技术以及现代多媒体通信技术正在向着信息化、高速化、智能化迅速发展。各个领域的应用与发展，各个系统的数据量越来越大，给数据的存储、传输以及有效、快速获取信息带来了严重的障碍。数据压缩技术可以比较有效地解决这个问题。尚有在最近几年中兴起的物联网和云计算都是对海量的数据进行解决和传输的，假如不对数据进行压缩，那么数据传输所需的带宽规定就很高，物理成本上也随之上升。所以说数据压缩在计算机通信中占有很重要的位置，且涉及领域多，应用广泛，与我们的生活息息相关。1.2课题规定1.2.1实现一个基于哈夫曼树的文献压缩程序和文献解压程序。1.2.2.压缩程序能输入源文献进行压缩，输出压缩文献；1.2.3解压程序读入压缩文献，根据相应的哈夫曼编码解压还原 ，得到相应的源文献。1.2.4可选做：求出压缩率；打印哈夫曼树；对文献夹压缩；图形图形化窗口操作界面。1.3任务和规定1.3.1选择1时：输入一个待压缩的文本文献名称(可带途径)。如:D:1XXX.txt压缩文献名称= D:1XXX.zip1.3.2选择2时：输入一个待解压的压缩文献名称(可带途径)。如:D:1YYY.txt解压文献名称=D:1YYY.zip2概要设计2.1问题解决的思绪概述建立哈夫曼树根据哈夫曼树解码对二进制文献进行解码记录字符，得出记录出字符的权值n根据哈夫曼树编码对编码进行压缩生成哈夫曼树生成相应文献生成二进制文献 图1 主程序流程图2.2 算法思想：2.2.1输入要压缩的文献一方面运营的时候，用户主界面上有菜单提醒该如何使用软件，根据菜单提醒选择所要执行的项，依次进行，由于各个环节之间有先后顺序。第一步为输入压缩软件的名称，由键盘输入文献途径和文献名称，读入字符数组中，打开该文献，按照提醒进行压缩。若打不开，则继续输入。2.2.2读文献并计算字符频率文献将信息存放在字符数组中；计算每个字符出现的次数，申请一个结构体数组空间， 用读取的字符减去字符结束符作为下标记录字符的频率。2.2.3根据字符的频率，运用Huffman编码思想创建Huffman树将所记录的字符的频率作为权值来创建Huffman树，依次选择权值最小的两个字符作为左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符结点都成为叶子结点。2.2.4由创建的Huffman树来决定字符相应的编码，进行文献的压缩根据创建的Huffman树来拟定个字符的01编码，左孩子为0，右孩子为1。读取文献，依次将每个字符用他们的编码表达，即完毕一次编码。2.2.5解码压缩即根据Huffman树进行译码读取编码文献，依据创建的Huffman树，定义一个指针指向根结点。从根结点开始，每读一个字符，指针变化一次（当读取的字符是1时，指针指向当前所指结点的右孩子，当读取的字符是0时，指针指向当前所指结点的左孩子），直至该指针所指结点为叶子结点时结束（即当结点的左右孩子均为空时）。将当前叶子结点所代表的字符值输出到译码文献中，依次读取编码文献中的字符，按照上述方法依次进行下去直至文献2.3数据结构定义typedef struct node /哈夫曼树结构体 long w;/权重 short p,l,r; /定义双亲，左孩子，右孩子htnode,*htnp;typedef struct huffman_code unsigned char len;/记录该结点哈夫曼编码的长度 unsigned char *codestr; /记录该结点的哈夫曼编码hufcode;2.5主程序的流程及模块间关系主函数实例化huffmanTree类，并实现菜单工具栏，通过用户的选择输入，用switch语句进行分支执行huffmanTree类中功能函数：1:压缩函数 int compress(char *source_file,char *obj_file)；2:解压函数 int decompress(char *source_file,char*obj_file)；并可在完毕相应功能后安全退出，压缩或解压的文献在同文献夹下生成。3. 具体设计核心算法-huffman算法：3.1根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn,其中每棵二叉树T1中只有一个带权的 w1的根据点，其左右子树均空。3.2在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右树上根结点的权值之和。3.3在F中删除这两棵树，同时将所得到的二叉树加入F中。3.4反复3.2,3.3,直到F中只含一棵树为止。这棵树便是Huffman树。Huffman树可用于构造代码总长度最短的编码方案。为了具体说明这个问题，特以下面例子来说明: 图2 问题详解编码完毕之后，开始对源文献进行压缩。1. 从源文献读一个字符，从叶子结点中找出和此字符相同的字符结点，将其编码写入一个临时字符组codes；2. 当codes的长度大于等于8时，将其前8位转换成字符写入目的文献中；3. 反复1和2此过程，直至读完源文献中的所有字符；4. 若codes最后尚有剩余的局限性8位的01代码，则将其低位补0至8位，再写入目的文献。 主程序模块: 图 3 主程序模块4. 调试分析报告由于压缩与解压过程中没有输入新生成文献的途径，因此解压后的文献会将原文献覆盖。如图： 图4 压缩前原文献 图 5 压缩后生成文献 图 6 解压后文献5.用户使用说明在运营程序之前，一方面在D盘先建立一个待压缩的文献1.doc，运营程序如下图所示。 图7 版本测试结果图压缩：在命令行下输入1对文献进行压缩，根据提醒输入刚刚建的文本文献（1.doc），和要生成的压缩文献名称，按回车确认进行压缩。 图 8 执行压缩操作图成功执行完毕后如下图所示。 图 9 执行压缩操作图选择打印哈夫曼树及编码。 图10 执行打印操作图解压：在命令行下输入2对本程序压缩的文献进行恢复，根据提醒输入待恢复的文献名称和恢复后的文献名称，按回车拟定，成功执行后如下图所示。 图11 执行解压操作图6.测试结果具体测试结果请参见 5 使用功能。6.1测试报告原文献压缩后解压后1txt文献(14598b)8192b8192b2pdf文献(359398b)356352b359398b3jpg文献(31455b)28672b31455b4Mp3文献(72023b)69632b72023b参考文献1郑莉等编著C+语言程序设计（第三版）北京：清华大学出版社.2谭浩强 .C+面向对象程序设计(第二版) M.北京：中国铁道出版社，2023.3洪国胜等编著C+Builder程序设计轻松上手北京：清华大学出版社.4胡学钢等数据结构算法设计指导北京：清华大学出版社，1999年第1版.5王昆仑等编著数据结构域算法（高等学校计算机精品课程系列教材）中国铁道工业出版社.附录：源程序#include #include #include #include typedef struct node /哈夫曼树结构体 long w;/权重 short p,l,r; /定义双亲，左孩子，右孩子htnode,*htnp;typedef struct huffman_code unsigned char len;/记录该结点哈夫曼编码的长度 unsigned char *codestr; /记录该结点的哈夫曼编码hufcode;typedef char *huffmancode;int initial_files(char *source_file,FILE *inp,char *obj_file,FILE *outp);/文献初始信息char *create_file(char *source_file,char* obj_file);/创建待压缩文献名int compress(char *source_file,char *obj_file);/压缩函数long frequency_data(FILE *in,long fre);/计算字符频率int search_set(htnp ht,int n,int *s1, int *s2);/查找文献int create_hftree(long w,int n,htnode ht);/创建哈夫曼树int encode_hftree(htnp htp,int n,hufcode hc);/记录哈夫曼编码unsigned char chars_to_bits(const unsigned char chars8);/计算文献大小int write_compress_file(FILE *in,FILE *out,htnp ht,hufcode hc,char* source_file,long source_filesize);/输入待压缩文献途径int decompress(char *source_file,char *obj_file);/解压函数void get_mini_huffmantree(FILE* in,short mini_ht2);/建立哈弗曼树中用于选择最小权值结点的函数int write_decompress_file(FILE *in,FILE* out,short mini_ht2,long bits_pos,long obj_filesize);/输入待解压文献途径int d_initial_files(char *source_file,FILE *inp,char *obj_file,FILE *outp);main()int s;char file10;system(color 3F);printf( *n);printf( * 菜单： *n);printf( * 1.-压缩- *n);printf( * 2.-解压- *n);printf( * 0.-退出- *n);printf( *n);scanf(%d,&s);while(s!=0)getchar();switch(s)case 1:puts(请输入待压缩文献途径：);gets(file);compress(file,NULL);break;case 2:puts(请输入待解压文献途径：);gets(file);decompress(file,NULL);break;default : printf(指令错误！请重新输入指令：n);puts( );printf( *n);printf( * 菜单： *n);printf( * 1.-压缩- *n);printf( * 2.-解压- *n);printf( * 0.-退出- *n);printf( *n);scanf(%d,&s);/文献初始信息int initial_files(char *source_file,FILE *inp,char *obj_file,FILE *outp) if(fopen(source_file,rb)=NULL) return -1; if(obj_file=NULL) if(obj_file=(char*)malloc(256*sizeof(char)=NULL) return -1; create_file(source_file,obj_file); if(strcmp(source_file,obj_file)=0) return -1; printf(待压缩文献:%s,压缩文献:%sn,source_file,obj_file); if(*outp=fopen(obj_file,wb)=NULL) return -1; if(*inp=fopen(source_file,rb)=NULL) return -1; free(obj_file); return 0; /创建待压缩文献名char *create_file(char *source_file,char* obj_file) char *temp; if(temp=strrchr(source_file,.)=NULL) strcpy(obj_file,source_file); strcat(obj_file,.zip); else strncpy(obj_file,source_file,temp-source_file); obj_filetemp-source_file=0; strcat(obj_file,.zip); return obj_file;/压缩函数int compress(char *source_file,char *obj_file) FILE *in,*out;char ch; int error_code,i,j; float compress_rate; hufcode hc256; /编码的位数最多为256位 htnode ht256*2-1; long frequency256,source_filesize,obj_filesize=0; error_code=initial_files(source_file,&in,obj_file,&out); if(error_code!=0) puts(文献打开失败！请重新输入文献途径：); return error_code; source_filesize=frequency_data(in,frequency); printf(文献大小 %ld 字节n,source_filesize); error_code=create_hftree(frequency,256,ht); if(error_code!=0) puts(建立哈夫曼树失败！); return error_code; error_code=encode_hftree(ht,256,hc); if(error_code!=0) puts(建立哈夫曼编码失败！); return error_code; for(i=0;i256;i+) obj_filesize+=frequencyi*hci.len; obj_filesize=obj_filesize%8=0?obj_filesize/8:obj_filesize/8+1; for(i=0;i256-1;i+) obj_filesize+=2*sizeof(short); obj_filesize+=strlen(source_file)+1; obj_filesize+=sizeof(long); obj_filesize+=sizeof(unsigned int); compress_rate=(float)obj_filesize/source_filesize; printf(压缩文献大小:%ld字节,压缩比例:%.2lf%n,obj_filesize,compress_rate*100); error_code=write_compress_file(in,out,ht,hc,source_file,source_filesize); if(error_code!=0) puts(写入文献失败！); return error_code; puts(压缩完毕!); puts( );puts(是否打印该文献中字符相应的huffman树及编码？);puts( Please input Y OR N);doscanf(%s,&ch);switch(ch)case Y: puts(以下是哈夫曼树：);for(i=256;i0)printf(%-10d%-10d%-10d%-10d%-10dn,i,hti.w,hti.p,hti.l,hti.r);puts(以下是哈夫曼编码：);for(i=0;i256;i+)if(frequencyi=0)i+;elseprintf(%dt,frequencyi);for(j=0;jhci.len;j+)printf( %d,hci.codestrj);printf(n);break;case N:break;default : printf(指令错误！请重新输入指令：n);while(ch!=Y&ch!=N); fclose(in); fclose(out); for(i=0;i256;i+) free(hci.codestr); return 0; /计算字符频率long frequency_data(FILE *in,long frequency) int i,read_len; unsigned char buf256; long filesize; for(i=0;i256;i+) /去掉权值为0的结点 frequencyi=0; fseek(in,0L,SEEK_SET); read_len=256; while(read_len=256) read_len=fread(buf,1,256,in); for(i=0;iread_len;i+) /初始化根结点 frequency*(buf+i)+; for(i=0,filesize=0;i256;i+) filesize+=frequencyi; return filesize; int search_set(htnp ht,int n,int *s1, int *s2) int i,x; long minValue = 999999,min = 0; for(x=0;xn;x+) if(htx.p=-1) break; for(i=0;in;i+) if(hti.p=-1 & hti.w minValue) minValue = hti.w; min=i; *s1 = min; minValue = 999999,min = 0; for(i=0;in;i+) if(hti.p=-1 & hti.w minValue & i != *s1) minValue = hti.w; min=i; *s2 = min; return 1; /创建哈夫曼树int create_hftree(long w,int n,htnode ht) int m,i,s1,s2; if (n1) return -1; m=2*n-1; if (ht=NULL) return -1; for(i=0;in;i+) hti.w=wi;hti.p=hti.l=hti.r=-1; for(;im;i+) hti.w=hti.p=hti.l=hti.r=-1; for(i=n;im;i+) search_set(ht,i,&s1,&s2); hts1.p = hts2.p = i; hti.l = s1;hti.r = s2; hti.w = hts1.w + hts2.w; return 0; int encode_hftree(htnp htp,int n,hufcode hc) int i,j,p,codelen; unsigned char *code=(unsigned char*)malloc(n*sizeof(unsigned char); if (code=NULL) return -1; for(i=0;in;i+) for(p=i,codelen=0;p!=2*n-2;p=htpp.p,codelen+) codecodelen=(htphtpp.p.l=p?0:1); if(hci.codestr=(unsigned char *)malloc(codelen)*sizeof(unsigned char)=NULL) return -1; hci.len=codelen; for(j=0;jcodelen;j+) hci.codestrj=codecodelen-j-1; free(code); return 0; unsigned char chars_to_bits(const unsigned char chars8) int i; unsigned char bits=0; bits|=chars0; for(i=1;i8;+i) bits=1; bits|=charsi; return bits; int write_compress_file(FILE *in,FILE *out,htnp ht,hufcode hc,char* source_file,long source_filesize) unsigned int i,read_counter,write_counter,zip_head=0xFFFFFFFF; unsigned char write_char_counter,code_char_counter,copy_char_counter, read_buf256,write_buf256,write_chars8,file_size=strlen(source_file); hufcode *cur_hufcode; fseek(in,0L,SEEK_SET); fseek(out,0L,SEEK_SET); fwrite(&zip_head,sizeof(unsigned int),1,out); fwrite(&file_size,sizeof(unsigned char),1,out); fwrite(source_file,sizeof(char),file_size,out); fwrite(&source_filesize,sizeof(long),1,out); for(i=256;i256*2-1;i+) fwrite(&(hti.l),sizeof(hti.l),1,out); fwrite(&(hti.r),sizeof(hti.r),1,out); write_counter=write_char_counter=0; read_counter=256; while(read_counter=256) read_counter=fread(read_buf,1,256,in); for(i=0;ilen) copy_char_counter= (8-write_char_counter cur_hufcode-len-code_char_counter ? cur_hufcode-len-code_char_counter : 8-write_char_counter); memcpy(write_chars+write_char_counter,cur_hufcode-codestr+code_char_counter,copy_char_counter); write_char_counter+=copy_char_counter; code_char_counter+=copy_char_counter; if(write_char_counter=8) write_char_counter=0; write_bufwrite_counter+=chars_to_bits(write_chars); if(write_counter=256) fwrite(write_buf,1,256,out); write_counter=0; fwrite(write_buf,1,write_counter,out); if(write_char_counter!=0) write_char_counter=chars_to_bits(write_chars); fwrite(&write_char_counter,1,1,out); return 0; /建立哈弗曼树中用于选择最小权值结点的函数void get_mini_huffmantree(FILE* in,short mini_ht2) int i; for(i=0;i256;i+) mini_hti0=mini_hti1=-1; fread(mini_hti,sizeof(short),2*(256-1),in); int write_decompress_file(FILE *in,FILE* out,short mini_ht2,long bits_pos,long obj_filesize) long