Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[C++] Kopiec w odwrotnej kolejności; problem z funkcją pop()

Ostatnio zmodyfikowano 2015-01-14 00:06
Autor Wiadomość
olokotampus
Temat założony przez niniejszego użytkownika
[C++] Kopiec w odwrotnej kolejności; problem z funkcją pop()
» 2015-01-11 14:51:12
Mój kopiec jest przechowywany w tablicy intów o znanym z góry rozmiarze, korzeń znajduje się w tab[0]. O ile funkcja push() nie sprawiła mi większych problemów, o tyle tu nie mogę dojść, dlaczego nie działa.. błąd wywala się tylko w pierwszym przypadku, gdy kopiec zawiera 3 i więcej elementów.
edit: w korzeniu jest przechowywana najmniejsza wartość, odwrotnie niż w klasycznym kopcu.

C/C++
void pop( int tab[], int n ) {
    int tmp;
    if( n > 2 ) { //przypadek ogolny
        n--;
        while( tab[ n ] == NULL )
             n--;
       
        tab[ 0 ] = tab[ n ];
        tab[ n ] = NULL;
        //iMn - indeks mniejszego syna
        int x = 0, iMn;
        //petla
        while( tab[ x ] > tab[( x * 2 ) + 1 ] or tab[ x ] > tab[( x + 1 ) * 2 ] ) {
            if( tab[( x * 2 ) + 1 ] < tab[( x + 1 ) * 2 ] )
                 iMn =( x * 2 ) + 1;
            else
                 iMn =( x + 1 ) * 2;
           
            tmp = tab[ iMn ];
            tab[ iMn ] = tab[ x ];
            tab[ x ] = tmp;
            x = iMn;
        }
    }
    else {
        if( n == 2 ) { //przypadek dla tablicy 2-elementowej
            if( tab[ 1 ] < tab[ 0 ] ) {
                tmp = tab[ 0 ];
                tab[ 0 ] = tab[ 1 ];
                tab[ 1 ] = tmp;
            }
        }
        else { //przypadek dla "tablicy" 1-elementowej
            return;
        }
    }
}
P-124651
pekfos
» 2015-01-13 20:01:21
Jaki błąd?
P-124825
olokotampus
Temat założony przez niniejszego użytkownika
» 2015-01-13 21:47:10
Znaczy, kompiluje się, ale to, co otrzymuję po usunięciu ostatniego elementu z kopca, nie jest już kopcem. Jakieś zera (NULLe) w środku, synowie mniejsi od ojców itp. =__= Jak na moje oko, kod powinien właśnie tak być napisany, a mimo to nie widzę, gdzie kryje się błąd.
P-124846
pekfos
» 2015-01-14 00:06:11
Pętla wykonuje za dużo obiegów - wchodzi w zera poza kopcem i pompuje je w górę, więc w praktyce algorytm nie działa na kopcu i z tego powodu nie ma sensu. NULL nie oznacza braku wartości, jak w niektórych językach, i na dodatek używasz tej stałej niezgodnie z przeznaczeniem.
P-124866
« 1 »
  Strona 1 z 1