C++链表复制和克隆函数

Question

这也是我的链表 questions 的延续

我没有得到关于删除的答案。当调用 delete 时，删除的是实际值还是只是指向它的指针？

这次我的问题是关于 clone() 和 list_copy() 函数。我想用这些功能做的是；

1. 首先调用列表 _copy() 将一个结构复制到一个新结构中。

2. list _copy() 调用 clone() 将递归克隆所有节点

我现在遇到的问题是它会复制。但是，我只得到一个指向相同值的新结构，而不是一个独立的新结构。请问是什么问题？

#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)
    if(item)
    {
        list_item *temp = item;
        item = temp->next;
        cout << "Destroy item" << endl;
        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);
  cout << "Destroy list" << endl;
  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)

    list_item *new_node = new list_item;

    if(item != NULL)
    {
        new_node->key = item->key;
        new_node->value = item->value;
        new_node->next = item->next;

        cout <<"Clone "<< item->key << ". " << item->value << endl;
        clone(item->next);
    }
    else
    {
        new_node->next = NULL;
        cout << "END" << endl;
    }

    return new_node;
}

//+-----------------------------------------------------
//| 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)

    //copy of the list which will be returned
    my_list *foo = new my_list;


    list_item *temp = new list_item;
    list_item *temp2 = new list_item;


    temp = my_this->first; //head

    temp2 = clone(temp);

    foo->first = temp2;

    //this is to check whether clone() worked
    while(temp2)
    {
        cout << "Did it work? " << temp2->value << endl;
        temp2=temp2->next;
    }

    return *foo;

}


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




    list_remove(list, 3);
    cout << endl << "Print list1" << endl;
    for(my_iterator i = list_begin(list); !iterator_end(&i); iterator_next(&i))
    {
        cout << iterator_get_key(&i) << " " << iterator_get_value(&i) << endl;
    }



    cout << endl << "Print list2" << endl;
    for(my_iterator i = list_begin(list2); !iterator_end(&i); iterator_next(&i))
    {
        cout << iterator_get_key(&i) << " " << iterator_get_value(&i) << endl;
    }


    cout << endl << endl;


    list_destroy(list);

    cout << endl << "Print list1" << 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

我将从纯粹的 C++/面向对象的角度回答这个问题(问题被标记为 C++)，即使您的代码更接近 C 并且也许您期待 C 解决方案。从评论看来，这是您正在尝试实现的某种练习，并且评论似乎是针对 C 类(class)的。

I did not get the answer regarding delete. When delete is called is the actual value deleted or is it just the pointer to it?

当您删除 指针时，会调用所指向实例的析构函数(对于类类型)，然后释放内存。对于您没有提供析构函数的任何类(结构也是类)，编译器将为您生成一个。

隐式生成的析构函数将调用每个子对象的析构函数(如果存在)，但它不会删除任何内容(也就是说，不会释放任何内存)。

如果您的类需要管理资源(包括内存)，您应该为此使用 RAII 技术。最简单的两种方法是实现您自己的析构函数，或者将资源存储在 RAII 对象(通常是智能指针)中。

在 C 中，没有析构函数，也没有 RAII...但同样的事实也是如此:它不会为您释放列表的其余部分，您必须手动删除其余部分列表中的元素。

The issue I have with the function now is that it will copy. However I only get a new struct which points to the same values instead for an independent new struct. I wonder what the problem is?

最简单的答案是您应该提供一个复制列表尾部的复制构造函数。