Как создать вложенный связанный список с помощью рекурсии? - PullRequest
Новая
       30

Как создать вложенный связанный список с помощью рекурсии?

0 голосов
/ 05 марта 2020

Итак, в классе нас просят прочитать в текстовом файле. Формат примерно такой:

ab (c d (ef) g) h

Нам нужно создать вложенный связанный список, например, такой:

a

b

..... c

..... d

.......... e

.......... f

..... g

h

Каждая левая скобка обозначает перемещение вниз по уровню, затем правая скобка обозначает переход на один уровень вверх. Так, ссылка на b, b имеет вложенную ссылку на c, c ссылки на d, d имеет вложенную ссылку на e, e ссылается на f, d ссылается на g, затем b ссылается на h

Мы используем измененный LLNode:

publi c class LLNode {

protected LLNode<T> link;
protected LLNode<T> nested;
protected T info;
public LLNode(T info) 
{
    this.info = info;
    link = null;
    nested = null;
}
public void setInfo(T info) 
{
    this.info = info;
}
public T getInfo() 
{
    return info;
}
public void setLink(LLNode<T> link) 
{
    this.link = link;
}
public LLNode<T> getLink() 
{
    return link;
}
public void setNested(LLNode<T> nested)
{
    this.nested = nested;
}
public LLNode<T> getNested()
{
    return nested;
}

}

Нам нужно использовать рекурсию для чтения входного файла, создать узлы для каждой буквы и связать их соответственно. Я понятия не имею, как подойти к этому рекурсивно. Любая помощь с благодарностью.

1 Ответ

0 голосов
/ 08 марта 2020

Я знаю, что не должен давать вам ответы на ваши домашние задания, но мне нравится рекурсия, поэтому я не смог устоять перед этим. Пожалуйста, потратьте некоторое время на понимание и, возможно, на изменение кода, прежде чем передать его. Умные учителя ищут в StackOverflow, особенно если материал, который вы передаете, на удивление хорош:)

Мне пришлось добавить parent к LLNode. Вместо родительского атрибута у вас может быть список LLNode в классе NodeParser, где список отслеживает самого последнего отца, деда и т. Д. c.

Новый LLNode: 

public class LLNode<T> {

    protected LLNode<T> link;
    protected LLNode<T> nested;
    protected LLNode<T> parent; // New field
    protected T info;

    public LLNode(T info) {
        <old code>
        parent = null;
    }

    <old code>

    public void setParent(LLNode<T> parent) {
        this.parent = parent;
    }

    public LLNode<T> getParent() {
        return parent;
    }

}

А потом парсер (включая рекурсивный принтер!): 

public class NodeParser {

private String str;

public static void main(String[] args) {
    new NodeParser();
}

public NodeParser() {
    this.str = "a b ( c d ( e f ) g ) h ( i j ( k ) l ) m n";
    LLNode<Character> topNode = new LLNode<>(null);
    parse(topNode, false);
    print("", topNode.getLink());
}

private synchronized void parse(LLNode<Character> node, boolean nested) {
    if (str.length() == 0) {
        return;
    }
    while (str.charAt(0) == ' ') {
        str = str.substring(1);
    }
    char c = str.charAt(0);
    str = str.substring(1);

    if (c == '(') {
        parse(node, true);
    } else if (c == ')') {
        parse(node.getParent(), false);
    } else if (c >= 'a' && c <= 'z') {
        LLNode<Character> nextNode = new LLNode<>(c);
        if (nested) {
            node.setNested(nextNode);
            nextNode.setParent(node);
        } else {
            node.setLink(nextNode);
            nextNode.setParent(node.getParent());
        }
        parse(nextNode, false);
    }
}

private void print(String indent, LLNode<Character> node) {
    if (node == null) {
        return;
    }
    System.out.println(indent + node.getInfo());
    print(indent + "  ", node.getNested());
    print(indent, node.getLink());
}

}
...