C++ связанный список копирования и клон функция

Question

это также продолжение моего связанного списка questions

Я не получил ответа относительно удаления. Когда вызывается delete, фактическое значение удаляется или это только указатель на него?

Для моего вопроса на этот раз о функциях clone() и list_copy(). То, что я хочу делать с этими функциями, - это;

1. Сначала вызовите список _copy(), чтобы скопировать одну структуру в новую структуру.

2. список _copy() вызывает клон(), который будет рекурсивно клонировать все узлы

Проблема у меня с функцией сейчас, что она будет копировать. Однако я получаю только новую структуру, которая указывает на одни и те же значения вместо независимой новой структуры. Интересно, в чем проблема?

#include <iostream> 

using namespace std; 

struct list_item 
{ 
    int key;    // identifies the data 
    double value;   // the data stored 
    struct list_item* next; // a pointer to the next data 
}; 

// Why do you need this? And why would you want it anyway? 
struct my_list 
{ 
    struct list_item* first; // a pointer to the first element of the list 
}; 

//+----------------------------------------------------- 
//| Module:  list_init 
//| Description: Initiate the list to an empty list 
//| Input:  A pointer to the uninitialized list 
//| Result:  The list is empty 
//| Conditions: Assumes the list is uninitialized 
//+----------------------------------------------------- 
void list_init(struct my_list* my_this) 
{ 
    // ADD YOUR CODE HERE (approx 1 line) 
    //set the list NULL at beginning 
    my_this->first = NULL; 
} 

//+----------------------------------------------------- 
//| Module:  list_add 
//| Description: Insert a new key, value pair in a sorted list 
//| Input:  The list to insert in and the key, value to insert 
//| Result:  The list is sorted according to keys and include the 
//|    new key, value pair 
//| Conditions: The list is assumed to be sorted before the insert 
//|    Duplicate keys are allowed. The order of duplicate 
//|    keys is undefined 
//+----------------------------------------------------- 
void list_add(struct my_list* my_this, int key, double value) 
{ 
    // ADD YOUR CODE HERE (approx 23 lines) 

    //create new list_item node 
    list_item* new_node; 

    //allocate memory to it 
    new_node = new list_item; 

    //adding values 
    new_node->key = key; 
    new_node->value = value; 

    if (my_this->first != NULL) 
    { 
     new_node->next = my_this->first; 
    } 
    else 
    { 
     new_node->next = NULL; 
    } 
    my_this->first = new_node; 

} 

//+----------------------------------------------------- 
//| Module:  list_remove 
//| Description: Remove the value with key from a sorted list 
//| Input:  The list to remove from and the key of the value to remove 
//| Result:  The list is sorted and do not contain a value with that key 
//| Conditions: The list is assumed to be sorted before the insert 
//|    If duplicates of the key to remove exist only is removed. 
//|    It is undefined which of the duplicates that are removed. 
//+----------------------------------------------------- 
void list_remove(struct my_list* my_this, int key) 
{ 
    // ADD YOUR CODE HERE (approx 23 lines) 
    list_item *curr; 

    //allokera minne 
    curr = new list_item; 
    curr = my_this->first; 

    list_item *prev = new list_item; 

    for(int i=0; i<key;i++) 
    { 
     prev = curr; 
     curr = curr->next; 

    } 
    prev->next = curr->next; 
    delete(curr); 
} 

//+----------------------------------------------------- 
//| Module:  destroy 
//| Description: First destroy any next list item, then release the 
//|    memory of the specified list item. 
//|    This will recursively destroy an list starting on this item. 
//| Input:  The list item to relese memory for (delete) 
//| Result:  The memory used by the list item, and any linked items, 
//|    are reclaimed by the OS 
//|    Further use of the list item is invalid 
//| Conditions: The item is a pointer allocated with new and not 
//|    deleted before 
//+----------------------------------------------------- 
void destroy(struct list_item* item) 
{ 
    // ADD YOUR CODE HERE (approx 5 lines) 
    if(item) 
    { 
     list_item *temp = item; 
     item = temp->next; 
     cout << "Destroy item" << endl; 
     delete temp; 
     destroy(item); 
    } 
} 

