c++ - 空动态列表

Question

我创建了一个简单的动态模板列表，但在清除整个列表时遇到了一些问题。

List.h

#ifndef LIST_H
#define LIST_H

#include <Node.h>

template <class T> class List
{
public:
    typedef Node<T> node_type;
    typedef node_type* node_pointer;
    typedef T data_type;
    typedef T& reference_type;

    List();
    void push_back(data_type);
    reference_type at(int);
    void clear();
    void swap(int,int);
    int size();

private:
    int list_size = 0;
    node_pointer head, tail;
};

template <class T> List<T>::List()
{
    head=NULL;
    tail=NULL;
}

template <class T> void List<T>::push_back(data_type data)
{
    if(head == NULL) {
        head = new node_type(data);
        tail = head;
    } else {
        node_pointer temp = new node_type(data);
        temp->setNextNull();
        tail->setNext(temp);
        tail = tail->getNext();
    }
    list_size++;
}

template <class T> typename List<T>::reference_type List<T>::at(int x)
{
    node_pointer pointer=head;
    for(int i=0; i<x; i++)
        pointer=pointer->getNext();

    return pointer->getData();
}

template <class T> void List<T>::clear()
{
    node_pointer pointer = head;
    for(int i=0; i<list_size; i++) {
        node_pointer temp = pointer;
        pointer=pointer->getNext();
        delete(temp);
    }
    head=NULL;
    list_size=0;
}



template <class T> void List<T>::swap(int x, int y)
{
    data_type buffer=at(x);
    at(x)=at(y);
    at(y)=buffer;
}

template <class T> int List<T>::size()
{
    return list_size;
}

#endif // LIST_H

Node.h

template <class T> class Node
{
public:
    typedef T data_type;
    typedef T& reference_type;

    Node(data_type _data);
    void setData(data_type);
    void setNextNull();
    void setNext(Node*);

    reference_type getData();
    Node* getNext();

private:
    data_type data;
    Node* next;
};


template <class T> Node<T>::Node(data_type _data) : data(_data)
{
    setNextNull();
}

template <class T> void Node<T>::setData(data_type _data)
{
    data=_data;
}

template <class T> void Node<T>::setNextNull()
{
    next=NULL;
}

template <class T> void Node<T>::setNext(Node* _next)
{
    next=_next;
}

template <class T> typename Node<T>::reference_type Node<T>::getData()
{
    return data;
}

template <class T> typename Node<T>::Node* Node<T>::getNext()
{
    return next;
}

如果我清除调用“清除”方法的列表，几乎所有其他方法都会出现各种错误，但如果我使用列表下方的版本，则效果很好。

template <class T> void List<T>::clear()
{
    head=NULL;
    tail=NULL;
    list_size=0;
}

只有在使用删除功能清除内存时才会出现此问题。我该如何解决这个问题？

Answer 1

您的代码非常危险，因为您跳过了重要的检查。尝试使用以下 at() 的实现:

template <class T> typename List<T>::reference_type List<T>::at(int x)
{
    if (x < 0 || x >= list_size || list_size <= 0)
        return DATA_WITH_ERROR_FLAG; // since you return data instead of pointer,
                                     // you can't return NULL here
                                     // (you need special constant for error status
                                     //  or support it another way)

    node_pointer pointer=head;
    for(int i=0; i<x; i++)
    {
        if (!pointer)
            return DATA_WITH_ERROR_FLAG;
        pointer=pointer->getNext();
    }

    if (!pointer)
        return DATA_WITH_ERROR_FLAG;
    return pointer->getData();
}

在它之后，您必须在每个 at() 调用之后添加检查。例如，您必须修改 swap() 以使其也安全:

template <class T> void List<T>::swap(int x, int y)
{
    data_type v1=at(x);
    data_type v2=at(y);
    if (v1 == DATA_WITH_ERROR_FLAG || v2 == DATA_WITH_ERROR_FLAG)
        return; // and somehow set error flag!
    data_type t=v1;
    v1 = v2;
    v2 = t;
}

即如果你不喜欢这样的问题，你需要到处检查正确性。并且有必要支持错误状态的返回，以简化错误分析。