[C++] Union - Find ??

[Zeldic]

Ciao!! E' da un po' di giorni che ho un problema con l'algoritmo Union - Find, non saprei proprio cosa fare. Ce n'è voluto molto per capire esattamente come funziona (con i due ordinamenti Quick - Union e Quick - Find..), ma ora ad implementarlo è tutta un'altra storia..

Le slide dicono questo :

Tipo di dato : Union Find
Collezione di insiemi disgiunti identificati mediante una etichetta

Operazioni : Makeset( Elemento a )
Crea un insieme formato da un solo elemento, 'a', ed associa all’insieme
l’etichetta 'a'

Union( Insieme A, Insieme B )
Unisce gli elementi degli insiemi A e B in un unico insieme che etichetta
con 'A'. I vecchi insiemi A ed B saranno cancellati

Find( Elemento a )
Restituisce l’etichetta dell’insieme contenente l’elemento a.


Io sono riuscito purtroppo a fare solo questo in codice, per ora :

#include <iostream>
#include <stdlib.h>

using namespace std;


class Union {
  private : 
    struct Nodo {
      char name;
      char elem;
    };
    Nodo* A;                          
    //Nodo* B;    // Ho bisogno di dichiarare anche un altro nodo, 'B',  che è il fratello di 'A'??

  public :          
    Union() { A = NULL; }             
    ~Union() { delete A; }            
    void makeSet(Nodo*, char, char);  
    char unione(Nodo*, Nodo*);        
    char find(Nodo*);                 
    void print(Nodo*);
};

void Union::makeSet(Nodo* A, char n, char e) {     
  cout << "Inserisci il nome del nuovo insieme : ";
  cin >> n;
  cout << "Inserisci l'elemento (carattere) : ";
  cin >> e;
  
  A = new Nodo();   
  A->name = n;               
  A->elem = e;
} 

