調試由AVL樹支持的地圖？

Question

這是我用來解析文本並打印出每一個唯一的單詞，它出現的行號，以及它出現的次數的三棵樹之一。我已經使用了散列和樹形圖，並且它們都能正常工作。我的老師說我們需要爲第三張地圖使用AVL樹並給我們提供代碼。這是我不確定去哪裏的地方。我將包括創建/填充AVL地圖以及AVL地圖類的方法。如果需要進一步的代碼，我會很樂意包含它。

public void avlMap(String fileName){ 

    //try/catch block to check for invalid file name 
    try{ 
     //creates new bufferedreader object for input file 
     BufferedReader inFile = new BufferedReader(new FileReader(fileName)); 

     //creates new treeMap object named avlMap 
     Map avlMap = new AvlMap(); 
     String oneLine; 

     //Read the words and add them to the avlMap 
     for (int lineNum = 1; (oneLine = inFile.readLine()) != null; lineNum++){ 
      String delims = " !@#$%{}[]/^&*,.()-;:\'\"\t"; 
      StringTokenizer st = new StringTokenizer(oneLine, delims); 
      while (st.hasMoreTokens()){ 
       String word = st.nextToken(); 
       WordStats stats = (WordStats) avlMap.get(word); 

       //if WordStats is empty/doesnt exist, 
       //if exists, adds line numbers into a WordStats in the value 
       //...field for the int's respective key 
       if (stats == null){ 
        stats = new WordStats(); 
        avlMap.put(word, stats); 
       } 
       //WordStats already exists for the word 
       //calls addOccurrence method and adds the line number 
       stats.addOccurrence(new Integer(lineNum)); 
      } 
     } 

     //creates a new iterator object to iterate entries 
     Iterator itr = avlMap.entrySet().iterator(); 

     //runs printEntry for each key in the treeMap 
     while (itr.hasNext()){ 
      printEntry((Map.Entry) itr.next()); 
     } 
    } 
     //the file name used wasn't able to be reached 
     catch(IOException e){ 
      e.printStackTrace(); 
     } 
} 

AvlMap類。我知道這是相當長的，但是這些方法看起來與我一直使用的其他地圖類非常相似。

