C++链接列表破坏函数

Question

这是有点关于链表的最后question的继续。我已经多做了一些工作，并且陷入了一些我需要实现的功能。我现在有疑问的是destroy（）函数。

它应该释放每个list_ item的内存。该方法是从前端到末尾递归地删除每个list_item，直到找到NULL。但是由于某些原因，它只会从结构中删除键值。虽然节点仍然在那里。

以下是代码 我在list_ destroy（）中评论delete（my_ this）的原因是要检查list_item是否被删除。

#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

你destroy()功能的主要内容是接近正确的 - 唯一真正的错误是一次写入temp和覆盖在如果item参数不是NULL的new list_item的分配。为什么您在拨打delete时不会删除列表项？ （注意：指针不会被delete调用设置为NULL，但指向的对象将被删除。）请澄清！

顺便说一句，你摧毁了整个名单的递归方法仅适用于列表达到一定长度 - 长名单，因为也有destroy()嵌套调用过多可能会获得Stack overflow错误。为此更好地使用循环。

Answer 2

下应该做的伎俩：

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

或者，如果你喜欢的递归解决方案：

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

Answer 3

删除所有的节点后，您需要设置first指针为NULL。由于您没有这样做，您的代码在执行destroy操作后正在访问已释放的内存。

Answer 4

好的。你不应该在销毁函数中分配一个新的列表项。 相反，我会做：

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

delete运算符是不是一个功能，所以可以去掉括号。 把它作为递归函数也有点不寻常。这没有错，但代码更像是更正常的：

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