Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicit e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Segmentation fault
Forum - C/C++ - Segmentation fault

Pagine: [ 1 2 3 ] Precedente | Prossimo
Avatar
flavio89 (Normal User)
Rookie


Messaggi: 26
Iscritto: 07/09/2011

Segnala al moderatore
Postato alle 12:17
Sabato, 04/02/2012
Ragazzi ho un problema.
Sto lavorando ad un progetto di un dizionario che implementi gli alberi red-black.

Alla compilazione (senza errori) mi viene mostrato il messaggio di Errore Segmentazione.
Uso Code::blocks come IDE.

Allego anche il rar del progetto, che penso sia pi chiaro rispetto a quello che posto su questo thread.
Progetto.rar -> http://tinyurl.com/7gxcohx

Header:
Codice sorgente - presumibilmente C++

  1. #include <string>
  2. #include <list>
  3. #include <iostream>
  4.  
  5.  
  6. using namespace std;
  7. typedef list<string> ELENCO;
  8.  
  9.  
  10. // crea la lista di elementi
  11. ELENCO crea();



Class Header:
Codice sorgente - presumibilmente C/C++

  1. #include "header.h"
  2. #include <list>
  3.  
  4. class word  {
  5.      protected:
  6.           string parola;                                  // chiave
  7.  
  8.           word () {};                                     // costruttore
  9.           ~word ();                                       // distruttore
  10.  
  11.     public:
  12.         string get_parola () {return parola;};            // restituisce la chiave del nodo
  13. };
  14.  
  15. enum color {red,black};                                   // definisco un nuovo tipo di variabile
  16.  
  17. class RedBlack : public word{
  18.      private:
  19.           color colore;                                   // RED = 0      BLACK = 1
  20.           RedBlack* left, *right;                         // puntatore a nodo sx e dx
  21.           RedBlack* parent;                               // puntatore al nodo padre
  22.  
  23.           RedBlack () {};                                 // costruttore
  24.           ~RedBlack ();                                   // distruttore
  25.  
  26.      public:
  27.           RedBlack* build () ;                            // inizializza un albero vuoto
  28.           color get_col () {return colore;};              // torna il colore del nod
  29.           void erase ();
  30.           RedBlack* insert  (RedBlack*&, RedBlack*&, string);         // inserisce nodi all' interno dell' albero
  31.           RedBlack* balance (RedBlack*&, RedBlack*&, string);
  32.           RedBlack* left_rotate (RedBlack*&, RedBlack*&);
  33.           void write (RedBlack*,int);                     // output formattatato dell' albero
  34. };
  35.  
  36. typedef RedBlack* RB;
  37. typedef list <RB> PILA;



