Кодирование функции для копирования связанного списка в С++

Ответ 1

Первый вопрос, который вам нужно задать себе, - это семантика копии. В частности, вы используете Student* как node. Что означает копирование содержимого node? Должны ли мы скопировать указатель, чтобы два списка указывали (совместно использовать) те же экземпляры экземпляра, или вы должны выполнить глубокую копию?

struct Listnode {    
  Student *student; // a pointer?  shouldn't this be a `Student` object?
  Listnode *next;
};

Следующий вопрос, который вы должны задать себе, - это то, как вы выделите узлы для второго списка. В настоящее время вы выделяете только 1 node в копии.

Я думаю, что код должен выглядеть больше:

Listnode *SortedList::copyList(Listnode *L) {

    Listnode *current = L;

    // Assume the list contains at least 1 student.
    Listnode *copy = new Listnode;
    copy->student = new Student(*current->student);
    copy->next = NULL;

    // Keep track of first element of the copy.
    Listnode *const head = copy;

    // 1st element already copied.
    current = current->next;

    while (current != NULL) {
       // Allocate the next node and advance `copy` to the element being copied.
       copy = copy->next = new Listnode;

       // Copy the node contents; don't share references to students.
       copy->student = new Student(*current->student);

       // No next element (yet).
       copy->next = NULL;

       // Advance 'current' to the next element
       current = current->next;
    }

    // Return pointer to first (not last) element.
    return head;
}

Если вы предпочитаете делиться студенческими экземплярами между двумя списками, вы можете использовать

copy->student = current->student;

вместо

copy->student = new Student(*current->student);

Ответ 2

Это отличный вопрос, так как вы сделали большую часть работы самостоятельно, намного лучше, чем большинство вопросов "пожалуйста, сделайте мою домашнюю работу для меня".

Несколько пунктов.

Во-первых, что произойдет, если вы перейдете в пустой список? Вы, вероятно, захотите поймать это вверх и просто вернуть пустой список вызывающему.

Во-вторых, вы выделяете только первый node в списке копий, вам нужно сделать один за node в исходном списке.

Что-то вроде (псевдокод (но С++ - как) для домашней работы, извините):

# Detect empty list early.

if current == NULL:
    return NULL;

# Do first node as special case, maintain pointer to last element
# for appending, and start with second original node.

copy = new node()
last = copy

copy->payload = current->payload
current = current->next

# While more nodes to copy.

while current != NULL:
    # Create a new node, tracking last.

    last->next = new node()
    last = last->next

    # Transfer payload and advance pointer in original list.

    last->payload = current->payload
    current = current->next

# Need to terminate new list and return address of its first node

last->next = NULL
return copy

И, хотя вы правы, что вы не должны возвращать указатель на переменную локального стека, это не то, что вы делаете. Переменная, которую вы возвращаете, указывает на выделенную кучу память, которая выдержит функцию выхода.

Ответ 3

Я пытаюсь сделать то же самое. Мои требования:

1. Каждый node является очень простым и простым классом (я отошел от модели структуры).
2. Я хочу создать глубокую копию, а не только указатель на старый связанный список.

Способ, которым я решил сделать это, - это следующий код на С++:

template <class T>
Node <T> * copy(Node <T> * rhs)
{
    Node <T> * current = new Node<T>();
    Node <T> * pHead = current;
    for (Node <T> * p = rhs; p; p = p->pNext)
    {
        Node <T> * prev = current;
        prev->data = p->data;
        if (p->pNext != NULL)
        {
            Node <T> * next = new Node<T>();
            prev->pNext = next;
            current = next;
        }
        else
        {
            prev->pNext = NULL;
        }
    }
    return pHead;
}

Это хорошо работает, без ошибок. Поскольку "голова" - это особый случай, мне нужна моя реализация "текущего" указателя.

Ответ 4

Утверждение copy->next = current->next неправильно. Вы должны сделать

Create the first node copy here
copy->student = current->student;
copy->next = NULL;
while(current->next!=NULL)
{
    Create new node TEMP here
    copy->next = TEMP;
    TEMP->student = current->student;
    TEMP->next = NULL;
    copy = TEMP;
}

Ответ 5

Поскольку вам нужен экземпляр связанного списка, вам нужно создать новый node в цикле, пройдя через исходный список.

Listnode *startCopyNode = copy;

while (current != NULL) {
   *(copy->student) = *(current->student);
    copy->next = new Listnode;
    copy = copy->next;
    current = current->next;
}

copy->next = NULL;
return startCopyNode;

Помните delete узлы связанного списка.

Ответ 6

@pat, я думаю, вы получите seg_fault, потому что вы создаете память только один раз. Вам нужно создать память (в основном вызов "новый" ) для каждого node. Узнайте, где вам нужно использовать "новое" ключевое слово, чтобы создать память для всех узлов.

Как только вы закончите с этим, вам нужно связать его с предыдущим node, так как его односвязный список, вам нужно сохранить указатель на предыдущий node. Если вы хотите учиться и должны помнить всю жизнь, не см. Какой-либо из упомянутых выше кодов. Попытайтесь подумать об упомянутых выше факторах и попытайтесь найти свой собственный код.

Ответ 7

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

Другим фактором, с которым я сталкиваюсь с этой функцией, является идея вернуть указатель на локальную переменную.

Вы не возвращаете указатель на локальную переменную; когда вы вызывали new, вы выделяли память в куче и возвращали указатель на это (что, конечно же, означает, что вам нужно запомнить вызов delete, чтобы освободить его, когда вы закончите с новым списком, извне функция).