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