《赫夫曼编码及译码器设计文档》由会员分享,可在线阅读,更多相关《赫夫曼编码及译码器设计文档(32页珍藏版)》请在金锄头文库上搜索。
1、滁州学院课程设计报告课程名称:数据结构设计题目 :赫夫曼编码与解码器系 另计算机科学与技术专 业:计算机科学与技术组 别:第二组起止日期:11年5月25日 11年6月10日指导教师:胡成祥计算机科学与技术系二OO九年制课程设计题目赫夫曼编码和解码组长陆伟学号2010211108班级 计科(2)班系别计算机系专业计算机科学与技术组员李梦 2010211102林川 2010211105彭祥 2010211112马岩 2010211109指导教师胡成祥课程设计目的设计一个赫夫曼编码和解码程序课程设计所需环境Microsoft Visual C+6.0课程设计任务要求通过设计的程序对指定的文件进行编码
2、和解码课程设计工作进度计划序号起止日期工作内容分工情况5-255-27商讨问题的解决路径和初 步实施方案。本小组组员根据个人所学情况,对问题 认真分析,想出自己特色的实施方案, 为下次会议的方案选择做准备。5-286-6针对问题提出自己的见解, 并根据实际情况采取行动。林川、李梦编写赫夫曼树的生成及初始 化;马岩编写编码;彭祥编写界面和主 函数;陆伟编写译码以及负责最后的程 序代码的综合和检查修补。6-76-10完成文档的编写并对个人 工作进行分析,发表自己的 见解。林川、李梦:需求分析;马岩:概要设 计及调试操作;彭祥:目录和总结、体 会;陆伟:需求分析和致谢、参考文献。指导教师签字:年月日
3、教研室审核意见:教研室主任签字:年月日目录1 引言 4.1.1 课程设计目的 4.1.2 课程设计背景 4.1.3 课程设计主要内容 52. 需求分析 52.1 课程设计题目 5.2.2 课程设计任务 5.2.3 要求 62.4 课程设计思想 6.2.5 软硬件运行环境 62.6 开发工具 63. 概要设计 63.1 课程设计的流程图 63.2 主要的数据结构 73.3 完成本课程设计所用方法及其原理 84 详细设计 85 调试与操作说明 215.1 首先进行初始化操作 215.2 译码、编码等操作实现 225.2.1 译码操作 225.2.2 编码操作 235.2.3 退出程序的运行操作 2
4、46课程设计总结与体会 257致谢 2. 68参考文献 2. 69附录 2. 71 引言当今社会,计算机技术和通信技术已经不断发展, 处理和传输的数据量越来 越庞大。如何采用有效的数据压缩技术引起了人们的极大重视。 从而产生了赫夫 曼编码,它是一种应用广泛且非常有效的数据压缩技术, 该技术一般可将数据压 缩 20%至 90%,通常我们将压缩技术称为编码,将解压过程称为解码。树状结构简称为数, 是一种以分支关系进行定义的层次结构, 是十分重要的 非线性数据结构,在计算机软件设计方面,有着广泛的应用。1.1 课程设计目的本课程设计是为了让同学们了解学习数据结构的作用和意义。数据结构是计算机科学 与
5、技术专业的专业基础课, 是十分重要的课程。 所有的计算机系统软件和应用软件都要用到 各种类型的数据结构。 因此, 想要更好地运用计算机来解决实际问题, 仅仅掌握几门计算机 程序设计语言是远远难以应付当前众多复杂的课题, 想要有效地使用计算机, 充分发挥它的 性能, 还必须学习和掌握好数据结构的有关知识, 打好数据结构这门课的扎实基础, 对于学 习计算机专业其它的课程,如操作系统、软件工程、编译原理、数据库、人工智能等十分有、益。1.2 课程设计背景当今社会,计算机技术和通信技术已经不断发展, 处理和传输的数据量越来 越庞大。如何采用有效的数据压缩技术引起了人们的极大重视。 从而产生了赫夫 曼编
6、码,它是一种应用广泛且非常有效的数据压缩技术, 该技术一般可将数据压 缩 20%至 90%,通常我们将压缩技术称为编码,将解压过程称为解码。树状结构简称为数, 是一种以分支关系进行定义的层次结构, 是十分重要的 非线性数据结构,在计算机软件设计方面,有着广泛的应用。在这个信息量发达的时代, 随着社会的进步, 信息不断地增多和更新, 为了使信息更加 快速、准确有效的传输,那就需要一个编码和解码的程序来完成。1.3 课程设计主要内容本课程设计要求完成发送端对待传送数据的编码和接收端对传送来的数据的译码。 要实 现五个功能:接收原始数据、编码、译码、将编码和译码存档。通过系统的提示建立赫夫曼 树并对
7、载入的原文件进行编码, 并保存到指定的文件中, 同时输出到屏幕。 另一方面, 对原 文件进行译码, 并将译码的结果保存到指定的文件中, 同时输到屏幕。 对于编码和译码的操 作中的文件导入,分为键盘输入和文件输入两种。2. 需求分析2.1 课程设计题目赫夫曼编 /译码器。2.2 课程设计任务设计一个赫夫曼编码和解码程序。2.3 要求根据赫夫曼编码和解码算法,将指定的文件中的赫夫曼编码进行译码,并输出到文件中,还要实现对文件中支付的编码,并输出编码到文件中。2.4 课程设计思想输入字符的和字符出现的频率,并将字符作为叶子节点,频率作为节点权值建立哈夫曼树, 再根据在哈夫曼树中, 由叶子结点逐步走到
8、根节点的路径对叶子节点进行编码,码时,从根节点找到叶子节点完成译码过程。2.5 软硬件运行环境Microsoft Windows XP 版本 2002 Service Pack 3或Microsoft Windows 7 旗舰版2.6 开发工具Microsoft Visual C+6.03. 概要设计3.1 课程设计的流程图课程设计中算法的函数模块生成哈夫曼树 void haffman(int weight,char ch,int n,HafNode haffTree)void Haffma nCode (HafNode haffTree, int n,HCode haffCode)务始化操作
9、,、生成哈夫曼树及哈夫曼编码VoidIn it( int weighty char ch)Void哈夫曼编码的函数,用于将文件编码Bia n_ ma()哈夫曼译码过 程的函数,用 于将文件译码void Yi_ma()界面设计void print()3.2主要的数据结构#define M 100#define MAX 10000typedef struct int weight;int flag;int pare nt; char ch;int lchild;int rchild; HafNode; typedef structint bitM;int start;int weight;char
10、 ch;HCode;typedef structchar bitM;char ch;int weight;Coding;译码3.3 完成本课程设计所用方法及其原理 输入字符的和字符出现的频率,并将字符作为叶子节点,频率作为节点权值建立哈夫 曼树, 再根据在哈夫曼树中, 由叶子结点逐步走到根节点的路径对叶子节点进行编码, 时,从根节点找到叶子节点完成译码过程。4 详细设计程序源代码:#include #include #include #define M 100#define MAX 10000typedef structint weight;int flag;int parent;char c
11、h;int lchild;int rchild;HafNode;typedef structint bitM;int start;int weight;char ch;HCode;typedef structchar bitM;char ch;int weight;Coding;void haffman(int weight,char ch,int n,HafNode haffTree)int i,j,m1,m2,x1,x2;for (i=0;i2*n-1;i+)if(in)haffTreei.weight=weighti;haffTreei.ch=chi;elsehaffTreei.weig
12、ht=0;haffTreei.parent=-1;haffTreei.flag=0;haffTreei.lchild=-1;haffTreei.rchild=-1;for (i=0;in-1;i+)m1=m2=MAX;x1=x2=0;for (j=0;jn+i;j+)if (haffTreej.weightm1&haffTreej.flag=0)m2=m1;x2=x1;m1=haffTreej.weight;x1=j;else if(haffTreej.weightm2 & haffTreej.flag=0) m2=haffTreej.weight;x2=j;haffTreex1.parent
13、= n + i;haffTreex2.parent = n + i;haffTreex1.flag = 1;haffTreex2.flag = 1;haffTreen+i.weight = haffTreex1.weight + haffTreex2.weight;haffTreen+i.lchild = x1;haffTreen+i.rchild = x2;FILE *fp;fp=fopen(huffman.txt,w+);printf(%dn,n);fprintf(fp,%dn,n);for (i=0;in;i+)fprintf(fp,%c %d %d%dn,haffTreei.ch,ha
14、ffTreei.parent,haffTreei.lchild,haffTreei.rchild);for (i=n;i2*n-1;i+)fprintf(fp,% %d %dn,haffTreei.parent,haffTreei.lchild,haffTreei.rchild);fclose(fp);void HaffmanCode (HafNode haffTree,int n,HCode haffCode) HCode *cd=( HCode *) malloc (sizeof (HCode); int i,j,child,parent;for (i=0; istart=n-1;cd-weight=haffTreei.weight; cd-ch=haffTreei.c