проблема в указателях

195

26 ноября 2016, 19:02

здравствуйте, пишу односвязный список, вот кусок:

template<typename T>
struct one_list;
template<typename T>
struct node_list {
    node_list(const T& val)
        : data(val), next(nullptr)
    {   
    }
    const T& get_data() {
        return data;
    }
    node_list<T>* get_next() {
        return next;
    }
    friend struct one_list<T>;
private:
    T data;
    node_list<T>* next;
};
template<typename T>
struct one_list {
    typedef node_list<T> node_t;
    one_list()
        : size(0), root(nullptr)
    {
    }
    void push(const T& val) {
        ++size;
        node_t* ptr = &(*(root + (size - 1)));
        ptr = new node_t(val);
        ptr->next = nullptr;
    }
    void pop() {
        if (size) {
            node_t* ptr = root + size - 1;
            delete ptr;
            ptr = nullptr;
            --size;
        }
        else
            throw std::runtime_error("remove nullable element\n");
    }
    const size_t& get_size() {
        return size;
    }
    node_t* get_root() {
        return root;
    }
private:
    size_t size;
    node_t* root;
};
int main() {
one_list<int> list;
    list.push(1);
    list.push(2);
    list.push(3);
    list.pop();
}

вылетает исключение в методе pop в строке с delete ptr... не могу понять почему root остается нулю равным... помогите решить трабл

Answer 1

Функции push и pop некорректные

void push(const T& val) {
    ++size;
    node_t* ptr = &(*(root + (size - 1)));
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    ptr = new node_t(val);
    ptr->next = nullptr;
}

Узлы для списка не выделяются в непрерывном участке памяти, как это имеет место для массивов. Поэтому арифметика указателей здесь не применима. Более того сначала вы указателю ptr присваиваете значение выражения &(*(root + (size - 1))), что само по себе, как уже сказано, не имеет смысла, а затем переписываете это значение новым значением, возвращаемом выражением new node_t(val)

Аналогичные проблемы имеют место с функцией pop.

Функция push может быть написана значительно проще

void push( const T &val ) 
{
    node_t **ptr = &root;
    while ( *ptr ) ptr = &( *ptr )->next;
    *ptr = new node_list<T>( val );
    ++size;
}

Функция pop может выглядеть как

void pop() 
{
    if ( size ) 
    {
        node_t **ptr = &root;
        while ( ( *ptr )->next ) ptr = &( *ptr )->next;
        delete *ptr;
        *ptr = nullptr;
        --size;
    }
    else
    {
        throw std::runtime_error("remove nullable element\n");
    }
}

Имейте в виду, что когда вы определяете односвязный список, то значительно эффективнее добавлять и удалять элементы из начала списка, чем из конца списка, как это вы намереваетесь делать.