mrokas Temat założony przez niniejszego użytkownika |
Program na linuxie działa prawidłowo, na Windows też ale tylko przy debugowaniu, co może być nie tak? » 2014-12-05 23:41:23 Program pisałem na linuxie Ubuntu, program Codeblocks, po przerzuceniu to na Windows wywala mi błędy, chciałem je wychwycić przez debugowanie, jednak tutaj wszystko działa jak należy. Co może być przyczyną? |
|
DejaVu |
» 2014-12-06 00:15:24 Błędny kod. |
|
Tomek_z_W11 |
» 2014-12-06 00:23:03 Błędy, czyli że się nie kompiluje? Czy może daje złe wyniki? Masz na Windowsie dokładnie taką samą wersję C&B jak na linuksie? I taką samą wersję kompilatora? |
|
mrokas Temat założony przez niniejszego użytkownika |
» 2014-12-06 00:43:54 #include <iostream> #include <iomanip> #include <string> #include <cstdlib> #include <vector> #include <fstream>
using namespace std;
struct AVLNode { char imie[ 20 ]; char nazwisko[ 20 ]; char adres[ 30 ]; vector < int > numery; AVLNode * p, * left, * right; int bf; };
int porownaj( AVLNode * pierwszy, AVLNode * drugi ) { for( int i = 0; i < 20; i++ ) { if( pierwszy->nazwisko[ i ] > drugi->nazwisko[ i ] ) { return 1; } else if( pierwszy->nazwisko[ i ] < drugi->nazwisko[ i ] ) { return 2; } } for( int i = 0; i < 20; i++ ) { if( pierwszy->imie[ i ] > drugi->imie[ i ] ) { return 1; } else if( pierwszy->imie[ i ] < drugi->imie[ i ] ) { return 2; } } for( int i = 0; i < 30; i++ ) { if( pierwszy->adres[ i ] > drugi->adres[ i ] ) { return 1; } else if( pierwszy->adres[ i ] < drugi->adres[ i ] ) { return 2; } } return 0; };
class AVL { public: AVLNode * root; int count; AVL(); ~AVL(); AVLNode * rotationRR( AVLNode * A ); AVLNode * rotationLL( AVLNode * A ); AVLNode * rotationRL( AVLNode * A ); AVLNode * rotationLR( AVLNode * A ); bool insert( AVLNode * n ); AVLNode * search( AVLNode * szukany ); AVLNode * maxNode( AVLNode * x ); AVLNode * pred( AVLNode * x ); AVLNode * remove( AVLNode * x ); void walk( AVLNode * x ); };
AVL::AVL() { root = NULL; count = 0; }
AVL::~AVL() { while( root ) delete( remove( root ) ); }
AVLNode * AVL::rotationRR( AVLNode * A ) { AVLNode * B = A->right, * P = A->p; A->right = B->left; if( A->right ) A->right->p = A; B->left = A; B->p = P; A->p = B; if( P ) { if( P->left == A ) P->left = B; else P->right = B; } else root = B; if( B->bf == - 1 ) { A->bf = B->bf = 0; } else { A->bf = - 1; B->bf = 1; } return B; }
AVLNode * AVL::rotationLL( AVLNode * A ) { AVLNode * B = A->left, * P = A->p; A->left = B->right; if( A->left ) A->left->p = A; B->right = A; B->p = P; A->p = B; if( P ) { if( P->left == A ) P->left = B; else P->right = B; } else root = B; if( B->bf == 1 ) { A->bf = B->bf = 0; } else { A->bf = 1; B->bf = - 1; } return B; }
AVLNode * AVL::rotationRL( AVLNode * A ) { AVLNode * B = A->right, * C = B->left, * P = A->p; B->left = C->right; if( B->left ) B->left->p = B; A->right = C->left; if( A->right ) A->right->p = A; C->left = A; C->right = B; A->p = B->p = C; C->p = P; if( P ) { if( P->left == A ) P->left = C; else P->right = C; } else root = C; A->bf =( C->bf == - 1 ) ? 1 : 0; B->bf =( C->bf == 1 ) ? - 1 : 0; C->bf = 0; return C; }
AVLNode * AVL::rotationLR( AVLNode * A ) { AVLNode * B = A->left, * C = B->right, * P = A->p; B->right = C->left; if( B->right ) B->right->p = B; A->left = C->right; if( A->left ) A->left->p = A; C->right = A; C->left = B; A->p = B->p = C; C->p = P; if( P ) { if( P->left == A ) P->left = C; else P->right = C; } else root = C; A->bf =( C->bf == 1 ) ? - 1 : 0; B->bf =( C->bf == - 1 ) ? 1 : 0; C->bf = 0; return C; }
bool AVL::insert( AVLNode * n ) { AVLNode * x = root, * y, * z; y = n->left = n->right = NULL; n->bf = 0; while( x ) { if( x->imie == n->imie && x->nazwisko == n->nazwisko && x->adres == n->adres ) { delete n; return false; } y = x; if( porownaj( x, n ) == 1 ) { x = x->left; } else x = x->right; } count++; if( !( n->p = y ) ) { root = n; return true; } if( porownaj( n, y ) == 1 ) { y->left = n; } else y->right = n; if( y->bf ) { y->bf = 0; return true; } y->bf =( y->left == n ) ? 1 : - 1; z = y->p; while( z ) { if( z->bf ) break; z->bf =( z->left == y ) ? 1 : - 1; y = z; z = z->p; } if( !z ) return true; if( z->bf == 1 ) { if( z->right == y ) { z->bf = 0; return true; } if( y->bf == - 1 ) rotationLR( z ); else rotationLL( z ); return true; } else { if( z->left == y ) { z->bf = 0; return true; } if( y->bf == 1 ) rotationRL( z ); else rotationRR( z ); return true; } }
AVLNode * AVL::search( AVLNode * szukany ) { AVLNode * x = root; while(( x ) &&( porownaj( szukany, x ) != 0 ) ) { if( porownaj( szukany, x ) == 2 ) x = x->left; else x = x->right; } return x; }
AVLNode * AVL::maxNode( AVLNode * x ) { while( x->right ) x = x->right; return x; }
AVLNode * AVL::pred( AVLNode * x ) { if( x->left ) return maxNode( x->left ); AVLNode * y; do { y = x; x = x->p; } while( x &&( x->right != y ) ); return x; }
AVLNode * AVL::remove( AVLNode * x ) { AVLNode * t, * y, * z; bool nest; if(( x->left ) &&( x->right ) ) { y = remove( pred( x ) ); count++; nest = false; } else { if( x->left ) { y = x->left; x->left = NULL; } else { y = x->right; x->right = NULL; } x->bf = 0; nest = true; } if( y ) { y->p = x->p; if( y->left = x->left ) y->left->p = y; if( y->right = x->right ) y->right->p = y; y->bf = x->bf; } if( x->p ) { if( x->p->left == x ) x->p->left = y; else x->p->right = y; } else root = y; if( nest ) { z = y; y = x->p; while( y ) { if( !( y->bf ) ) { y->bf =( y->left == z ) ? - 1 : 1; break; } else { if((( y->bf == 1 ) &&( y->left == z ) ) ||(( y->bf == - 1 ) &&( y->right == z ) ) ) { y->bf = 0; z = y; y = y->p; } else { t =( y->left == z ) ? y->right : y->left; if( !( t->bf ) ) { if( y->bf == 1 ) rotationLL( y ); else rotationRR( y ); break; } else if( y->bf == t->bf ) { if( y->bf == 1 ) rotationLL( y ); else rotationRR( y ); z = t; y = t->p; } else { if( y->bf == 1 ) rotationLR( y ); else rotationRL( y ); z = y->p; y = z->p; } } } } } count--; return x; }
void AVL::walk( AVLNode * x ) { cout << x->imie << " : bf = " << setw( 2 ) << x->bf << " : Lewa -> "; if( x->left ) cout << setw( 3 ) << x->left->imie; else cout << "NULL"; cout << ", Prawa-> "; if( x->right ) cout << setw( 3 ) << x->right->imie; else cout << "NULL"; cout << " : rodzic -> "; if( x->p ) cout << setw( 3 ) << x->p->imie; else cout << "NULL"; cout << endl; if( x->left ) walk( x->left ); if( x->right ) walk( x->right ); }
void add( AVL * T ) { int ile_numerow = 0; int numeros; cout << "Dodawanie nowego rekordu\n" "------------------------\n\n"; AVLNode * w; w = new AVLNode; cout << "Imie: "; cin >> w->imie; cout << "Nazwisko: "; cin >> w->nazwisko; cout << "Adres: "; cin >> w->adres; cout << "Ile numerow telefonow wprowadzic? : "; cin >> ile_numerow; for( int i = 0; i < ile_numerow; i++ ) { cout << "Podaj " << i + 1 << " numer: "; cin >> numeros; w->numery.push_back( numeros ); } T->insert( w ); T->walk( T->root ); }
void wypisz_telefon( AVLNode * e ) { if( e->numery.size() == 0 ) { cout << "Ta osoba nie ma numerow telefonow"; } for( int i = 0; i < e->numery.size(); i++ ) { cout << e->numery[ i ] << "\n"; } }
void del( AVL * T ) { cout << "Usuwanie rekordu:\n" "-----------------\n" "Podaj wartosci rekordu : " << endl; AVLNode * w, * r; r = new AVLNode; cout << "Imie: "; cin >> r->imie; cout << "Nazwisko: "; cin >> r->nazwisko; cout << "Adres: "; cin >> r->adres; w = T->search( r ); if( w ) { delete T->remove( w ); cout << endl; if( T->root ) T->walk( T->root ); } else cout << "Brak takiego rekordu w bazie \n"; }
void check( AVL * T ) { cout << "Szukanie rekordu w drzewie AVL\n" "------------------------------\n\n" "Podaj wartosci rekordu : " << endl; AVLNode * w; w = new AVLNode; cout << "Imie: "; cin >> w->imie; cout << "Nazwisko: "; cin >> w->nazwisko; cout << "Adres: "; cin >> w->adres; system( "clear" ); if( T->search( w ) ) { cout << "Numery telefonow osoby " << T->search( w )->imie << " " << T->search( w )->nazwisko << ": \n"; wypisz_telefon( T->search( w ) ); } else cout << "Brak rekordow o danych podanych przez uzytkownika\n"; cin.get(); cin.get(); }
int main() { AVL * T = new AVL(); int choice; do { system( "clear" ); cout << "Drzewo AVL - Ksiazka telefoniczna \n" "--------------------------------- \n" "0) Zamknij program \n" "1) Dodaj rekord \n" "2) Szukaj rekordu \n" "3) Wyswietl korzen\n" "4) Usun rekord \n" "5) Zapisz do pliku \n" "6) Czytaj z pliku \n" "--------------------------------- \n" "Twoj wybor: "; cin >> choice; system( "clear" ); switch( choice ) { case 1: add( T ); break; case 2: check( T ); break; case 4: del( T ); break; case 7: T->walk( T->root ); cin.get(); cin.get(); break; } if(( choice >= 1 ) &&( choice <= 9 ) ) { cout << endl; system( "pause" ); } } while( choice ); delete T; return 0; }
Sprawdzcie sami, na linuxie wszystko chodzi jak nalezy, przy debugowaniu na Windowsie tez, sprawdziłem cały kod, wszystko moim zdaniem jest dobrze ..[/i][/i] |
|
DejaVu |
» 2014-12-06 02:37:43 Operujesz na wskaźnikach. Na bank masz błąd skoro się aplikacja wywala (no chyba, że masz jakiś stary kompilator GCC z bugami na Windowsa, choć to jest raczej mało prawdopodobna ścieżka). |
|
mrokas Temat założony przez niniejszego użytkownika |
» 2014-12-06 11:22:01 Mi właśnie się wydaje, że jest okej, chodzi tutaj o operację szukania w drzewie binarnym AVL. Dodanie działa, usuwanie odnosi się do funkcji szukania, także usuwanie też nie działa |
|
DejaVu |
» 2014-12-06 13:35:19 Czyli sam sobie odpowiedziałeś na pytanie gdzie jest błąd - albo źle jest zbudowane drzewo AVL albo masz nieprawidłową implementację wyszukiwania. |
|
mrokas Temat założony przez niniejszego użytkownika |
» 2014-12-06 13:37:10 A czy mógłby ktoś swoim okiem zobaczyć na te wyszukiwanie? |
|
« 1 » 2 |