La mise en œuvre d'une carte en Java

Question

Je travaille actuellement sur une mission qui m'a création d'une classe de la carte en Java, et j'ai rencontré une erreur tout en travaillant avec la méthode « put » que je ne peux pas sembler corriger. Essentiellement, lorsque le test est exécuté, le nouveau nœud dans la carte ne sera pas créé, et je n'arrive pas à comprendre pourquoi. Merci d'avance!

Classe:

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; 
    } 
} 
} 

Test:

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")); 
} 
} 

Answer 1

l'intérieur de votre méthode put(K key, V value, MapNode ref), vous attribuez un nouveau MapNode à ref contenant le nœud que vous souhaitez ajouter.

Je vois que vous appelez cette méthode en passant root. Ceci stocke la même référence que celle enregistrée dans root dans ref. Ce que cela signifie, c'est qu'ils pointent vers le même objet, si root n'étaient pas null. Cependant, comme root est null, ils pointent tous deux à null.

Lorsque vous affectez ref = new MapNode(key, value);, vous pointez ref vers le nouveau nœud, mais root pointe toujours vers zéro.

Vous devez pointer root vers le nouveau MapNode, pointant ref pour qu'il ne le fasse pas pour vous.

Answer 2

Le problème que vous avez est que vous ne changez pas la racine nulle part si vous associez ne rien avoir en elle. Vous passez par valeur, pas par référence, donc quand vous faites ref = new MapNode() cela change votre variable locale, pas la valeur des appelants.

Answer 3

Votre problème est que vous perdre de vue le fait que Java est passe par référence non - passe des références en termes de valeur. Quand vous dites ref = new MapNode(...), vous ne changez rien. Vous devrez explicitement faire pointer le nœud parent sur le nœud nouvellement créé.