//+----------------------------------------------------- 
//| Module:  list_destroy 
//| Description: Free the memory of an entire list. 
//| Input:  The list to destroy. 
//| Result:  All memory used by the list is reclaimed by the OS. 
//|    The list will become a valid but empty list. 
//| Conditions: The list is initiated and valid. 
//+----------------------------------------------------- 
void list_destroy(struct my_list* my_this) 
{ 
    // ADD YOUR CODE HERE (approx 2 lines) 
    destroy(my_this->first); 
    cout << "Destroy list" << endl; 
    delete(my_this); 
} 

//+----------------------------------------------------- 
//| Module:  clone 
//| Description: First create a new copy of the specified list 
//|    then append to the new item a clone of the next. 
//|    This will recursively create a copy of a entire 
//|    list starting on this item. 
//| Input:  The list item to clone. 
//| Result:  A copy of the specified item and any linked items. 
//| Conditions: The item is valid. 
//+----------------------------------------------------- 
struct list_item* clone(struct list_item* item) 
{ 
    // ADD YOUR CODE HERE (approx 10 lines) 

    list_item *new_node = new list_item; 

    if(item != NULL) 
    { 
     new_node->key = item->key; 
     new_node->value = item->value; 
     new_node->next = item->next; 

     cout <<"Clone "<< item->key << ". " << item->value << endl; 
     clone(item->next); 
    } 
    else 
    { 
     new_node->next = NULL; 
     cout << "END" << endl; 
    } 

    return new_node; 
} 

//+----------------------------------------------------- 
//| Module:  list_copy 
//| Description: Copy an entire list 
//| Input:  The list to copy 
//| Result:  A new and valid list that are an independent copy 
//| Conditions: The list is initiated and valid. 
//+----------------------------------------------------- 
struct my_list list_copy(struct my_list* my_this) 
{ 
    // ADD YOUR CODE HERE (approx 3 lines) 

    //copy of the list which will be returned 
    my_list *foo = new my_list; 


    list_item *temp = new list_item; 
    list_item *temp2 = new list_item; 


    temp = my_this->first; //head 

    temp2 = clone(temp); 

    foo->first = temp2; 

    //this is to check whether clone() worked 
    while(temp2) 
    { 
     cout << "Did it work? " << temp2->value << endl; 
     temp2=temp2->next; 
    } 

    return *foo; 

} 


struct my_iterator 
{ 
    struct list_item* current; // a pointer to the "current" list element 
}; 

//+----------------------------------------------------- 
//| Module:  list_begin 
//| Description: 
//| Input: 
//| Result: 
//| Conditions: 
//+----------------------------------------------------- 
struct my_iterator list_begin(struct my_list* my_this) 
{ 
    struct my_iterator i; 
    i.current = my_this->first; 
    return i; 
} 

//+----------------------------------------------------- 
//| Module:  iterator_end 
//| Description: 
//| Input: 
//| Result: 
//| Conditions: 
//+----------------------------------------------------- 
bool iterator_end(struct my_iterator* i) 
{ 
    return i->current == NULL; 
} 

//+----------------------------------------------------- 
//| Module:  iterator_next 
//| Description: 
//| Input: 
//| Result: 
//| Conditions: 
//+----------------------------------------------------- 
void iterator_next(struct my_iterator* i) 
{ 
    i->current = i->current->next; 
} 

//+----------------------------------------------------- 
//| Module:  iterator_get_key 
//| Description: 
//| Input: 
//| Result: 
//| Conditions: 
//+----------------------------------------------------- 
int iterator_get_key(struct my_iterator* i) 
{ 
    return i->current->key; 
} 

//+----------------------------------------------------- 
//| Module:  iterator_get_value 
//| Description: 
//| Input: 
//| Result: 
//| Conditions: 
//+----------------------------------------------------- 
double iterator_get_value(struct my_iterator* i) 
{ 
    return i->current->value; 
} 

