课程设计---哈夫曼树的编码与解码(Java详解)

目录

一.设计任务&&要求:

二.方案设计报告:

2.1 哈夫曼树编码&译码的设计原理:

2.3设计目的:

2.3设计的主要过程:

2.4程序方法清单:

三.整体实现源码:

四.运行结果展示:

五.总结与反思:


一.设计任务&&要求:

题目要求:测试数据是一段任意的英文,也可以是一段完整的中文,采用哈夫曼算法进行编码,可输出对应的字符编码的解码

哈夫曼编码是一种最优变长码,即带权路径最小。这种编码有很强的应用背景,是数据压缩中的一个重要理论依据。对输入的一串文字符号实现哈夫曼编码,再对哈夫曼编码生成的代码串进行译码,输出字符串。要求完成以下功能:

1.针对给定的字符串,建立哈夫曼树。

2.生成哈夫曼编码。

3.对编码字符串译码

二.方案设计报告:

2.1 哈夫曼树编码&译码的设计原理:

  • 哈夫曼编译码器的主要功能是先建立哈夫曼树,然后利用建好的哈夫曼树生成哈夫曼编码后进行译码。在数据通信中,通常需要将传送文字转换成由二进制字符0,1组成的二进制串,称之为编码。构建一个哈夫曼树,设定哈夫曼树中的左分支为0,右分支代表1,则从根结点到每个叶子节点所经过的路径组成的0和1的序列便为该节点对应字符的编码,称之为哈夫曼编码。最简单的二进制编码方式是等长编码。若采用不等长编码,让出现频率高的字符具有较短的编码,让出现频率低的字符具有较长的编码,这样可以有效缩短传送文字的总长度。哈夫曼树则是用于构造使编码总长最短,最节省空间成本的编码方案。
  • 2.3设计目的:

  • (1) 巩固和加深对数据结构课程所学知识的理解,了解并掌握数据结构与算法的设计方法;
    (2) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;
    (3) 提高综合运用所学的理论知识和方法,独立分析和解决问题的能力;
    (4) 训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的工作方法和作风;
    (5) 培养查阅资料,独立思考问题的能力。

2.3设计的主要过程:

     1.哈夫曼树叶子节点的创建

叶子节点需要存储字符,及其出现的频率,指向左右子树的指针和将来字符所编码成的二进制数字。这里用一个静态内部来来初始化树的叶子节点:

  //用一个静态内部类来初始化树的节点static class Node{char ch;     //记录字符int freq;    //统计每个字符出现的频次Node left;Node right;String code;  //编码public Node(char ch) {this.ch = ch;}public Node(int freq, Node left, Node right) {this.freq = freq;this.left = left;this.right = right;}//判断是否是叶子节点->哈夫曼树是满二叉树boolean isLeaf(){return left == null;}public char getCh() {return ch;}public void setCh(char ch) {this.ch = ch;}public int getFreq() {return freq;}public void setFreq(int freq) {this.freq = freq;}//重写的toString 方法只需要打印字符和其对应的频次即可@Overridepublic String toString() {return "Node{" +"ch=" + ch +", freq=" + freq +'}';}}

      2.构建哈夫曼树

 构建过程:首先要统计每个字符出现的频率①.将统计了出现频率的字符,放入优先级队列中,利用优先级队列的特点,将字符按照出现的频率从小到大排序②.每次出队两个频次最低的元素,给它们找一个父亲节点③.将父亲节点放入队列中,重复②~③两个步骤④.当队列中只剩一个元素时,哈夫曼树就构建完了 

 //构造哈夫曼树//->由于这里是一个自定义的类,我们需要传入比较器,按照节点的频次进行比较PriorityQueue<Node> q = new PriorityQueue<>(//通过Comparator 的方法来获得Node节点的其中一个属性Comparator.comparingInt(Node::getFreq));for(Node node : hash.values()){q.offer(node);}while(q.size() >= 2){Node x = q.poll();Node y = q.poll();int freq = x.freq + y.freq;q.offer(new Node(freq,x,y));}

       3.哈夫曼编码