Class functions
Codice sorgente - presumibilmente C++

  1. #include  "class_header.h"
  2.  
  3. PILA padre;     // stack globale per trovare nodo padre
  4.  
  5. // inizializza albero vuoto
  6. RB RedBlack::build () {
  7.           RB tree = new RedBlack;
  8.           tree = NULL;
  9.           return tree;
  10. };
  11.  
  12. // pulisco lo stack ed inserisco una sentinella
  13. void RedBlack::erase () {
  14.         padre.clear();
  15.         padre.push_back (NULL);
  16. }
  17.  
  18.  
  19. RB RedBlack::balance (RB &tree,RB &nodo,string chiave) {
  20.     tree = insert (tree,nodo,chiave);
  21.     RB root = tree;
  22.  
  23.     // se radice, colore nero.
  24.     if (nodo == root) {
  25.         nodo->parent = NULL;
  26.         nodo->colore = black;
  27.         }
  28.  
  29.     else nodo->colore = red;
  30.  
  31.     // ripristina lo stack per trovare il padre
  32.     erase ();
  33.  
  34.     RB y;
  35.  
  36.     while ((nodo->parent->colore == red) && (nodo->parent != NULL))  {     // e se il colore del padre ROSSO
  37.             if (nodo->parent == nodo->parent->parent->left) {
  38.              y = nodo->parent->parent->right;
  39.  
  40.             if (y->colore == red) {
  41.                 nodo->parent->colore = black;
  42.                 y->colore = black;
  43.                 nodo->parent->parent->colore = red;
  44.                 nodo = nodo->parent->parent;
  45.                 }   // fine IF
  46.  
  47.             else if (nodo == nodo->parent->right) {
  48.                 nodo = nodo->parent;
  49.               left_rotate (nodo,root);    // albero nodo
  50.                 nodo->parent->colore = black;
  51.                 nodo->parent->parent->colore = red;
  52.                 //right_rotate;   // albero padre padre nodo
  53.                 } // fine ELSE IF
  54.         } // if IF GENERALE
  55.     // -------------------------------------------------------
  56.             else  {
  57.             y = nodo->parent->parent->left;
  58.  
  59.             if (nodo == nodo->parent->left) {
  60.                 nodo = nodo->parent;
  61.                 left_rotate (nodo,root);    // albero nodo
  62.                 nodo->parent->colore = black;
  63.                 nodo->parent->parent->colore = red;
  64.                // right_rotate;   // albero padre padre nodo
  65.                 } // fine IF
  66.  
  67.  
  68.             } // fine ELSE
  69.         }   // fine WHILE
  70.  
  71.         return tree;
  72. }
  73.  
  74. // inserisco il termine all' interno dell' albero
  75. RB RedBlack::insert(RB &tree, RB &nodo, string chiave)  {
  76.  
  77.     // inserisci il termine
  78.     if (tree == NULL) {
  79.     nodo = new RedBlack;
  80.  
  81.     nodo->parola = chiave;
  82.     nodo->left = NULL;
  83.     nodo->right = NULL;
  84.     nodo->parent = padre.back();                        // il padre l' ultimo nodo esaminato
  85. //    tree = nodo;
  86.     return nodo;
  87.     }
  88.  
  89.     // determina la posizione del nodo
  90.     else if (chiave < tree->parola) {
  91.        padre.push_back (tree);                         // salva il nodo appena esaminato per trovare il padre
  92.         return insert (tree->left,nodo,chiave);
  93.     }
  94.  
  95.     else if (chiave > tree->parola) {
  96.          padre.push_back (tree);
  97.             return insert (tree->right,nodo,chiave);
  98.     }
  99. }
  100.  
  101.  
  102. RB RedBlack::left_rotate (RB &nodo,RB& root) {
  103.     RB y;
  104.     y = nodo->right;
  105.     nodo->right = y->left;
  106.  
  107.     if (y->left != NULL) {
  108.         y->left->parent = nodo;
  109.         y->parent = nodo->parent;
  110.  
  111.         if (nodo->parent == NULL) root = y;
  112.         else if (nodo == nodo->parent->left) nodo->parent->left = y;
  113.         else nodo->parent->right = y;
  114.  
  115.     y->left = nodo;
  116.     nodo->parent = y;
  117.     } // fine IF
  118.  
  119.     return nodo;
  120. }
  121.  
  122. // stampa l' albero
  123. void RedBlack::write (RB tree,int i) {
  124.     if (tree != NULL) {
  125.         write (tree->right,i+1);
  126.         for (int j = 1; j <= i; j++) cout << "   ";
  127.  
  128.         cout << tree->parola << endl;
  129.         write (tree->left,i+1);
  130.     }
  131. }



Main:
Codice sorgente - presumibilmente C++

  1. #include "header.h"
  2. #include "class_header.h"
  3.  
  4.  
  5. int main () {
  6.  
  7.     // carica la lista dei termini
  8.     ELENCO termini  = crea();
  9.  
  10.     // inizializza un albero vuoto
  11.     RB tree = tree->build();
  12.  
  13.     // scorri la lista di termini caricata precedentemente
  14.     ELENCO::iterator it;
  15.     it = termini.begin();
  16.  
  17.     RB nodo;
  18.     for (it = termini.begin(); it != termini.end(); it++) tree->balance (tree,nodo,*(it));
  19.     //tree->insert (tree,nodo,*(it));
  20.  
  21.  
  22.     cout << endl;
  23.     // stampa l' albero formattato
  24.     tree->write (tree,1);
  25.  
  26.     return 0;
  27.     }



Functions:
Codice sorgente - presumibilmente C/C++

  1. #include "header.h"
  2.  
  3. // carica termini in memoria mediante una lista
  4. ELENCO crea () {
  5.     ELENCO lista;
  6.  
  7.     lista.push_back ("Casa");
  8.     lista.push_back ("Tavolo");
  9.     lista.push_back ("Macchina");
  10.     lista.push_back ("Abaco");
  11.     lista.push_back ("Abete");
  12.     lista.push_back ("Computer");
  13.     lista.push_back ("Armadio");
  14.     lista.push_back ("Sedia");
  15.     lista.push_back ("Televisore");
  16.     lista.push_back ("Cane");
  17.     lista.push_back ("Fotografia");
  18.     lista.push_back ("Modem");
  19.     lista.push_back ("Cellulare");
  20.     lista.push_back ("Penna");
  21.     lista.push_back ("Gomma");
  22.     lista.push_back ("Ruota");
  23.     lista.push_back ("Mano");
  24.     lista.push_back ("Piede");
  25.     lista.push_back ("Cd");
  26.     lista.push_back ("Disco");
  27.     lista.push_back ("Calamita");
  28.     lista.push_back ("Pioggia");
  29.     lista.push_back ("Sogno");
  30.     lista.push_back ("Segreto");
  31.     lista.push_back ("Schermo");
  32.     lista.push_back ("Mouse");
  33.     lista.push_back ("Chitarra");
  34.     lista.push_back ("Batteria");
  35.     lista.push_back ("Pinza");
  36.     lista.push_back ("Napoli");
  37.     lista.push_back ("Roma");
  38.     lista.push_back ("Milano");
  39.  
  40.     return lista;
  41. }



