数据结构哈夫曼编码译码器课程设计报告
- 格式:doc
- 大小:277.97 KB
- 文档页数:28
《数据结构》课程设计实验报告题目哈夫曼编码/译码器学院数理与信息学院专业计算机科学与技术班级计科132学生姓名刘海澍 5周弘杰8徐铭瑶 3指导教师编写日期数据结构课程设计目录1 问题描述.................................................................错误!未定义书签。
2 问题分析.................................................................错误!未定义书签。
3 算法设计 (2)3.1抽象数据类型定义 (2)3.2模块划分 (3)4 详细设计 (4)4.1数据类型的定义 (4)4.2主要模块的算法描述 (4)4.3 流程图 (6)5 测试分析 (9)6 课程设计总结 (10)7 成员分工 (10)参考文献 (11)附录(源程序清单) (12)1.问题描述设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止。
1) 初始化:键盘输入字符集大小n、n个字符和n个权值,建立哈夫曼树;2) 编码:利用建好的哈夫曼树生成哈夫曼编码;3) 输出编码;4)显示哈夫曼树;5)界面设计的优化;6) 设字符集及频度如下表:字符空格 A B C D E F频度4 9 23 2 17 15字符G H I J K频度1 2 3 3 42.问题分析(1)定义一个变量名为HTNode的结构体,用该结构体中的char data、int weight、int parent、int lchild、int rchild分别表示哈夫曼树中每个结点的权值、权重、双亲结点、左孩子、右孩子,再定义一个HTNode类型的数组ht[60]存放哈夫曼树;另外定义一个变量名为HCode的结构体,采用HCode类型变量的cd[start]~cd[n]存放当前结点的哈夫曼编码、最后定义一个HCode类型的数组hcd[30]的数组用于存放当前叶子结点ht[i]的哈夫曼编码。
哈夫曼编码与译码器-数据结构课程设计报告以下是为大家整理的哈夫曼编码与译码器-数据结构课程设计报告的相关范文,本文关键词为哈夫曼,编码,译码器,数据结构,课程,设计,报告,沈阳,航空,您可以从右上方搜索框检索更多相关文章,如果您觉得有用,请继续关注我们并推荐给您的好友,您可以在教育文库中查看更多范文。
沈阳航空航天大学课程设计报告课程设计名称:数据结构课程设计课程设计题目:实现哈夫曼编码和译码器院(系):计算机学院专业:计算机科学与技术班级:24010102学号:20XX040101082姓名:尹伟和指导教师:徐蕾沈阳航空航天大学课程设计报告此页为任务书I沈阳航空航天大学课程设计报告目录1.题目分析................................................................................................................. ..11.1.题目重述............................................................................................................11.1.1.系统功能需求分析.....................................................................................12.程序设计...................................................................................................................22.1.系统功能模块说明............................................................................................22.1.1.系统功能模块结构.....................................................................................22.1.2.系统模块功能说明.....................................................................................32.2.数据结构说明....................................................................................................32.2.1.结构体定义说明.........................................................................................32.2.2.哈夫曼树.....................................................................................................42.2.3.字符-哈夫曼编码对照表............................................................................42.3.函数说明............................................................................................................43.算法描述................................................................................................................. ..63.1.3.2.3.3.3.4.哈夫曼树的构建................................................................................................6字符-哈夫曼编码对照表...................................................................................6编码................................................................................................................. ...6译码....................................................................................................................74.程序测试................................................................................................................. ..94.1.字符集输入........................................................................................................94.2.编码测试..........................................................................................................104.3.译码测试 (11)参考文献................................................................................................................. .......13附录(程序清单).. (14)II沈阳航空航天大学课程设计报告1.题目分析1.1.题目重述本次课程设计的目标是实现一个哈夫曼编码和译码器。
目录目⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ (2)1 程的目的和意⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯32 需求分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯43 概要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯4 4⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.85 分析和果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.11 6⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯127致⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯138附⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯13参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..201课程设计目的与意义在当今信息爆炸时代,如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。
哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。
哈夫曼编码的应用很广泛,利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。
树中从根到每个叶子都有一条路径,对路径上的各分支约定:指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“ 1”的序列作为和各个对应的字符的编码,这就是哈夫曼编码。
通常我们把数据压缩的过程称为编码,解压缩的过程称为解码。
电报通信是传递文字的二进制码形式的字符串。
但在信息传递时,总希望总长度尽可能最短,即采用最短码。
作为计算机专业的学生,我们应该很好的掌握这门技术。
在课堂上,我们能过学到许多的理论知识,但我们很少有过自己动手实践的机会!课程设计就是为解决这个问题提供了一个平台。
在课程设计过程中,我们每个人选择一个课题,认真研究,根据课堂讲授内容,借助书本,自己动手实践。
这样不但有助于我们消化课堂所讲解的内容,还可以增强我们的独立思考能力和动手能力;通过编写实验代码和调试运行,我们可以逐步积累调试 C 程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。
XXX学院本科数据结构课程设计总结报告设计题目:实验一、哈夫曼编/译码器学生姓名:XXX系别:XXX专业:XXX班级:XXX学号:XXX指导教师:XXX XXX2012年6 月21日xxx学院课程设计任务书题目一、赫夫曼编译码器专业、班级xxx学号xxx 姓名xxx主要内容、基本要求、主要参考资料等:1. 主要内容利用哈夫曼编码进行信息通信可大大提高信道利用率,缩短信息传输时间,降低传输成本。
要求在发送端通过一个编码系统对待传数据预先编码;在接收端将传来的数据进行译码(复原)。
对于双工信道(既可以双向传输信息的信道),每端都需要一个完整的编/译码系统。
试为这样的信息收发站写一个哈夫曼的编/译码系统。
2. 基本要求系统应具有以下功能:(1)C:编码(Coding)。
对文件tobetrans中的正文进行编码,然后将结果存入文件codefile中,将以此建好的哈夫曼树存入文件HuffmanTree中(2)D:解码(Decoding)。
利用已建好的哈夫曼树将文件codefile中的代码进行译码,结果存入textfile中。
(3)P:打印代码文件(Print)。
将文件codefile以紧凑格式显示在终端上,每行50个代码。
同时将此字符形式的编码文件写入文件codeprint中。
(4)T:打印哈夫曼树(Tree Printing)。
将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件treeprint中。
3. 参考资料:数据结构(C语言版)严蔚敏、吴伟民编著;数据结构标准教程胡超、闫宝玉编著完成期限:2012年6月21 日指导教师签名:课程负责人签名:2012年 6月 21 日一、设计题目(任选其一)实验一、哈夫曼编/译码器二、实验目的1巩固和加深对数据结构的理解,提高综合运用本课程所学知识的能力;2 深化对算法课程中基本概念、理论和方法的理解;3 巩固构造赫夫曼树的算法;4 设计试验用程序实验赫夫曼树的构造。
哈夫曼编码译码课程设计报告《数据结构》课程设计——赫夫曼编码/译码器设计指导教师:李文书、周维达班级:10电信实验班学号:Q10600132姓名:王彬彬一、实验目的1、提高分析问题、解决问题的能力,进一步巩固数据结构各种原理与方法。
2、熟悉掌握一门计算机语言,能够进行数据算法设计。
二、实验原理哈夫曼编\译码器的主要功能是先建立哈夫曼树,然后利用建好的哈夫曼树生成哈夫曼编码后进行译码。
在数据通信中,经常需要将传送的文字转换成由二进制字符0、1组成的二进制串,称之为编码。
构造一棵哈夫曼树,规定哈夫曼树中的左分之代表0,右分支代表1,则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码,称之为哈夫曼编码。
最简单的二进制编码方式是等长编码。
若采用不等长编码,让出现频率高的字符具有较短的编码,让出现频率低的字符具有较长的编码,这样可能缩短传送电文的总长度。
哈夫曼树课用于构造使电文的编码总长最短的编码方案。
主要流程图如下:三、实验步骤1:写好流程图,设计实验方案。
2:初始化,从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件HuofumanTree中。
3:编码。
利用已建好的哈夫曼树,对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。
4:译码。
利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件Textfile中。
5:印代码文件(Print).将文件CodeFile以紧凑格式显示在终端上,每行50个代码。
同时将此字符形式的编码文件写入文件CodePrint中。
6:印哈夫曼树(Treeprinting).将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint 中。
具体函数如下:1:Initialization() 初始化2:Encoding() 编码3:Decoding() 译码4:Print_file() 打印代码文件5:search(k,j,p) 搜索二叉树6:Print_tree() 打印二叉树7:menu() 主菜单9:main() 主函数四、实验结果与分析(1)大致个人测试案例:主界面:。
数据结构课程设计信息科学与工程学院:学院计算机科学与技术专业:1601 计卓级:班号:学:学生姓名指导教师:23/ 1年月日题目名称一、实验内容哈夫曼编码译码系统【问题描述】用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。
但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。
对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。
试为这样的信息收发站写一个哈夫曼码的编/译码系统。
【基本要求】1)初始化。
从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树。
2)编码。
利用已建好的哈夫曼树对输入英文进行编码,编码结果存储在数组中。
3)译码。
利用已建好的哈夫曼树将数组中的代码进行译码,结果存入一个字符数组。
4)输出编码。
将编码结果显示在终端上,每行50个代码。
5)输出哈夫曼树。
将哈夫曼树以直观的方式(树或凹入表形式)显示出来。
【实现提示】用户界面可以设计为“菜单”方式,再加上一个“退出”功能。
请用户键入一个选择功能符。
此功能执行完毕后再显示此菜单,直至某次用户选择了“退出”为止。
参考教材P240-246【选做内容】将哈夫曼树保存到文件中,编码和译码的结果也分别存放在两个文本文件中。
23/ 2二、数据结构设计储存结构struct HNodeType {//字符结构体类型int weight;//权int parent;//双亲位置int lchild;//左孩子int rchild;//右孩子char inf;// 字符};struct HcodeType {存储编码int bit[MaxBit];// int start;// 起始位置};三、算法设计1、在构造哈夫曼树时,设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息,根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点,所以数组HuffNode的大小设置为2n-1。
数据结构课程设计报告题目:哈夫曼编/译码器院(系):计算机工程学院专业:信息与计算科学班级:0902学生:陈辉指导教师:2010年12月目录1实验目的 (2)2概要设计 (2)2.1 总体功能结构 (2)2.2 数据结构设计 (4)2.3 方法及原理 (5)3详细设计和实现 (6)3.1 创建Huffman树 (6)3.2 编码 (9)3.3 译码 (11)4调试与操作说明 (13)总结 (14)1实验目的设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止。
【基本要求】(1)初始化:键盘输入字符集大小n、n个字符和n个权值,建立哈夫曼树;(2)编码:利用建好的哈夫曼树生成哈夫曼编码;(3)输出编码;(4)译码功能;(5)设字符集及频度如下表:字符空格 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1通过此次课程设计主要达到以下目的:1.了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力;2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力;4.训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的工作方法和作风。
本程序采用Visual C++编程实现。
2概要设计2.1 总体功能结构本程序的主要功能是实现对用户输入的字符编码,然后再把编码结果翻译成原字符。
但在进行这些操作之前必须做一项工作,就是创建Huffman树。
哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。
所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。
XXX学院本科数据结构课程设计总结报告设计题目:实验一、哈夫曼编/译码器学生:XXX系别:XXX专业:XXX班级:XXX学号:XXX指导教师:XXX XXX2012年6 月21日xxx学院课程设计任务书题目一、赫夫曼编译码器专业、班级xxx学号xxx xxx主要容、基本要求、主要参考资料等:1. 主要容利用哈夫曼编码进行信息通信可大大提高信道利用率,缩短信息传输时间,降低传输成本。
要求在发送端通过一个编码系统对待传数据预先编码;在接收端将传来的数据进行译码(复原)。
对于双工信道(既可以双向传输信息的信道),每端都需要一个完整的编/译码系统。
试为这样的信息收发站写一个哈夫曼的编/译码系统。
2. 基本要求系统应具有以下功能:(1)C:编码(Coding)。
对文件tobetrans中的正文进行编码,然后将结果存入文件codefile中,将以此建好的哈夫曼树存入文件HuffmanTree中(2)D:解码(Decoding)。
利用已建好的哈夫曼树将文件codefile中的代码进行译码,结果存入textfile中。
(3)P:打印代码文件(Print)。
将文件codefile以紧凑格式显示在终端上,每行50个代码。
同时将此字符形式的编码文件写入文件codeprint中。
(4)T:打印哈夫曼树(Tree Printing)。
将已在存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件treeprint中。
3. 参考资料:数据结构(C语言版)严蔚敏、吴伟民编著;数据结构标准教程胡超、闫宝玉编著完成期限:2012年6月21 日指导教师签名:课程负责人签名:2012年 6月 21 日一、设计题目(任选其一)实验一、哈夫曼编/译码器二、实验目的1巩固和加深对数据结构的理解,提高综合运用本课程所学知识的能力;2 深化对算法课程中基本概念、理论和方法的理解;3 巩固构造赫夫曼树的算法;4 设计试验用程序实验赫夫曼树的构造。
《数据结构》课程设计报告题目: 哈夫曼编/译码器 专业: 计算机科学与技术(对口)班级: 13(3) 姓名: 陈霞指导教师:彭飞2015-2016学年 第1学期成绩:计算机学院2015年11月12日目录1 设计内容及要求 (3)1.1 内容 (3)1.2 要求 (4)2 概要设计 (5)2.1 抽象数据类型定义 (5)2.2 模块划分 (6)3 设计过程及代码 (7)3.1 设计过程 (7)3.2 代码 (11)4 设计结果与分析 (17)5 参考文献 (20)1设计内容及要求1.1 内容利用哈夫曼编码进行信息通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。
但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。
对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。
试为这样的信息收发站写一个哈夫曼编/译码系统。
1.2 要求一个完整的系统应具有以下功能:(1)I:初始化(Initialization)。
从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。
(2)E:编码(Encoding)。
利用已建好的哈夫曼树(如不在内存,则从文件htmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。
(3)D:译码(Decoding)。
利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。
(4)P:印代码文件(Print)。
将文件CodeFile以紧凑格式显示在终端上,每行50个代码。
同时将此字符形式的编码写入文件CodePrint中。
(5)T:印哈夫曼树(Tree Printing)。
将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。
[测试数据](1)数据一:已知某系统在通信联络中只可能出现8种字符,其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,以此设计哈夫曼编码。
目录目⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ (2)1 程的目的和意⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯32 需求分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯43 概要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯4 4⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.85 分析和果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.11 6⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯127致⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯138附⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯13参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..201课程设计目的与意义在当今信息爆炸时代,如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。
哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。
哈夫曼编码的应用很广泛,利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。
树中从根到每个叶子都有一条路径,对路径上的各分支约定:指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“ 1”的序列作为和各个对应的字符的编码,这就是哈夫曼编码。
通常我们把数据压缩的过程称为编码,解压缩的过程称为解码。
电报通信是传递文字的二进制码形式的字符串。
但在信息传递时,总希望总长度尽可能最短,即采用最短码。
作为计算机专业的学生,我们应该很好的掌握这门技术。
在课堂上,我们能过学到许多的理论知识,但我们很少有过自己动手实践的机会!课程设计就是为解决这个问题提供了一个平台。
在课程设计过程中,我们每个人选择一个课题,认真研究,根据课堂讲授内容,借助书本,自己动手实践。
这样不但有助于我们消化课堂所讲解的内容,还可以增强我们的独立思考能力和动手能力;通过编写实验代码和调试运行,我们可以逐步积累调试 C 程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。
题目一: 哈夫曼编码与译码一、任务设计一个运用哈夫曼算法的编码和译码系统, 反复地显示并解决以下项目, 直到选择退出为止。
规定:1) 将权值数据存放在数据文献(文献名为data.txt, 位于执行程序的当前目录中) ;2) 初始化:键盘输入字符集记录字符权值、自定义26个字符和26个权值、记录文献中一篇英文文章中26个字母, 建立哈夫曼树;3) 编码: 运用建好的哈夫曼树生成哈夫曼编码;4) 输出编码(一方面实现屏幕输出, 然后实现文献输出);5)译码(键盘接受编码进行译码、文献读入编码进行译码);6) 界面优化设计。
二、流程图三、代码分解 //头文献 #include<stdio.h> #include<string.h> #include<stdlib.h> #include <conio.h> #define N 1000 #define M 2*N-1 #define MAXcode 6000 //函数声明void count(CHar &ch,HTNode ht[]);void editHCode(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]); //编码函数void printyima(HTNode ht[],HCode hcd[],int n,char bianma[]); //译码函数 void creatHT(HTNode ht[],int n);字符集记录符集记录权值 权值 至文献“哈夫曼树。
t xt” 菜单1.从键盘输入字符集进行编码2.从文献读入字符集进行编码1.从键盘输入编码进行译码2.从文献读入编码进行译码0.返回上级菜单 0.返回上级菜单void CreateHCode (HTNode ht[],HCode hcd[],int n);void DispHCode(HTNode ht[],HCode hcd[],int n);void input_key(CHar &ch);void input_file(CHar &ch);void input_cw(HTNode ht[]);void bianma1(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]); void bianma2(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]); void yima1(HTNode ht[],HCode hcd[],int n,char bianma[]);void yima2(HTNode ht[],HCode hcd[],int n,char bianma[]);void creat_cw();void bianmacaidan();void yimacaidan();void bianmayima();int caidan();//结构体typedef struct{char data;int parent;int weight;int lchild;int rchild;}HTNode;typedef struct{char cd[N];int start;}HCode;typedef struct{char s[N];int num;}CHar;CHar ch;HTNode ht[M];HCode hcd[N];//主函数int main(){int xh;while(1){system("color 1f"); //操作菜单背景颜色 xh=caidan(); //调用菜单函数switch(xh) //switch语句 {case 1:system("cls");creat_cw();break;case 2:system("cls");creatHT(ht,n);break;case 3:system("cls");CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);break;case 4:system("cls");bianmayima();break;case 0:system("cls");printf("\n\n\n\n\n\n\n\n\n\t\t\t\t感谢使用本系统!\n\n\n\n\n\n\n \t\t\t");exit(0);default:system("cls");putchar('\a');printf("\n\t\t输入有误, 请重新输入:\n");break;}}return 0;}//菜单函数int caidan() //菜单函数模块//{int xh;printf("\n\n\n");printf("\t\t 欢迎使用哈夫曼编码译码系统\n");printf("\t\t \n");printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");printf("\t\t*= =*\n");printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n");printf("\t\t*= 1.建立字符权值=*\n");printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n"); printf("\t\t*= 2.建立并输出哈夫曼树=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n"); printf("\t\t*= 3.生成并查看哈夫曼编码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n"); printf("\t\t*= 4.编码与译码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n"); printf("\t\t*= 0.退出系统=*\n"); printf("\t\t*= =*\n"); printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d", &xh);return xh; //返回从键盘接受的选项}void bianmayima(){int xh;while(1){printf("\n\n\n\n\n");printf("\t\t 编码与译码\n"); printf("\t\t \n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");printf("\t\t*= 1.编码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 2.译码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 0.返回上级菜单=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d",&xh);switch(xh) //switch语句{case 1:system("cls");bianmacaidan();break;case 2:system("cls");yimacaidan();break;case 0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t输入有误, 请重新输入:\n");break;}}}void yimacaidan(){int xh;while(1){printf("\n\n\n\n\n");printf("\t\t 译码\n"); printf("\t\t \n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 1.键盘输入编码进行译码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 2.文献读入编码进行译码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 0.返回上级菜单=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d",&xh);switch(xh) //switch语句{case 1:system("cls");yima1(ht,hcd,n,bianma);break;case 2:system("cls");yima2(ht,hcd,n,bianma);break;case 0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t输入有误, 请重新输入:\n");break;}}}void bianmacaidan(){int xh;while(1){printf("\n\n\n\n\n");printf("\t\t 编码\n"); printf("\t\t \n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 1.键盘输入字符集编码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 2.文献读入文章编码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 0.返回上级菜单=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d",&xh);switch(xh) //switch语句{case 1:system("cls");bianma1(ht,hcd,ch,n,bianma);break;case 2:system("cls");bianma2(ht,hcd,ch,n,bianma);break;case 0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t输入有误, 请重新输入:\n");break;}}}void creat_cw(){int xh2;while(1){printf("\n\n\n\n\n");printf("\t\t 建立字符权值\n"); printf("\t\t \n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 1.从键盘输入字符集进行记录=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 2.从文献读入字符集记录=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 3.自定义字符权值=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 0.返回上级菜单=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d",&xh2);switch(xh2) //switch语句{case 1:system("cls");input_key(ch);break;case 2:system("cls");input_file(ch);break;case 3:system("cls");input_cw(ht);break;case 0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t输入有误, 请重新输入:\n");break;}}}//建立字符权值模块void input_key(CHar &ch){int i,j=0;char st[N];printf("请输入字符集(以‘#’结束):\n");for(i=0;i<N;i++){scanf("%c",&st[i]);if(st[i]=='#'){st[i]='\0';break;}}strcpy(ch.s,st);count(ch,ht);printf("按任意键返回!");getch();system("cls");return;}void input_file(CHar &ch){int i;FILE*fp;char filename[20];printf("请输入要打开的文献名(*.txt):");scanf("%s",&filename);if((fp=fopen(filename,"r"))==NULL){printf("\n\t\t文献打开失败");return;}for(i=0;!feof(fp);i++){fread(&ch.s[i],sizeof(char),1,fp);}printf("读入成功!\n");printf("文献中的字符集为:%s\n",ch.s);fclose(fp);count(ch,ht);printf("按任意键返回!");getch();system("cls");return;}void input_cw(HTNode ht[]){int i,w,s,j;char a;printf("要输入的字符总个数是?:");scanf("%d",&s);n=s;printf("请输入字符及其权值:\n");for(i=0;i<s;i++){printf("请输入第%d个字母:",i+1);scanf("%s",&a);ht[i].data=a;printf("请输入其权值:");scanf("%d",&w);ht[i].weight=w;}FILE *fp;if((fp=fopen("data.txt","w"))==0){printf("\n\t\t文献打开失败");return;}printf("\n定义权值成功!\n\n");printf("各字符及其权值为:\n\n");fprintf(fp,"各字符及其权值为:\n");printf(" 字符\t权值");fprintf(fp," 字符\t权值");for(j=0;j<i;j++){ printf("\n");fprintf(fp,"\n");printf(" %-8c%-8d",ht[j].data,ht[j].weight);fprintf(fp," %-8c%-8d%",ht[j].data,ht[j].weight); }printf("\n");printf("\n字符权值已输出至文献“data.txt”!");fclose(fp);printf("输入完毕, 按任意键返回!");getch();system("cls");return;}//记录字符权值函数void count(CHar &ch,HTNode ht[]){int i,j,m=0;char c[N];int sum[N]={0};for(i=0;ch.s[i]!='\0';i++){for(j=0;j<m;j++)if(ch.s[i]==c[j]||(c[j]>='a'&&c[j]<='z'&&ch.s[i]+32==c[j])) break;if(j<m)sum[j]++;else{if(ch.s[i]>='A'&&ch.s[i]<='Z')c[j]=ch.s[i]+32;else c[j]=ch.s[i];sum[j]++;m++;}}for(i=0;i<m;i++){ht[i].data=c[i];ht[i].weight=sum[i];}n=m;FILE *fp;if((fp=fopen("data.txt","w"))==0) {printf("\n\t\t文献打开失败"); return;}printf("\n记录权值成功!\n\n"); printf("各字符及其权值为:\n\n"); fprintf(fp,"各字符及其权值为:\n"); printf(" 字符\t权值");fprintf(fp," 字符\t权值");for(j=0;j<m;j++){ printf("\n");fprintf(fp,"\n");printf(" %-8c%-8d",ht[j].data,ht[j].weight);fprintf(fp," %-8c%-8d%",ht[j].data,ht[j].weight);}printf("\n");printf("\n字符权值已输出至文献“data.txt”!");fclose(fp);}//构造哈夫曼树void creatHT(HTNode ht[],int n){FILE *fp;if((fp=fopen("哈夫曼树.txt","w"))==0){printf("\n\t\t文献打开失败");return;}int i,j,k,lnode,rnode;int min1,min2;for (i=0;i<2*n-1;i++)ht[i].parent=ht[i].lchild=ht[i].rchild=-1;for (i=n;i<2*n-1;i++){min1=min2=32767;lnode=rnode=-1;for(k=0;k<=i-1;k++)if(ht[k].parent==-1){if (ht[k].weight<min1){min2=min1;rnode=lnode;min1=ht[k].weight;lnode=k;}else if(ht[k].weight<min2){min2=ht[k].weight;rnode=k;}}ht[lnode].parent=i;ht[rnode].parent=i;ht[i].weight=ht[lnode].weight+ht[rnode].weight;ht[i].lchild=lnode;ht[i].rchild=rnode;}printf("建立huffman树成功!\n");printf("输出huffman树:\n");fprintf(fp,"输出huffman树:\n");printf("\t字符\t权值\t父节点\t 左子节点\t右子节点");fprintf(fp,"\t字符\t权值\t父节点\t 左子节点\t右子节点");for(j=1;j<i;j++){ printf("\n");fprintf(fp,"\n");printf("\t %-8c%-8d%-10d%-14d%-10d",ht[j].data,ht[j].weight,ht[j].parent,ht[i]. lchild,ht[j].rchild);fprintf(fp,"\t %-8c%-8d%-10d%-14d%-10d",ht[j].data,ht[j].weight,ht[j].parent,h t[i].lchild,ht[j].rchild);}printf("\n");printf("哈夫曼树已输出至文献“哈夫曼树.txt”!按任意键返回!");fclose(fp);getch();system("cls");return;}//生成哈夫曼编码void CreateHCode (HTNode ht[],HCode hcd[],int n){int i,f,c,j=0;HCode hc;for(i=0;i<n;i++){hc.start=n;c=i;hc.cd[hc.start--]='0';f=ht[i].parent;while(f!=-1){if (ht[f].lchild==c)hc.cd[hc.start--]='0';elsehc.cd[hc.start--]='1';c=f;f=ht[f].parent;}hc.start++;for(j=0;j<hc.start;j++)hc.cd[j]=' ';hcd[i]=hc;}}void DispHCode(HTNode ht[],HCode hcd[],int n) {FILE *fp;if((fp=fopen("哈夫曼编码.txt","w"))==0){printf("\n\t\t文献打开失败");return;}int i,k;int sum=0,m=0,j;printf("输出字符哈夫曼编码:\n"); fputs("输出字符哈夫曼编码:\n",fp); for (i=0;i<n;i++){j=0;printf("%c:\t",ht[i].data);fprintf(fp,"\n%c:\t",ht[i].data);for (k=hcd[i].start;k<=n;k++){printf("%c",hcd[i].cd[k]);j++;fprintf(fp,"%c",hcd[i].cd[k]); }m+=ht[i].weight;sum+=ht[i].weight*j;printf("\n");}printf("\n哈夫曼编码已保存至文献“哈夫曼编码.txt!按任意键返回!”");fclose(fp);getch();system("cls");}//编码函数void bianma1(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]){int i;char str[N];printf("请输入要编码的字符集(以‘#’结束):\n");for(i=0;i<N;i++){scanf("%c",&str[i]);if(str[i]=='#'){str[i]='\0';break;}}strcpy(ch.s,str);ch.num=strlen(str);editHCode(ht,hcd,ch,n,bianma);getch();system("cls");}void bianma2(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]) {int i;FILE*fp;char filename[20];printf("请输入要打开的文献名(*.txt):");scanf("%s",&filename);if((fp=fopen(filename,"r"))==NULL){printf("\n\t\t文献打开失败");return;}for(i=0;!feof(fp);i++){fread(&ch.s[i],sizeof(char),1,fp);}ch.num=strlen(ch.s);printf("\n读入成功!\n");printf("文献中的字符集为:\n%s",ch.s);fclose(fp);editHCode(ht,hcd,ch,n,bianma);system("cls");return;}//译码函数void yima1(HTNode ht[],HCode hcd[],int n,char bianma[]) {int i;char code[MAXcode];printf("请输入编码进行译码(以‘#’结束):\n");for(i=0;i<MAXcode;i++){scanf("%c",&code[i]);if(code[i]=='#'){code[i]='\0';break;}}strcpy(bianma,code);printyima(ht,hcd,n,bianma);printf("\n译码完毕!按任意键返回!");getch();system("cls");return;}void yima2(HTNode ht[],HCode hcd[],int n,char bianma[]) {int i;FILE*fp;char filename[20];printf("请输入要打开的文献名(*.txt):");scanf("%s",&filename);if((fp=fopen(filename,"r"))==NULL){printf("\n\t\t文献打开失败");return;}for(i=0;!feof(fp);i++){fread(&bianma[i],sizeof(char),1,fp);}printf("读入成功!\n");printf("文献中的编码是:%s\n",bianma);printyima(ht,hcd,n,bianma);printf("\n译码完毕!按任意键返回!");getch();system("cls");}四、调试结果主菜单建立字符权值选择2.从文献读入字符进行记录输入测试文献名“cs.txt”输出个字符权值建立哈夫曼树并输出至文献生成哈夫曼编码并保存至文献编码选择2.从文献读入字符集编码编码结果保存至文献译码选择2.从文献读入编码, 读入上一步的编码译码完毕, 返回!退出系统。
数据结构课程设计实验报告书姓名:班级:12数字媒体技术二班学号:2014 年06 月赫夫曼编码/译码器一、实验目的1.进一步掌握最优二叉树的含义。
2.掌握最优二叉树的结构特征,以及各种存储结构的特点及使用范围。
3.熟练掌握哈夫曼树的建立和哈夫曼编码方法。
4.掌握用指针类型描述、访问和处理运算。
二、实验内容编写一个哈夫曼码的编/译码系统,一个完整的系统应具有以下功能:(1)初始化。
从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree.txt中。
(2)编码。
利用已建好的哈夫曼树,对文件ToBeTra.txt中的正文进行编码,然后将结果存入文件CodeFil.txt中。
(3)译码。
利用已建好的哈夫曼树将文件CodeFile.txt中的代码进行译码,结果存入文件Textfile.txt中。
(4)打印哈夫曼树(Treeprinting).将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint.txt 中。
三、实验步骤1.定义结点结构,定义哈夫曼树结构;2.初始化哈夫曼树,存储哈夫曼树信息;3.定义求哈夫曼编码的函数;4.定义译哈夫曼编码的函数;5.写出主函数。
6.测试系统。
四、实验内容1.文件工程包含两个头文件,Huffman.h用于定义显示选项菜单的相关函数,HuffmanTree.h 用于定义与霍夫曼编码相关的类;包含三个cpp文件,Huffman.cpp用于实现显示选项菜单的相关函数,HuffmanTree.cpp用于实现与霍夫曼编码相关的类的成员函数等,HuffmanCode.cpp用于主函数的实现。
2.霍夫曼编码相关类程序中将霍夫曼树结点与霍夫曼编码相关操作分别封装为类3.选项菜单等相关函数Init()函数用于从外部文件中加载霍夫曼树,因为树人工不好整理所以我设置了读入树的叶子结点与权值,然后内部编写函数将这两种数据整理成霍夫曼树ChooseCode()函数用于执行从终端读取编码串,然后根据读取的霍夫曼树来解码ChooseRecode()函数用以执行解码操作,对从终端或者从文件读取的编码串进行解码并输出InputFromFile()函数用于从外部文件读取待解码的编码串OutputToFile()函数可以将霍夫曼树,解码后的字符串输出到外部文件中4.霍夫曼编码操作编码首先从外部初始化霍夫曼树,即调用Init()函数从外部读取数据;然后选择编码串来源,可以从外部文件读取,也可从终端输入;最后是进行霍夫曼解码,调用HuffmanRecoding()函数;五、实验结果首先在C盘下设置HuffmanTree.txt的初始值,第一行为叶子结点的值,第二行为权值然后设置code.txt的初始值,为要解码的字符串运行程序第一步初始化第二步从code.txt读取编码串第三步,解码第四步,输出到HuffmanCode.txt文件还可以选择从终端输入编码串然后解码,输出到外部,比如编码串000011010(lqt)六、实验心得实验之后,我对于程序设计的思路又有了加深的理解,同时掌握了一定的霍夫曼编码方面的知识。
数据结构哈夫曼编码器课程设计报告哈夫曼编码器课程设计报告设计目标:本课程设计的目标是实现一个哈夫曼编码器,能够实现对给定文本文件进行压缩和解压缩操作。
通过使用哈夫曼编码,可以使文本文件的大小大幅度减小,从而节约存储空间。
设计原理及实现方法:本设计主要包括以下几个步骤:1、文本文件的读取:首先需要从外部文件中读取待压缩的文本文件,读取过程可以通过使用文件输入流进行操作。
读取的文本内容将用于构建哈夫曼树和编码表。
2、构建哈夫曼树:哈夫曼树是通过给定文本中的字符出现频率来构建的,出现频率更高的字符将拥有更短的编码。
构建哈夫曼树的过程可以通过使用优先队列和二叉树来实现。
3、编码表:在构建哈夫曼树的过程中,每个字符都会有一个唯一的编码。
根据哈夫曼树的特性,左子树的编码为0,右子树的编码为1,根据这个规则可以通过遍历哈夫曼树来编码表。
4、压缩文本文件:在编码表后,可以利用编码表来对文本文件进行压缩操作。
遍历文本文件中的每个字符,通过编码表将字符转换为对应的哈夫曼编码,并将编码存储在一个压缩文件中。
5、解压缩文本文件:解压缩操作是压缩操作的逆过程。
根据编码表将压缩文件中的哈夫曼编码逐个解码为字符,并将解码后的字符写入解压缩文件中。
附件说明:本文档的附件包括以下内容:1、源代码文件:- HuffmanEncoder:java:包含了哈夫曼编码器的主要实现代码。
- Mn:java:包含了测试哈夫曼编码器的主函数。
2、示例文本文件:- input:txt:用于测试的示例文本文件。
法律名词及注释:本文档中涉及的法律名词及注释如下:1、哈夫曼编码:用于数据压缩的一种编码方式,旨在通过减少字符的编码长度来节省存储空间。
2、压缩:将原始文件经过编码转换为较短的文件,从而减小存储空间的占用。
3、解压缩:将压缩文件经过解码转换为原始文件,恢复原始文件的过程。
全文结束。
课程设计任务书课程名称数据结构课程设计课题赫夫曼编译码器专业班级网络工程***学生姓名***学号**指导老师审批任务书下达日期:2011 年6 月26 日任务完成日期:2011 年7 月15 日一、设计内容1)问题描述对输入的一串电文字符实现赫夫曼编码,再对赫夫曼编码生成的代码串进行译码,输出电文字符串。
2)基本要求a.初始化,键盘输入字符集大小n,n个字符和n个权植,建立哈夫曼树。
b.编码,利用建好的huffman树生成huffman编码;c.输出编码;d.译码功能;二.设计要求:课程设计报告1)需求分析a.程序的功能。
1.初始化,键盘输入字符集大小n,n个字符和n个权植,建立哈夫曼树。
2.编码,利用建好的huffman树生成huffman编码;3.输出编码;4.译码功能;b.输入输出的要求。
2)概要设计a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系;每个模块的功能。
i.void main()ii.void tohuffmancode(int n)//编码部分iii.void decode(char ch[],huftree tree[],int n)//译码iv.void huffman(huftree tree[],int *w,int n) //生成huffman树v.void select(huftree tree[],int k) //找寻parent为0,权最小的两个节点vi.void huffmancode(huftree tree[],char code[],int n)//输出huffman编码其流程图如下:主函数main 调用其他函数:tohuffmancode(int n)decode(char ch[],huftree tree[],int n)huffman(huftree tree[],int *w,int n)select(huftree tree[],int k)huffmancode(huftree tree[],char code[],int n) 其主流程图如下:(3)主要模块程序流程图下面介绍三个主要的程序模块流程图:①函数流程图:流程图注释:该图比较简单,主要是调用各个函数模块,首先代开已经存在的文件,然后统计总的字符数以及出现的各个字符和频率。
专业资料安徽大学数据结构课程设计报告项目名称:哈弗曼编/译码系统的设计与实现姓名:鉏飞祥学号:E21414018专业:软件工程完成日期2016/7/4计算机科学与技术学院1 .需求分析1.1问题描述•问题描述:利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。
但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(解码)。
对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。
试为这样的信息收发站设计一个哈夫曼编译码系统。
1.2基本要求(1) 输入的形式和输入值的范围;(2) 输出的形式;(3) 程序所能达到的功能。
1.基本要求(1)初始化(Initialzation)。
从数据文件DataFile.data中读入字符及每个字符的权值,建立哈夫曼树HuffTree;(2)编码(EnCoding)。
用已建好的哈夫曼树,对文件ToBeTran.data中的文本进行编码形成报文,将报文写在文件Code.txt中;(3)译码(Decoding)。
利用已建好的哈夫曼树,对文件CodeFile.data 中的代码进行解码形成原文,结果存入文件Textfile.txt中;(4)输出(Output)。
输出DataFile.data中出现的字符以及各字符出现的频度(或概率);输出ToBeTran.data及其报文Code.txt;输出CodeFile.data 及其原文Textfile.txt;2. 概要设计说明本程序中用到的所有抽象数据类型的定义。
主程序的流程以及各程序模块之间的层次(调用)关系。
(1)数据结构哈夫曼树的节点struct huff{int weight;int parent;int l;int r;};哈夫曼编码的存储struct huff *hufftree;(2)程序模块选择1到i-1中parent为0且权值最小的两个下标void Select(struct huff *HT, int n, int &s1, int &s2)构建哈夫曼树:void huffmancoding(struct huff *ht,int *w,int n)对原文进行编码:void code(char *c)根据报文找到原文:void decoding(char *zifu)3. 详细设计核心技术分析:1:构建哈夫曼树及生成哈夫曼编码:根据每个字符权值不同,根据最优二叉树的构建方法,递归生成哈夫曼树,并且用数组存放哈夫曼树。
JAVA语言实验报告学院计算机工程学院班级计算1013 姓名佐伊伦学号 201081xxxx 成绩指导老师 xxxx2012年09月03日目录目录 (1)1 课程设计的目的和意义 (2)2 需求分析 (3)3 系统(项目)设计 (5)①设计思路及方案 (5)②模块的设计及介绍 (5)③主要模块程序流程图 (8)4 系统实现 (11)①主调函数 (12)②建立HuffmanTree (12)③生成Huffman编码并写入文件 (15)④电文译码 (16)5 系统调试 (17)参考文献 (21)附录源程序 (22)1 课程设计的目的和意义在当今信息爆炸时代,如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。
哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。
哈夫曼编码的应用很广泛,利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。
树中从根到每个叶子都有一条路径,对路径上的各分支约定:指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码,这就是哈夫曼编码。
通常我们把数据压缩的过程称为编码,解压缩的过程称为解码。
电报通信是传递文字的二进制码形式的字符串。
但在信息传递时,总希望总长度尽可能最短,即采用最短码。
作为信息管理专业的学生,我们应该很好的掌握这门技术。
在课堂上,我们能过学到许多的理论知识,但我们很少有过自己动手实践的机会!课程设计就是为解决这个问题提供了一个平台。
在课程设计过程中,我们每个人选择一个课题,认真研究,根据课堂讲授内容,借助书本,自己动手实践。
这样不但有助于我们消化课堂所讲解的内容,还可以增强我们的独立思考能力和动手能力;通过编写实验代码和调试运行,我们可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。
在课程设计过程中,我们不但有自己的独立思考,还借助各种参考文献来帮助我们完成系统。
更为重要的是,我们同学之间加强了交流,在对问题的认识方面可以交换不同的意见。
同时,师生之间的互动也随之改善,我们可以通过具体的实例来从老师那学到更多的实用的知识。
数据结构课程具有比较强的理论性,同时也具有较强的可应用性和实践性。
课程设计是一个重要的教学环节。
我们在一般情况下都能够重视实验环节,但是容易忽略实验的总结,忽略实验报告的撰写。
通过这次实验让我们明白:作为一名大学生必须严格训练分析总结能力、书面表达能力。
需要逐步培养书写科学实验报告以及科技论文的能力。
只有这样,我们的综合素质才会有好的提高。
2 需求分析课题:哈夫曼编码译码器系统问题描述:打开一篇英文文章,统计该文章中每个字符出现的次数,然后以它们作为权值,对每一个字符进行编码,编码完成后再对其编码进行译码。
问题补充:1. 从硬盘的一个文件里读出一段英语文章;2. 统计这篇文章中的每个字符出现的次数;3. 以字符出现字数作为权值,构建哈夫曼树,并将哈夫曼树的存储结构的初态和终态进行输出;4. 对每个字符进行编码并将所编码写入文件然后对所编码进行破译。
具体介绍:在本课题中,我们在硬盘E盘中预先建立一个file1.txt文档,在里面编辑一篇文章(大写)。
然后运行程序,调用fileopen()函数读出该文章,显示在界面;再调用jsq()函数对该文章的字符种类进行统计,并对每个字符的出现次数进行统计,并且在界面上显示;然后以每个字符出现次数作为权值,调用ChuffmanTree()函数构建哈夫曼树;并调用print1()和print2()函数将哈夫曼的存储结构的初态和终态进行输出。
然后调用HuffmanEncoding()函数对哈夫曼树进行编码,调用coding()函数将编码写入文件;再调用decode()对编码进行译码,再输出至界面。
至此,整个工作就完成了。
测试数据:例如从文本中读到文章为:IAMASTUDENT。
则效果如下:IAMASTUDENT--------------------------------------HuffmanTree的初态:2 0 0 01 0 0 01 0 0 01 0 0 01 0 0 01 0 0 01 0 0 02 0 0 01 0 0 0- 0 0 0- 0 0 0- 0 0 0- 0 0 0- 0 0 0- 0 0 0- 0 0 0- 0 0 0--------------------------------------字符A次数:2字符D次数:1字符E次数:1字符I 次数:1字符M次数:1字符N 次数:1字符S 次数:1字符T次数:2字符U次数:1--------------------------------------HuffmanTree的终态:2 13 0 01 10 0 01 10 0 01 11 0 01 11 0 01 12 0 01 12 0 02 14 0 01 13 0 02 14 2 32 15 4 52 15 6 73 16 9 14 16 8 104 17 11 127 17 13 1411 0 15 16--------------------------------------译码后的字符串:IAMASTUDENT********************************************************** Press any key to continue三维谷屋3 系统(项目)设计(1)设计思路及方案本课题是用最优二叉树即哈夫曼树来实现哈夫曼编码译码器的功能。
假设每种字符在电文中出现的次数为Wi,编码长度为Li,电文中有n种字符,则电文编码总长度为(W1*L1)+(W2*L2)+…+(Wi*Li)。
若将此对应到二叉树上,Wi为叶结点,Li为根结点到叶结点的路径长度。
那么,(W1*L1)+(W2*L2)+…+(Wi*Li)恰好为二叉树上带权路径长度。
三维谷屋因此,设计电文总长最短的二进制前缀编码,就是以n种字符出现的频率作权,构造一棵哈夫曼树,此构造过程称为哈夫曼编码。
该系统将实现以下几大功能:从硬盘读取字符串,建立哈夫曼树,输出哈夫曼树的存储结构的初态和终态,输出各种字符出现的次数以及哈夫曼编码的译码等。
(2)模块的设计及介绍①从硬盘读取字符串fileopen(参数){实现命令;打印输出;}②建立HuffmanTree通过三个函数来实现:void select(参数){初始化;for{接受命令;处理命令;}}说明:在ht[1....k]中选择parent为0且权值最小的两个根结点的算法int jsq(参数){初始化;for{接受命令;处理命令;}}淘宝返利网哪个好三维谷屋 说明:统计字符串中各种字母的个数以及字符的种类void ChuffmanTree(){初始化;for{接受命令;处理命令;}输出字符统计情况;}说明:构造哈夫曼树③输出哈夫曼树的存储结构的初态和终态分别调用print1()和print2()来实现void print1(参数){初始化;输出初态;}说明:输出哈夫曼树的初态void print2(参数){for{输出终态;}}说明:输出哈夫曼树的终态④哈夫曼编码和译码void HuffmanEncoding(参数){定义变量;{处理命令;}}说明:哈夫曼编码char*decode(参数){定义变量;while{接受命令;处理命令;}}说明:哈夫曼译码(3)主要模块程序流程图下面介绍三个主要的程序模块流程图:①主函数流程图:图3.1 流程图注释:该图比较简单,主要是调用各个函数模块,首先代开已经存在的文件,然后统计总的字符数以及出现的各个字符和频率。
然后才开始建立哈夫曼树,接着在哈夫曼树的基础上对其进行编码,编码之后才是译码。
最后输出结束。
淘宝返利网哪个好 三维谷屋 ②构造哈夫曼树:结束统计字符种类及频率字符总数num建立哈夫曼树哈夫曼编码哈夫曼译码打开文件?开始否是图3.2 流程图注释:该图是表示构造哈夫曼树的过程。
首先输入num 个叶结点的权值,当i=num 是循环结束。
然后进行哈夫曼树的构建,当i=2*num-1是循环结束。
最后输出所得到的字符统计情况。
三维谷屋返利 ③哈夫曼编码:开始结束第i 个结点权值i=num?创建哈夫曼树输出字符统计情况第i 个根结点i=2*num-1?i=num?否是 否是否是图3.3流程图解释:该流程图表四哈夫曼编码情况。
首先初始化,Cd[--start]=0,start=num 。
然后进行 编码,使用了一个三目运算符。
cd[--start]=(T[p].lchild==c) ? '0' : '1',即当cd[--start]=T[p].lchild= =c 时,cd[--start]=0;当cd[--start]=T[p].lchild != =c 时,cd[--start]=1。
这个编码循环一直到i=num 时结束。
结束开始T[p].lchlid=c?i<=num?Cd[--start]=0,start=numCd[--start]=0Cd[--start]=1否否是是4 系统实现各模块关键代码及算法的解释:①主调函数代码解释:这是main函数里的各个函数调用情况。
fileopen(string); //从硬盘中读取文件num=jsq(string,cnt,str); //统计字符种类及各类字符出现的频率DhuffmanTree(HT,cnt,str);printf("HuffmanTree的初态:\n");print1(HT); //输出哈夫曼树的初态ChuffmanTree(HT,HC,cnt,str);//建立哈夫曼树HuffmanEncoding(HT,HC); //生成哈夫曼编码printf("HuffmanTree的终态:\n");print2(HT); //输出哈夫曼树的终态s=decode(HC); //读编码文件译码printf("译码后的字符串:\n");printf("%s\n",s); //输出译码后的字符串②建立HuffmanTree代码解释:该函数为在ht[1....k]中选择parent为0且权值最小的两个根结点的算法,其序号为s1和s2。
void select(HuffmanTree T,int k,int &s1,int &s2){int i,j;int min1=101;for(i=1;i<=k;i++)if(T[i].weight<min1 &&T[i].parent==0){j=i;min1=T[i].weight;}s1=j;min1=32767;for (i=1;i<=k;i++)if(T[i].weight<min1 && T[i].parent==0 && i!=s1){j=i;min1=T[i].weight;}s2=j;}代码解释:下面函数用来统计字符串中各种字母的个数以及字符的种类。