2

Реализую двусвязный список на С++ без использования STL.

struct DLNode {    //узел списка
    int d;
    DLNode * next,
           * prev;
};

DLNode * AddHeadDL (int data, DLNode * head) {
    DLNode * temp = new DLNode;
    temp->d = data;
    temp->next = head;
    if (head)
        head->prev = temp;
    head = temp;
    temp->prev = NULL;
    return head;
} //функция, добавляющая элемент в начало списка и возвращающая указатель на начало списка

DLNode * RemoveHeadDL (DLNode * head) {
    if (head) {
        DLNode * cur = head;
        head = head->next;
        cur->next = NULL;
        delete cur;
        cur=NULL;
    }
    if (!head)
        cout << "head is null" << endl;
return head;
} //функция, удаляющая первый элемент из списка и возвращающая указатель на список

void ListAll (DLNode * head) {
    if (head) {
        DLNode * cur = head;
        while (cur) {
            cout << cur->d << endl;
            cur=cur->next;
        }
    }
} //функция вывода списка в консоль

/*Текст основной программы*/
int main()
{
    DLNode * head = 0;
    head = AddHeadDL (21, head);
    ListAll (head);
    if (!head->next)
        cout << "end is null" << endl;
    if (!head->prev)
        cout << "prev is null" << endl;
    if (head)
        cout << "list isn't empty" << endl;
    RemoveHeadDL (head);
    if (!head)
        cout << "success" << endl;
    else
        cout << head->d << endl;
    _getch ();
    return 0;
}

После удаления единственного элемента из списка, он продолжает оставаться непустым. При этом, если сделать простую проверку и внутри функции RemoveHeadDL после строки head = head->next; осуществить вывод в консоль: if (!head) cout << "head is null" << endl;, можно легко убедиться, что head никуда не указывает, как и должно быть. Однако, сразу же после использования функции RemoveHeadDL в main, выясняется что head все же указывает на некий узел, содержащий некоторое значение. В чём может быть проблема?

1 ответ 1

1

Вы должны вызывать функцию удаления элемента следующим образом

head = RemoveHeadDL (head);

Иначе head в main не изменится.

Помимо этого в самой функции значение head->prev не устанавливается в NULL.

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

DLNode * RemoveHeadDL( DLNode * head ) 
{
    if ( head ) 
    {
        DLNode * cur = head;
        head = head->next;
        if ( head ) head->prev = NULL;
        delete cur;
    }

    if (!head)
        cout << "head is null" << endl;

    return head;
} //функция, удаляющая первый элемент из списка и возвращающая указатель на список
2
  • Я бы еще добавил, что правильный (или более общий) подход к построению двусвязного списка, это представление его в виде пары указателей, один на голову (на первый), а второй на хвост (на последний) элементы списка.
    – avp
    30 дек 2015 в 21:17
  • @Vlad Благодарю за очень быстрый отклик, решение проблемы и дельное замечание!
    – neonb
    30 дек 2015 в 21:35

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.