- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
这是代码...
public class Huffman_Coding {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter a string to compress: ");
String str = sc.nextLine();
sc.close();
HashString hs = new HashString();
HashMap<Character, Integer> hm = hs.getStringHash(str);
PriorityQueue<Node> pq = new PriorityQueue<Node>();
for (char ch : hm.keySet()) {
pq.add(new Node(null, null, hm.get(ch), ch));
}
System.out.println(pq);
while (pq.size() != 1) {
Node left = pq.poll();
Node right = pq.poll();
Node parent = new Node(left, right, left.freq + right.freq, '\0');
pq.add(parent);
System.out.println(pq);
}
Huffman_Tree ht = new Huffman_Tree();
String ans = "";
ht.inOrder(pq.poll(), ans);
}
}
class Node implements Comparable<Node> {
@Override
public String toString() {
return "Node [freq=" + freq + ", ch=" + ch + "]";
}
Node lptr;
Node rptr;
int freq;
char ch;
Node(Node lptr, Node rptr, int freq, char ch) {
this.freq = freq;
this.lptr = lptr;
this.rptr = rptr;
this.ch = ch;
}
public int compareTo(Node o) {
int comparedvalue = Integer.compare(this.freq, o.freq);
if (comparedvalue != 0)
return comparedvalue;
else
return Integer.compare(this.ch, o.ch);
}
}
boolean isLeaf() {
return this.lptr == null && this.rptr == null;
}
}
class Huffman_Tree {
void inOrder(Node root, String code) {
if (!root.isLeaf()) {
inOrder(root.lptr, code + '0');
inOrder(root.rptr, code + '1');
} else
System.out.println(root.ch + " : " + code);
}
}
这里,对于输入字符串abccddeeee
,我收到类似的信息:
[Node [freq=1, ch=a], Node [freq=1, ch=b], Node [freq=2, ch=c], Node [freq=2, ch=d], Node [freq=4, ch=e]]
[Node [freq=2, ch= ]]
我很困惑为什么在第二步中具有“d”的节点比“e”领先。这使我在最终编码中出现错误。为什么compareTo 方法失败我无法理解。
getHashString 返回一个哈希值,其中键中包含字符,值中包含它们的频率。
最佳答案
我不明白为什么 PriorityQueue
中的元素顺序不是在轮询元素和添加新元素之后的预期顺序”合成”元素,但我认为您可以解决切换到 TreeSet
的问题,正如我已经成功完成的那样
TreeSet<Node> pq = new TreeSet<Node>((n1, n2) -> n1.compareTo(n2)); // explicit but unnecessary comparator
并将每个 pq.poll()
调用更改为 pq.pollFirst()
...
希望这个解决方法可以帮助您!
编辑
正如您可以在 official PriorityQueue
documentation 中读到的那样, * 方法 iterator() 中提供的迭代器不保证以任何特定顺序遍历优先级队列的元素。如果需要有序遍历,请考虑使用 Arrays.sort(pq.toArray()).*
这应该可以解释为什么 toString()
方法调用以不同于预期优先级顺序的顺序显示队列元素...
关于java - 我在霍夫曼编码 java 中遇到一些逻辑错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59737317/
已关闭。此问题需要 debugging details 。目前不接受答案。 编辑问题以包含 desired behavior, a specific problem or error, and the
我这样定义了一个二叉树: struct btree { int x; btree* left_child = nullptr; btree* right_child = nul
我有这个霍夫曼代码,旨在返回数组中每个字母的霍夫曼代码并按字母顺序打印它们。问题是它不生成任何输出,而是继续处理,直到我手动退出它。谁能帮我找出错误吗?我认为我的代码是正确的,但我不知道无限循环从何而
动机 想象一下一个哈夫曼压缩文件被部分下载,就像在p2p软件中一样,所以我们首先为整个文件分配磁盘空间,然后开始随机下载文件块。其中一个哈夫曼密码(但我们不知道是哪一个)是一个结束密码,所以如果这个密
以下 block 由霍夫曼 block 标记嵌套 -HUFF---------------------------------------------------------------------0
我是一名优秀的程序员,十分优秀!