Как мне превратить мой пользовательский связанный список в массив? - PullRequest
Новая
       13

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

1 голос
/ 21 октября 2010

Мне нужно реализовать метод: 

E[] toArray(E[] a) // Pass an array, convert to singly linked list, then return the array.

из java.util Interface List<E>

Как я уже говорил, мне нужно передать массив, преобразовать его в односвязный список, сортируйте его, а затем возвращайте массив.

В классе Node мне нужно с этим работать: 

public Node(E v, Node<E> next) {
    // pre: v is a value, next is a reference to remainder of list
    // post: an element is constructed as the new head of list
    data = v;
    nextElement = next;
}

public Node(E v) {
    // post: constructs a new tail of a list with value v
    this(v,null);
}

public Node<E> next() {
    // post: returns reference to next value in list
    return nextElement;
}

public void setNext(Node<E> next)  {
    // post: sets reference to new next value
    nextElement = next;
}

public E value() {
    // post: returns value associated with this element
    return data;
}

public void setValue(E value) {
    // post: sets value associated with this element
    data = value;
}

Я лаю не на том дереве или кто-то может мне помочь с этим здесь?Извините, если это неправильное место для таких вопросов.

Ответы [ 3 ]

1 голос
/ 21 октября 2010

Следующий код создаст единый связанный список и скопирует его обратно в новую копию массива.Для сортировки вам нужно убедиться, что вы делаете сопоставимые реализации типа "E".Один из способов заключается в том, чтобы изменить общий декларатор \ "E" \, чтобы>. 


    E[] toArray(E[] a)
    {
        E[] result ;
        Class<?> type ;
        Node<E> head, temp, current ;

        /*
         * Makes a copy of the original array
         */
        type = a.getClass().getComponentType() ;
        result = (E[])java.lang.reflect.Array.newInstance(type, a.length);
        for(int idx = 0; idx < a.length; idx++)
            result[idx] = a[idx] ;

        /*
         * Sort the array (selection copy)
         */
        for(int idx = 0; idx < result.length; idx++)
        {
            int best = idx ;
            for(int jdx = idx + 1; jdx < result.length; jdx++)
            {
                if (result[best].compareTo(result[jdx]) > 0)
                {
                    best = jdx ;
                }
            }
            // swap
            if (best != idx)
            {
                E temporal = result[idx] ;
                result[idx] = result[best] ;
                result[best] = temporal ;
            }
        }

        /*
         * Compose the single linked list (SORTED)
         */
        head = new Node<E>(null, null) ;

        // Create the single linked list
        current = head ;
        for(E element : result)
        {
            temp = new Node<E>(element, null) ;
            current.setNext(temp) ;
            current = current.next();
        }

        /*
         * Copy the single linked list to the array 
         * (Not needed, added just for educational purpose,
             * the result array is already SORTED)
         */

        current = head.next ;
        // copies the values to the result array
        for(int index = 0; current != null ; current = current.next)
            result[index++] = current.value();

        return result ;
    }
0 голосов
/ 21 октября 2010

Я надеюсь, что это то, что вы хотите: 

/**
 * You need to pass in the class of the object you are creating
 * because you can't instantiate a generic class.
 */
public static <E> E[] toArray(E[] a, Class<E> clazz) {
    Node<E> root = null;
    Node<E> prev = null;
    Node<E> curr = null;

    for (E e : a) {
        curr = new Node<E>(e);
        if (prev != null) {
            prev.setNext(curr);
        }
        else {
            root = curr;
        }
        prev = curr;
    }

    curr =  root;

    // Cast is unsafe. I don't know a better way to do this.
    E[] newArray = (E[]) Array.newInstance(clazz, a.length);
    int i = 0; 
    while (curr != null) {
        newArray[i] = curr.value();
        curr = curr.next();
        i++;
    }

    return newArray;
}

Как я уже сказал в коде, я не знаю, как правильно создать экземпляр универсального класса. Кто-нибудь может меня поправить?

0 голосов
/ 21 октября 2010

Очевидный неправильный ответ: 

    E[] toArray(E[] a)
    { return a; }  // Prove I didn't make the linked list.

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

...