1

我目前正在处理一项让我在 Java 中创建 Map 类的任务,并且在使用我似乎无法修复的“put”方法时遇到了错误。本质上,当测试运行时,地图中的新节点不会被创建,我似乎无法弄清楚为什么。先感谢您!

班级:

public class MyMap<K extends Comparable<K>, V> {
private class MapNode {
    private K key;
    private V value;
    private MapNode left;
    private MapNode right;

    public MapNode(K theKey, V theValue) {
        key = theKey;
        value = theValue;
        left = null;
        right = null;
    }
}

private MapNode root;

public MyMap() {
    root = null;
}

/**
 * Associates key to value and stores mapping If key exists, replaces value
 * with a new value
 * 
 * @param key
 * @param value
 * @return value replaced; null if no value
 */

public V put(K key, V value) {
    return put(key, value, root);
}

private V put(K key, V value, MapNode ref) {
    V temp;
    if (ref == null) {
        ref = new MapNode(key, value);
        return null;
    } else {
        if (ref.key.compareTo(key) == 0) {
            temp = ref.value;
            ref.value = value;
            return temp;
        } else if (key.compareTo(ref.key) < 0)
            return put(key, value, ref.left);
        else
            return put(key, value, ref.right);
    }
}

/**
 * Return value to which key is mapped
 * 
 * @param key
 * @return value of key; null
 */

public V get(K key) {
    return get(key, root);
}

private V get(K key, MapNode ref) {
    if (ref == null) {
        return null;
    } else {
        if (ref.key.compareTo(key) == 0)
            return ref.value;
        else if (key.compareTo(ref.key) < 0)
            return get(key, ref.left);
        else if (key.compareTo(ref.key) > 0)
            return get(key, ref.right);
        else
            return null;
    }
}

/**
 * Returns true if Map already uses the key
 * 
 * @param key
 * @return true; false
 */

public boolean containsKey(K key) {
    return containsKey(key, root);
}

private boolean containsKey(K key, MapNode ref) {
    if (ref == null) {
        return false;
    } else {
        if (ref.key.compareTo(key) == 0)
            return true;
        else if (key.compareTo(ref.key) < 0)
            return containsKey(key, ref.left);
        else if (key.compareTo(ref.key) > 0)
            return containsKey(key, ref.right);
        else
            return false;
    }
}
}

测试:

import org.junit.Test;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

public class MyMapTest {
@Test
public void testMyMap(){
    MyMap<String, Integer> m = new MyMap<String, Integer>();

    assertFalse(m.containsKey("one"));
    assertEquals(null, m.get("one"));
    assertEquals(null, m.put("one", 1));
    assertTrue(m.containsKey("one"));
}
}
4

3 回答 3

2

在您的put(K key, V value, MapNode ref)方法中,您分配一个新的 MapNode 以ref包含您要添加的节点。

我看到您通过传递来调用该方法root。这存储了与存储在相同的引用。rootref这意味着,如果root它们不为空,它们将指向同一个对象。但是,按原样rootnull它们都指向null

分配时ref = new MapNode(key, value);,您指向ref新节点,但root仍指向 null。

您需要指向root新的 MapNode,指向ref它不会为您做这件事。

于 2012-04-19T20:17:34.480 回答
0

您遇到的问题是您不会在任何地方更改根目录,因此您的 Map 不会有任何内容。您是按值传递,而不是按引用传递,因此当您这样做时会ref = new MapNode()更改您的局部变量,而不是调用者的值。

于 2012-04-19T20:17:50.343 回答
0

您的问题是您忘记了 Java 不是按引用传递的事实——它按值传递引用。当你说 时ref = new MapNode(...),你实际上并没有改变任何东西。您需要明确地使父节点指向新创建的节点。

于 2012-04-19T20:18:04.463 回答