[c++] problema con l' ordinamento di un vettore di oggetti.

di
squall869
il
10 risposte
S
squall869
Pochi posts
Iscritto da
set, 2011
Messaggi:
6

[c++] problema con l' ordinamento di un vettore di oggetti.

Innanzitutto salve a tutti, mi chiamo Francesco e sono nuovo del forum. Vi scrivo perche non riesco a risolvere da solo una tipologia di esercizi che mi è capitata all' ultimo esame di informatica. Si tratta di scrivere funzioni per l' ordinamento di un vettore di oggetti appartenenti a una classe definita dal professore.
Esempio: 

class Messaggio
{
public:
Messaggio ();
Messaggio (string d,int l);
string get_dest () const;
int get_lunghezza () const;
private:
string dest;
int lunghezza; 
};
per prima cosa il testo dell' esercizio chiede di implementare una classe SMS che eredita alcune funzioni da Messaggio e ne aggiunge altre,naturalmente assumendo implementata questa,e fino a qui nessun problema (credo!).
Il secondo esercizio però mi mette in difficoltà, ecco il testo:
"scrivere una funzione void sort (vector <Messaggio> & v) che ordina un vettore di messaggi in base alla loro lunghezza (in ordine decrescente) e in caso di ugual lunghezza li ordini in base al destinatario (in ordine lessicografico)."
Inoltre richiede di scrivere la complessità dell' algoritmo di ordinamento utilizzato.
Naturalmente ho pensato che la risoluzione del problema fosse legata all' utilizzo di algoritmi di ordinamento come selection_sort, merge_sort, ma ho studiato la loro applicazione soltanto su vettori contenenti parametri e non oggetti. Non so come risolverlo..Vi sarò grato se mi aiuterete. Grazie mille.

10 Risposte

  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: [c++] problema con l' ordinamento di un vettore di oggetti.

    Allora iniziamo da capo. Cosa ti è permesso utilizzare? STL (credo di si visto che parli di vector). Puoi utilizzare la funzione sort di <algorithm>? Puoi utilizzare i template? sai come si dichiarano/svolgono i seguenti funzioni/overload:
    1. overload del costruttore di copia: Messaggio(const Messagio & rhs)
    2. overload di assegnazione (operatore =); Messagio & operator =(const Messagio & rhs)
    3. creazione di un dtor (distruttore): virtual ~Messaggio() (virtual così puoi usare il polimorfismo)
    4. overload del operatore < (less than): Messagio & operator <(const Messagio & rhs)

    Una volta fatti questi funzioni non ti serve altro che mettere la tua funzione di sort sotto forma di template che accetta qualsiasi tipo di variabile (oggetti compresi).
    O meglio ancora utilizzare la funzione sort del header <algorithm> che funziona con tutte le classi che hanno definite le 4 funzioni sopra.

    P.S.: Final Fantasy VIII?
  • S
    squall869
    Pochi posts
    Iscritto da
    set, 2011
    Messaggi:
    6

    Re: [c++] problema con l' ordinamento di un vettore di oggetti.

    Allora aspetta un' attimo...premetto che ho capito poco di ciò che mi hai scritto anche perche al nostro corso il prof non ce le ha nemmeno accennate...per riolvere il mio problem sicuramente bisogna usare questo: 
    
int min_position(vector<int>& a, int from, int to)
{  
   int min_pos = from;
   int i;
   for (i = from + 1; i <= to; i++)
      if (a[i] < a[min_pos]) min_pos = i;
   return min_pos;
}

/** 
   Sorts a vector using the selection sort algorithm
   @param a the vector to sort
*/
void selection_sort(vector<int>& a)
{  
   int next; /* the next position to be set to the minimum */

   for (next = 0; next < a.size() - 1; next++)
   {  
      /* find the position of the minimum */
      int min_pos = min_position(a, next, a.size() - 1);
      if (min_pos != next)
         swap(a[min_pos], a[next]);
   }
}
    come vedrai la prima funzione trova il piu piccolo tra gli elementi di un vettore e la seconda ordina lo stesso...ra queste funzioni vanno bene se il vettore è di numeri, ma se è di oggetti facenti parte di una classe come faccio?
  • S
    squall869
    Pochi posts
    Iscritto da
    set, 2011
    Messaggi:
    6

    Re: [c++] problema con l' ordinamento di un vettore di oggetti.

    P.s. si si proprio squall di ff8..
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: [c++] problema con l' ordinamento di un vettore di oggetti.

    
template <class T>
size_t min_position(vector<T>& a, size_t from, size_t to)
{ 
   size_t min_pos = from;
   size_t i;
   for (i = from + 1; i <= to; i++)
	  if (a[i] < a[min_pos]) min_pos = i;
   return min_pos;
}

