Usuwanie listy 2-kierunkowej cyklicznej rekurencyjnie - pilne (na 5 rano)

Question

Potrzebuje usunac liste 2-kierunkowa cykliczna rekurencyjnie ale nie wychodzi. Wklejam kod, należy poprawić funkcje removee żeby usuwała całą liste. Liczę na szybką pomoc bo potrzebuje to na zaraz :D

 

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

struct listnode {
    int data;
    struct listnode *next, *previous;
} *listpointer;

struct listnode *create (int data)
{
    struct listnode *first = (struct listnode*)malloc(sizeof(struct listnode));
    if (first)
    {
        first->data=data;
        first->next=first->previous=first;
    }
    return first;
};

struct listnode *findmin (struct listnode *listpointer)
{
    struct listnode *start, *result;
    start=result=listpointer;
    int min = listpointer->data;
    do {
        if (min>listpointer->data)
        {
            min = listpointer -> data;
            result = listpointer;
        }
        listpointer = listpointer -> next;
    }while (listpointer!=start);
    return result;
};

struct listnode *findnext (struct listnode *listpointer, int data)
{
    listpointer=findmin(listpointer);
    struct listnode *start = listpointer;
    do {
        if (listpointer->data>data)
            break;
        listpointer=listpointer->next;
    }while (listpointer!=start);
    return listpointer;
};

void add (struct listnode*listpointer, int data)
{
    if (listpointer)
    {
        struct listnode *newnode = (struct listnode*)malloc(sizeof(struct listnode));
        if (newnode)
        {
            newnode->data=data;
            listpointer = findnext(listpointer, data);
            newnode->next=listpointer;
            newnode->previous=listpointer->previous;
            listpointer->previous->next=newnode;
            listpointer->previous=newnode;
        }
    }
}

struct listnode *deletenode (struct listnode *listpointer, int data)
{
    if (listpointer)
    {
        listpointer = findnext(listpointer, data);
        listpointer = listpointer ->previous;
        if (listpointer->data==data && listpointer==listpointer->next)
        {
            free(listpointer);
            return NULL;
        }
        else
            if (listpointer->data==data)
            {
                struct listnode *next = listpointer -> next;
                listpointer->previous->next = listpointer->next;
                listpointer->next->previous = listpointer->previous;
                free(listpointer);
                listpointer = next;
            }
    }
    return listpointer;;
};

void wypisz (struct listnode *listpointer)
{
    listpointer = findmin(listpointer);
    struct listnode *start = listpointer;
    do {
        printf("%4d", listpointer->data);
        listpointer = listpointer ->next;
    } while (listpointer != start);
}

void removee (struct listnode **listpointer)
{
    if (*listpointer)
    {
        struct listnode *start=*listpointer;
        if (*listpointer != start)
        {

            removee(&(*listpointer)->next);
            free(*listpointer);
        }
    }
}

int main()
{
    listpointer = create(4);
    add(listpointer, 6);
    add(listpointer, 0);
    add(listpointer, 38);
    add(listpointer, 2);
    wypisz(listpointer);
    puts("");
    listpointer = deletenode(listpointer, 77);
    listpointer = deletenode(listpointer, 2);
    listpointer = deletenode(listpointer, 0);
    listpointer = deletenode(listpointer, 38);
    wypisz(listpointer);
    puts("");
    removee(&listpointer);
    wypisz(listpointer);
    puts("");
    return 0;
}

 

Answer 1

struct listnode *start=*listpointer;
if (*listpointer != start)

Nie uważasz, że te dwie linie(103-104) są trochę nielogiczne? Najpierw przypisujesz jednej zmiennej wartość drugiej, a potem kluczowy moment w tej funkcji jest wywoływany jeśli są różne, czyli nigdy nie jest wykorzystywana rekurencja.

Comments

Poprawiłem na "==" i teraz program przestał działać.

---

Skoro teraz wywołuje się za każdym razem nie sądzisz, że lepiej usunąć tego ifa?

A co do programu to po nieco głębszej analizie mogę tylko stwierdzić, że logika jest zepsuta. Nigdzie nie widzę wartownika w postaci NULL'a, przez co nie jest możliwe zrobienie tego w łatwy sposób. Elementy stają się zapętlone i po usunięciu jednego wraca się ponownie do tego samego, który już został usunięty i wywala segfaulta. (Dodaj w linii 106 printf("%d\n",(*listpointer)->data); i zobacz co się dzieje). Nie jestem w stanie pomóc z taką logiką to ją trzeba poprawić w pierwszej kolejności.

Najpoważniejszy błąd to brak NULL'i. Nie ma po czym się orientować czy jesteśmy na liście czy już wyszliśmy poza nią.

Jeżeli lista ma być posortowana to po co funkcja szukająca minimum. Minimum zawsze musi być wskazywane przez head.

Poczytaj o listach i musisz przerobić tą logikę. LINK

---

O to chodzi w liście cyklicznej, że nie ma NULLa i na takiej liście ja muszę to zrobić :P do tego co jest po prostu mam dopisać tą funkcję bez modyfikacji innych :)

Answer 2

Masz problem z zatrzymaniem rekurencji, popraw funkcje wyświetlającą by sprawdzała przypadek gdy listpointer jest nullem

void removerek(struct listnode *ptr)
{
    if (ptr)
    {
        if(ptr->next!=listpointer)
            removerek(ptr->next);
        free(ptr);
    }
}

void removee (struct listnode *ptr)
{
    removerek(ptr);
    listpointer=NULL;
}