добавление или вставка, наконец, в двусвязный список

Я пытаюсь вставить значение в конец двусвязного списка, мне удается вставить значение в начало или первый узел, но второе значение не вставляется

Проблема здесь при вводе второго значения

class d_list
{
private:

    struct node
    {
        double data;
        node *next;
        node *previous;
    };

    node *first;
    node *last ;
public:
    d_list(void)
    {
        first = nullptr;
        last = nullptr;
    };
    void append(double);

};

void d_list::append(double num)
{
    node *ptr;
    node *toinsert;
    if(!first)
    {
        first = new node;
        first->previous= nullptr;
        first->data = num;
        last= new node;
        first->next= last->previous;
        last->previous = first->next;
        last->next= nullptr;

    }
    else
    {
        if(last->next == nullptr)
        {
            ptr = new node;
            ptr->next =last->previous;
            ptr->data=num;
            last->previous = ptr->next  ;
        }


        last->next= nullptr;
    }

}


int _tmain(int argc, _TCHAR* argv[])
{
    d_list aa;
    cout<<"going to append first"<<endl;
    aa.append(44);
    cout<<"going to append second"<<endl;
    aa.append(50.5);

    return 0;
}

person sparkling_spark    schedule 26.02.2012    source источник
comment
Каков симптом? Что вы узнали, когда запускали свою программу в отладчике?   -  person Oliver Charlesworth    schedule 26.02.2012
comment
Пожалуйста, перестаньте писать C++ в конце всех ваших заголовков. Мы знаем, что это C++, потому что он имеет тег c++.   -  person Lightness Races in Orbit    schedule 26.02.2012
comment
несколько раз, когда я вносил изменения, он показывал ошибку нарушения доступа, если сделал твит и он был уничтожен, то я не вижу значения в данных следующего узла головы, а также нет значения в предыдущем или последнем узле.   -  person sparkling_spark    schedule 26.02.2012
comment
@LightnessRacesinOrbit Я пишу это для поисковой системы, я чувствую, что этот заголовок моего вопроса также искали в Google, так что в следующий раз, когда любой Google получит ответ, не используя пробел SO   -  person sparkling_spark    schedule 26.02.2012
comment
@sparkling_spark: Stack Overflow уже помещает первый тег в заголовок и правильно представляет метаданные. Я бы не беспокоился о поисковых системах; SO очень хорошо индексируется, я уверен, вы это заметили. Написание тегов в заголовках в каком-то личном, нетрадиционном, неиндексированном, непоследовательном стиле просто запутывает эту систему и делает поиск хуже.   -  person Lightness Races in Orbit    schedule 26.02.2012
comment
@sparkling_spark Подсказка: last должно всегда указывать на только что добавленный узел. Посмотрите на свои пути управления.   -  person James McLaughlin    schedule 26.02.2012
comment
@JamesMcLaughlin, какая линия? я только что завершил простой связанный список и увидел диаграмму википедии двусвязного списка, а затем написал выше код, что я делаю, так это присваиваю новый указатель (ptr) предыдущему из последних, а затем уже предыдущему последнему со следующим из новых понтер (ptr)   -  person sparkling_spark    schedule 26.02.2012
comment
Добавление тегов к заголовку не обязательно. Пожалуйста, сосредоточьтесь на том, чтобы ваш заголовок описывал суть вашего вопроса.   -  person    schedule 27.02.2012


Ответы (5)


У вас есть ряд проблем в вашем коде:

  • Ваши node следующий и предыдущий элементы никогда и нигде не инициализируются, и в результате они не определены при использовании. Либо добавьте конструктор в node, либо убедитесь, что они инициализированы после выделения.
  • Добавление узла в пустой список некорректно. first->next остается неопределенным, и почему вы создаете два узла, первый и последний? В списке с одним элементом тогда first == last. Установка следующего/предыдущего в первом/последнем также не имеет никакого смысла.
  • В правильно сформированном двусвязном списке last->next всегда должно быть нулевым, как и first->previous.
  • Добавление узла в непустой список также некорректно.
  • Хотя вы не показываете это в примере, вам в конечном итоге понадобится деструктор, а также оператор копирования и конструктор копирования (правило трех). На данный момент у вас происходит утечка памяти, и если вы попытаетесь удалить узлы, вы, скорее всего, получите двойное освобождение и сбой.

Я бы посоветовал немного отступить от кода, чтобы убедиться, что вы правильно понимаете концепции, лежащие в основе двусвязного списка. Нарисуйте список на бумаге со стрелками «следующий/предыдущий» и посмотрите, как их нужно изменить при добавлении узлов в пустой/непустой список, а также как удалять и перемещать узлы. Как только вы выясните, как должен быть установлен следующий/предыдущий, перевод этого в код должен быть относительно простым.

Изменить, чтобы ответить на комментарий: чтобы добавить новый узел, вы можете технически добавить его где угодно, но обычно он добавляется в конце (по крайней мере, из того, что я видел). См. другие ответы для получения полного и правильного кода для добавления новых узлов в пустой и непустой список.

