- 1、本文档共9页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
数据结构课程设计报告
题目赫夫曼编码
题目
赫夫曼编码
一、需求分析
问题描述
利用赫夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。
基本要求
一个完整的系统应具有以下功能:
(1) I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立赫夫曼树,并将它存于文件hfmTree中。
(2) E:编码(Encoding)o利用已建好的赫夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。
(3) D:译码(Decoding)o利用已建好的赫夫曼树将文件CodeFile中的代码进行译码,结果存入文件Textfile中。
⑷P:印代码文件(Print)o将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。
⑸T:印赫夫曼树(Treeprinting)o将已在内存中的赫夫曼树以直观的方式(比如树)显示在终端上,同时将此字符形式的赫夫曼树写入文件TreePrint中。
测试要求
⑴已知某系统在通信联络中只可能出现八种字符,其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,试设计赫夫曼编码。
(2)用下表给出的字符集和频度的实际统计数据建立赫夫曼树,并实现以下报文的编码和译码:“THISPROGRAMEISMYFAVORITE”。
字符
A
B
C
D
E
F
G
H
I
J
K
L
M
频度
186
64
13
22
32
103
21
15
47
57
1
5
32
20
字符
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
频度
57
63
15
1
48
51
80
23
8
18
1
16
1
实现提示
⑴编码结果以文本方式存储在文件Codefile中。
用户界面可以设计为“菜单”方式:显示上述功能符号,再加上Q”,表示退出运行Quito请用户键入一个选择功能符。此功能执行完毕后再显示此菜单,直至某次用户选择了“。”为止。
在程序的一次执行过程中,第一次执行I,D或C命令之后,赫夫曼树已经在内存了,不必再读入。每次执行中不一定执行I命令,因为文件hfmTree可能早已建好。
二、概要设计
问题分析哈夫曼树的定义
哈夫曼树节点的数据类型定义为:
typedefstruct( 〃赫夫曼树的结构体
charch;
intweight; 〃权值
intparent,lchild,rchild;
}htnode,*hfmtree;
所实现的功能函数如下
1、 voidhfmcoding(hfmtreeHT,hfmcodeHC,intn初始化哈夫曼树,处理InputHuffman(HuffmanHfm)函数得到的数据,按照哈夫曼规则建立2叉树。此函数块调用7Select()函数。
2、 voidSelect(hfmtreeHT,inta,int*p1,int*p2) //Select函数,选出HT树到a为
止,权值最小且parent为0的2个节点
2、intmain()
主函数:利用已建好的哈夫曼树(如不在内存,则从文件hfmtree.txt中读入)
对文件中的正文进行编码,然后将结果存入文件codefile.txt中。如果正文中没有要编码的字符,则键盘读入并存储到ToBeTran文件中。读入ToBeTran中将要编码的内容,将编码好的哈夫曼编码存储到CodeFile中。
3、 Encoding
编码功能:对输入字符进行编码
4、 Decoding
译码功能: 利用已建好的哈夫曼树将文件 codefile.txt中的代码进行译码,结果存入文件
textfile.dat中。
Print()打印功能函数:输出哈夫曼树,字符,权值,以及它对应的编码。
主函数的简要说明,主函数主要设计的是一个分支语句,让用户挑选所实现的功能。
使用链树存储,然后分别调用统计频数函数,排序函数,建立哈夫曼函数,编码函数,译码函数来实现功能。
2)系统结构图(功能模块图)
三、详细设计
#includeiostream.h#includestdio.h#includestdlib.h#includestring.h#includefstream.htypedefstruct( 〃赫夫曼树的结构体
ch
您可能关注的文档
最近下载
- 第4课《古代诗歌四首——闻王昌龄左迁龙标遥有此寄》课件(共27张PPT)2022—2023学年部编版语文七年级上册.pptx
- 直播运营管理全套完整教学课件.pptx
- PDA TR27-1998 Pharmaceutical Package Integrity英文原版资料.pdf
- Q∕GDW 11897-2018 调度自动化机房设计与建设规范.docx
- 建筑专业图集-03J001:围墙大门.pdf
- 2024年采制样工考试2024年采制样工试题库(判断题)试卷 .pdf
- 营销心理学(第五版)——数字时代消费者行为分析 课件 单凤儒 模块6--8 场景行为:传播与广告心理效应 ---现代场景:网络与新媒体营销心理效应 .pptx
- 内典讲座之研究.pdf
- 新建南通至宁波高速铁路环境影响报告书.pdf
- 2024年GD省生态环境监测专业技术人员大比武模拟试卷及答案-3应急监测.pdf
文档评论(0)