C++ liste liée détruire la fonction

Question

c'est un peu une suite de mon dernier question à propos de la liste chaînée. J'y ai travaillé un peu plus et je me suis retrouvé coincé à certaines fonctions que je devais mettre en place. Celui sur lequel j'ai une question en ce moment est la fonction destroy().

Il est supposé libérer de la mémoire pour chaque élément list_. L'approche consiste à supprimer chaque list_item récursivement du front à la fin jusqu'à ce que NULL soit trouvé. Toutefois, pour une raison quelconque, il supprimera uniquement la valeur de clé de la structure. Le nœud est toujours là.

Voici le code La raison pour laquelle j'ai commenté la suppression (my_ this) dans list_ destroy() est de vérifier que l'élément list_item est supprimé.

#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) 
    list_item *temp = new list_item; 


    if(item) 
    { 
     temp = item; 
     item = temp->next; 
     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); 
// 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) 

    return item; 
} 

//+----------------------------------------------------- 
//| 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) 
    my_list *copy = new my_list; 
    copy = my_this; 
    return *copy; 

} 


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); 


    //destroy the list and its content 
    list_destroy(list); 

    list_remove(list, 3); 
    cout << endl << "Print list" << 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(list); 
    cout << endl << "Print list" << 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

Le contenu principal de vos destroy() fonctions sont presque correcte - la seule erreur réelle est l'attribution du new list_item qui est écrit à temp et écrasé à la fois si le paramètre item n'est pas NULL. Pourquoi pensez-vous que les éléments de la liste ne sont pas supprimés lorsque vous appelez le delete? (NB: les pointeurs ne sont pas définis sur NULL par l'appel delete, mais les objets pointés sont néanmoins supprimés.) Veuillez clarifier!

BTW, votre méthode récursive de détruire toute une liste ne fonctionne que pour les listes jusqu'à une certaine longueur - pour les longues listes vous obtenez une erreur Stack overflow parce qu'il ya trop d'appels imbriqués de destroy(). Mieux vaut utiliser une boucle pour cela.

Answer 2

Ce qui suit devrait faire l'affaire:

void destroy(struct list_item* item) 
{ 
    struct list_item *temp; 
    while (item) 
    { 
    temp = item; 
    item = temp->next; 
    delete(temp); 
    } 
} 

Ou si vous préférez la solution récursive:

void destroy(struct list_item* item) 
{ 
    if (item) { 
    destroy(item->next); 
    delete(item); 
    } 
} 

Answer 3

Après avoir supprimé tous les nœuds, vous devez définir le pointeur NULL first. Puisque vous ne faites pas cela, votre code accède à la mémoire libérée après l'opération destroy.

Answer 4

Ok. Vous ne devez pas allouer un nouvel élément de liste dans la fonction destroy. Au lieu de cela, je le ferais:

void destroy(struct list_item* item) 
{ 
    // ADD YOUR CODE HERE (approx 5 lines) 
    if(item) 
    { 
     list_item *temp = item; 
     item = temp->next; 
     delete temp; 
     destroy(item); 
    } 

L'opérateur suppression n'est pas une fonction de sorte que vous pouvez laisser hors des parenthèses. Il est également un peu inhabituel de le faire comme une fonction récursive. Ce n'est pas faux, mais il est plus normal d'avoir le code plus comme:

void destroy(struct list_item* item) 
{ 
    // ADD YOUR CODE HERE (approx 5 lines) 
    while(item) 
    { 
     list_item *temp = item; 
     item = temp->next; 
     delete temp; 
    }