通过将每个叶子节点保存好的字符编码利用StringBuilder中的append()方法拼接起来后返回即可

 //编码操作:public String encode(){char[] chars = str.toCharArray();StringBuilder sb = new StringBuilder();for(char c : chars){sb.append(hash.get(c).code);}return sb.toString();}

     4.哈夫曼译码

 从根节点开始,寻找数字对应的字符编码,如果是0向右走,如果是数字1向左走,如果没有走到头(一个字符的编码结尾),每一步数字的索引cur++,每找到一个编码字符,在将node重置为根节点,接着重个节点开始继续往下寻找,一直找到字符串末尾即可

 /***  从根节点开始,寻找数字对应的字符*  数字是0 向右走,数字是1 向左走*  如果没有走到头,每一步数字的索引 cur++*  走到头就可以 找到编码字符,再将node 重置为根节点* @param str* @return*///解码操作:public String decode(String str){char[] chars = str.toCharArray();StringBuilder sb = new StringBuilder();int cur = 0;Node node = root;while(cur < chars.length){if(!node.isLeaf()){//非叶子节点if(chars[cur] == '0'){//向左走node = node.left;}else if(chars[cur] == '1'){//向右走node =node.right;}//每走完一步 cur++;cur++;if(node.isLeaf()){sb.append(node.ch);//每找到一个叶子节点,就重置后再次查找,直到遍历完整个数组node = root;}}}return sb.toString();}
  • 大致模块图:

设计流程图:

2.4程序方法清单:

①.构造哈夫曼树:public HuffmanTree(){

}//这里我选择在函数的构造方法中将哈夫曼树给先构造完

②.编码:public String encode(){};

③.解码:pulbic String decode(){};

④.找到编码,并计算其对应的bit位:private int findCode(Node node,StringBuilder code){};

⑤.打印菜单:menu(){};

⑥.测试函数:main(){};

模块展示:

三.整体实现源码:

