代码之家 › 专栏 › 技术社区 › Snowman

Java中的反向递归和LinkedList帮助

linked-list recursion java

Snowman · 技术社区 · 16 年前

/**
     * Converts linked list into a sentence (a single string representation).
     * Each word pair is separated by a space. A period (".") is appended after
     * the last word. The last link represents the first word in the sentence
     * (and vice versa). The partialResult is the partial string constructed
     * from earlier links. This partialResult is initially an empty string. 
     */
    public String getReversedSentence(String partialResult) {
        if (next==null) {
            partialResult+=this.word;
            return partialResult + ".";
        }
        else{
            partialResult=next.getReversedSentence(partialResult) + this.word;
            return partialResult;
            }
    }

一切都很好,除了时间(和空间,但我还不担心)。我不能把这段时间安排妥当。

这是它失败的测试:

public void testGetReversedSentence() {
        LinkedList tail = new LinkedList("not",null);
        LinkedList middle = new LinkedList("too",tail);
        LinkedList head = new LinkedList("tricky",middle);
        assertEquals("not.",tail.getReversedSentence(""));
        assertEquals("not too tricky.",head.getReversedSentence(""));

它产生了 not.too tricky 而不是 not too tricky.

编辑:控制器

public LinkedList(String word, LinkedList next) {
        this.word = word;
        this.next = next;
    }

有什么线索吗?

4 回复 | 直到 16 年前

irrelephant 16 年前

好。。。无需使用两种方法(重要)--> String partialResult 作为参数。 (如果您愿意,并且在解决方案中允许helper方法,但这是不必要的,您可以这样做。)换句话说,尝试找到某种方法将当前单词与partialResult合并。另一个提示:有一个3行长的解决方案(格式正确)。

The Archetypal Paul 16 年前

 public String getReversedSentence(String partialResult) {
        if (next==null) {
            partialResult+=this.word;
            return partialResult + ".";
        }
        else{
            partialResult=next.getReversedSentence(partialResult) + this.word; // <---
            return partialResult;
            }
    }

问题是标记为<--。递归调用将使用返回eventuallyt。追加(因为它将递归到列表的末尾,然后添加a.,返回a.,然后追加this.word。

既然这是作业,我就不给答案。

rsp 16 年前

出问题的是“.”被附加到递归最深的单词后面,这是逆序列中的第一个单词。

您想找到一种方法将“.”添加到反向序列的末尾,也许可以将您的方法分成两个方法,其中一个调用另一个的方法知道结果。

-1

Sanya Zahid 13 年前

//--------------------------linklist class------------------------------------------------

import java.util.Stack;

public class Linklist {
    Stack <Character> a = new Stack <Character>();
    Node front; 
    Node back;
    Node Temp;

    public void insert (char d){
        Node newNode = new Node (d);
    if (front == null){
        front = newNode;
        back = newNode;
    }


    else {
        Temp = front;
        while (Temp != null){

            back= Temp;
        Temp = Temp.next ;
        }

        back.next = newNode;
    }


    }





    public void display(){
        Node T=front;
        System.out.print(T.data);
        T=T.next;
        while(T!=front)
        {
            System.out.print(T.data);
            T=T.next;
            if (T == null ){
                break;
            }
        }
    }


    public void reverse(){
    Linklist bb = new Linklist ();


        Node temp = front;
        while(temp != null ){
            if (temp.data != '_'){
 a.push(temp.data);

            }


            else{
        //char x =  
while (!a.isEmpty()){
    char pop = a.pop();
bb.insert(pop);


            }
bb.insert('_');
            }
            temp = temp.next;
        }// while end

        bb.display();

    }


}
//-------------------------------------------------------------------------------------


//------------------ test class
public class Test {

    /**
     * @param args
     */
    public static void main(String[] args) {

        queueLinklist a = new queueLinklist ();
a.insert('m');
a.insert('y');
a.insert('_');
a.insert('n');
a.insert('a');
a.insert('m');
a.insert('e');
a.insert('_');
a.insert('i');
a.insert('s');
a.insert('_');
a.insert('s');
a.insert('a');
a.insert('m');
a.insert('_');

a.display();
System.out.println(" ");
    a.reverse();
    a.reverse();
    }

}
// ---------- node class

public class Node {
char data;
Node next;

Node (){
    data= (Character) null ;
    next = null;
}

Node (char d){
    data = d;
    next = null;
}
}