1

私は、配列をソートし、作成した二重リンク リスト ADT にインデックスを格納する必要がある割り当てに取り組んでいます。

Example:
{"A","B","C","A"} -> {0,3,1,2}

私の現在のアプローチは、インデックスを ADT に取り込み、配列をソートするときに ADT をソートすることです。私が知る限り、どちらかのループが実行されるたびに、配列と双方向リンクリストの両方でまったく同じ操作を行っていますが、出力は一致しません。

public static void main(String[] args ) {
    List A = new List();
    String[] inputArray = {"A","C","B","A"};
    int i,j;
    String key;
    //load indices into doubly-linked list
    for (int x = 0; x < inputArray.length; x++ ) {
        A.append(x);
    }
    //begin insertion sort
    for (j = 1; j < inputArray.length; j++) {
        System.out.println(A);
        System.out.println(Arrays.toString(inputArray));
        key = inputArray[j];
        i = j - 1;
        while (i >= 0) {
            if (key.compareTo(inputArray[i]) > 0) {
                break;
            }
            inputArray[i+1] = inputArray[i];
            //moveTo moves the cursor to <int>
            A.moveTo(i);
            //make sure we aren't trying to insert before first node
            if (i > 0) { A.insertBefore(i+1); }
            else { A.prepend(i+1); }
            //remove node at cursor
            A.delete();
            i--;
        }
        inputArray[i+1] = key;
        A.moveTo(i+1);
        if (i > 0) { A.insertBefore(i+1); }
        else { A.prepend(i+1); }
        A.delete();
    }
    System.out.println(A);
    System.out.println(Arrays.toString(inputArray));
}

上記のコードは、次の出力を提供します。

実行:
0 1 2 3
[A、C、B、A]
1 0 2 3
[A、C、B、A]
1 1 2 3
[A、B、C、A]
0 2 3 3
[A、A、 B, C]
BUILD SUCCESSFUL (合計時間: 0 秒)

編集: List.java

public class List {

    private class Node{
        //Fields
        int data;
        Node next, previous;
        //Constructor
        Node(int data) {
            this.data = data;
            next = null;
            previous = null;
        }
        public String toString() { return String.valueOf(data); }
    }

    //Fields
    private Node frontNode, backNode, cursorNode;
    private int totalSize, cursorPosition;

    //Constructor
    List() {
        frontNode = backNode = cursorNode = null;
        totalSize = 0;
        cursorPosition = -1;
    }
    //moveTo(int i): If 0<=i<=length()-1, moves the cursor to the element 
    // at index i, otherwise the cursor becomes undefined.
    void moveTo(int i) {
        if (i == 0) {
            cursorPosition = i;
            cursorNode = frontNode;
        }
        else if (i == length() - 1) {
            cursorPosition = i;
            cursorNode = backNode;
        }
        else if (i > 0 && i < length() - 1 ) {
            cursorNode = frontNode;
            cursorPosition = i;
            for (int x=0; x < i; x++) {
                cursorNode = cursorNode.next;
            }
        }
        else {
            cursorPosition = -1; 
        }
    }

//prepend(int data): Inserts new element before front element in this List.
    void prepend(int data) {
        Node node = new Node(data);
        if ( this.length() == 0 ) {
            frontNode = backNode = node;
        }
        else {
            frontNode.previous = node;
            node.next = frontNode;
            frontNode = node;
        }
        totalSize++;
        //cursorPosition might change?
    }
    //insertBefore(int data): Inserts new element before cursor element in this
    // List. Pre: length()>0, getIndex()>=0
    void insertBefore(int data) {
        Node node = new Node(data);
        if ( this.length() > 0 && this.getIndex() >= 0 ) {
            node.previous = cursorNode.previous;
            node.next = cursorNode;
            cursorNode.previous.next = node;
            cursorNode.previous = node;
            totalSize++;
        }
        else if ( this.length() <= 0 )
        {
           throw new RuntimeException
                    ("Error: insertBefore called on empty list");
        }
        else {
            throw new RuntimeException
                    ("Error: insertBefore called without cursor set");
        }
    }
4

1 に答える 1

1

わかりました、ありがとう。insertBefore() と prepend() が何を意図しているのか正確にはわかりませんでした (推測することはできましたが、プログラミングは、メソッドが何をするべきかを推測することではありません。ドキュメントを参照する方がはるかに優れています)。

これは課題ですので、お答えするつもりはありません。しかし、手がかりは次のとおりです。ループを最初に通過した後、A のダンプにより、開始時と同じインデックスが再配置されます。それが、ループの繰り返しのたびにあるべき姿だと思います。しかし、ループを 2 回通過した後はそうではありません (1 が 2 回表示され、0 はなくなります)。考えてみてください。A の要素を再配置するために A.insertBefore() を呼び出したとき、挿入するように insertBefore() に指示する必要があったのはどのデータで、実際に何を挿入したのでしょうか?

于 2013-07-02T23:44:24.747 に答える