haffmanwindow.java

有独立的窗口 输入字符数以及权值 实现哈弗曼编码

import java.awt.EventQueue;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.FocusEvent;
import java.awt.event.FocusListener;
import java.util.Timer;
import java.util.TimerTask;

import javax.swing.JButton;

import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JTextArea;
import javax.swing.JTextField;

public class HaffManWindow implements FocusListener {

	private JTextField nodeWightText;
	private JTextArea textArea;
	private JTextField nodeNumText;
	private JFrame frame;
	private JLabel statusLabel;
	private boolean isLegal = true;

	public static void main(String args[]) {
		EventQueue.invokeLater(new Runnable() {
			public void run() {
				try {
					HaffManWindow window = new HaffManWindow();
					window.frame.setVisible(true);
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		});
	}

	public HaffManWindow() {
		createContents();
	}

	/**
	 * Initialize the contents of the frame
	 */
	private void createContents() {
		frame = new JFrame();
		frame.getContentPane().setLayout(null);
		frame.setBounds(100, 100, 453, 307);
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

		final JLabel nodeNumLabel = new JLabel();
		nodeNumLabel.setText("结点数:");
		nodeNumLabel.setBounds(10, 10, 42, 18);
		frame.getContentPane().add(nodeNumLabel);

		nodeNumText = new JTextField();
		nodeNumText.setBounds(58, 8, 39, 22);
		nodeNumText.setToolTipText("输入大于等于0的整数.");
		nodeNumText.addFocusListener(this);
		frame.getContentPane().add(nodeNumText);

		final JLabel nodeWightLabel = new JLabel();
		nodeWightLabel.setText("权值：");
		nodeWightLabel.setBounds(113, 10, 39, 18);
		frame.getContentPane().add(nodeWightLabel);

		textArea = new JTextArea();
		textArea.setBounds(10, 76, 413, 146);
		textArea.setToolTipText("各结点的哈夫曼编码.");
		frame.getContentPane().add(textArea);

		final JLabel label_2 = new JLabel();
		label_2.setText("输出：");
		label_2.setBounds(10, 43, 52, 18);
		frame.getContentPane().add(label_2);

		nodeWightText = new JTextField();
		nodeWightText.setToolTipText("输入各结点的权值以逗号隔开");
		nodeWightText.setBounds(158, 8, 265, 22);
		nodeWightText.addFocusListener(this);
		frame.getContentPane().add(nodeWightText);

		statusLabel = new JLabel();
		statusLabel.setBounds(10, 236, 328, 27);
		frame.getContentPane().add(statusLabel);

		final JButton button = new JButton();
		button.addActionListener(new ActionListener() {
			public void actionPerformed(final ActionEvent e) {
				if (e.getSource() == button && isLegal == true) {
					statusLabel.setText("");
					int n = Integer.parseInt(nodeNumText.getText());
					HaffmanTree myHaff = new HaffmanTree(n);					         String[]weightStr=nodeWightText.getText().split(",");
					if(weightStr.length!=n)
						return;
					int[] weight = new int[weightStr.length];
					for (int i = 0; i < weightStr.length; i++) {
						weight[i] = Integer.parseInt(weightStr[i]);
					}
					HaffNode[] node = new HaffNode[2 * n + 1];
					Code[] haffCode = new Code[n];

					myHaff.haffman(weight, node);
					myHaff.haffmanCode(node, haffCode);
					StringBuffer strBuf = new StringBuffer();
				   for (int i = 0; i < n; i++) 
{strBuf.append("Weight="+haffCode[i].weight+"Code=");
						for (int j = haffCode[i].start + 1; j < n; j++)
							strBuf.append(haffCode[i].bit[j]);
						strBuf.append("\n");
					}
					textArea.setText(strBuf.toString());
				}
			}
		});
		button.setText("编码");
		button.setBounds(344, 235, 79, 28);
		frame.getContentPane().add(button);

	}

	
	public void focusGained(FocusEvent e) {
		isLegal=true;
	}


	public void focusLost(FocusEvent e) {
		if (e.getSource() == nodeNumText) {
			String nodeNum = nodeNumText.getText();
			boolean is = nodeNum.matches("^[0-9]*[1-9][0-9]*$");
			if (is == false) {
				statusLabel.setText("结点数不正确,请输入大于0的整数！");
				Timer timer = new Timer();
				timer.schedule(new TimerTask() {
					@Override
					public void run() {
						statusLabel.setText("");
					}
				}, 5000);
				isLegal = false;
			}

		}
		if (e.getSource() == nodeWightText) {
			String weightStr = nodeWightText.getText();
			boolean isMatch = weightStr.matches("(\\d\\,)*\\d");
			if (isMatch == false) {
				statusLabel.setText("权值的数据的格式不正确！");
				Timer timer = new Timer();
				timer.schedule(new TimerTask() {
					@Override
					public void run() {
						statusLabel.setText("");
					}
				}, 5000);

				isLegal = false;
			}
		}

	}

	class Code { // 哈夫曼编码类
		int[] bit; // 数组
		int start; // 编码的起始下标
		int weight; // 字符的权值

		public Code(int n) {
			bit = new int[n];
			start = n - 1;
		}
	}

	class HaffNode { // 哈夫曼树的结点类
		int weight; // 权值
		int flag; // 标记
		int parent; // 双亲结点下标
		int leftChild; // 左孩子下标
		int rightChild; // 右孩子下标

		public HaffNode() {
		}
	}

	class HaffmanTree {
		static final int maxValue = 10000; // 最大权值
		private int nodeNum; // 叶结点个数

		public HaffmanTree(int n) {
			nodeNum = n;
		}

		public void haffman(int[] weight, HaffNode[] node) {
			// 构造权值为weight的哈夫曼树haffTree
			int m1, m2, x1, x2;
			int n = nodeNum;

			// 哈夫曼树haffTree初始化。n个叶结点的哈夫曼树共有2n-1个结点
			for (int i = 0; i < 2 * n - 1; i++) {
				HaffNode temp = new HaffNode();
				if (i < n)
					temp.weight = weight[i];
				else
					temp.weight = 0;
				temp.parent = 0;
				temp.flag = 0;
				temp.leftChild = -1;
				temp.rightChild = -1;
				node[i] = temp;
			}

			// 构造哈夫曼树haffTree的n-1个非叶结点
			for (int i = 0; i < n - 1; i++) {
				m1 = m2 = maxValue;
				x1 = x2 = 0;
				for (int j = 0; j < n + i; j++) {
					if (node[j].weight < m1 && node[j].flag == 0) {
						m2 = m1;
						x2 = x1;
						m1 = node[j].weight;
						x1 = j;
					} else if (node[j].weight < m2 && node[j].flag == 0) {
						m2 = node[j].weight;
						x2 = j;
					}
				}

				// 将找出的两棵权值最小的子树合并为一棵子树
				node[x1].parent = n + i;
				node[x2].parent = n + i;
				node[x1].flag = 1;
				node[x2].flag = 1;
				node[n + i].weight = node[x1].weight + node[x2].weight;
				node[n + i].leftChild = x1;
				node[n + i].rightChild = x2;
			}
		}

		public void haffmanCode(HaffNode[] node, Code[] haffCode) {
			// 由哈夫曼树haffTree构造哈夫曼编码haffCode
			int n = nodeNum;
			Code cd = new Code(n);
			int child, parent;

			// 求n个叶结点的哈夫曼编码
			for (int i = 0; i < n; i++) {
				cd.start = n - 1; // 不等长编码的最后一位为n-1
				cd.weight = node[i].weight; // 取得编码对应的权值
				child = i;
				parent = node[child].parent;

				while (parent != 0) {
					// 由叶结点向上直到根结点循环
					if (node[parent].leftChild == child)
						cd.bit[cd.start] = 0; // 左孩子结点编码0
					else
						cd.bit[cd.start] = 1; // 右孩子结点编码1
					cd.start--;
					child = parent;
					parent = node[child].parent;
				}

				Code temp = new Code(n);

				// 保存叶结点的编码和不等长编码的起始位
				for (int j = cd.start + 1; j < n; j++)
					temp.bit[j] = cd.bit[j];
				temp.start = cd.start;
				temp.weight = cd.weight;
				haffCode[i] = temp;
			}
		}

	}
}