import java.util.*;public class HuffmanTree {//用一个静态内部类来初始化树的节点static class Node{char ch;     //记录字符int freq;    //统计每个字符出现的频次Node left;Node right;String code;  //编码public Node(char ch) {this.ch = ch;}public Node(int freq, Node left, Node right) {this.freq = freq;this.left = left;this.right = right;}//判断是否是叶子节点->哈夫曼树是满二叉树boolean isLeaf(){return left == null;}public char getCh() {return ch;}public void setCh(char ch) {this.ch = ch;}public int getFreq() {return freq;}public void setFreq(int freq) {this.freq = freq;}//重写的toString 方法只需要打印字符和其对应的频次即可@Overridepublic String toString() {return "Node{" +"ch=" + ch +", freq=" + freq +'}';}}String str;Node root;Map<Character,Node> hash = new HashMap<>();public HuffmanTree(){}public HuffmanTree(String str){this.str = str;//统计字符出现的频次char[] chars = str.toCharArray();for(char ch : chars){if(!hash.containsKey(ch)){hash.put(ch,new Node(ch));}Node node = hash.get(ch);node.freq++;}for(Node node : hash.values()){System.out.println(node);}//构造哈夫曼树//->由于这里是一个自定义的类,我们需要传入比较器,按照节点的频次进行比较PriorityQueue<Node> q = new PriorityQueue<>(//通过Comparator 的方法来获得Node节点的其中一个属性Comparator.comparingInt(Node::getFreq));for(Node node : hash.values()){q.offer(node);}while(q.size() >= 2){Node x = q.poll();Node y = q.poll();int freq = x.freq + y.freq;q.offer(new Node(freq,x,y));}root = q.poll();//System.out.println(root);//计算每个字符的编码 以及其一共包含的bit位System.out.println("输出编码信息:");int sum = findCode(root,new StringBuilder());for(Node node : hash.values()){//打印节点及其编码信息System.out.println(node + " " + node.code);}System.out.println("总共占有的bit位是:" + sum);}//找到编码,并计算其对应的bit位private int findCode(Node node,StringBuilder code){int sum = 0;if(node.isLeaf()){//找到编码 并计算字符串编码后所占的bitsnode.code = code.toString();sum = node.freq * code.length();}else{sum += findCode(node.left,code.append("0"));code.deleteCharAt(code.length() - 1);sum += findCode(node.right,code.append("1"));code.deleteCharAt(code.length() - 1);}return sum;}//编码操作:public String encode(){char[] chars = str.toCharArray();StringBuilder sb = new StringBuilder();for(char c : chars){sb.append(hash.get(c).code);}return sb.toString();}/***  从根节点开始,寻找数字对应的字符*  数字是0 向右走,数字是1 向左走*  如果没有走到头,每一步数字的索引 cur++*  走到头就可以 找到编码字符,再将node 重置为根节点* @param str* @return*///解码操作:public String decode(String str){char[] chars = str.toCharArray();StringBuilder sb = new StringBuilder();int cur = 0;Node node = root;while(cur < chars.length){if(!node.isLeaf()){//非叶子节点if(chars[cur] == '0'){//向左走node = node.left;}else if(chars[cur] == '1'){//向右走node =node.right;}//每走完一步 cur++;cur++;if(node.isLeaf()){sb.append(node.ch);//每找到一个叶子节点,就重置后再次查找,直到遍历完整个数组node = root;}}}return sb.toString();}static final int all_block_nums = 100;public static void memu() throws InterruptedException {//菜单加载页面for(int i = 0;i < all_block_nums;i++){System.out.printf("\r[%d%%]>",i*100/(all_block_nums-1));for(int j = 1;j <= i*20/(all_block_nums);j++){System.out.print("▉");Thread.sleep(2);}}System.out.println();System.out.println("-------------------------------------------");System.out.println("----------                     ------------");System.out.println("--------    欢迎使用哈夫曼编码      ----------");System.out.println("---------     1.编码与解码          ---------");System.out.println("----------    0.退出              ----------");System.out.println("-------------------------------------------");}public static void main(String[] args) throws InterruptedException {Scanner sc = new Scanner(System.in);while(true){memu();String str = "0000";System.out.println("请选择:");int input = sc.nextInt();switch (input){case 0:System.out.println("你选择了退出程序~~~");break;case 1 :System.out.println("你选择了编码与解码");System.out.println("请输入要编码的字符串:");String in = sc.next();HuffmanTree huffmanTree = new HuffmanTree(in);str = huffmanTree.encode();System.out.println("编码后的字符串为:");System.out.println(str);System.out.println("将刚才编码好的字符串进行解码:");String cur = huffmanTree.decode(str);System.out.println("解码后的字符串:");System.out.println(cur);}if(input == 0) break;}}
}

四.运行结果展示:

五.总结与反思:

这次课程设计的心得体会通过实践我的收获如下:
① 巩固和加深了对数据结构的理解,提高综合运用本课程所学知识的能力。
② 培养了我选用参考书,查阅手册及文献资料的能力。培养独立思考,深入研究,分析问题、解决问题的能力。
③ 通过实际编译系统的分析设计、编程调试,掌握应用软件的分析方法和工程设计方法。
④ 通过课程设计,培养了我严肃认真的工作作风,逐步建立正确的生产观念、经济观念和全局观念。

通过本次数据结构的课设计,我学习了很多在上课没懂的知识,并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解,更巩固了课堂中学习有关于哈夫曼编码的知识,真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做,而是首先要先对它有个大概的了解,接着再详细地分析每一步怎么做,无论自己以前是否有处理过相似的问题,只要按照以上的步骤,必会顺利地做出来。

结语: 写博客不仅仅是为了分享学习经历,同时这也有利于我巩固知识点,总结该知识点,由于作者水平有限,对文章有任何问题的还请指出,接受大家的批评,让我改进。同时也希望读者们不吝啬你们的点赞+收藏+关注,你们的鼓励是我创作的最大动力!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/354445.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

pytorch库 02 Anaconda、Jupyter常用命令及操作

