`
wojiaolongyinong
  • 浏览: 74756 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

哈夫曼编码的自动生成

    博客分类:
  • Java
 
阅读更多


         经过4个版本,我的哈夫曼编码的自动生成做好了,但这只是发报机的第一步,但是感觉编码的自动

生成每一个版本都让我收获不少,前两个版本都是手动连接哈夫曼树,第三个版本是采用自动连接,但是

做的时候,做得过于复杂,采用了双数组,一个存储未挂在树上的字母及其频率对象,一个用来存储哈夫

曼树的临时节点,但是这样做过于复杂,所以错误难免。今天早上经过对于第三版本的删减,修改优化,

在第四版中,哈夫曼编码的自动生成成功了!

       在第四版中,只采用了一个数组,来存储临时节点,最终形成哈夫曼树,并且采用向上找双亲节点的

方式,生成每个叶节点的编码。具体代码解释,以及运行时的结果图如下:

 

哈夫曼树节点类的定义:

/**
 * 定义构造哈夫曼树的节点类
 * @author LONG 2013-04-05
 * @version V4.0
 *
 */
public class Node {
	private char values;		//在该节点存储的字母值
	private int number = 0;		//在该节点存储的字母的频率大小
	private Node left = null;	//定义该节点的属性左孩子节点
	private Node right = null;	//定义该节点的属性右孩子节点
	private Node parent = null;	//定义该节点的属性双亲节点

	//设置该节点在双亲节点的左边还是右边,如果在左边则添加字符1,如果在右边则添加字符0
	private String position = null;	
	
	/**
	 * 重写构造方法,在创建叶节点时调用
	 * @param values	传入的字母值
	 * @param number	字母的频率大小
	 */
	public Node(char values,int number){
		this.values = values;
		this.number = number;
	}
	
	/**
	 * 重写构造方法,在创建非叶节点时调用
	 * @param number
	 */
	public Node(int number){
		this.number = number;
	}
	
	/**
	 * 恢复系统默认的构造方法
	 */
	public Node(){}
	
	/**
	 * 返回该节点存储的字母
	 * @return
	 */
	public char getValues(){
		return values;
	}
	
	/**
	 * 返回该节点存储的字母的频率
	 * @return
	 */
	public int getNumber(){
		return number;
	}
	
	/**
	 * 设置该节点的左孩子
	 * @param left
	 */
	public void setLeft(Node left){
		this.left = left;
	}
	
	/**
	 * 设置该节点的右孩子
	 * @param right
	 */
	public void setRight(Node right){
		this.right = right;
	}
	
	/**
	 * 返回该节点的左孩子引用
	 * @return
	 */
	public Node getLeft(){
		return left;
	}
	
	/**
	 * 返回该节点的右孩子引用
	 * @return
	 */
	public Node getRight(){
		return right;
	}
	
	/**
	 * 设置该节点的父节点
	 * @param par
	 */
	public void setParent(Node par){
		this.parent = par;
	}
	
	/**
	 * 返回该节点的父节点的引用
	 * @return
	 */
	public Node getParent(){
		return parent;
	}
	
	/**
	 * 设置该节点是在双亲节点的右边还是左边,如果在左边则传入1否则传入0
	 * @param var
	 */
	public void setPosition(int var){
		this.position = "" + var;
	}
	
	/**
	 * 得到该节点是处于双亲节点的左边还是右边
	 * @return
	 */
	public String getPosition(){
		return position;
	}
}

 

哈夫曼编码的实现类:

/**
 * 实现哈夫曼树的主要类
 * @author LONG 2013-04-05
 * @version V4.0
 *在4.0版本中,希望在节点中添加新的属性,即指向父节点的引用,以及记录自己被添加时处于左右边分支
 *在节点中进行记录,最后通过由叶节点开始向上找自己的祖先,来得到自己的哈夫曼编码。
 *
 */
public class HuffmanTree {
	private Node[] leaf = null;	//设置该树的叶子节点数组,在创建对象时进行初始化
	private int length = 0;		//用于记录叶子节点的数组长度
	private int size = 0;		//用于记录用户指定的数组的长度
	private int count = 0;		//用于记录用户输入元素的个数
	
	/**
	 * 重写构造方法,设置创建对象时,指定该树叶子节点的个数,及所存储的字母个数
	 * @param size
	 */
	public HuffmanTree(int size){
		this.size = size;
		leaf = new Node[this.size];
	}
	
	/**
	 * 在叶子节点的数组中进行添加值
	 * @param values	添加进来的字母
	 * @param number	添加进来的字母频率
	 * 
	 * 该方法首先需要判断传进来的字母是否已经存在,
	 *然后还有数组是否已经存满,如果满足添加的条件,
	 * 然后才进行创建节点,添加进去。
	 */
	public void add(char values,int number){
		count++;//记录用户执行了多少次add方法,用来与用户指定的数组长度比较
		if(!isFull() && !isSame(values)){
			Node temp = new Node(values,number);
			leaf[length++] = temp;
		}
	}
	
	/**
	 * 生成哈夫曼编码与用户直接交流的方法,来确保类的封装性及安全性
	 */
	public void showCode(){
		if(isFull() && size == count){
			Node temp = showTree();
			showResult(temp);
		}else{
			System.out.println("请检查输入的字母,不能出现重复,以及指定的大小是否与添加的值个数相同!");
		}
	}
	
	/**
	 * 对初始化时判断存储的叶子节点数组是否已满,如果满了,则返回true,否则返回false
	 * @return
	 */
	private boolean isFull(){
		boolean theResult = true;
		if(length < leaf.length){	//说明数组未满
			theResult = false;
		}
		return theResult;
	}
	
	/**
	 * 对传入的字母与已存在叶子数组中的元素的字母相比较,如果相同,则返回true,否则返回false
	 * @param var
	 * @return
	 */
	private boolean isSame(char var){
		boolean theResult = false;
		for(int i = 0; i < length; i++){
			if(leaf[i].getValues() == var){
				theResult = true;
			}
		}
		return theResult;
	}
	
	/**
	 * 对传入的树的节点数组,按照节点中的频率由小到大进行冒泡排序,最后返回排好序的数组
	 * @param no
	 * @return
	 */
	private Node[] getNewNode(Node[] no){
		for(int i = 0; i < length; i++){
			for(int j = i + 1; j < length; j++){
				if(no[i].getNumber() > no[j].getNumber()){
					Node temp = no[i];
					no[i] = no[j];
					no[j] = temp;
				}
			}
		}
		return no;
	}
	
	/**
	 * 生成一颗哈夫曼树
	 */
	private Node showTree(){
		Node result = null;
		if(isFull()){	//首先判断是否元素已经填满

			//判断节点数组中含有元素的个数,如果为1,说明哈夫曼树已经建好
			while(length > 1){	

				//然后对于节点数组按照里面存储的频率大小进行排序,
				//那么就知道数组的前两位就是需要连接起来的
				leaf = getNewNode(leaf);

				//设置新的节点的频率为前两个元素的频率之和
				Node temp = new Node(leaf[0].getNumber() + leaf[1].getNumber());
				leaf[0].setParent(temp);//设置节点对双亲节点的引用
				leaf[1].setParent(temp);//设置节点对双亲节点的引用
				temp.setLeft(leaf[0]);//设置第一个元素为左孩子

				//因为该节点处于双亲节点的左边,所以传进的位置参数为1
				leaf[0].setPosition(1);

				temp.setRight(leaf[1]);//设置第二个元素为右孩子

				//因为该节点处于双亲节点的右边,所以传进的位置参数为0
				leaf[1].setPosition(0);
				length -= 2;	//将数组的长度减小2个单位

				//对数组进行移位,因为前两个元素已经被挂在新的节点上
				leaf = move(leaf,2);
				leaf[length++] = temp;//添加新的节点放在数组最后面,并将数组长度加1
			}
			result = leaf[length - 1];//得到最终数组中的唯一一个元素的引用
		}
		return result;
	}
	
	/**
	 * 对节点数组进行移位,按照传进来的跨度extent来对数组元素进行移动
	 * @param node	传进的需要移位的数组
	 * @param extent	传进的需要移位的跨度大小
	 * @return	返回完成移位的数组
	 */
	private Node[] move(Node[] node,int extent){		
		for(int i = 0; i < length; i++){
			node[i] = node[i + extent];
		}
		return node;
	}
	
	/**
	 * 遍历生成的哈夫曼树,输出叶节点上的字母的哈夫曼编码
	 * @param head
	 */
	private void showResult(Node head){
		if(head.getLeft() == null && head.getRight() == null){	//当找到叶节点时

			//首先输出叶节点上的字母
			System.out.print(head.getValues() + " 哈夫曼编码是:");	
			Node temp = head;	//创建动态节点变量指向此时的叶节点
			String posi = "";	//创建空字符串,用来保存字母的哈夫曼编码
			while(temp.getPosition() != null){//向上循环,找该节点的双亲,直到找到根节点
				
				//每找到一个节点,就将它的位置参数读取出来,添加进编码字符串
				posi = temp.getPosition() + posi;

				temp = temp.getParent();//然后再让该节点指向它的双亲节点
			}
			System.out.println(posi);	//最后输出哈夫曼编码
		}else{
			showResult(head.getLeft());
			showResult(head.getRight());
		}
	}
}

 

       那么我们可以看到,对于哈夫曼编码生成的主要部分已经完成,那么我们可以试着编写

如下简单的测试类,进行测试哈夫曼编码生成的效果。

 

测试部分:

/**
 * 该类用于测试哈夫曼树的生成情况
 * @author LONG 2013-04-05
 * @version V4.0
 *
 */
public class Manager {
	public static void main(String[] args){
		HuffmanTree hf = new HuffmanTree(6);
		hf.add('s',12);
		hf.add('a',2);
		hf.add('c',21);
		hf.add('b',7);
		hf.add('e',9);
		hf.add('f',11);
		hf.showCode();
	}
}

 

那么我们会得到如下所示结果:



 

 

      可以看到在控制台输出了哈夫曼编码的结果,在这个过程中,用户只需要指定需要存入的字母的个数,

以及将字母及其频率添加进去,就可以自动得到哈夫曼编码。

      但是用户如果输入有误,比如说添加的字母大于指定的字母数,或是小于指定的字母数,或是字母出

现重复,那么会有以下结果:

 

1.添加的字母大于指定的字母数



 

 

2.添加的字母小于指定的字母数

 



 

 

3.字母出现重复

 



 

 

至此,哈夫曼编码的自动生成OK了!下来就是对发报机的进一步研究。。。。。。

 

  • 大小: 105 KB
  • 大小: 103.5 KB
  • 大小: 103.6 KB
  • 大小: 103.3 KB
分享到:
评论

相关推荐

    哈夫曼编码以及解码实现

    在实际应用中,为了实现友好的用户界面,可以设计一个交互式的程序,用户可以在界面上输入字符,程序会自动计算出这些字符的哈夫曼编码。同时,程序还应提供解码功能,用户可以输入已编码的字符串,程序通过查找编码...

    哈夫曼编码解决UDP传输,可延伸做GUI界面

    通过GUI,用户可以方便地输入待压缩的数据,程序会自动进行哈夫曼编码,显示编码结果,并提供压缩数据的保存和解压缩功能。同时,GUI还可以展示编码过程和解码过程,帮助用户理解哈夫曼编码的工作原理。 为了实现...

    哈夫曼树生成程序(含源码)

    `a.exe`文件可能是编译后的可执行程序,用户可以直接运行该程序,输入待压缩的文本,程序会自动生成哈夫曼树并输出对应的哈夫曼编码。对于学习和理解哈夫曼编码和树的构建,`huffman.c`源码是一个很好的参考资料。 ...

    从文件读取字符串建立哈夫曼树并进行哈夫曼编码

    5. **编码字符串**:最后,使用生成的哈夫曼编码,将原始字符串转换为压缩后的哈夫曼编码字符串。为了方便解码,还需要保存字符编码的映射关系,通常是通过字典的形式。 在"数据结构_习题三"这个压缩包中,可能包含...

    哈夫曼编码译码

    用户需提供待编码的文本文件"english.txt",运行程序后,程序会自动生成源文件字符统计和对应的哈夫曼编码,并在指定目录下创建压缩文件"English.huf"和译文文件"e.txt"。 **测试结果** 实验结果显示,该系统能够...

    哈夫曼编码译码器

    一个完整的系统应具有以下功能: (1)I:初始化:从键盘读入字符集大小N,以及N个字符和N个权值,建立哈夫曼树,并将它保存在...(5)懒人模式,一键自动生成权值信息、哈夫曼编码及译码文件保存在源程序的根目录下。

    【C++】根据输入的字符串生成哈夫曼树, 并进行哈夫曼编码和解码

    /********************************************************************** * Description : create huffmanTree and huffmanCode by input string * and decode a 0、1 sequence by huffmanCode ...

    哈夫曼编码

    通过运行这个程序,用户可以输入具有特定频率分布的字符集,程序会自动生成哈夫曼树,并输出对应的哈夫曼编码表。同时,程序还提供了将已编码的数据进行解码的功能,以验证编码的正确性。 总结起来,哈夫曼编码是一...

    数据结构——哈夫曼编码

    3. **生成哈夫曼编码**:从哈夫曼树的根节点出发,左分支代表“0”,右分支代表“1”,沿着树向下遍历,直到到达叶节点,叶节点所对应的字符就是其哈夫曼编码。所有字符的编码都是唯一的,并且频繁出现的字符编码较...

    JiSuanQi.rar_哈夫曼编码

    - 根据描述,这个程序似乎提供了一个用户界面,用户可以输入字符频率,程序会自动生成哈夫曼树并给出编码。 - 用户还可以输入已编码的数字序列进行解码,如果输入的字符不在编码表中,程序会提示错误。 - 这种...

    哈夫曼编码和译码系统

    3. **生成哈夫曼编码**:从哈夫曼树的根节点出发,左分支代表0,右分支代表1,遍历树的路径就形成了每个符号的哈夫曼编码。 4. **编码数据**:将原始数据中的每个符号替换为其对应的哈夫曼编码,得到压缩后的数据。 ...

    哈夫曼编码译码器.docx

    整个哈夫曼树的构建与编码生成过程都是通过`HuffmanCoding`函数来完成的,在此过程中,系统还会输出每个字符的哈夫曼编码,以便于用户查看和理解编码细节。 在编码阶段,程序将根据构建好的哈夫曼树生成每个字符的...

    哈夫曼编码算法实现完整版.doc

    程序会自动生成哈夫曼树,并输出每个字符的哈夫曼编码。这样,当传输数据时,使用哈夫曼编码可以减少传输的位数,提高信道利用率,降低传输成本。 总结来说,这个实验是关于如何利用C++编程语言实现哈夫曼编码的...

    数据结构课程设计报告基于堆的哈夫曼编码问题.doc

    - 用户需求分析:设计出用户友好的接口,使得用户能输入文本,自动生成哈夫曼编码,并能够解码回原始文本。 3. **方案设计**: - 总体功能设计:包括输入处理、哈夫曼树构建、编码生成、解码功能以及用户交互界面...

    huffman编码java实现

    6. **写入Javadoc文档**:Javadoc是Java的一个工具,用于自动生成关于代码的文档,包括类、方法、变量的说明、参数、返回值、抛出的异常等。对于哈夫曼编码的Java实现,Javadoc文档会详细解释各个类和方法的功能、...

    信息论与编码课程设计(哈夫曼编码的分析与实现).pdf

    此外,MATLAB等编程语言可以用来实现哈夫曼编码,通过编程实现字符频率统计、哈夫曼树构建和编码生成。 在进行课程设计时,学生需要理解无失真信源编码的理论,掌握哈夫曼编码的基本步骤和优缺点,同时通过编程实现...

    基于Java的哈夫曼编码译码系统报告毕业论文.doc

    用户在输入框中输入要编码的文章,点击“转成哈夫曼编码”按钮,系统将自动进行编码操作,并展示编码结果。 综上所述,该毕业设计项目实现了一个基于Java的哈夫曼编码译码系统,利用哈夫曼算法对英文文本进行高效...

    哈夫曼编码和译码系统.docx

    哈夫曼编码是一种高效的数据压缩方法,主要用于优化通信和存储效率。它基于一种特殊的二叉树结构,称为哈夫曼树(Huffman Tree),通过构建这棵树,可以为每个字符或符号分配一个唯一的二进制编码,使得频繁出现的...

Global site tag (gtag.js) - Google Analytics