-6

我有课：

public class WordNode {

    private String _word;
    private WordNode _next;
....
}

和以下列表：

public class TextList {
    private WordNode _head;

    public char mostFrequentStartingLetter(....){}
}

在 TextList 类中，我应该使用递归方法（mostFrequentStartingLetter），它返回列表中单词开头的最常见字母......我什至不知道从哪里开始......

请帮忙...

谢谢， 阿罗娜

只是为了让你知道我没有作弊：

public class TextList {
    private WordNode _head;

    public TextList(String text) {
    String word = "";
    WordNode tmp;

    // After the split that in the array we are going over all the array
    for (int i = 0; i < text.length(); i++) {
        for (int j = 0; j < text.length(); j++) {
            if (text.charAt(j) == ' ') {
                word = text.substring(0, j);
                text = text.substring(j + 1);
                i = 0;
                break;
            } else if (j == text.length() - 1) {
                word = text.substring(0, j + 1);
                text = text.substring(j + 1);
                break;
            }
        }
        if (_head == null) {
            tmp = new WordNode(word, null);
            _head = tmp;
        }
        // if the word starts with a smalles letter then the head, make it
        // the head
        else if (_head.getWord().compareTo(word) > 0) {
            tmp = new WordNode(word, _head);
            _head = tmp;

        } else {
            WordNode current;
            current = _head;
            // go over all the nodes in the list and push the current word
            // to the list in the right order
            while (current.getNext() != null) {
                if (current.getWord().compareTo(word) < 1
                        && current.getNext().getWord().compareTo(word) > 0) {
                    tmp = new WordNode(word, current.getNext());
                    current.setNext(tmp);

                    break;
                }
                current = current.getNext();
            }
            // If the current was the tail, check that the word is bigger
            // and then make it the tail.
            if (current.getNext() == null
                    && current.getWord().compareTo(word) < 1) {
                tmp = new WordNode(word, null);
                current.setNext(tmp);

            }
        }
    }

    }

    public String mostFrequentWord() {

        String frequentWord = _head.getWord();
        WordNode current = _head;
        int count = 0;
        int max = 0;

        while (current.getNext() != null) {

            if (current.getWord().compareTo(current.getNext().getWord()) == 0) {
                count++;
            }

            if (count > max) {
                max = count; frequentWord = current.getWord();
            }

            current = current.getNext();
        }

        return frequentWord;
    }

    public String toString() {

        String s = "";
        WordNode current = _head;
        int count = 1;

        while (current != null) {
            while (current.getNext() != null && current.getWord().equals(current.getNext().getWord())) {

                count++;
                current = current.getNext();
            }

            s += current.getWord() + "\t" + count + "\n";
            count = 1;
            current = current.getNext();
        }
        return s;
    }

    public char mostFrequentStartingLetter(....){}
}
4

1 回答 1

2

由于这是作业，我只会给你一些提示。

您需要在这里做两件事。

  • 递归地遍历你的链表。
  • 跟踪起始字母。

当你有一个递归函数时，你需要一个停止条件。想想你的链表的停止条件。你怎么知道你什么时候到达了链表的末尾？的价值_next是多少？

您的方法最终看起来像这样：

///The pieces in the angle brackets are for you to figure out.
public void determineStartingLetter(WordNode currentNode) {
    if(!<stopping condition>) {
        determineStartingLetter(<next node after currentNode>);
    }
}

现在这只遍历链表。您还需要跟踪到目前为止所看到的起始字符。想想你可以用来做这件事的结构。您想将角色映射到您看到它的次数。什么数据结构可以为您做到这一点？

现在你可以在哪里维护这样的结构？最简单的解决方案（但不是最可维护或最优雅的）将是TextList类的私有成员。但是有一个更好的方法。如果您可以简单地将这个数据结构传递给递归方法，然后传递给每个递归调用会怎样？

那么您的方法将如下所示：

//As before, the things in angle brackets are for you to figure out.
public <data structure> determineStartingLetter(WordNode currentNode, <data structure>) {
    if(!stopping condition>) {
        <look at starting letter for currentNode>
        <increment the count for this letter in the data structure>
        return determineStartingLetter(<next node after currentNode>, <data structure>);
    }

    return <data structure>
}

这应该给你足够的提示来弄清楚如何去做。在第二部分中，我实际上给了你一些比我应该有的更多的提示:)。

于 2013-05-16T19:51:55.910 回答