C ++链表删除功能 [英] C++ Linked list destroy function

问题描述

这是我关于链接列表的最后一个问题的继续。我已经做了一些工作，我陷入了一些功能，我需要实现。我现在问的问题是destroy（）函数。

this is kinda a continue of my last question about linked list. I have worked a little more on it and I got stuck at some functions I need to implement. The one I have question on right now is the destroy() function.

它应该释放每个list_项的内存。方法是从前面到结尾递归地删除每个list_item，直到找到NULL。但是由于某种原因，它只会从struct中删除键值。节点仍然存在。

It is supposed to release memory of every list_ item . The approach is to remove every list_item recursivly from the front to the end until NULL is found. However for some reason it will only delete the key value from the struct. The node still there though.

这里是代码
我在list_ destroy（）中注释删除（my_ this）的原因是检查list_item

Here's the code The reason I have commented the delete(my_ this) in list_ destroy() is to check so the list_item is deleted.

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

推荐答案

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

Ok. You should not be allocating a new list item in the destroy function. Instead I would do:

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操作符不是一个函数，因此可以省略括号。
这也是一个不寻常的做这个作为递归函数。这没有错，但是更正常的是让代码更像：

The delete operator is not a function so you can leave off the parentheses. It is also a bit unusual to do this as a recursive function. It is not wrong, but it is more normal to have the code be more like:

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

这篇关于C ++链表删除功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！