двойной связанный список и его удаление

Question

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

struct nodeb
{
    int value;
    nodeb *next;
    nodeb *pre;   //pre of first node and next of last node point to null...
    nodeb(int a,nodeb *ptr1=0, nodeb *ptr2=0):value(a), next(ptr1), pre(ptr2)
    {}
};

class doublelist
{
private:

nodeb *head1,*head2;

public:

doublelist():head1(0),head2(0)
  {cout<<"double list created"<<endl;}


void deletebeg()//delete beginning node
{
    if(head1->next==0)
    {
        nodeb *ptr=head1;
        head1=head2=0;
        delete ptr;
    }
    else 
    {
        nodeb *ptr=head1->next;
        nodeb *ptr1=head1;
        ptr->pre=0;
        head1=ptr;
        delete ptr1;
    }
}


void deleteend()//delete end node
{
    nodeb *ptr=head1;
    nodeb *ptr1;
    while(ptr->next!=0)
    {
        ptr1=ptr;
        ptr=ptr->next;
    } 

    delete ptr;
    ptr1->next=0;
}
};  //class ends here


int main()
{
    doublelist list1;
nodeb node(8);
nodeb node1(7);
nodeb node2(9);
nodeb node3(4);
list1.insertbeg(node);
list1.insertbeg(node1);
    list1.insertafter(node3,1);
list1.insertend(node2);  //insertbeg,insertafter and insertend are three functions i defined to        attach nodes at the beginning,at a particular location and at  the end of the list 
list1.deletebeg();
} 

Может кто-нибудь сказать, пожалуйста, проблема ?? это ссылка на три функции для вставок

Answer 1

Теперь я вижу весь код, проблема очень проста. Ваша функция deletebeg удаляет начальный узел с delete, но вы не выделяете узел с new. Вы должны только delete памяти, если вы создали его с помощью new.

Обычно, когда люди пишут классы связанного списка, они распределяют узлы внутри методов списка, используя new. Тогда они могут безопасно delete узлы внутри методов. Вы делаете удаления, но вы не используете новый. Поэтому вам нужно переписать вашу основную функцию следующим образом:

int main()
{
    doublelist list1;
    list1.insertbeg(8); // add 8 to beginning of list
    list1.insertbeg(7); // add 7 to beginning of list
    list1.insertafter(4,1); // add 4 after first item of list
    list1.insertend(9); // add 9 to end of list
    list1.deletebeg();
} 

Тогда вам нужно переписать ваши методы, как это

void insertbeg(int value)//insert beginning
{
    nodeb* a = new nodeb(value); // allocate node inside of method using new
    if(head1==0)
    {
        head1=a;
        head2=a;
        a->next=0;
        a->pre=0;
    }
    else
    {
        nodeb *ptr=head1;
        ptr->pre=a;
        a->pre=0;
        a->next=ptr;
        head1=a;
    }
}

Я только показал insertbeg, вам нужно изменить все ваши методы вставки таким же образом.

Я не обещаю, что это единственная проблема, но внесите это изменение, и вы будете на правильном пути. Если у вас возникли проблемы, отправьте сообщение снова, но помните отправьте полный код . Это единственный способ получить помощь в решении подобных проблем.

Answer 2

В дополнение к комментариям к моему предыдущему ответу

Этот код неправильный

void insertbeg(int value)//insert beginning
{
    nodeb a(value); // create node on the stack
    if(head1==0)
    {
        head1=&a;
        head2=&a;
        a.next=0;
        a.pre=0;
    }
    else
    {
        nodeb *ptr=head1;
        ptr->pre=&a;
        a.pre=0;
        a.next=ptr;
        head1=&a;
    }
}

Приведенный выше код будет иметь проблему, которую вы описали, когда вы сказали, что head1 и head2 никуда не укажут».Но этот код совершенно другой

void insertbeg(int value)//insert beginning
{
    nodeb* a = new nodeb(value); // allocate node inside of method using new
    if(head1==0)
    {
        head1=a;
        head2=a;
        a->next=0;
        a->pre=0;
    }
    else
    {
        nodeb *ptr=head1;
        ptr->pre=a;
        a->pre=0;
        a->next=ptr;
        head1=a;
    }
}

Он отличается, потому что он использует new для создания объектов.Когда вы используете new объекты не разрушаются при выходе из функции.Вот что означает new.Но когда вы используете new, вы также должны использовать delete, когда закончили работу с узлами.

Answer 3

Несмотря на то, что нередко видеть функции, объявленные вне класса в C ++, это не невозможно.Но это означало бы, что head1 - это глобальная переменная, которая где-то не отображается.

Вы пропустили ту часть, которая фактически вызывает deletebeg и deleteend, поэтому трудно точно сказать, что происходит,Возможно, вы используете указатель после того, как он был удален.

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

Я предполагаю, что вы вызвали deleteend с узлом, который по какой-либо причине имел head1==0, затем ptr1 никогда не инициализировался, и программа зависалапоследняя строка deleteend при попытке разыменования неинициализированного указателя.

Answer 4

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

Функции deletebeg и deleteend не объявлены нигде в определении класса, только после него. Обычно это будет выглядеть примерно так:

class List{
    void aFunction(List * argument);
};  

void List::aFunction(List * argument){
    do something
};

Но, кроме всего прочего, не создавайте свой собственный связанный список, он намного быстрее и облегчит вашу жизнь, используя std::list<int> (заменив int любым типом данных, для которого вы создаете список).

Есть много причин для этого, но главная из них в том, что вам не нужно только писать это, но вам также не нужно отлаживать это. Например, созданная реализация связанного списка использует рекурсивную функцию для удаления самой себя (когда функция вызывает себя, это рекурсивно). Если связанный список очень большой, это может вызвать переполнение стека, вызванное слишком большим количеством функций внутри функций. Такие вещи являются кошмаром, чтобы выследить и найти, и отвлечь вас от реальной причины, по которой вы программируете. Это предполагает, что причина не в создании связанного списка. : P