文章目录 一、Anaconda Prompt1、conda常用命令2、pip常用命令 二、Jupyter1、Jupyter常用命令及基本操作2、Jupyter代码补全插件安装 一、Anaconda Prompt 1、conda常用命令 下列命令可以在Anaconda Prompt中输入。 清屏&#xff1a; cls 查看帮助&#xff1a; conda -h 查…

【MySQL统计函数count详解】

MySQL统计函数count详解 1. count()概述2. count(1)和count(*)和count(列名)的区别3. count(*)的实现方式 1. count()概述 count() 是一个聚合函数&#xff0c;返回指定匹配条件的行数。开发中常用来统计表中数据&#xff0c;全部数据&#xff0c;不为null数据&#xff0c;或…

【尝鲜】SpringCloudAlibaba AI 配置使用教程

1、环境配置 maven依赖pom.xml 注意配置远程仓库&#xff0c;原因见&#xff1a;Unresolved dependency: ‘org.springframework.ai:spring-ai-core:jar:0.8.1’ <dependencies><!--Base--><dependency><groupId>org.springframework.boot</group…

【Python机器学习实战】 | Lasso回归和弹性网回归详细分析研究

&#x1f3a9; 欢迎来到技术探索的奇幻世界&#x1f468;‍&#x1f4bb; &#x1f4dc; 个人主页&#xff1a;一伦明悦-CSDN博客 ✍&#x1f3fb; 作者简介&#xff1a; C软件开发、Python机器学习爱好者 &#x1f5e3;️ 互动与支持&#xff1a;&#x1f4ac;评论 &…

自然语言处理概述

目录 1.概述 2.背景 3.作用 4.优缺点 4.1.优点 4.2.缺点 5.应用场景 5.1.十个应用场景 5.2.文本分类 5.2.1.一般流程 5.2.2.示例 6.使用示例 7.总结 1.概述 自然语言处理&#xff08;NLP&#xff09;是计算机科学、人工智能和语言学的交叉领域&#xff0c;旨在实…

Charles代理https接口到本地

一、操作手册 1、安装工具 1.1、安装代理软件Charles 软件下载地址&#xff1a;Download a Free Trial of Charles • Charles Web Debugging Proxy 1.2、安装https代理插件&#xff1a;&#xff08;有问题自行百度解决&#xff09; 2、配置策略 以下以https接口为例&…

JAVAEE之网络原理(2)_传输控制协议(TCP)的连接管理机制,三次握手、四次挥手,及常见面试题

前言 在上一节中&#xff0c;我们简单介绍了 TCP 协议的相关概念和格式&#xff0c;而且还介绍了TCP 协议原理中的 确认应答机制、超时重传机制&#xff0c;在本节中我们将会继续介绍 TCP协议原理中的其他机制。 连接管理机制&#xff08;安全机制&#xff09; 在正常情况下&…

QT基础 - QMainWindow主窗口

目录 零. 简介 一. 菜单栏 二. 工具栏 三. 状态栏 四. 可停靠区域 五. 总结 零. 简介 QMainWindow 是 Qt 中用于构建主窗口的类。 它通常包含以下几个主要部分&#xff1a; 菜单栏&#xff1a;用于提供各种操作选项。工具栏&#xff1a;放置常用的操作按钮。中心区域&…

气体泄露隐患多,佛山工业可燃气体报警器年检校准来帮忙

在佛山这座工业发达的城市&#xff0c;可燃气体报警器的应用日益广泛&#xff0c;涉及化工、冶金、石油等多个领域。 然而&#xff0c;长时间的使用和恶劣的工业环境可能导致报警器的性能下降&#xff0c;甚至出现误报或漏报的情况。 因此&#xff0c;定期对可燃气体报警器进…

win 打包java项目为exe一键部署,包括mysql和redis

需求&#xff1a;打包springboot项目在win系统下执行&#xff0c;并且要一键部署和开机启动 把所需的程序放在同一个文件夹 1.jdk文件夹&#xff1a;自己去下载&#xff0c;jdk8的话拿jre目录好了 2.mysql文件夹&#xff1a;是8.0.36版&#xff0c;270M精简版了 3.redis文件夹…

Apple - Authorization Services Programming Guide

