没有合适的资源?快使用搜索试试~ 我知道了~
哈夫曼树的实现.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 59 浏览量
2022-07-06
01:38:05
上传
评论
收藏 1.97MB DOCX 举报
温馨提示
试读
34页
。。。
资源推荐
资源详情
资源评论
《数据结构》课程设计
哈夫曼编码
一 目的
1.实现一个哈夫曼编码系统,让用户可以选择输入字符或者读取指定文件的字符;统
计出现的字符及其频率;根据统计结果建立哈夫曼树并且利用该树将各字符对应的编码表
保存在指定文件中;同时可以利用该哈夫曼表,将用户输入的字符或者指定文件的字符转
换成相应的编码文件。
2. 培养动手操作能力,将知识从书面理论层次提升到动手实践操作层次,通过尝试和
分析培养编程逻辑思维能力,并在其中找到属于自己的方法。
3. 通过课程设计,加深对《数据结构》课程所学知识的理解。
二 需求分析
1、输入数据需求分析
用户可以输入自己想要编码的字符串;并且程序可从相应的 EnglishPassage.txt 文档
中读取信息。
2、输出数据需求分析
用户可以在运行界面清晰明了的看到每种选择。并且程序可以将字符频率,编码后的
结果以及译码后的结果输出到屏幕上。
3、程序功能需求分析
(1)菜单选择功能:该程序包含主次两个菜单;向用户输出菜单选择页面,让用户能
够清晰的看到本程序所包含的各项功能,用户根据菜单提示选择输入执行相应的功能,当
用户输入不合法时提示用户。
(2)统计字符及其频率功能:用户可以输入自己想要编码的字符串或者选择从文件中
读取,该字符串必须含有字母,否则系统会提示输入有误。然后统计该字符串中每种字符
及其出现的频率。
(3)形成编码表功能:根据建立的哈夫曼树,程序会生成编码表。该编码表会被输出
到屏幕并且保存在 Code.txt 文件中。
(4)编码功能:形成编码表之后,程序会将字符串根据该编码表生成编码显示在屏幕
中并写入 ResultFile.txt 文件中。
(5)译码功能:程序可以将 ResultFile.txt 文件中的编码翻译成可读的字符串显示在屏
幕上并写入 translate.txt 文件中。
三 概要设计
1、流程图
整个哈夫曼编码系统的流程如图 1 所示。
1
《数据结构》课程设计
主菜单
文件读取
退出
非法
合法
提示有误
次菜单
结束
统计字符频率
编码表
编码
译码
返回主菜单
显示出现字符
及频率
显示每个字符
对应编码
显示编码结果
图 1.系统流程图
(1)主菜单
当程序开始运行时,用户会先看到主菜单。主菜单有三个选项,分别为用户输入,文
件读取以及退出系统;
(2)选择输入
当用户选择输入时系统会提示用户输入文本并进入次菜单。在次菜单中有五个选项,
分别为统计字符及其频率,构建编码表,编码和译码以及返回主菜单。用户每做一个选择
(除去返回主菜单),程序执行相应的命令后,按下任意键继续,程序则会返回到次菜
单,让用户进行下一步选择;
(3)选择从文件读取
当用户选择从文件读取时,读取完毕之后会显示次菜单。同样,该次菜单也有五个选
项,与第(2)项中描述内容相同。用户每做一个选择(除去返回主菜单),程序执行完毕
后会再次返回次菜单,让用户进行下一步操作;
(4)退出
当用户在次菜单中选择返回主菜单时,会显示主菜单,用户可在此时选择退出程序,
或者再次进入程序进行编码等操作。用户退出后,程序结束。
2
《数据结构》课程设计
2、模块功能
(1)统计字符及其频率
可以统计用户输入的字符种类以及对应的频率或者是 D 盘下名为 TheHuffmanTree 文件
内 EnglishPassage.txt 中的字符种类以及对应的频率。可以统计的字符包括各种符号,字
母,空格以及数字。并且可以区分英文字母的大小写。同时可以在用户进行非法输入时,
提示用户。
(2)构建哈夫曼树
根据统计得出的字符频率,利用我们已经构造好的数据结构最小堆构建哈夫曼树。
(3)得到编码表
得到一颗哈夫曼树以后用 DFS 来遍历这颗二叉树,得到每个叶子结点对应的编码,并
将这个叶子节点对应的字符和所对应的编码记录且保存。然后将编码写入文件 Code.txt,
同时在屏幕输出。
(4)编码
如果是选择从键盘输入的话,输入内容会存到 KeyBoard.txt 文件中;如果选择从文件
读取的话,是从 EnglishPassage.txt 中读取。读取我们需要编码的文本文件,将该文件中
的内容转化为对应的编码写入到 ResultFile.txt 文件中,并将结果输出到屏幕上。
(5)译码
读取 ResultFile.txt 文件中的编码,利用已经构造好的哈夫曼树去翻译该编码。将翻
译后的结果显示在屏幕上并保存在 translate.txt 文件中。
四 详细设计
1、统计字符及其频率
该功能通过 ReadFromFile(char *str)函数去读取 str 这个文件里面的字符,每次读取
一个字符,并用 Map 去记录每个字符所对应的频率。比如读取一个字符 a,那么就令
Map['a']++。一直这样进行下去,直到文件读取完毕为止。这样就可以得到每个字符所对
应的频率,为我们后面构造哈夫曼树做好准备。具体实现过程如下:首先定义一个字符型
变量 ch,再定义一个输入文件流的对象 in。使用 in.open(str,ios::in)用只读的方式打
开 str 这个文件。使用 while(!in.eof())循环,当文件没有读取完毕就一直读取并且每次
读取一个字符。令 ch=in.get()来读取文件中的字符,读取字符之后使用 Map[ch]++来统
计字符个数,其中 Map 是一个 char 型到 int 型的映射。如果文件读取完毕则退出 while 循
环,并用 in.close()关闭文件。如果文件没有读完,则继续执行 while 循环里的语句,读
取字符,统计字符频率直到文件读取完毕,关闭文件。
2、构建哈夫曼树的过程
(1)假设八个结点的权值大小如图 2 所示,从 19,21,2,3,6,7,10,32 中选择两
个权值最小的结点。选中 2,3,同时算出这两个结点的和 5,如图 3 所示。
图 2.八个结点的权值
3
《数据结构》课程设计
图 3.选出 2 和 3 之后
(2)从 19,21,6,7,10,32,5 中选出两个权值最小的结点,如图 4 所示。选中 5,
6。同时计算出它们的和 11 如图 4 所示。
图 4.选出 5 和 6 之后
(3)从 19,21,7,10,32,11 中选出两个权值最小的结点。选中 7 和 10。同时计算
出它们的和为 17。(这时选出的两个数字都不是已经构造好的二叉树里面的结点,所以要
另开一棵二叉树)如图 5 所示。
图 5.选出 7 和 10 之后
4
《数据结构》课程设计
(4)从 19,21,11,17,32 中选出两个权值最小的点。选中 11,17,并计算出它们的
和 28。如图 6 所示。
图 6.选出 11 和 17 之后
(5)从 19,21,28,32 中选出两个权值最小的点。选中 19,21 并计算出它们的和
40。另起一颗二叉树。如图 7 所示。
图 7.选出 19 和 21 之后
(6)从 32,28,40 中选出两个权值最小的结点。选中 32,28。同时计算出它们的和
60。如图 8 所示。
图 8.选出 32 和 28 之后
5
剩余33页未读,继续阅读
资源评论
xxpr_ybgg
- 粉丝: 6506
- 资源: 3万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功