Связанный список Deep Copy - O (n) - PullRequest
Новая
       0

Связанный список Deep Copy - O (n)

0 голосов
/ 20 февраля 2011

Я пытаюсь глубоко скопировать связанный список.Мне нужен алгоритм, который выполняется в линейное время O (n).Это то, что у меня есть сейчас, но я не могу понять, что с ним не так.Мое приложение аварийно завершает работу, и я подозреваю, что произошла утечка памяти, которую я пока не смог выяснить.Это то, что у меня есть сейчас 

 struct node {
    struct node *next;
    struct node *ref;
 };


struct node *copy(struct node *root) {
    struct node *i, *j, *new_root = NULL;

    for (i = root, j = NULL; i; j = i, i = i->next) {
        struct node *new_node;
        if (!new_node) 
        {
            abort();
        }
        if (j) 
        {
            j->next = new_node;
        }
        else 
        {
            new_root = new_node;
        }

        new_node->ref = i->ref;
        i->ref = new_node;
    }
    if (j) 
    {
            j->next = NULL;
    }
    for (i = root, j = new_root; i; i = i->next, j = j->next)
        j->ref =i->next->ref;

      return new_root;
}

Может кто-нибудь указать, где я ошибаюсь?

Ответы [ 3 ]

4 голосов
/ 20 февраля 2011

Эта часть одна: 

    struct node *new_node;
    if (!new_node) 
    {
        abort();
    }

Кажется хорошим для случайного abort() события.new_node не присваивается и будет содержать случайное значение.Выражение !new_node уже может быть фатальным (в некоторых системах).

Как общий совет, вам нужно только 1 цикл for.Некоторый код для установки new_root.

Но на самом деле глубокая копия также потребует клонирования того, на что указывает ref.Мне кажется, второй цикл назначает что-то из оригинала в копию.Но я не уверен, что такое ref?

2 голосов
/ 20 февраля 2011

Одна вещь, которую я сразу заметил, состояла в том, что вы никогда не выделяете место для new_node.Поскольку автоматические переменные не гарантируются для инициализации, new_node будет установлен на любое значение, которое было в этой памяти раньше.Возможно, вам следует начать с чего-то вроде: 

struct node *new_node = (new_node *) malloc(sizeof(struct node));

в C или, если вы используете C ++: 

node* new_node = new node;

Копирование списка достаточно просто сделать.Тем не менее, требование, чтобы указатели ссылки указывали на те же узлы в новом списке относительно списка источников, будет трудно выполнить каким-либо эффективным способом.Во-первых, вам нужно каким-то образом определить, на какой узел относительно списка источников они указывают.Вы можете поместить какой-то идентификатор в каждый узел, например, int, для которого в первом узле установлено значение 0, во втором - 1 и т. Д. Затем, после того как вы скопировали список, вы можете сделать еще один проход по списку, чтобы настроитьссылки на ссылки.Проблема этого подхода (кроме добавления другой переменной к каждому узлу) заключается в том, что временная сложность алгоритма переместится с O (n) на O (n ^ 2).

0 голосов
/ 20 февраля 2011

Это возможно, но это требует некоторой работы.Я возьму C ++ и опущу ключевое слово struct в struct node.

. Вам нужно будет провести некоторую бухгалтерию, чтобы отслеживать указатели "ref".Здесь я конвертирую их в числовые индексы в исходный список, а затем обратно в указатели в новый список. 

node *copy_list(node const *head)
{
    // maps "ref" pointers in old list to indices
    std::map<node const *, size_t> ptr_index;
    // maps indices into new list to pointers
    std::map<size_t, node *>       index_ptr;

    size_t length = 0;
    node       *curn; // ptr into new list
    node const *curo; // ptr into old list

    node       *copy = NULL;

    for (curo = head; curo != NULL; curo = curo->next) {
        ptr_index[curo] = length;
        length++;

        // construct copy, disregarding ref for now
        curn = new node;
        curn->next = copy;
        copy = curn;
    }

    curn = copy;
    for (size_t i=0; i < length; i++, curn = curn->next)
        index_ptr[i] = curn;

    // set ref pointers in copy
    for (curo = head, curn = copy; curo != NULL; ) {
        curn->ref = index_ptr[ptr_index[curo->ref]];

        curo = curo->next;
        curn = curn->next;
    }

    return copy;
}

Этот алгоритм работает в O ( n lg n ), поскольку он хранит все элементы списка n в std::map, который имеет сложность вставки и извлечения O (lg n ).Вместо этого его можно сделать линейным с помощью хеш-таблицы.

ПРИМЕЧАНИЕ: не проверено, может содержать ошибки.

...