本文翻译整理自&#xff1a;Authorization Services Programming Guide&#xff08;更新日期&#xff1a;2011-10-19 https://developer.apple.com/library/archive/documentation/Security/Conceptual/authorization_concepts/01introduction/introduction.html#//apple_ref/d…

【JavaEE 进阶(五)】SpringBoot日志

❣博主主页: 33的博客❣ ▶️文章专栏分类:JavaEE◀️ &#x1f69a;我的代码仓库: 33的代码仓库&#x1f69a; &#x1faf5;&#x1faf5;&#x1faf5;关注我带你了解更多进阶知识 目录 1.前言2.日志使用2.1打印日志2.2 门面模式(外观模式)2.3SLF4J框架2.4日志格式说明 3.Sl…

SQL注入-下篇

HTTP注入 一、Referer注入 概述 当你访问一个网站的时候&#xff0c;你的浏览器需要告诉服务器你是从哪个地方访问服务器的。如直接在浏览器器的URL栏输入网址访问网站是没有referer的&#xff0c;需要在一个打开的网站中&#xff0c;点击链接跳转到另一个页面。 Less-19 判…

Elasticsearch 认证模拟题 - 22

一、题目 索引 task 索引中文档的 fielda 字段内容包括了 hello & world&#xff0c;索引后&#xff0c;要求使用 match_phrase query 查询 hello & world 或者 hello and world 都能匹配该文档 1.1 考点 分词器 1.2 答案 # 创建符合条件的 task 索引&#xff0c;…

华为云与AWS负载均衡服务深度对比:性能、成本与可用性

随着云计算的迅速发展&#xff0c;企业对于云服务提供商的选择变得越来越关键。在选择云服务提供商时&#xff0c;负载均衡服务是企业关注的重点之一。我们九河云将深入比较两大知名云服务提供商华为云和AWS的负载均衡服务&#xff0c;从性能、成本和可用性等方面进行对比。 AW…

Blender:渲染输出

一、渲染设置 渲染设置界面&#xff1a; 渲染器选择切换 Cycles渲染器 【文档】 Cycles渲染目标&#xff1a; Cycles是Blender用于产品级渲染&#xff0c;基于物理的路径跟踪器。主要关注于影视质量&#xff0c;更高质量的外观它旨在提供易于使用以及准确的物理渲染结果具有艺术…

Ubuntu服务器搭建Git远程仓库

本文所述方法适用于小型团队在局域网环境中使用Git进行代码版本管理。 1. 安装Git 打开终端(Ctrl + Alt + T) ,输入以下命令: sudo apt update #更新软件包列表信息 sudo apt install git #安装Git 验证Git是否安装成功,可以查看Git版本: git --version 也需…

同三维T80002JEHV H.265高清解码器

同三维T80002JEHV H.265高清解码器 1路HDMI1路VGA解码输出&#xff0c;1/2/4画面分割或16路轮询显示 产品简介&#xff1a; 同三维T80002JEHV解码器使用Linux系统&#xff0c;支持VGA/HDMI二种接口同时输出&#xff0c;支持多流输入多流解码及多屏显示&#xff0c;具有完善的…

NET Core C# 中的Action委托:语法、用法和示例_2024-06-19

Action委托是一个内置的泛型委托类型。此委托使您的程序更具可读性和效率&#xff0c;因为您无需定义自定义委托&#xff0c;如以下示例所示。 它在 System 命名空间下定义。它没有输出参数&#xff0c;输入参数最少为 1 个&#xff0c;最多为 16 个。 Action委托通常用于具有…

【windows|004】BIOS 介绍及不同品牌电脑和服务器进入BIOS设置的方法

&#x1f341;博主简介&#xff1a; &#x1f3c5;云计算领域优质创作者 &#x1f3c5;2022年CSDN新星计划python赛道第一名 &#x1f3c5;2022年CSDN原力计划优质作者 ​ &#x1f3c5;阿里云ACE认证高级工程师 ​ &#x1f3c5;阿里云开发者社区专家博主 &#x1f48a;交流社…