7-1 构造哈夫曼树 (40分)
输入一些单词及其出现的频度,构造一棵哈夫曼树,输出哈夫曼编码的平均码长。
输入格式:
输入N,表示有N个单词,以下N行,每一行表示一个单词及其频度。
输出格式:
平均码长用浮点数类型表示,保留小数点后5位。
输入样例:
在这里给出一组输入。例如:
11
The 1192
of 677
a 541
to 518
and 462
that 242
he 195
is 190
for 157
His 138
are 124
输出样例:
在这里给出相应的输出。例如:
3.10437
import java.text.DecimalFormat; import java.util.ArrayDeque; import java.util.Scanner; /** * JAVA中的对象类型本质上应该叫做 对象指针 类型。那么传统的对象类型呢?在JAVA里已经不见了踪影! * 既然没有了传统的对象类型,那么 对象指针变量 前面的*也就可以不要了。对象指针变量也就可以简称为对象变量了, * 反正也不会和其它概念混淆! 所有的对象变量都是指针,没有非指针的对象变量,想不用指针都不行,这就是指针的泛化和强化。 * 不叫指针了,就叫对象变量,这就是概念上的淡化和弱化。 没有了指针的加减运算,也没有了*、->等运算符,这是对指针的简单化。 */ //测试时复制还是指针指向 // Node node1=new Node(); // Node node2=new Node(); // node1.parent=node2; // if (node2.hashCode()==node1.parent.hashCode()){ // System.out.println("是指向"); // }else { // System.out.println("是复制"); // } public class Main { public static void main(String[] args) { //输入N,表示有N个单词,以下N行,每一行表示一个单词及其频度。 Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); Array array=new Array(n); for (int i=0;i<n;i++){ Node node=new Node(); node.data=scanner.next(); node.frequency=scanner.nextInt(); array.add(node); } System.out.println(new DecimalFormat(".00000").format(array.calculate(array.create()))); } private static class Array{ Node[] array; //此时数组中node的个数 int current=0; public Array(int n) { array=new Node[2*n]; } //向数组中加入结点 public void add(Node ... nodes){ if (nodes.length+current>array.length){ System.out.println("数组溢出"); } for (Node node:nodes){ array[current++]=node; } } //找到两个最小频率的结点 public Node[] findMin(){ if (array.length<2){ System.out.println("数组长度过短"); } Node node1=null; Node node2=null; Node[] temp=new Node[2]; for (int i=0;i<current;i++) { if (array[i].flag == false) { if (node1 == null ) { node1 = array[i]; } else if (node2 == null ) { node2 = array[i]; } else if (node1.frequency > array[i].frequency||node2.frequency > array[i].frequency) { if (node2.frequency>node1.frequency){ node2=array[i]; }else { node1=array[i]; } } } } temp[0]=node1; temp[1]=node2; return temp; } //建树 public Node create(){ for (int i=0;i<current;i++){ Node[] temp=findMin(); if (temp[0]==null&&temp[1]!=null){ return temp[1]; }else if (temp[1]==null&&temp[0]!=null){ return temp[0]; }else if (temp[1]!=null&&temp[0]!=null){ temp[0].flag=true; temp[1].flag=true; Node node=new Node(temp[0].frequency+temp[1].frequency); node.lchild=temp[0]; node.rchild=temp[1]; add(node); }else { System.out.println("数组中没数!!!"); return null; } } return null; } /** * 计算平均码长 * @param root 根节点 * @return 平均码长 */ public float calculate(Node root){ float total=0; //总频率 float count=0; ArrayDeque<Node> arrayDeque=new ArrayDeque<>(); arrayDeque.push(root); root.floor=0; while (!arrayDeque.isEmpty()){ Node temp=arrayDeque.poll(); if (temp.isLeaf()){ total+=temp.floor*temp.frequency; count+=temp.frequency; } if (temp.lchild!=null){ temp.lchild.floor=temp.floor+1; arrayDeque.push(temp.lchild); } if (temp.rchild!=null){ temp.rchild.floor=temp.floor+1; arrayDeque.push(temp.rchild); } } return total/count; } }; //建立node结点类 private static class Node{ String data=null; int frequency; Node lchild=null; Node rchild=null; //表示是否被遍历 Boolean flag=false; //存储层数 Integer floor=null; public Node() { } public Node(int frequency) { this.frequency = frequency; } /** * 判断是否是叶子结点 * @return 是则返回true,不是则返回false */ public boolean isLeaf(){ if (lchild==null&&lchild==null){ return true; }else return false; } } }
记录点滴,乐于分享,转载请注明出处
以梦为马,不负人生韶华,我们追梦在路上!
愿与君共勉!