C++ 연결된 목록 파괴 기능

Question

이것은 연결된 목록에 대한 내 마지막 question 계속됩니다. 나는 그것에 대해 조금 더 연구했고, 구현해야 할 몇 가지 기능에 매달렸다. 내가 지금 질문하는 것은 destroy() 함수이다.

모든 list_ item의 메모리를 해제해야합니다. 이 방법은 NULL이 발견 될 때까지 모든 list_item을 앞에서 끝까지 반복적으로 제거하는 것입니다. 그러나 어떤 이유로 그것은 단지 구조체에서 키 값을 삭제합니다. 여전히 노드가 있습니다.

다음 코드는 입니다. list_ destroy()에서 삭제 (my_ this)를 주석 처리 한 이유는 list_item이 삭제되도록 확인하는 것입니다. 당신의 destroy() 기능

#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

주요 내용은 거의 정확 - 유일한 진짜 오류가 item 매개 변수 NULL가없는 경우 한 번에 temp에 기록하고 덮어 쓰기하는 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

을, 당신은 NULL로 first 포인터를 설정해야합니다. 이 작업을 수행하지 않으므로 destroy 작업 후에 코드에서 해제 된 메모리에 액세스하고 있습니다.

Answer 4

확인. destroy 함수에 새 목록 항목을 할당하면 안됩니다. 대신 내가 할 것이다 : 당신이 괄호를 생략 할 수

이

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