//+----------------------------------------------------- 
//| Module:  main 
//| Description: 
//| Input: 
//| Result: 
//| Conditions: 
//+----------------------------------------------------- 
int main() 
{ 
    // ADD YOUR CODE HERE (approx 50 lines) 
    my_list*list = NULL; 
    list = new my_list; 

    list_init(list); 
    //list->first = NULL; 


    int key = 0; 
    double value = 0; 

    int i =0; 
    while(i <5) 
    { 
     ++i; 
     cin>> value; 
     value = (int) value; 
     key = (int) value; 

     list_add(list,key,value); 
     cout << "Adding" << endl; 


    } 
    my_list *list2 = new my_list; 
// list_init(list2); 
    list2 = &list_copy(list); 




    list_remove(list, 3); 
    cout << endl << "Print list1" << endl; 
    for(my_iterator i = list_begin(list); !iterator_end(&i); iterator_next(&i)) 
    { 
     cout << iterator_get_key(&i) << " " << iterator_get_value(&i) << endl; 
    } 



    cout << endl << "Print list2" << endl; 
    for(my_iterator i = list_begin(list2); !iterator_end(&i); iterator_next(&i)) 
    { 
     cout << iterator_get_key(&i) << " " << iterator_get_value(&i) << endl; 
    } 


    cout << endl << endl; 


    list_destroy(list); 

    cout << endl << "Print list1" << endl; 
    for(my_iterator i = list_begin(list); !iterator_end(&i); iterator_next(&i)) 
    { 
     cout << iterator_get_key(&i) << " " << iterator_get_value(&i) << endl; 
    } 

// list_destroy(list2); 
    return 0; 
} 

Answer 1

Скажите, у вас есть небольшие листы бумаги. Ваш друг пишет письма на них для написания творческих сообщений. Когда он спрашивает у вас некоторое количество промахов, это похоже на вызов оператора new. Когда он закончил и вернет их вам, это delete. Ничто не было уничтожено: это вопрос собственности.

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

Answer 2

У вас здесь много кода. Трудно видеть каждую вещь

new_node->next = item->next; 

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

Ключ и значение не являются указателями, поэтому их значение будет скопировано и фактически клонирует данные.

Обратите внимание, что при вызове клона внутри вашей функции клонирования указатель на выделение памяти отсутствует. Таким образом, вы не сможете вызвать delete на нем, и у вас будет утечка памяти.

EDIT Это может быть решение:

list_item* clone(list_item* item) 
{ 
    list_item *new_node = new list_item; 

    if(item != NULL) 
    { 
     new_node->key = item->key; 
     new_node->value = item->value; 
     //NOTE: this is probably what you want 
     new_node->next = clone(item->next); 
     cout <<"Clone "<< item->key << ". " << item->value << endl; 
    } 

    // NOTE: the clone of NULL should be NULL, not a new list item ! 
    return new_node; 
} 

Однако, как и для образовательных целей (в противном случае вы будете использовать зЬй :: список), попробуйте приложить усилия для развития в C, не в C++. Каждый раз, когда вы добавляете новую функцию или элемент, запустите valgrind, чтобы убедиться, что проблем нет. Только тогда перейдите к реализации новой функции.

Answer 3

Я отвечу на эти вопросы с чисто C++/объектно-ориентированной точки зрения (вопрос отмечен как C++), даже если ваш код намного ближе к C и, возможно, вы ожидаете решения C. Из комментариев видно, что это какое-то упражнение, которое вы пытаетесь реализовать, а комментарии, похоже, для курса C.

Я не получил ответ об удалении.Когда вызывается delete, фактическое значение удаляется или это только указатель на него?

Когда вы вызываете указатель деструктор (для типов классов) вызываемого экземпляра, а затем освобождается память. Для любого класса (structs также являются классами), для которых вы не предоставили деструктор, компилятор будет генерировать один для вас.

Неявно сгенерированный деструктор вызовет деструкторы каждого подобъекта (если они есть), но он ничего не удалит (то есть, память не будет освобождена).

Если вашим классам необходимо управлять ресурсами (включая память), для этого вам следует использовать методы RAII. Двумя простейшими способами это реализация вашего собственного деструктора или сохранение ресурсов в объектах RAII (обычно это интеллектуальные указатели).

В C нет деструктора, кроме RAII ... но тот же факт имеет значение: он не освободит остальную часть списка для вас, вам придется вручную удалить удаление остального элементов в списке.

Проблема, с которой я сейчас сталкиваюсь, заключается в том, что она будет скопирована. Однако я получаю только новую структуру, которая указывает на одни и те же значения вместо независимой новой структуры. Интересно, в чем проблема?

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