public class AvlMap <AnyType extends Comparable<? super AnyType>> implements Map 
    { 
    //construct the tree 
    public AvlMap(){ 
     root = null; 
    } 

    //inserts object into the map 
    public void insert(AnyType x, AnyType y){ 
     root = insert(x, y, root); 
    } 

    //removes the key from the map 
    public void remove(AnyType x){ 
     root = remove(x, root); 
    } 

    //internal method to remove from a subtree 
    private AvlNode<AnyType> remove(AnyType x, AvlNode<AnyType> t){ 
     if(t == null) 
      return t; // Item not found; do nothing 

     int compareResult = x.compareTo(t.key); 

     if(compareResult < 0) 
      t.left = remove(x, t.left); 
     else if(compareResult > 0) 
      t.right = remove(x, t.right); 
     else if(t.left != null && t.right != null) // Two children 
     { 
      t.key = findMin(t.right).key; 
      t.right = remove(t.key, t.right); 
     } 
     else 
      t = (t.left != null) ? t.left : t.right; 
     return balance(t); 
    } 

    //returns the smallest item in the tree 
    public AnyType findMin(){ 
     if(isEmpty()) 
      throw new UnderflowException("Error"); 
     return findMin(root).key; 
    } 

    //returns the largest item in the tree 
    public AnyType findMax(){ 
     if(isEmpty()) 
      throw new UnderflowException("Error"); 
     return findMax(root).key; 
    } 

    //finds the provided item in the tree 
    public boolean contains(AnyType key){ 
     return contains(key, root); 
    } 

    //make the tree empty 
    public void makeEmpty(){ 
     root = null; 
    } 

    //tests if the tree is empty 
    public boolean isEmpty(){ 
     return root == null; 
    } 

    //prints the tree in sorted order 
    public void printTree(){ 
     if(isEmpty()) 
      System.out.println("Empty tree"); 
     else 
      printTree(root); 
    } 

    private static final int ALLOWED_IMBALANCE = 1; 

    // Assume t is either balanced or within one of being balanced 
    private AvlNode<AnyType> balance(AvlNode<AnyType> t) 
    { 
     if(t == null) 
      return t; 

     if(height(t.left) - height(t.right) > ALLOWED_IMBALANCE) 
      if(height(t.left.left) >= height(t.left.right)) 
       t = rotateWithLeftChild(t); 
      else 
       t = doubleWithLeftChild(t); 
     else 
     if(height(t.right) - height(t.left) > ALLOWED_IMBALANCE) 
      if(height(t.right.right) >= height(t.right.left)) 
       t = rotateWithRightChild(t); 
      else 
       t = doubleWithRightChild(t); 

     t.height = Math.max(height(t.left), height(t.right)) + 1; 
     return t; 
    } 

    //checks the trees balance 
    public void checkBalance(){ 
     checkBalance(root); 
    } 

    //driver for checking the trees balance 
    private int checkBalance(AvlNode<AnyType> t){ 
     if(t == null) 
      return -1; 

     if(t != null) 
     { 
      int hl = checkBalance(t.left); 
      int hr = checkBalance(t.right); 
      if(Math.abs(height(t.left) - height(t.right)) > 1 || 
        height(t.left) != hl || height(t.right) != hr) 
       System.out.println("OOPS!!"); 
     } 

     return height(t); 
    } 

    //method to insert into a subtree 
    private AvlNode<AnyType> insert(AnyType key, AnyType value, AvlNode<AnyType> t){ 
     if(t == null) 
      return new AvlNode<>(key, value, null, null); 

     int compareResult = key.compareTo(t.key); 

     if(compareResult < 0) 
      t.left = insert(key, value,t.left); 
     else if(compareResult > 0) 
      t.right = insert(key, value, t.right); 
     else 
      ; // Duplicate; do nothing 
     return balance(t); 
    } 

    //returns the smallest item in a subtree 
    private AvlNode<AnyType> findMin(AvlNode<AnyType> t) 
    { 
     if(t == null) 
      return t; 

     while(t.left != null) 
      t = t.left; 
     return t; 
    } 

    //finds the largest item in a subtree 
    private AvlNode<AnyType> findMax(AvlNode<AnyType> t){ 
     if(t == null) 
      return t; 

     while(t.right != null) 
      t = t.right; 
     return t; 
    } 

    //finds an item in a subtree 
    private boolean contains(AnyType x, AvlNode<AnyType> t){ 
     while(t != null){ 
      int compareResult = x.compareTo(t.key); 

      if(compareResult < 0) 
       t = t.left; 
      else if(compareResult > 0) 
       t = t.right; 
      else 
       return true; // Match 
     } 
     return false; // No match 
    } 

    //prints the subtree in sorted order 
    private void printTree(AvlNode<AnyType> t){ 
     if(t != null){ 
      printTree(t.left); 
      System.out.println(t.key + " " + t.value); 
      printTree(t.right); 
     }  
    } 

    //returns the height of node t or -1 if null 
    private int height(AvlNode<AnyType> t){ 
     return t == null ? -1 : t.height; 
    } 

    //rotates tree node with left child 
    private AvlNode<AnyType> rotateWithLeftChild(AvlNode<AnyType> k2){ 
     AvlNode<AnyType> k1 = k2.left; 
     k2.left = k1.right; 
     k1.right = k2; 
     k2.height = Math.max(height(k2.left), height(k2.right)) + 1; 
     k1.height = Math.max(height(k1.left), k2.height) + 1; 
     return k1; 
    } 

    //rotates tree node with right child 
    private AvlNode<AnyType> rotateWithRightChild(AvlNode<AnyType> k1){ 
     AvlNode<AnyType> k2 = k1.right; 
     k1.right = k2.left; 
     k2.left = k1; 
     k1.height = Math.max(height(k1.left), height(k1.right)) + 1; 
     k2.height = Math.max(height(k2.right), k1.height) + 1; 
     return k2; 
    } 

    //double rotates tree node. first left child with its right child, then 
    //...node k3 with new left child. 
    private AvlNode<AnyType> doubleWithLeftChild(AvlNode<AnyType> k3){ 
     k3.left = rotateWithRightChild(k3.left); 
     return rotateWithLeftChild(k3); 
    } 

    //double rotates tree node. first right child with its left child, then 
    //...node k1 with new right child 
    private AvlNode<AnyType> doubleWithRightChild(AvlNode<AnyType> k1){ 
     k1.right = rotateWithLeftChild(k1.right); 
     return rotateWithRightChild(k1); 
    } 

    private static class AvlNode<AnyType>{ 
      // Constructors 
     @SuppressWarnings("unused") 
     AvlNode(AnyType theKey, AnyType theValue){ 
      this(theKey, theValue, null, null); 
     } 

     AvlNode(AnyType theKey, AnyType theValue, AvlNode<AnyType> lt, AvlNode<AnyType> rt){ 
      key = theKey; 
      value = theValue; 
      left  = lt; 
      right = rt; 
      height = 0; 
     } 

     AnyType   key;  // The data in the node 
     AnyType   value; 
     AvlNode<AnyType> left;   // Left child 
     AvlNode<AnyType> right;  // Right child 
     int    height;  // Height 
    } 

    //trees root 
    private AvlNode<AnyType> root; 

    //implemented methods for AvlTreeMap 
    @Override 
    public void clear() { 
     makeEmpty();  
    } 

    @SuppressWarnings("unchecked") 
    @Override 
    public boolean containsKey(Object key) { 
     contains ((AnyType)key); 

     return false; 
    } 

    @SuppressWarnings("unchecked") 
    @Override 
    public boolean containsValue(Object value) { 
     contains ((AnyType)value); 
     return false; 
    } 

    @Override 
    public Set entrySet() { 
     return null; 
    } 

    @Override 
    public Object get(Object key) { 
     return key; 
    } 

    @Override 
    public Set keySet() { 
     return null; 
    } 

    @SuppressWarnings("unchecked") 
    @Override 
    public Object put(Object key, Object value) { 
     insert ((AnyType)key, (AnyType) value); 

     return true; 
    } 

    @Override 
    public void putAll(Map m) { 
    } 

    @SuppressWarnings("unchecked") 
    @Override 
    public Object remove(Object key) { 
     remove ((AnyType)key); 
     return null; 
    } 

    @Override 
    public int size() { 
     return 0; 
    } 

    @Override 
    public Collection values() { 
     return null; 
    } 
    } 

