невозможно удалить узел в двусвязном списке

Я пытаюсь это сделать без указателя головы/начала, который обычно содержит адрес первого узла. У меня есть 3 узла, из которых я пытаюсь удалить последний узел, но этого не происходит. Я могу ошибаться в своей логике, и это моя первая программа со связанными списками, поэтому, пожалуйста, помогите мне!

#include <stdio.h>
#include <stdlib.h>

struct dll {
    struct dll* prev;
    int data;
    struct dll* next;
};

int main() {
    struct dll* p1, *p2, *p3, *temp;
    p1 = malloc(sizeof(struct dll));
    p2 = malloc(sizeof(struct dll));
    p3 = malloc(sizeof(struct dll));
    temp = malloc(sizeof(struct dll));
    p1->prev = NULL;
    p1->data = 1;
    p1->next = p2;
    p2->prev = p1;
    p2->data = 2;
    p2->next = p3;
    p3->prev = p2;
    p3->data = 3;
    p3->next = NULL;
    struct dll* add = NULL;
    int count = 0;
    printf("add of p1::%p add of p2::%p add of p3::%p add of p1->prev::%p add "
           "of p1->next::%p add of p2->prev::%p add of p2->next::%p add of "
           "p3->prev::%p add of p3->next::%p\n",
           p1, p2, p3, p1->prev, p1->next, p2->prev, p2->next, p3->prev,
           p3->next);
    while (p1->next != NULL) {
        count++;
        p1 = p1->next;
    }
    printf("no of nodes %d\n", count + 1);
    puts("enter the addresss of node to delete it");
    scanf("%p", &add);
    while (p1->next != NULL) {
        if (p1->next == add) {
            temp = p1->next;
            p1->next = NULL;
            free(temp);
            temp = NULL;
        } else
            p1 = p1->next;
    }
    puts("after deletion attempted");
    printf("add of p1::%p add of p2::%p add of p3::%p add of p1->prev::%p add "
           "of p1->next::%p add of p2->prev::%p add of p2->next::%p add of "
           "p3->prev::%p add of p3->next::%p\n",
           p1, p2, p3, p1->prev, p1->next, p2->prev, p2->next, p3->prev,
           p3->next);

    while (p1->next != NULL) {
        count++;
        p1 = p1->next;
    }
    printf("no of nodes %d\n", count + 1);
    free(p1);
    p1 = NULL;
    free(p2);
    p2 = NULL;
    free(p3);
    p3 = NULL;
    return 0;
}

выход::::

add of p1::0x9605008 add of p2::0x9605018 add of p3::0x9605028 add of p1->prev::(nil) add of p1->next::0x9605018 add of p2->prev::0x9605008 add of p2->next::0x9605028 add of p3->prev::0x9605018 add of p3->next::(nil)

no of nodes 3

enter the addresss of node to delete it
0x9605028

after deletion attempted

add of p1::0x9605028 add of p2::0x9605018 add of p3::0x9605028 add of p1->prev::0x9605018 add of p1->next::(nil) add of p2->prev::0x9605008 add of p2->next::0x9605028 add of p3->prev::0x9605018 add of p3->next::(nil)

no of nodes 3

В этом примере я пытаюсь удалить узел 3, который является p3, удалив его адрес 0x9605028. Но после удаления количество узлов по-прежнему равно 3, а адреса как неожиданные!


person jeevan    schedule 22.08.2014    source источник
comment
Я вынужден упомянуть, что temp = p1->next приводит к утечке памяти при первом вызове. Указатель temp был инициализирован в верхней части функции как temp=malloc(sizeof(struct dll)). Это указатель. C — это не Java. Фактически, вы могли бы полностью удалить объявление в main() и объявить указатель local-scope внутри фигурных скобок if{} (и, вероятно, было бы понятнее, если бы вы сделали именно это).   -  person WhozCraig    schedule 23.08.2014
comment
Привет, спасибо за ваше время, но я не понял часть утечки памяти, если вы не возражаете, пожалуйста, найдите еще немного времени, чтобы четко объяснить мне, почему утечка памяти ?! На самом деле я в большом замешательстве из-за связанных списков.   -  person jeevan    schedule 23.08.2014
comment
Код должен проверять правильный указатель узла, прежде чем проверять, является ли node...next нулевым. т.е. необходимо исправить следующее: while (p1->next != NULL) { if (p1->next == add) {   -  person user3629249    schedule 23.08.2014


Ответы (3)


Вы не повторно инициализируете свои переменные.

После первого «счета» p1 фактически указывает на третий элемент в списке и никогда не возвращается к началу (на самом деле вы не сохраняете положение начала цикла). Итак, с этого момента p1->next!=NULL ложно. Ни один из двух других циклов не выполняется.

Обратите внимание, что адрес, который вы выведете для p1 после «удаления», такой же, как и для p3. Вы получаете тот же счет только потому, что никогда не устанавливаете count обратно на ноль, прежде чем пытаться снова считать.

person Neal Miller    schedule 22.08.2014
comment
Спасибо! Да, с этого момента я буду заботиться! - person jeevan; 23.08.2014

После этого цикла

while(p1->next!=NULL)
{
    count++;
    p1=p1->next;
}

p1->next равно NULL. Теперь p1 указывает на тот же узел, что и p3. Значит у тебя утечка памяти.

Поскольку p1->next равно NULL, этот цикл

while(p1->next!=NULL)
{
    if(p1->next==add)
    {
        temp = p1->next;
        p1->next=NULL;
        free(temp);
        temp=NULL;
    }
    else
    p1=p1->next;
}

никогда не будет повторяться.

Также нет необходимости выделять память для указателя temp.

temp=malloc(sizeof(struct dll));

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

int count = 0;

for ( temp = p1; temp != NULL; temp = temp->next ) ++count;
person Vlad from Moscow    schedule 22.08.2014
comment
Спасибо! Да, с этого момента я буду заботиться! Ваш ответ тоже правильный, мне помог, но я не могу принять два ответа! Не против! - person jeevan; 23.08.2014

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

  1. создайте указатель, указывающий на узел, который вы хотите удалить, назовем его deleteMe
  2. Создайте еще один указатель, указывающий либо на предыдущий, либо на следующий узел deletMe.
  3. Затем сбросьте свои ссылки.

    (удалитьЯ->предыдущий)->следующий = удалитьЯ->следующий;

    (deleteMe->следующий)->предыдущий = deleteMe->предыдущий;

  4. Теперь вы можете бесплатно удалить меня

  5. Но убедитесь, что у вас есть указатель на один из оставшихся узлов на шаге 2, иначе вы потеряете список из-за утечки памяти.

person Dan    schedule 22.08.2014