2019獨(dú)角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>

package org.loda.greedy;import org.junit.Test; import org.loda.structure.MinQ;/*** * @ClassName: HuffmanCoding * @Description: 哈夫曼編碼 * @author minjun * @date 2015年5月21日 上午12:04:02 **/ public class HuffmanCoding {@Testpublic void huffmanCoding(){String text="ABRACADABRA!";MinQ<Node> minQ=getMinQFromText(text);Node root=getRoot(minQ);printTree(root,"");}/*** * @Title: printTree * @Description: 打印哈夫曼編碼后的字符編碼鍵值對(duì) * @param @param x* @param @param str 設(shè)定文件 * @return void 返回類型 * @throws*/private void printTree(Node x,String str) {if(x.left==null&&x.right==null){System.out.println("字符"+x.c+"\t——>編譯碼\t"+str);return;}printTree(x.left,str+"0");printTree(x.right,str+"1");}/*** * @Title: getRoot * @Description: 構(gòu)造哈夫曼樹，并返回根節(jié)點(diǎn) * @param @param minQ* @param @return 設(shè)定文件 * @return Node 返回類型 * @throws*/private Node getRoot(MinQ<Node> minQ) {//保證本次迭代前隊(duì)列至少有兩個(gè)元素，不然兩次poll取出元素會(huì)報(bào)錯(cuò)while(minQ.size()>1){//選出當(dāng)前最優(yōu)解（即選出目前最小的兩個(gè)節(jié)點(diǎn)，為其組合父親節(jié)點(diǎn)，以便使得優(yōu)先隊(duì)列的元素不斷組合成一棵二叉樹）Node x=minQ.poll();Node y=minQ.poll();//創(chuàng)建兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)Node node=new Node(x.freq+y.freq,'\0');//將父節(jié)點(diǎn)與兩個(gè)子節(jié)點(diǎn)組合node.left=x;node.right=y;//將組合完成的父節(jié)點(diǎn)添加到哈弗曼樹中minQ.offer(node);}//取出哈夫曼樹的根節(jié)點(diǎn)return minQ.poll();}/*** * @Title: getMinQFromText * @Description: 統(tǒng)計(jì)文本串中字符出現(xiàn)頻率（次數(shù)），并以出現(xiàn)頻率小到到排序（添加到優(yōu)先隊(duì)列） * @param @param text* @param @return 設(shè)定文件 * @return MinQ<Node> 返回類型 * @throws*/private MinQ<Node> getMinQFromText(String text) {MinQ<Node> minQ=new MinQ<Node>();int R=256;Node[] nodes=new Node[R];for(int i=0;i<text.length();i++){if(nodes[text.charAt(i)]!=null){nodes[text.charAt(i)].freq++;}else{nodes[text.charAt(i)]=new Node(1,text.charAt(i));}}for(Node node:nodes){if(node!=null){minQ.offer(node);}}return minQ;}class Node implements Comparable<Node>{//訪問頻率int freq;//字母char c;//左右節(jié)點(diǎn)Node left;Node right;public Node(int freq, char c) {super();this.freq = freq;this.c = c;}@Overridepublic int compareTo(Node o) {return this.freq-o.freq;}@Overridepublic String toString() {return "Node [freq=" + freq + ", c=" + c + "]";}} }輸出內(nèi)容為：字符A ——>編譯碼 0 字符D ——>編譯碼 100 字符! ——>編譯碼 1010 字符C ——>編譯碼 1011 字符R ——>編譯碼 110 字符B ——>編譯碼 111

上面代碼中使用到的優(yōu)先隊(duì)列MinQ是我在該系列博客中已經(jīng)放出來過的，可以參考http://my.oschina.net/u/1378920/blog/417175這個(gè)地址

轉(zhuǎn)載于:https://my.oschina.net/u/1378920/blog/417471

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的算法导论——贪心算法：哈夫曼编码（霍夫曼编码）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。