2

パラメータで指定されているように、要素のリストをインデックス a から b に反転させる二重リンク リスト データ構造のメソッドを作成していましたが、それを再帰的に行うことにしました。課題の目的は、ノードを使用してポインター操作を練習することでした。メソッドのロジックは問題ないように見えましたが、コードを JUnit テストで実行すると終了しませんでした。これはおかしいと思い、println ステートメントを追加して、コードのどの部分に到達したかを確認しました。すべてが正常にチェックアウトされました。そこで、Eclipse のデバッガーで実行したところ、終了することなく、すべての再帰呼び出しを前後に行った後、終了ブラケットに到達しました。それはちょうど最後のブラケットに座っていました、そして私は前にこのようなものを見たことがありません. なぜそれをしているのですか？それを修正するにはどうすればよいですか？

コードは次のとおりです。

public void reverseList(int start, int end)
{
    if (start >= end)
    {
        return;
    }

    ListNode left = getListNode(start);
    ListNode right = getListNode(end);
    ListNode leftNext = left.next;
    ListNode leftPrev = left.previous;
    ListNode rightNext = right.next;
    ListNode rightPrev = right.previous;

    leftPrev.next = right;
    rightPrev.next = left;
    leftNext.previous = right;
    rightNext.previous = left;
    left.next = rightNext;
    left.previous = rightPrev;
    right.next = leftNext;
    right.previous = leftPrev;

    reverseList(start + 1, end - 1);
}

編集：これをテストするコードは次のとおりです

JUnit:

@Test
public void testReveseList()
{
StudentList list = new StudentList();
list.add("a", "");
list.add("b", "");
list.add("c", "");
list.add("d", "");
list.add("e", "");
list.add("f", "");
list.add("g", "");
list.add("h", "");
list.add("i", "");
list.add("j", "");
list.printlist();
list.reverseList(2, 5);
System.out.println();
StudentList expectedList = new StudentList();
expectedList.add("a", "");
expectedList.add("b", "");
expectedList.add("f", "");
expectedList.add("e", "");
expectedList.add("d", "");
expectedList.add("c", "");
expectedList.add("g", "");
expectedList.add("h", "");
expectedList.add("i", "");
expectedList.add("j", "");
assertEquals(expectedList, list);
list.reverseList(2, 5);

System.out.println();

StudentList expectedList1 = new StudentList();
expectedList1.add("a", "");
expectedList1.add("b", "");
expectedList1.add("c", "");
expectedList1.add("d", "");
expectedList1.add("e", "");
expectedList1.add("f", "");
expectedList1.add("g", "");
expectedList1.add("h", "");
expectedList1.add("i", "");
expectedList1.add("j", "");
assertEquals(expectedList1, list);
list.reverseList(0, 9);
System.out.println();
StudentList expectedList2 = new StudentList();
expectedList2.add("j", "");
expectedList2.add("i", "");
expectedList2.add("h", "");
expectedList2.add("g", "");
expectedList2.add("f", "");
expectedList2.add("e", "");
expectedList2.add("d", "");
expectedList2.add("c", "");
expectedList2.add("b", "");
expectedList2.add("a", "");
assertEquals(expectedList2, list);

}

テスト クラス:

public class StudentList
{
private ListNode head = null;

public void add(StudentData data)
{
    ListNode newNode = new ListNode(data);
    ListNode lastNode = getTail();

    if (lastNode == null)
    {
        head = newNode;
    }
    else
    {
        lastNode.next = newNode;
    }

    newNode.previous = lastNode;
    newNode.next = null;

}       

    public ListNode getListNode(int indexOfDesiredNode)
{
    if (indexOfDesiredNode >= size())
    {
        // --- Error: There aren't that many nodes
        return null;
    }

    // --- Move through the list, node by node, until we find
    // --- the one we want
    int count = 0;
    ListNode current = head;
    while ((count < indexOfDesiredNode) && (null != current))
    {
        current = current.next;
        count = count + 1;
    }

    // --- So, did we find anything?
    if (null == current)
    {
        // --- Error: We didn't find the node
        return null;
    }

    return current;
}

    public int size()
{
    if (null == head)
    {
        return 0;
    }

    int count = 0;
    ListNode current = head;
    while (current != null)
    {
        count = count + 1;
        current = current.next;
    }
    return count;
}

    public void reverseList(int start, int end)
{
    if (start >= end)
    {
        return;
    }

    ListNode left = getListNode(start);
    ListNode right = getListNode(end);
    ListNode leftNext = left.next;
    ListNode leftPrev = left.previous;
    ListNode rightNext = right.next;
    ListNode rightPrev = right.previous;

    leftPrev.next = right;
    rightPrev.next = left;
    leftNext.previous = right;
    rightNext.previous = left;
    left.next = rightNext;
    left.previous = rightPrev;
    right.next = leftNext;
    right.previous = leftPrev;

    //-- The easy way of doing it... *sigh*
    // StudentData temp = get(start);
    // getListNode(start).data = getListNode(end).data;
    // getListNode(end).data = temp;

    reverseList(start + 1, end - 1);
}
}

そして ListNode クラス:

public class ListNode
{
public StudentData data = null;
public ListNode next = null;
public ListNode previous = null;

public ListNode(StudentData data)
{
    this.data = data;
}

@Override
public String toString()
{
    return data.toString();
}
}

コピーと貼り付けで発生した、書式設定が最適ではないことをお詫びします。

4

1 に答える 1

0

end == start + 1問題は、したがっての場合にありrightPrev == leftます。次にrightPrev.next = left、リストを循環させるものを設定するので、getListNode終了しません。

于 2013-10-20T20:06:41.740 に答える