Drzewa czerwono czarne crash programu

Question

Witam, próbuję napisać implementację drzew czerwono czarnych w C, jednak po uruchomieniu funkcji dodawanie() program się wysypuje. Funkcja ta najpierw znajduje miejsce, w które ma włożyć nową wartość, a potem zostaje uruchomiona funkcja correct_tree, która ma za zadanie uporządkować drzewo zgodnie z trzema przypadkami. Swój kod opierałem o stronę http://eduinf.waw.pl/inf/alg/001_search/0121.php

Dostaję również warning

|105|warning: conflicting types for 'correct_tree' [enabled by default]|

|76|note: previous implicit declaration of 'correct_tree' was here|

To samo dotyczy funkcji Rot_L i Rot_R odpowiedzialne za rotację odpowiednich korzeni, jednak nie wiem dlaczego się one pojawiają. Być może to one są przyczyną tych crashy. Będę wdzięczny za wszelką pomoc, jeśli napisałem za mało informacji proszę o tym napisać.

mój kod : http://ideone.com/dGVtqO

Answer 1

Ja nie mogę, przez dobre pięć minut zastanawiałem się, co to jest ten "wezel". :) "Nigdy nie słyszałem o żadnym wezelu, o co chodzi...?" Gdybyś pisał identyfikatory po angielsku, byłoby odrobinę wygodniej.

Zaznaczam, że nie analizowałem całości kodu. Tam, gdzie są wskaźniki, należy spodziewać się niespodziewanego, tak więc nie zdziwiłbym się, gdyby błędów było więcej.

Co do warningów jednak da się coś poradzić. Zacznij od deklaracji zapowiadającej funkcję correct_tree. Język C jest paskudny, jeśli chodzi o niezadeklarowane funkcje - jeśli mu coś nie pasuje z argumentem lub zrobi się literówkę (lub użyje funkcji, która nie została jeszcze zdefiniowana, a nie jest zapowiedziana) - kompilator sobie wyczarowuje pasującą mu funkcję z powietrza, która działa w sposób nieprzewidziany.

Comments

Tak warningi udało się usunąć, ale problem jednak został niezmieniony. Wezel to tylko nazwa zmiennej, rzeczywiście powinny być w języku angielskim, ale część kodu jest stara i dlatego część jest po angielsku, a część po polsku.

---

Nie pisze się po polsku, to w złym stylu. A jeśli już, to na pewno nie mieszając polskiego z angielskim. Ale zostawmy to, bo to kwestia drugorzędna.

Odpaliłem debugger. Wyrzuca 'Segmentation fault' w funkcji correct_tree, w linii:

if(tmp->kolor == 'R') //przypadek 1

Przyczyną segfaulta jest przypisanie do tmp wartości:

start->rodzic->rodzic->p_syn

która w momencie drugiej iteracji w main() przy wywołaniu funkcji dodawanie() ma wartość NULL.

---

zmieniłem funkcje dodawanie na 

int dodawanie(int n, struct wezel *X)
{
    X->l_syn = &S;
    X->p_syn = &S;
    X->rodzic = root;
    X->wartosc = n;
    if(X->rodzic == &S) root = X;
    else
    while(true)
    {
        if(n<X->rodzic->wartosc)
        {
            if(X->rodzic->l_syn == &S)
            {
                X->rodzic->l_syn = X;
                break;
            }
            X->rodzic = X->rodzic->l_syn;
        }
        else
        {
            if(X->rodzic->p_syn == &S)
            {
                X->rodzic->p_syn = X;
                break;
            }
            X->rodzic = X->rodzic->p_syn;
        }

    }
    correct_tree(X);
}

i dodałem strażnika

void ustaw_straznika()
{
    S.kolor = 'B';
    S.rodzic = root;
    S.l_syn = &S;
    S.p_syn = &S;
    root = &S;
}

i przy wstawianiu już nie crashuje, ale nie moge teraz wyświetlić tego drzewa funkcją in_order_tree_walk, debugger wyrzuca błąd gdy uruchamiam in_order_tree_walk(start->l_syn);

co może być powodem? 

---

Nie mam pojęcia. Pokaż kod, który otrzymałeś po swoich poprawkach.

Poza tym... czy Ty napisałeś całość tego kodu bez testowania poszczególnych funkcjonalności...?