сжатие в массиве, хранящем 2 связанных списка - PullRequest
Новая
       13

сжатие в массиве, хранящем 2 связанных списка

0 голосов
/ 04 августа 2011

Массив Arr (размер n) может представлять собой двусвязный список. [Скажите, что у клеток есть struct {int val, next, prev; }]

У меня есть два списка A и B, хранящихся в массиве. A имеет m узлов, а B имеет n - m узлов.

Эти узлы разбросаны, я хочу переставить их так, чтобы все узлы A были из Arr [0] .. Arr [m-1], а остальные заполнены узлами B, за O (m) время.

Решение, которое приходит мне в голову:

  • Итерация A до появления узла, который находится за пределами Arr [m-1]
  • затем итерируйте B, пока не появится узел, который находится перед Arr [m]
  • поменяйте местами два (включая манипулирование следующими предыдущими связями между ними и их соседями).

Однако в этом случае общее количество итераций равно O (n + m). Следовательно, должен быть лучший ответ.

P.S: Этот вопрос возникает в Введение в алгоритмы, 2-е издание . Задача 10.3-5

Ответы [ 2 ]

2 голосов
/ 04 августа 2011

Как насчет итерации по списку A и размещения каждого элемента в Arr[0] ... Arr[m-1], очевидно, меняя свою позицию с тем, что было раньше, а также обновляя ссылки назад / назад.Произойдет много обмена, но, тем не менее, это будет O (м) , поскольку, как только вы закончите итерацию через A ( m итераций), все его элементыбудет расположен (по порядку, между прочим) в первых m слотах Arr, и, таким образом, B должен быть полностью расположен в остальной части Arr.

Чтобы добавить псевдокод 

a := index of head of A 
for i in 0 ... m-1
    swap Arr[i], Arr[a]
    a := index of next element in A
end
0 голосов
/ 03 ноября 2014

Я думаю, что "jw013" правильно, но идея нуждается в некоторых улучшениях:

путем замены вы меняете адрес элементов в массиве Arr.поэтому вы должны быть осторожны с этим!

например, скажем, у нас есть Arr как:

индексы: 0 1 2 3 4 

        | 2 | empty | 3 | empty | 1 |   (assume the link list is like  1 -> 2 -> 3)

так что Arr[4].next0 и Arr[0].next - это 2.

, но когда вы поменяете местами Arr[4] и Arr[0], тогда Arr[0].next будет 0.это не то, чего мы хотим добиться, поэтому мы должны рассмотреть возможность корректировки указателей при замене.

, поэтому код для него будет выглядеть так: 

 public static void compactify(int List_head , int Free , node [] array){
        int List_lenght ;
        
        List_lenght = find_listlenght(List_head , array);
        
        if(List_lenght != 0){ // if the list is not empty
            int a = List_head;
            for (int i = 0; i < List_lenght ; i++) {

                swap( array , a , i );
                a = array[i].next;
                
                print_mem(array);
            }
        }
         
       
    }

теперь при вызове swap: 

private static void swap(node[] array, int a, int i) {
        
        // adjust the next and prev of both array[a] and array[i]
        
        int next_a = array[a].next;
        int next_i = array[i].next;
        
        int prev_a = array[a].prev;
        int prev_i = array[i].prev;
        
        // if array[a] has a next adjust the array[next_a].prev to i
        if(next_a != -1)   
            array[next_a].prev = i;

        // if array[i] has a next adjust the array[next_i].prev to a
        if(next_i != -1)  
            array[next_i].prev = a;

        // like before adjust the pointers of array[prev_a] and array[prev_i] 

        if(prev_a != -1)
            array[prev_a].next = i;

        if(prev_i != -1)
            array[prev_i].next = a;
        
        node temp = array[a];
        array[a] = array[i];
        array[i] = temp;
        
    }
...