11.7 Sintesi Sugli Attributi Delle Strutture Dati

Transcript

appunti java pag. 182 11.7 Sintesi sugli attributi delle strutture dati Non rimane infine che costruire una tabella di sintesi che metta a confronto tutte le strutture Dati studiate. La tabella sarà più dettagliata di quella originaria in quanto si cercherà di dare conto anche dei diversi tempi di inserimento/generazione di una struttura, cancellazione e ricerca di un dato. Struttura Dati Array (semi stat.) Mod. Accesso Dim.nto Organizzazione Persistenza Lettura Dato Inserimento Dato Sequen. Indiciz. Statico(*) Volatile Ripetibile Veloce (10-8) [°] Sequen. Lista (LinkedList) Dinamico Volatile Ripetibile Veloce (10-8) [°] In coda Ovunq. ma lento O(n/2) In mezzo (Lento) O(lgn) (u) Sovrascr. In coda Ovunq. rapido O(n/2) In mezzo Vector Sequen. Indiciz. Dinamico Volatile Ripetibile Veloce (10-8) [°] Albero (TreeSet) Insieme (HashSet) File Testo Iterator Con Key Dinamico Disordinata Ordinata(u) Duplicati Disordinata Ordinata(u) Duplicati Disordinata Ordinata(u) Duplicati Ordinata Senza Dup. Volatile Ripetibile Veloce (10-8) [°] Iterator Con Key Dinamico Senza Dup. Volatile Sequen. Dinamico Disodinata Perm.te File Dati Sequen. Indiciz. Dinamico Disordinata Ordinata(u) Duplicati Perm.te Sequen. Dinamico Volatile Sequen. Dinamico Ord. Di ins. Duplicati Ord. Di ins. Duplicati Strutture Filtro Coda Pila (Stack) Volatile Cancell. Dato Ricerca un Dato O(n/2) O(lgn) (u) Generaz. struttura Rapida Rapida In coda In mezzo Sovrascr. In Ordine Ovunq. rapido Ovunq. V. media O(lgn) V. media Ripetibile Veloce (10-8) [°] Senza Ordine Ovunq. rapido V. media Ripetibile Lenta (10-3) [°] Ripetibile Lenta (10-3) [°] In Coda Ricop. lentissima O(n/2) Molto Lenta In Coda Sovrascr. Ricop. lentissima O(n/2) O(lgn) (u) Molto Lenta Distruttiva Veloce (10-8) [°] Distruttiva Veloce (10-8) [°] In Coda In Testa rapida Rapida In Testa In Testa rapida Rapida O(lgn) Rapida appunti java pag. 183 (*) l’array in java è allocato dinamicamente ma non può crescere in modo dinamico. (u) significa che per ottenere l’ordinamento o una ricerca di complessità logaritmica è necessario un algoritmo dell’utente. [°] la velocità di accesso 10-8 indica una tipica velocità di lettura in RAM, 10-3 una lettura su supporto esterno. • • Rapido, Semi Rapido, Lento, Molto Lento, Lentissimo, Si riferiscono rispettivamente: Rapido=velocità di semplice scrittura in Ram, Semi Rapido=scrittura in RAM con risistemazione di parte della struttura, Lenta=riscrittura in RAM di buona parte della struttura, Molto Lento=scrittura di un dato su dispositivo magnetico in sequenza, Lentissima = Riscrittura completa della struttura su disp. esterno. O(n/2) e O(lgn) significano rispettivamente che gli algoritmi di ricerca di un dato sono proporzionale a n/2 o al logn. appunti java pag. 180 11.E – Esercizi Esercizi su Liste 1. Si desidera progettare un programma che "Acquisisca il suo input da un testo contenuto in una Stringa e inserisca ciascuna parola del testo in una Lista”. Indicazioni: Fare uso si uno StreamTokenizer per isolare le Parole del testo. Richieste: • Progettare una classe opportuna ScanPar_01 che ottenga le funzionalità desiderate; • Testarne il funzionamento con un main() opportuno. 2. Generalizzare la classe progettata nell’esercizio 1) e chiamarla ScanPar_02 in modo che “a partire da un Testo contenuto indifferentemente sia in una Stringa che in un File di testo, ottenga sempre la lista delle parole”. La classe dovrebbe fornire anche la funzionalità aggiuntiva restituire un array di parole. 3. Generalizzare la classe progettata nell’esercizio 1) e chiamarla ScanPar_03 in modo che “restituisca le parole anche in ordine Lessicografico sia in un array che in una lista”. 4. Generalizzare la classe progettata nell’esercizio 1) e chiamarla ScanPar_04 e progettarne una seconda di nome Nodo in modo che “restituisca un elenco Ordinato di Oggetti Nodo costituito delle parole contenute nel testo con a fianco il numero di volte con cui ogni parola compare”. 5. Generalizzare la classe progettata nell’esercizio 1) e chiamarla ScanPar_05 inserendo un metodo che “consenta di stampare l’indice analitico di una parola assegnata del testo scandito”. Per indice analitico si intende la restituzione della parola con a fianco i numeri delle righe sulle quali la parola si trova nel testo. Es. se sul problema 5 si cerca la parola testo si deve ottenere: testo : 3, 5, 6 Esercizi sui Vector 6. Progettare una classe Misto che “Generi un Vector casuale sia per la distribuzione che per i valori delle componenti che devono essere Integer o Double in un range identico” . Es. se si chiedono 5 elementi questi saranno casualmente Integer o Double e avranno valori Integer nell’intervallo [MinMax] e Double nello stesso intervallo [Min.00000 – Max] 7. Generalizzare la classe del precedente esercizio 6) implementando un metodo che restituisca il Vector anche ordinato in modo crescente. appunti java pag. 181 8. Generalizzare la classe del precedente esercizio 7) implementando “un metodo di ricerca Dicotomina di un valore Integer o Double assegnato”. Richieste: Se il numero è presente ne restituisce la posizione se no la posizione corretta di inserimento. 9. Dopo aver generato un Vector Ordinato di grandi dimensioni [5.000, 10.000, 20.000 numeri] usando le classi precedenti, si desidera realizzare un main() che confronti i tempi a) di Ordinamento del vettore, b) di Ricerca Dicotomica della classe( 8) c) di ricerca interna alla Classe Vector. Esercizi su Insiemi 10. “Progettare e implementare la sottoclasse Insieme della classe HashTree come indicato nel capitolo”. 11. Per testare la classe 10) “Generare un Insieme con i numeri da 1 a 25 e stamparlo, eliminare tutti i numeri multipli di 2 e 3 e stamparlo ancora" 12. Per testare la classe 10) "Generare due insiemi con le parole dei due testi distinti contenuti in due stringhe, stamparli, ottenere Unione, Intersezione e le due Differenze e stamparle ancora" 13. Costrure una classe che "che restituisca in un Insieme i numeri primi compresi tra 2 e N, con N scelto dall’utente. Si utilizzi l’algoritmo di Eratostene. " 14. Costrure una classe che "che restituisca in un Insieme i numeri primi compresi tra 2 e N, con N scelto dall’utente. Si utilizzi un algoritmo DIVERSO da quello di Eratostene " 15. Costruire un programma “che confronti la velocità di esecuzione dei due algoritmi precedenti” Esercizi su collezioni 16. “Progettare un programma main con il minimo numero di righe di codice che consenta di ottenere un Insieme e mostrarlo, partendo da una Lista di 20 elementi Integer generarati casualmente nel range [0..9] e quindi con elementi ripetuti”. 17. “Progettare un programma main con il minimo numero di righe di codice che consenta di ottenere un Vector, partendo da un Insieme di elementi Integer generarati casualmente nel range [0..9]. Stampare il Vector ottenuto dopo aver aggiunto due Integer uguali a 9”. Esercizi su Pile, Code e Liste 18. “Progettare una classe Coda come illustrato nel relativo paragrafo del testo”. 19. “Progettare un programma main che utilizzi uno Stack per ottenere una lista Decrescente da una lista Crescente di Numeri”. appunti java pag. 182 20. “Progettare una Classe che ordini in modo Crescente una LinkedList qualsiasi di Double e restituisca la Lista Ordinata.” Vincoli: Si utilizzi l’algoritmo di Fusione descritto di seguito. Primo : se si dispone di due liste ordinate in modo crescente è sempre possibile fonderle per ottenere una lista ordinata. Procedura L3=fondi(L1, L2); L1=[2, 6, 8] L2=[1,6, 7] L3=[ ] L1=[2, 6, 8] L2=[6, 7] L3=[1 ] L1=[6, 8] L2=[6, 7] L3=[1, 2] L1=[8] L2=[6, 7] L3=[1, 2, 6 ] L1=[8] L2=[7] L3=[1, 2, 6, 6 ] L1=[8] L2=[ ] L3=[1, 2, 6, 6, 7 ] L1=[] L2=[ ] L3=[1, 2, 6, 6, 7,8 ] Secondo : Se una lista ha più di un elemento e non è ordinata dividerla in due liste L1,L2 =dimezza(L); Terzo : applica alla lista L il seguente algoritmo ricorsivo che restituisce la lista ordinata LF=MergeSort(L); public static LinkedList MergeSort(LinkedList L) { if (L.size()>1) { LinkedList K[]=dimezza(L); K[0]=MergeSort(K[0]); K[1]=MergeSort(K[1]); L=fondi(K[0],K[1]); } return L; } Richieste : • costruire una classe Fusione che contenga il metodo statico MergeSort() e i metodi statici privati fondi() e dimezza(); • realizzare il main di prova che richiami un metodo statico genera(N) che restituisce una lista casuale di Double e quindi applichi MergeSort(). 21. “Progettare una Classe che ordini in modo Crescente un Vector qualsiasi di Double restituendo il risultato in un Vector.” Vincoli: Si utilizzi l’algoritmo Bubble Sort. 22. “Progettare una main che confronti la velocita dei due ordinamenti precedenti realizzati su List e Vector casuali di grandi dimensioni 5.000 o 10.000 elementi”. 23. “Progettare una Classe che consenta di disporre di un metodo per Valutare un’espressione aritmetica qualsiasi che abbia gli operatori +,-,*,/,^ usando uno Stack”. Indicazioni: L’algoritmo da realizzare è il seguente: appunti java pag. 183 si supponga di avere la seguente stringa di caratteri che rapresenta un’espressione aritmetica: 3+4/2-7*2^2 = 3+4/2-7*4 = 3 + 2 – 28 = 23. Si noterà che per VALUTARE l’espressione si devono eseguire le singole operazioni rispettando le priorità degli operatori. L’operatore con massima priorità è la potenza ^ seguono a pari merito * e / e quindi la priorità più bassa riguarda gli operatori + e - . Come realizzare il rispetto delle priorità degli operatori ? Se rispettare la priorità significa rimandare le operazioni a priorità inferiore allora si può utilizzare lo Stak il cui funzionamento simila un rinvio temporaneo. Ecco le operazioni logiche da svolgere con l’uso di due Stak, uno di char e il secondo di numeri. )ESP)ressione 3+4/2-7*2^2 +4/2-7*2^2 4/2-7*2^2 StakNum [ empty ] [3] StackOp [ empty ] [ empty ] Ris 0 0 [3] [+] 0 [+] [/, +] [/, +] [-, +] 0 0 0 0 [-, +] [*, -, +] ] [*, -, +] ] [^, *, -, +] 3 ] [^, *, -, +] ] [*, -, +] 0 0 0 0 0 0 /2-7*2^2 2-7*2^2 -7*2^2 7*2^2 [4, [4, [2, [2, 3 3 4, 3 ] ] *2^2 2^2 ^2 2 [7, [7, [2, [2, [2, [4, 2, 2, 7, 7, 2, 7, 3 3 2, 2, 7, 2, 3] ] ] ] 3 3 2, 3 [28, 2, 3 ] [-26, 3 ] [-23 ] [] [ [ [ [ -, +] +] ] ] 0 0 0 -23 Algoritmo Inizializza Oggetti Fintanto che (ESP Non è vuota) (A) Leggi un operando e mettilo nello SN (B) Leggi un Op.re confrontalo con l’Op.reSO Se (SO vuoto o Op.reSO<=Op.re) impila l’Op.re, altrimenti Fintanto che (Op.reSO > Op.re) estrai l’Op.reSO, estrai Due operandi dallo SN esegui l’operazione e impila il risultato nello SN. Poi impila l’Op.re Letto (A) (B) (A) (B) – ha prior. Inferiore a / quindi esegue e impila (A) (B) (A) (B) (A) (C)ESP è vuota: Fintanto che (SO non à vuoto) preleva Op.reSO, preleva 2 Num da SN, esegui operazione e Impila in SN (2^2)=4 (C) 7*4=28 (C) 2-28=-26 (C) 3-26=-23 (D) SO è vuoto metti in SN in Ris 24. “Generalizzare la classe precedente introducendo nell’espressione aritmetica anche le parentesi tonde che indicano una ulteriore priorità”. Indicazioni: ripetere l’algoritmo precedente con la seguente variante opportunamente collocata; immettere le parentesi aperte sempre in SO, se appunti java pag. 184 si in contra una parentesi chiusa eseguire tutte le operazioni impilate fino alla parentesi aperta. Esercizi su Alberi 25. “Costruire un programma che acquisisca da tastiera (o da file di testo usando streamTokenizer) parole in ordine casuale, le inserisca in un Albero e stampi l’albero per verificarne l’ordinamento Lessicografico”. Richiesta: realizzare il tutto anche in un solo main(). 26. “Realizzare un programma come quello dell’esercizio 5) utilizzando un Albero”. 27. “Realizzare un programma come quello dell’esercizio 6) utilizzando un Albero”.