char Union::unione(Nodo* A) {
  // Non lo so!
void Union::find(Nodo* etichetta) {
  // Nemmeno  :confused:

Ciò che ho bisogno di fare l'ho disegnato nel file in allegato (spero si capisca, anche perché è banale).

Sarei molto grato a chiunque mi darà anche un piccolo suggerimento su come andare avanti nelle funzioni 'unione()' e 'find()', e mi piacerebbe sapere da qualcuno esperto come voi se la classe è corretta, o meglio, ho bisogno di un solo puntatore alla struttura, o due? O sarebbe meglio non utilizzare proprio la struttura, ma semplicemente un campo per il nome del nodo ed uno per l'elemento??

[Zeldic]

.. Nessuno mi può aiutare neanche un po'?? Ho l'esame di Algoritmi tra qualche giorno, e sono messo ancora male.. Per favore...

[Zeldic]

.. Forse ho chiesto troppo, oppure la mia è una domanda troppo banale da non essere degna nemmeno di una risposta??

[shodan]

Probabilmente la prima.

[Zeldic]

up

[Zeldic]

Ciao! Ho ancora dei problemi con la mia Union - Find, che ho terminato di implementare ancora oggi.. Compila, ma non funziona, perché il programma termina subito bruscamente. La mia idea è quella di creare 4 'insiemi' (o liste), costituite dal nome dell'insieme (un carattere) che rappresenta il primo elemento, e da un altro carattere ovviamente collegato ad esso. Ora, effettuando il debug, accade che nell'accedere inizialmente al costruttore, si apre l'header file 'iostream', e poi il programma si chiude.. Perché?? Potete dirmi cortesemente se ho sbagliato a scrivere così?
Io voglio utilizzare il costruttore per assegnare alle 4 strutture i rispettivi valori predefiniti : 'A', 'B', 'C', 'D', e voglio che rimangano quelli durante tutto il programma. Ma come lo faccio col costruttore??

Eccolo :

public : 
  Lista* nodoA, *nodoB, *nodoC, *nodoD;

  Union() { nodoA->name = 'A'; nodoA->nxt = NULL; nodoB->name = 'B'; nodoB->nxt = NULL; nodoC->name = 'C'; nodoC->nxt = NULL; nodoD->name = 'D'; nodoD->nxt = NULL; }

Spero in un vostro aiuto! Ciao!!

[shodan]

Devi però le devi creare le liste.

public : 
  Lista* nodoA, *nodoB, *nodoC, *nodoD;

  Union() {
      nodoA = new Lista;
      nodoA->name = 'A'; 
      nodoA->nxt = NULL; 

      nodoB = new Lista;
      nodoB->name = 'B'; 
      nodoB->nxt = NULL; 
      // etc...

[Zeldic]

Ciao, Shodan!!
Ho apportato quella modifica nel costruttore.. Giustamente prima non allocavo memoria per ciascuna lista. Ora però il debug mi segnala un errore più avanti nel programma :

"Warning : Il programma ha causato una violazione d'accesso. Errore di segmentazione."

E si conclude di nuovo, quando voglio unire l'elemento di una lista (praticamente il secondo, il 'figlio') agli elementi della lista precedente, che diverranno suoi fratelli. Quindi voglio cancellare il padre, che rappresenta il nome della lista.
Questa è la funzione in cui si presenta l'errore :

[CODE]

void internal_union(Lista* l1, Lista* l2) { // Qui gli passo le due liste che voglio unire.
Lista* tmp = l2;
l1->nxt->nxt = l2->nxt;

delete l2;
show(l1);
}

[CODE]

.. Mi sta venendo un dubbio.. E' legale scrivere "->nxt->nxt" per inserire un elemento in terza posizione (le mie 'liste' devono infine essere costituite da 3 elementi)??

Spero di essere stato chiaro..

[shodan]

Intanto dovresti mostrare il nuovo codice (magari in un altro thread), visto che è cambiato. Poi dovresti controllare che il campo a cui devi assegnare qualcosa non sia NULL (come intuisco sia).

[Zeldic]

Intanto dovresti mostrare il nuovo codice (magari in un altro thread), visto che è cambiato. Poi dovresti controllare che il campo a cui devi assegnare qualcosa non sia NULL (come intuisco sia).

.. Sì, hai ragione.. Ho cambiato alcuni parti del mio programma dal mio primo messaggio. Effettivamente risulta nullo il valore dei puntatori nel debug, per questo non si visualizza niente, ma purtroppo non so come fare... :master:

Posto qui il mio codice aggiornato :

#include <iostream>
#include <stdlib.h>

using namespace std;


class Union {
  private : 
    class Lista {                   
      private :                      
        char name;               
        Lista* nxt;

      public :                                       
        Lista() { name = '\0'; nxt = NULL; }   
        ~Lista() { name = '\0'; nxt = NULL; }  
        
    friend class Union;                                   
};  

  public :  
    Lista* nodoA, *nodoB, *nodoC, *nodoD;
    
    Union() {
      nodoA = new Lista(); 
      nodoA->name = 'A'; 
      
      Lista* nodoAfiglio = new Lista();
      nodoAfiglio->nxt = nodoA;
      nodoAfiglio->name = 'a';  
      
      
      nodoB = new Lista();
      nodoB->name = 'B'; 
      
      Lista* nodoBfiglio = new Lista();
      nodoBfiglio->nxt = nodoB;
      nodoBfiglio->name = 'b';
      
      
      nodoC = new Lista();  
      nodoC->name = 'C';
      
      Lista* nodoCfiglio = new Lista();
      nodoCfiglio->nxt = nodoC;
      nodoCfiglio->name = 'c';
      
      
      nodoD = new Lista();
      nodoD->name = 'D'; 
      
      Lista* nodoDfiglio = new Lista();
      nodoDfiglio->nxt = nodoD;
      nodoDfiglio->name = 'd'; 
    }  
    
    ~Union() { delete nodoA; delete nodoB; delete nodoC; delete nodoD; }  
    
    void show(Lista* l1) {
      Lista* ptr = l1;
  
      cout << "Visualizzo la lista cosi' ottenuta : \n\n";
      while(ptr != NULL) {
        cout << "[ " << ptr->name << " ] ";
        ptr = ptr->nxt;
      }
      cout << "\n\n";
    }
    
    void internal_union(Lista* l1, Lista* l2) {
      Lista* tmp = l2;
      l1->nxt->nxt = l2->nxt;
  
      delete l2;
      show(l1);
    }  
    
    void unione() { 
      cout << "Fondiamo gli Insiemi 'A' e 'B' : \n\n";
      internal_union(nodoA, nodoB);
  
      cout << "Fondiamo gli Insiemi 'A' e 'C' : \n\n";
      internal_union(nodoA, nodoC);
  
      cout << "Fondiamo gli Insiemi 'A' e 'D' : \n\n";
      internal_union(nodoA, nodoD);
  
      cout << "Fondiamo gli Insiemi 'B' e 'C' : \n\n";
      internal_union(nodoB, nodoC);
  
      cout << "Fondiamo gli Insiemi 'B' e 'D' : \n\n";
      internal_union(nodoB, nodoD);
  
      cout << "Fondiamo gli Insiemi 'C' e 'D' : \n\n";
      internal_union(nodoC, nodoD);
    }  
};


main() {
  Union obj;
  
  cout << "****************   UNION - FIND   ****************\n\n";
  obj.unione();
  
cout << "Premi Invio per terminare..";
cin.ignore();
return EXIT_SUCCESS;
}