Двойные связанные списки в C ++

У меня есть задание, которое требует от нас реализации класса двусвязного списка. По какой-то причине они определили узел struct следующим образом:

struct node {
  node   *next;
  node   *prev;
  T      *o;
};

Мне кажется, что было бы намного проще написать класс, если бы член структуры data не был указателем. Излишне говорить, что я не могу это изменить, поэтому мне придется просто обойти это. Я попытался реализовать метод, который добавляет элемент в начало списка следующим образом:

template <typename T>
void Dlist<T>::insertFront(T *o) {
    node *np = new node;
    T val = *o;

    np->o = &val;
    np->prev = NULL;
    np->next = first;

    if (!isEmpty()) {
        first->prev = np;
    } else {
        last = np;
    }
    first = np;
}

При использовании ddd для отладки я понял, что все работает нормально в первый раз, когда вы вставляете число, но во второй раз все оказывается напортаченным, поскольку как только вы устанавливаете 'val' в новый элемент, он "перезаписывает" первый, так как память был использован адрес val. Я пробовал делать другие вещи, например, вместо того, чтобы просто использовать переменную val, чтобы сделать следующее:

T *valp = new T;
T val;
valp = &val;
val = *o;

np->o = valp

Это тоже не сработало. Я думаю, это потому, что это просто более сложная форма того, что я сделал выше, только с дополнительной утечкой памяти :)

Любые идеи / указатели в правильном направлении были бы замечательными.


c++ pointers linked-list
person Ian Burris    schedule 11.12.2009    source источник
comment
+1 за отказ от ответственности за почетное домашнее задание.   -  person Drew Dormann    schedule 11.12.2009
comment
Взгляните на это, первый ответ может помочь вам понять проблему: stackoverflow.com/questions/5727/   -  person Dan    schedule 11.12.2009
comment
Когда у вас будет возможность, взгляните и на это: stackoverflow.com/questions/599308/ - разница между выделением стека и кучи.   -  person Dan    schedule 11.12.2009

Ответы (5)


arrow_upward
6
arrow_downward

T val, который вы создаете, является автоматической переменной. Ваша ошибка заключается в сохранении адреса этой переменной стека.

Вы должны использовать new для выделения места в куче, как вы подозреваете, но ваш указатель данных должен указывать непосредственно на адрес, возвращаемый new.

Ваша ошибка в вашей последней попытке здесь:

valp = &val;

Вы меняете valp на точку в другом месте (адрес val), когда вы, вероятно, пытаетесь скопировать данные val, а не его адрес.

Данные, переданные вашей функции, должны быть скопированы в новую память, где указывает valp.

person Drew Dormann    schedule 11.12.2009
comment
Ах. Это имеет смысл относительно того, почему я возвращал значения -1074723840, когда пытался прочитать значения. Это помогает, хотя, думаю, я все еще не совсем уверен, как это исправить? Можете ли вы дать мне какие-нибудь ключевые слова, которые могут помочь мне в поиске? Спасибо. - person Ian Burris; 11.12.2009
comment
Просто придирки: val это не временное явление. Это автоматическая переменная, также известная как стековая переменная. В противном случае хороший ответ. - person Dan; 11.12.2009
comment
Отредактировано, надеюсь ответить на ваш комментарий. - person Drew Dormann; 11.12.2009
comment
Совершенно верно, Дэн. И не придирки. Я использовал неправильный термин. - person Drew Dormann; 11.12.2009

arrow_upward
4
arrow_downward

Я не думаю, что вам следует это делать:

T val = *o;

Поскольку член o в структуре узла является указателем, а параметр insertFront также является указателем, ваш инструктор, вероятно, намеревается, чтобы вы взяли данный указатель и сохранили его в списке, а не сделали копию объекта. и сохраните указатель на это. Просто сохраните указатель o, переданный в insertFront, как o член узла, и все будет в порядке.

person Wyzard    schedule 11.12.2009
comment
Я абсолютно согласен. Скорее должно быть np->data = o; - person Samrat Patil; 11.12.2009
comment
Не обязательно. Должны быть некоторые комментарии, объясняющие, динамически ли распределяется переданный T *, и должен ли DList стать владельцем этого или он должен делать копию. Если вы не знаете ответов на эти вопросы, вы не сможете правильно реализовать это, кроме как по счастливой случайности. - person Dan; 11.12.2009
comment
@ Сэмми, откуда ты знаешь, что это не должно быть np->data = new(*o);? - person Dan; 11.12.2009
comment
Извините, ребята, я изменил структуру после копирования ее в SO и забыл изменить ее в других местах. - person Ian Burris; 11.12.2009

arrow_upward
0
arrow_downward 

 T val = *o;

    np->o = &val;

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

person aJ.    schedule 11.12.2009

arrow_upward
0
arrow_downward

Ваш код не соответствует вашему определению node - в node вы определяете член data, но вместо этого в вашем коде вы используете o.

В любом случае вам нужно будет сделать два динамических выделения для добавления каждого узла - одно для самого узла, а второе для объекта данных, на который он будет указывать. Когда вы выделяете этот объект данных, вы также можете назначить возвращаемое значение из new непосредственно указателю в вашем узле. Затем вам нужно скопировать объект данных, указатель которого был передан, в только что выделенный вами объект данных, на который указывает указатель в узле.

person Jerry Coffin    schedule 11.12.2009
comment
Хороший улов. Я изменил структуру после копирования в SO и забыл изменить ее в других местах. - person Ian Burris; 11.12.2009

arrow_upward
0
arrow_downward

Вы думаете, что полезные данные указателя неудобны. Но, возможно, список предназначен для создания ссылки поверх существующих объектов, например:

struct A { int i; };
A as[10] = { 1,2,3,4,5,6,7,8,9,10 };

LinkedList primes_in_my_data;
insertFront( primes_in_my_data, &as[1] );
insertFront( primes_in_my_data, &as[2] );
insertFront( primes_in_my_data, &as[3] );
insertFront( primes_in_my_data, &as[5] );
insertFront( primes_in_my_data, &as[7] );

// now I have a linked list of primes, and caused no extra memory allocation
// (except for the list overhead)
person xtofl    schedule 11.12.2009