Newsgroup: it.comp.lang.c++
Titolo: classe insieme

Allora, ieri ho fatto l'esame di c++, una delle due domande era
di realizzare il tipo di dato astratto insieme con elementi di
tipo parametrico con le seguenti operazioni:
- inserimento di un elemento
- cancellazione di un elemento dato
- cardinalita'
- verifica esistenza di un elemento dato
La richiesta era di realizzarlo in due modi: mediante vettore e
record e puntatori. Nessuna possibilita' di utilizzare le librerie
standard (eheh meno male che non si dovrebbe reinventare la ruota! :) ).
A parte il fatto che tra le funzioni manca quella che estrae un
elemento dall'insieme :), che ho aggiunto, ho riflettuto un po'
su come realizzare l'insieme con un vettore... alla fine ho
creato la classe pair (come quella standard) e ho usato un vettore
di coppie <bool, T> dove T e' il tipo parametrico dell'elemento,
usando il valore false per il primo indice se l'elemento e'
cancellato, true altrimenti. Cosa avreste fatto voi?
Cmq secondo me utilizzare un vettore per un insieme e' una cosa
un po' assurda.
-- 
Saluti,
 Francesco Cipriani

 un po' assurda.
Se non hai alcun requisito di prestazioni, puo` andare.
Alex

dello "shift all'ingiu` di tutti gli elementi seguenti".
Io invece ho inefficienza nell'inserimento che cerca il primo posto
libero, mi sa che era meglio quello che dici tu ma l'idea li' per
li' non mi attirava
-- 
Saluti,
 Francesco Cipriani

 li' non mi attirava
Guarda che io pago _anche_ il prezzo di cercare il primo
posto libero -- e` che, in mancanza di specifiche di
prestazioni, la soluzione migliore e` _la piu` semplice_ --
tutto qui.
Alex

In mancanza di altri requisiti, avrei probabilmente utilizzato una lista
ordinata implementata su array nel primo caso, linkata nel secondo.
Paolo
--------------------------------------------------
  Paolo Marotta
  Computer Science, University of Pisa
  home:   
http://www.cli.di.unipi.it/~marotta
--------------------------------------------------

 cancellato, true altrimenti. Cosa avreste fatto voi?
La stessa cosa, anche perchč durante un esame il tempo a disposizione e
poco, e a meno che non ti venga una idea brillante e CHIARA, č un rischio
tentare qualcosa di piů complesso.
Ma gli elementi T dell'insieme erano conosciuti e definiti o dovevano essere
inseriti man mano?
Nel secondo caso ti avrei consigliato (se non lo hai fatto) di ottimizzare
l'array utilizzando un bel insertion sort ordinando il vettore in base agli
elementi T, naturalmente se č definito un ordinamento, ad ogni inserimento.
In questo modo le operazioni di interrogazione (che tu hai inserito) e
eliminazione potevano usufruire di una ricerca binaria.
--
| /
| \Byte - Andrea Briganti
E-Mail 
kbyt...@freemail.it
ICQ 40872731

eliminazione potevano usufruire di una ricerca binaria.
Pero' l'inserimento non oso pensare quanto possa essere pesante con molti
elementi.. Mah, con un array secondo me le implementazioni che si possono
fare di un insieme hanno sempre qualche grossa inefficienza da qualche
parte..
-- 
Saluti,
 Francesco Cipriani

ordinata implementata su array nel primo caso, linkata nel secondo.
A dire il vero pero' non era garantito che fosse definito un
ordinamento tra gli elementi :-)
-- 
Saluti,
 Francesco Cipriani

Avrei una domanda da proporre al NG, qualcuno sa come creare dei files
.LIB con il Turbo C++ 3.0 (non ridetemi dietro...) ?
tnx! :)
[sniper]
________________________________________________________________________________
                   --= Close this world,open the next... =--
                 [sniper] Matrix - 
http://www.sniper2k.cjb.net/
              E-Mail : _
sni...@libero.it
, 
sni...@sniper2k.cjb.net
________________________________________________________________________________
 

tlib miofile.lib +obj1.obj +obj2.obj +obj3.obj ecc..