person uesp    schedule 26.02.2012
comment
я высоко ценю экспертов, которые рассказывают об основных понятиях и стимулируют мышление - person sparkling_spark; 26.02.2012
comment
Я понял, что когда я создаю первый узел (путем new), я указываю его предыдущий на null и указываю следующий за последним, теперь вот в чем дело, должен ли я назначить последний для создания нового узла? Я не понимаю запись 2-го элемента в список. - person sparkling_spark; 26.02.2012

...
if(last->next == nullptr)
{
  ptr = new node;
  ptr->next =last->previous; // <- is not correct
  ptr->data=num;
  last->previous = ptr->next  ; // <- does not do anything useful
  ...

Вы не добавляете новый узел в список.

...
if(!last->next)
{
  ptr = new node;
  ptr->previous=last->previous;
  ptr->next =last;
  ptr->data=num;
  last->previous = ptr  ;
  ...

должны быть лучше. Кстати: удалите выделенную память в деструкторе!

person alfa    schedule 26.02.2012
comment
почему это пожалуйста? если(!последний-›следующий) - person sparkling_spark; 26.02.2012
comment
и еще кое-что, пожалуйста, он добавляет данные в конец, но в отладчике он не показывает данные в следующем из первых - person sparkling_spark; 26.02.2012
comment
Да, вы сделали ту же ошибку там. first-›next должен быть последним, а last-›previous должен быть первым для вставки первого элемента. !last-›next совпадает с last-›next == 0. Обратите внимание, что вы должны инициализировать first.next/previous с 0. Создайте для этого конструктор. - person alfa; 26.02.2012
comment
у меня не было? d_list(void) { первый = nullptr; последний = nullptr; }; - person sparkling_spark; 26.02.2012
comment
Вы реализовали конструктор для списка. Вы не реализовали конструктор для node. - person alfa; 26.02.2012

Я бы написал ваш двойной связанный список в следующем коде:

    #include <iostream>
    using namespace std;
    class d_list
    {
    private:

        struct node
        {
            double data;
            node *next;
            node *previous;
        };

        node *first;
        // node *last ; no need for bidirectional list
    public:
        d_list(void)
        {
            first = nullptr;
            //last = nullptr;
        };
        void append(double);

    };

    void d_list::append(double num)
    {
        node *ptr = new node;
        ptr->data = num;
        node *toinsert;
        if(!first)
        {
            first = ptr;
            first->previous=first->next=first;
        }
        else
        {
            if(first->next == first)
            {
                ptr->next = ptr->previous = first;
                first->next = first->previous = ptr;
            }
            else{
                node *last = first->previous;
                ptr->next = first;
                ptr->previous = last;
                last->next = ptr;
                first->previous = ptr;
            }
        }
    }


    int _tmain(int argc, _TCHAR* argv[])
    {
        d_list aa;
        cout<<"going to append first"<<endl;
        aa.append(44);
        cout<<"going to append second"<<endl;
        aa.append(50.5);

        return 0;
    }
person Brent Jiang    schedule 26.02.2012
comment
Мне нужен двунаправленный список ссылок, разве двунаправленный список не нравится вдвойне? - person sparkling_spark; 26.02.2012
comment
Я думаю, что для этого потребуются итерации, если вы хотите вставить в последнюю очередь, не можем ли мы избежать этого, имея двунаправленный список? - person sparkling_spark; 26.02.2012
comment
Я отношусь к двунаправленному списку так же, как к двунаправленному списку ссылок. нет необходимости повторять вставку в последнюю очередь, просто используйте last=first->previous. - person Brent Jiang; 27.02.2012

Зачем вы вставили объявления node *ptr; и node *toinsert;, если вы их не используете? Также должно быть очевидно, что если вы вставляете один узел в конце, то должен быть создан только один новый элемент (и вы вызываете новый дважды, если первый имеет значение null).

person Ivaylo Strandjev    schedule 26.02.2012

Попробуйте этот код...

class d_list 
{


private:
      struct node
      {
         double data;
         node *next;
         node *previous;
     };
      node *first;
     node *last ;

 public:
     d_list(void)
     {
         first = nullptr;
         last = nullptr;
     };

     void append(double);
  }; 

 void d_list::append(double num)
 {
     node *ptr;
     node *toinsert;
     if(!first)
     {
         first = last = new node;
         first->previous= nullptr;
         first->next = nullptr;
         first->data = num;
     }
     else
     {
             ptr = new node;
             ptr->next =last->previous;
             ptr->data=num;
             last->previous = ptr->next  ;
     }
  }


 int _tmain(int argc, _TCHAR* argv[])
 {
     d_list aa;
     cout<<"going to append first"<<endl;
     aa.append(44);
     cout<<"going to append second"<<endl;
     aa.append(50.5);
      return 0;
 } 
person Sachin Mhetre    schedule 07.03.2012