数据结构课程设计报告哈夫曼树.doc
《数据结构课程设计报告哈夫曼树.doc》由会员分享,可在线阅读,更多相关《数据结构课程设计报告哈夫曼树.doc(35页珍藏版)》请在咨信网上搜索。
1、计算机科学学院数据结构课程设计题 目:基于哈夫曼树的文献压缩/解压程序学生姓名:林华学 号:专 业:计算机科学与技术班 级:12级(2)班 指导教师姓名及职称:陈明 讲师 起止时间: 2023 年 3 月 2023 年 4 月1 需求分析1.1课题背景及意义近年来,随着计算机技术的发展,多媒体计算机技术、计算机网络技术以及现代多媒体通信技术正在向着信息化、高速化、智能化迅速发展。各个领域的应用与发展,各个系统的数据量越来越大,给数据的存储、传输以及有效、快速获取信息带来了严重的障碍。数据压缩技术可以比较有效地解决这个问题。尚有在最近几年中兴起的物联网和云计算都是对海量的数据进行解决和传输的,假
2、如不对数据进行压缩,那么数据传输所需的带宽规定就很高,物理成本上也随之上升。所以说数据压缩在计算机通信中占有很重要的位置,且涉及领域多,应用广泛,与我们的生活息息相关。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.zip
3、1.3.2选择2时:输入一个待解压的压缩文献名称(可带途径)。如:D:1YYY.txt解压文献名称=D:1YYY.zip2概要设计2.1问题解决的思绪概述建立哈夫曼树根据哈夫曼树解码对二进制文献进行解码记录字符,得出记录出字符的权值n根据哈夫曼树编码对编码进行压缩生成哈夫曼树生成相应文献生成二进制文献 图1 主程序流程图2.2 算法思想:2.2.1输入要压缩的文献一方面运营的时候,用户主界面上有菜单提醒该如何使用软件,根据菜单提醒选择所要执行的项,依次进行,由于各个环节之间有先后顺序。第一步为输入压缩软件的名称,由键盘输入文献途径和文献名称,读入字符数组中,打开该文献,按照提醒进行压缩。若打不
4、开,则继续输入。2.2.2读文献并计算字符频率文献将信息存放在字符数组中;计算每个字符出现的次数,申请一个结构体数组空间, 用读取的字符减去字符结束符作为下标记录字符的频率。2.2.3根据字符的频率,运用Huffman编码思想创建Huffman树将所记录的字符的频率作为权值来创建Huffman树,依次选择权值最小的两个字符作为左右孩子,其和作为父结点的权值,依次进行下去,直到所有的字符结点都成为叶子结点。2.2.4由创建的Huffman树来决定字符相应的编码,进行文献的压缩根据创建的Huffman树来拟定个字符的01编码,左孩子为0,右孩子为1。读取文献,依次将每个字符用他们的编码表达,即完毕
5、一次编码。2.2.5解码压缩即根据Huffman树进行译码读取编码文献,依据创建的Huffman树,定义一个指针指向根结点。从根结点开始,每读一个字符,指针变化一次(当读取的字符是1时,指针指向当前所指结点的右孩子,当读取的字符是0时,指针指向当前所指结点的左孩子),直至该指针所指结点为叶子结点时结束(即当结点的左右孩子均为空时)。将当前叶子结点所代表的字符值输出到译码文献中,依次读取编码文献中的字符,按照上述方法依次进行下去直至文献2.3数据结构定义typedef struct node /哈夫曼树结构体 long w;/权重 short p,l,r; /定义双亲,左孩子,右孩子htnode
6、,*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
7、_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树可用于构造代码总长度最短的编码方案。为了具体说明这
8、个问题,特以下面例子来说明: 图2 问题详解编码完毕之后,开始对源文献进行压缩。1. 从源文献读一个字符,从叶子结点中找出和此字符相同的字符结点,将其编码写入一个临时字符组codes;2. 当codes的长度大于等于8时,将其前8位转换成字符写入目的文献中;3. 反复1和2此过程,直至读完源文献中的所有字符;4. 若codes最后尚有剩余的局限性8位的01代码,则将其低位补0至8位,再写入目的文献。 主程序模块: 图 3 主程序模块4. 调试分析报告由于压缩与解压过程中没有输入新生成文献的途径,因此解压后的文献会将原文献覆盖。如图: 图4 压缩前原文献 图 5 压缩后生成文献 图 6 解压后文
9、献5.用户使用说明在运营程序之前,一方面在D盘先建立一个待压缩的文献1.doc,运营程序如下图所示。 图7 版本测试结果图压缩:在命令行下输入1对文献进行压缩,根据提醒输入刚刚建的文本文献(1.doc),和要生成的压缩文献名称,按回车确认进行压缩。 图 8 执行压缩操作图成功执行完毕后如下图所示。 图 9 执行压缩操作图选择打印哈夫曼树及编码。 图10 执行打印操作图解压:在命令行下输入2对本程序压缩的文献进行恢复,根据提醒输入待恢复的文献名称和恢复后的文献名称,按回车拟定,成功执行后如下图所示。 图11 执行解压操作图6.测试结果具体测试结果请参见 5 使用功能。6.1测试报告原文献压缩后解
10、压后1txt文献(14598b)8192b8192b2pdf文献(359398b)356352b359398b3jpg文献(31455b)28672b31455b4Mp3文献(72023b)69632b72023b参考文献1郑莉等编著C+语言程序设计(第三版)北京:清华大学出版社.2谭浩强 .C+面向对象程序设计(第二版) M.北京:中国铁道出版社,2023.3洪国胜等编著C+Builder程序设计轻松上手北京:清华大学出版社.4胡学钢等数据结构算法设计指导北京:清华大学出版社,1999年第1版.5王昆仑等编著数据结构域算法(高等学校计算机精品课程系列教材)中国铁道工业出版社.附录:源程序#i
11、nclude #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_
12、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_hftre
13、e(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
14、,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.-
15、压缩- *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
16、);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_fil
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 报告 哈夫曼树
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。