/**
   Sorts a vector using the selection sort algorithm
   @param a the vector to sort
*/
template <class T>
void selection_sort(vector<T>& a)
{ 
   size_t next; /* the next position to be set to the minimum */

   for (next = 0; next < a.size() - 1; next++)
   { 
	  /* find the position of the minimum */
	  size_t min_pos = min_position(a, next, a.size() - 1);
	  if (min_pos != next)
		 swap(a[min_pos], a[next]);
   }
}
    adesso devi fare l'overload dell'operatore < (less than) nella tua classe e il sort funziona anche per la tua classe.
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: [c++] problema con l' ordinamento di un vettore di oggetti.

    Esempio finito: 
    
class Messaggio
{
public:
	Messaggio ();
	Messaggio (string d,int l);
	string get_dest () const;
	int get_lunghezza () const;

	bool operator<(const Messaggio & rhs)
	{
		if(lunghezza == rhs.lunghezza)
		{
			return dest < rhs.dest;
		}
		return lunghezza < rhs.lunghezza;
	}
private:
	string dest;
	int lunghezza;
};



template <class T>
size_t min_position(vector<T>& a, size_t from, size_t to)
{ 
   size_t min_pos = from;
   size_t i;
   for (i = from + 1; i <= to; i++)
	  if (a[i] < a[min_pos]) min_pos = i;
   return min_pos;
}

/**
   Sorts a vector using the selection sort algorithm
   @param a the vector to sort
*/
template <class T>
void selection_sort(vector<T>& a)
{ 
   size_t next; /* the next position to be set to the minimum */

   for (next = 0; next < a.size() - 1; next++)
   { 
	  /* find the position of the minimum */
	  size_t min_pos = min_position(a, next, a.size() - 1);
	  if (min_pos != next)
		 swap(a[min_pos], a[next]);
   }
}
  • S
    squall869
    Pochi posts
    Iscritto da
    set, 2011
    Messaggi:
    6

    Re: [c++] problema con l' ordinamento di un vettore di oggetti.

    Grazie skinet...ora in qst giorni lo provo su codeblocks e ti dico. Una cosa,qual' è la difficoltà dell' algoritmo utilizzato?cioè so che per il selection sort in generale effettua N(N - 1) / 2 confronti ed ha una difficoltà dell' ordine O(n^2)...
    grazie ancora
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: [c++] problema con l' ordinamento di un vettore di oggetti.

    Se l'algoritmo l'hai fatto tu saprai anche la complessità no? Cmq credo che sia nel ordine n^2 si.

    se invece utilizzassi il std::sort la complessità sarebbe n*logn
    http://www.cplusplus.com/reference/algorithm/sort
  • S
    squall869
    Pochi posts
    Iscritto da
    set, 2011
    Messaggi:
    6

    Re: [c++] problema con l' ordinamento di un vettore di oggetti.

    Allora ragazzi ho risolto elaborando questa funzione testata e funzionante: 
    void selection(vector <Messaggio>& a)
 {
 int i,j,max;
 for(i=0;i<a.size ()-1;i++)
 {
 max=i;
 for(j=i+1;j<a.size();j++)
 {
 if(a[j].get_lunghezza () > a[max].get_lunghezza ())
 max=j;
 }
 swap(a[max],a[i]);
 }
}
    il problema è che adesso non riesco a fare l' ordinamento in modo alfabetico se la lunghezza risulta uguale!ho elaborato questa funzione:
    
void selezione_per_nome (vector <Messaggio>& a,int n)
{
 int i,j;
 for(i=0;i<n;i++)
 {
 for(j=0;j<n;j++)
 {
if (a[i].get_dest() < a[j].get_dest())
swap(a[j],a[i]);
}
}
}
    anche lei funziona da sola ma non riesco ad accoppiarle..
    dove sbaglio?
  • S
    squall869
    Pochi posts
    Iscritto da
    set, 2011
    Messaggi:
    6

    Re: [c++] problema con l' ordinamento di un vettore di oggetti.

    Allora ho provato cosi: 
    
void selection(vector <Messaggio>& a)
 {
 int i,j,max;
 for(i=0;i<a.size ()-1;i++)
 {
 max=i;
 for(j=i+1;j<a.size();j++)
 {
 if(a[j].get_lunghezza () > a[max].get_lunghezza ())
 max=j;
}
swap(a[max],a[i]);
 else
 {
if(a[j].get_lunghezza () > a[max].get_lunghezza ())
if (a[j].get_dest() < a[max].get_dest())
swap(a[max],a[j]);
 }
 }
 }
}
    pero cosi non mi riconosce la corrispondenza che ce tra if ed else.mi dice :else without a previous if..so che dovrei inserire delle parentesi graffe dopo l' if ma non cambia nulla..uffa..
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: [c++] problema con l' ordinamento di un vettore di oggetti.

    Ma se te l'avevo già fatto, che vai a complicarti la vita 
    
bool operator<(const Messaggio & rhs)
   {
      if(lunghezza == rhs.lunghezza)
      {
         return dest < rhs.dest;
      }
      return lunghezza < rhs.lunghezza;
   }
    vedi return dest < rhs.dest; quello serve per l'ordinamento alfabetico.
Devi accedere o registrarti per scrivere nel forum
10 risposte