0

这是我用来解析文本并打印出每个唯一单词、它出现的行号以及它出现的次数的三棵树之一。我已经使用了哈希和树图，并且它们都可以正常工作。我的导师说我们需要为第三张地图使用 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;
}
    }

当我运行程序时，我收到错误：

线程“main”中的异常java.lang.ClassCastException：

java.lang.String不能转换为WordStats

在driver1.avlMap(driver1.java:182)

在driver1.main(driver1.java:36)

提前感谢您提供的任何见解。也没有任何编译器错误。

4

1 回答 1

0

如堆栈跟踪中所述，此问题的根本原因是您试图将 type 对象强制String转换为 type WordStats。我认为这发生在这一行：

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

那么让我们来看看avlMap.get(word)。这看起来如下：

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

所以这是有问题的 - 看起来每次您尝试查找时，您只是返回您试图在地图中查找的键！这可以解释转换错误 - 你传入 a Stringinto avlMap.get()，然后返回它。当您尝试将其转换为 aWordStats时，您会收到一个错误，因为 aString不是 a WordStats。

要解决此问题，我认为您需要您的get方法来实际在 AVL 树中进行搜索并进行查找。我会把这个留给你自己完成。我强烈建议不要尝试将您的地图集成到更大的程序中，直到您对其进行更彻底的测试 - 将处理单词的所有逻辑都放在有缺陷的 AVL 树之上，这将使调试变得非常困难，如果不是不可能的话。尝试为您的 AVL 树编写一些单元测试，看看它是否有效。您还可以考虑在此期间将您的 AVL 树图换成正常TreeMap的，以查看驱动程序代码是否有效。

另请注意 - 您应该强烈考虑不实现原始类型Map，而是Map通过键和值类型实现参数化。这使界面方式更易于使用，并有助于捕获您遇到的错误。

希望这可以帮助！

于 2013-03-18T19:41:19.567 回答