這是我的WordStats類，它將所有內容都保存到一個集合中並保持發生。

import java.util.SortedSet; 
    import java.util.TreeSet; 


    public class WordStats { 
private int occurrences; 
private SortedSet<Integer> lineNumbers = new TreeSet<Integer>(); 

public void addOccurrence(int lineNumber){ 
    occurrences++; 
    lineNumbers.add(lineNumber); 
} 

public int getOccurrences(){ 
    return occurrences; 
} 

public SortedSet<Integer> getLines(){ 
    return lineNumbers; 
} 
    } 

當我運行程序時，我得到的錯誤：

Exception in thread "main" java.lang.ClassCastException :

java.lang.String cannot be cast to WordStats

at driver1.avlMap(driver1.java:182)

at driver1.main(driver1.java:36)

預先感謝任何見解可以提供。也沒有任何編譯器錯誤。

Answer 1

正如堆棧跟蹤中所述，此問題的根本原因在於您正試圖將String類型的對象轉換爲WordStats類型的某個對象。我認爲這發生在這一行：

WordStats stats = (WordStats) avlMap.get(word); 

所以我們來看看avlMap.get(word)。這看起來如下：

@Override 
public Object get(Object key) { 
    return key; 
} 

所以這是有問題的 - 它看起來像每一次嘗試做一個查找時間，你只是返回鍵，你是試圖查找地圖裏面！這將解釋鑄造錯誤 - 您將String傳入avlMap.get()，然後將其返回。當您嘗試將其投射到WordStats時，您會收到錯誤消息，因爲String不是WordStats。

要解決這個問題，我認爲你需要你的get方法來實際在AVL樹中進行搜索並進行查找。我會留下這個給你完成自己。我會強烈建議不要試圖將您的地圖集成到一個更大的程序，直到你已經更徹底地測試它 - 具有處理字堆疊在一個錯誤的AVL樹頂部的所有邏輯將使調試非常困難，即使不是不可能。嘗試爲你的AVL樹編寫一些單元測試，看看它是否工作。您也可以考慮在過渡期間換出正常的TreeMap的AVL樹形圖，以查看驅動程序代碼是否有效。

作爲另一個音符 - 你應該強烈考慮不執行原始類型Map，而是實現Map參數在鍵和值的類型。這使得界面方式更易於使用，並有助於捕捉您遇到的錯誤。

希望這會有所幫助！