Aggiungo che secondo il debug, c' un errore nel file class_function, alla riga 36 (while) nella funzione ::balance.

Ultima modifica effettuata da flavio89 il 04/02/2012 alle 12:59


C, con te litigo spesso, ma alla fin fine ti voglio bene
PM Quote
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 5475
Iscritto: 03/01/2010

Segnala al moderatore
Postato alle 13:47
Sabato, 04/02/2012
Questa

RB tree = tree->build();

non ha senso.

Come fai a chiamare un metodo di un oggetto che ancora non esiste?


Ricorda che nessuno obbligato a risponderti e che nessuno perfetto ...
PM Quote
Avatar
flavio89 (Normal User)
Rookie


Messaggi: 26
Iscritto: 07/09/2011

Segnala al moderatore
Postato alle 11:12
Domenica, 05/02/2012
E come dovrei inizializzare l' albero?
Comunque quella parte funziona senza problemi, non voglio contraddirti ma penso l' intoppo ci sia non
appena chiamo la funzione 'balance' (come si segnala anche il debug), pi precisamente la parte del bilanciamento ("tradotta" da uno pseudocodice fornito dal professore) ma sinceramente proprio non riesco a risolvere.


C, con te litigo spesso, ma alla fin fine ti voglio bene
PM Quote
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 5475
Iscritto: 03/01/2010

Segnala al moderatore
Postato alle 11:43
Domenica, 05/02/2012
Io non voglio neanche contraddire il Visual C++ ma ho questo (logico) errore

Run-Time Check Failure #3 - The variable 'tree' is being used without being initialized.


Ricorda che nessuno obbligato a risponderti e che nessuno perfetto ...
PM Quote
Avatar
flavio89 (Normal User)
Rookie


Messaggi: 26
Iscritto: 07/09/2011

Segnala al moderatore
Postato alle 11:45
Domenica, 05/02/2012
quindi come dovrei inizializzare la variabile 'tree'?


C, con te litigo spesso, ma alla fin fine ti voglio bene
PM Quote
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 5475
Iscritto: 03/01/2010

Segnala al moderatore
Postato alle 12:07
Domenica, 05/02/2012
Attraverso il costruttore della sua classe.

Se tree deve essere un oggetto di classe RedBlack, devi usare il costruttore della classe RedBlack. E noto che il costruttore privato ... ma perch?

P.S. Non ho ancora letto il resto del codice ... mi sono solo soffermato su questo primo problema ...


Ricorda che nessuno obbligato a risponderti e che nessuno perfetto ...
PM Quote
Avatar
flavio89 (Normal User)
Rookie


Messaggi: 26
Iscritto: 07/09/2011

Segnala al moderatore
Postato alle 12:12
Domenica, 05/02/2012
Perdonami, quindi una cosa di questo tipo?

Nel MAIN:
RB tree; // inizializzo variabile
tree = RedBlack (tree);

Costruttore con parametri
RB::RedBlack (tree) { tree = new RedBlack; tree->left = NULL; tree->right = NULL; return tree;}



C, con te litigo spesso, ma alla fin fine ti voglio bene
PM Quote
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 5475
Iscritto: 03/01/2010

Segnala al moderatore
Postato alle 12:22
Domenica, 05/02/2012
Non hai molta confidenza con le basi dell'OOP ...

Il costruttore lo dichiari public e scrivi

RedBlack::RedBlack()
{
   left=right=parent = NULL;
   colore = red;
};

(anche il colore deve essere inizializzato)

e quando crei l'oggetto scrivi semplicemente

RB tree = new RedBlack();  


Ricorda che nessuno obbligato a risponderti e che nessuno perfetto ...
PM Quote
Avatar
flavio89 (Normal User)
Rookie


Messaggi: 26
Iscritto: 07/09/2011

Segnala al moderatore
Postato alle 12:29
Domenica, 05/02/2012
effettivamente sono solo 3-4 mesi che programmo ad oggetti.
Ho iniziato il corso a settembre.

Comunque ho corretto, ma persiste l' errore di segmentazione, che il debug di Code::blocks (programmo sotto ubuntu) mi segnala alla riga 44 del file class_function.cpp

Intanto ti ringrazio, perch sei stato molto disponibile con un newbie come me.


C, con te litigo spesso, ma alla fin fine ti voglio bene
PM Quote
Pagine: [ 1 2 3 ] Precedente | Prossimo