Newsgroup: it.comp.lang.c++
Titolo: lista dinamica ordinata

ciao a tutti,
la prof ci ha dato questo esercizio:
Progettare ed implementare una struttura dati LISTA ORDINATA. La struttura
dati deve essere realizzata mediante lista a puntatori. L'implementazione
delle funzioni, ove possibile, deve essere ricorsiva.
L'interfaccia deve prevedere le seguenti operazioni:
1)     creazione della struttura
2)     inserimento di un elemento
3)     eliminazione di un elemento
4)     le funzioni empty e full
5)     stampa della lista
so fare le 5 funzioni richieste non ho capito esattamente cosa si intende
per ORDINATA...
ciao!

 wrote in message
T_Xpa.3256$K35....@news2.tin.it...

Molto semplice, ogni volta che inserisci un elemento non lo inserisci nè in
coda, nè in testa, nè a puffo, ma lo inserisci nel posto tale che tutti gli
elementi precedenti abbiano valore chiave minore (o maggiore) e tutti gli
elementi successivi abbiano valore chiave maggiore (o minore).
Quello che mi sfugge invece è a cosa serva la funzione full se
l'implementazione è svolta con lista concatenata, deve ritornare sempre
false oppure serve nell'eventalità che si esaurisca l'heap?

 false oppure serve nell'eventalità che si esaurisca l'heap?
l'avevo notato anch'io...la prof. ha il vizio di scopiazzare qua e là dal
libro e a volte le sfugge qualcosa...;-))

 ehm...non c'ho capito molto...:-((
se tu inserisci 7 la lista conterra'
7
quando poi inserisci 5, conterra':
5 7
quando inserisci 13:
5 7 13
quando inserisci 9
5 7 9 13
Insomma la lista e' ordinata. i numeri vengono messi in ordine.
Se sono stringhe e non numeri puoi ordinare alfabeticamente. Se sono classi
o altro ci sara' probabilmente un modo per ordinare anche loro....
Tommy

 5 7 13
capito. Sul libro ho trovato questa funzione ma non ho capito l'else...:
//Funzione Inserisce: inserisce l'elemento "e" nella lista ordinata "l"; la
posizione
//in cui avviene l'inserimentoo è tale da mantenere la  lista ordinata
void inserisce(L& l, const E e){
   if ((l==0) || (e<l->elem))
        push(l,e); //inserisce in testa alla lista l
   else inserisce(l->punt,e); //aggiorna l
}
"e" è un intero, l una variabile di tipo puntatore a record.
non ho compreso bene come fa a mantenere la lista ordinata...:-((
ciao!

 non ho compreso bene come fa a mantenere la lista ordinata...:-((
Nell'esercizio del secondo tutorato ad Ingegneria Informatica (Napoli) la
traccia è posta in modo scorretto:
Per lista "ordinata" in realtà si voleva intendere lista "collegata".
E' consigliabile svolgere il tutto con la creazione di una classe che
gestisca dinamicamente la memoria; ergo la funzione full(), ove abbia ancora
senso prevederla, ritornerà sempre true.
--
Domenico Testa - Studente

 senso prevederla, ritornerà sempre true.
infatti sul libro si legge "la funzione full è mantenuta solo  compatibilità
con la versione statica della lista".
Non ho capito bene questa funzione ricorsiva:
void inserisce(L& l, const E e){
   if ((l==0) || (e<l->elem))
        push(l,e); //inserisce in testa alla lista l
   else inserisce(l->punt,e); //aggiorna l
}
puoi darmi una mano?
ciao!


Ovvero:
ipotizzando che L sia una lista di interi e quindi E equivalga al tipo int,
se L contiene 5 7 9 mentre e equivale alla costante 6 inserisce(l,e)
controlla se la lista è vuota (no) oppure se 6<5 (no) quindi chiama
ricorsivamente se stessa passando la lista 7 9 e la stessa e, controlla la
stessa cosa precedente e quindi dopo aver verificato che 6<7 richiama push
passando come parametri il puntatore all'elemento con valore 7 e l'elemento
e, che verrà aggiunto in testa, ovvero prima del 7, ordinatamente rispetto
alla lista generale che diventerà 5 6 7 9.
Però rileggiti il post del tuo collega napoletano Domenico Testa prima di
fare gli esercizi meglio di quanto devi.

 puoi darmi una mano?
se l==0 (nessun elemento nella lista) oppure e<l->elem allora inserisci nel
punto in cui ti trovi (inizio).
altrimenti richiama questa funzione passando l->punt ovvero l nella seconda
chiamata sara' non piu' la tesata delle lista ma il secondo elemento della
lista.
a questo punto riparte tutta la logica da capo:
se l==0 (se c'era un solo elemento, il secondo manca) oppure e<l->elem (del
secondo nodo della lista, non piu' del primo) allora scrivi nel punto in cui
ti trovi (2a pos), altrimenti richiama la funzione con l->punt e quindi
rpeti il tutto un altra volta, ma ora guardando il 3o elem, poi il 4o etc...
La ricorsione termina quando:   if ((l==0) || (e<l->elem)) risulta vera,
inseriamo l'elemento e pian piano ritorianiamo dalle varie chiamate
ricorsive.
Nel codice i commenti sono fatti male:
//inserisce in testa alla lista l
dovrebbe essere:
// inserisce l'elemento nelle lista l nel punto attuale che cambia a seconda
del numero di chiamate ricorsive.
e
//aggiorna l
dovrebbe essere:
// spostiamoci ricorsivamente all'elemento successivo.
Per finire, come esercizio va bene, ma in realta' non si implementerebbe MAI
una cosa di questo genere ricorsivamente!!!
Se hai una lista di 10.000 elementi, rischi di avere 10.000 chiamate
ricorsive e ricordati che sono pesanti (richiedono tempo e spazio sullo
stack). In certi casi la ricorsione va bene, passando in modo iterativo non
si hanno grossi (o nessun) vantaggi, ma in questo caso, la ricorsione e'
orribile! Ma ripeto, come esercizio va bene.
Spero di essere stato piu' chiaro del codice ma ne dubito.
Tommy

 ricorsivamente se stessa passando la lista 7 9 e la stessa e,
si ma come fa a passare la lista 7 9?? come fa a "spostare" il puntatore?
ciao e grazie mille per l'aiuto!


ehm...scusate ci ho pensato su e ora è tutto chiaro!!!
grazie a tutti!!!
ciao!

 Spero di essere stato piu' chiaro del codice ma ne dubito.
chiarissimo, grazie!

 libro e a volte le sfugge qualcosa...;-))
La full esiste per compatibilità con la implementazione "statica" (array)
della listae ritorna sempre false. E comunque, se ti riferisci alla
Vittorini gli esercizi e gli esempi sono gli stessi perchè quel libro è
stato scritto anche da lei! (vedi sezione ringraziamenti)
-- 
# Roberto Natella "Domine"           
http://www.autistici.org/domine/index.php
@a=qw/i p s hax t xlpx u e t o q hx e u l ae f o rrr a k t cn j /;unshift@a,[@
a];chop($b=$b=~/^.{0,$_}/&&$&.(chop$b).$')for 0..length ($b=join$b,a..x);$b=~/
$&/x,$c=$-[0]||$c||length$b,$_.=chop$a[$c],/.$/while$#a>=length;s/$&/ /g,print

 stato scritto anche da lei! (vedi sezione ringraziamenti)
miiiii!!! c'hai ragione! stai nella mia stessa aula? (Ta3)???
ciao!