Liste linkate

[Darèios89]

Una domanda, in un esercizio in cui mi si chiede di prende in input un file del genere:

2000
(57,51,02)
(17,69,25)
(27,39,11)
(17,04,33)
(91,76,31)
(98,75,10)
(43,13,85)
(10,91,72)
(94,81,04)
(86,77,91)
(68,86,42)
(70,03,12)
(47,82,03)
(59,99,07)
(44,42,83)
(75,41,10)
(37,84,75)
(23,47,19)
(95,41,00)
(51,28,29)

Il primo numero indica il totale di elementi, mi si chiede di generare un output in cui quelle liste siano ordinate in base al primo numero, in ordine non decrescente.

Ora mi chiedevo, leggendo il file, per ogni riga, posso semplicemente scrivere per creare le liste ad esempio:

try{
			reader=new FileReader("input.txt");
			buff=new BufferedReader(reader);
			out=new PrintWriter("OUTPUT.txt");
                                        
                                     String lista="";
			
                                      while((lista=buff.readLine()!=null)
			{
				new LinkedList(lista);
                                                    .
                                                    .
                                                    .
                                       }

Il mio dubbio è su come creare la lista sull'input.

[andbin]

Originariamente inviato da Darèios89
Il mio dubbio è su come creare la lista sull'input.

Ogni riga (a parte la prima) che si vede nell'esempio es. "(17,69,25)" rappresenta un "record" di informazione?? Allora dovresti "modellarlo" appositamente. Visto che sono 3 interi allora potrebbe bastare anche solo un array int[] di 3 elementi. Quindi nella tua lista ci saranno oggetti int[].

Poi altra questione: devi per forza usare un LinkedList? Ordinare un LinkedList è ovviamente possibile con il sort() di Collections che riceve un generico List. Ma sarebbe meno efficiente. Sarebbe preferibile avere un ArrayList.

Stabilito questo e avendo un XyzList di oggetti es. int[] come detto sopra, ti basta definire una classe che implementa Comparator<int[]> (senza generics è solo Comparator e basta) e poi passarlo al sort() di Collections.

[Darèios89]

Si purtroppo devo usare la lista linkata semplice.


Cioè io leggo l'input e creo un array dove memorizzo gli elementi, poi la lista avrà oggetti di tipo int[], cioè deve avere l'intero array o i suoi elementi?
E praticamente per creare una nuova lista devo fare qualcosa come:

new LinkedList(int [] A)

???

per ogni lettura del file posso sovrascrivere il mio array?
e poi creare una lista con il relativo array?

P.S. è giusto il modo di generare la lista?

Però l'esercizio vuole che si lavori con altre due classi.
"Si realizzino due classi che implementino le interfacce Node e LinkedList (descritte
nella pagina seguente) e che siano in grado gestire un insieme attraverso l'uso di
una lista linkata semplice."

I meotodi sommariamente sono quelli per restituire il nodo successivo, settare il primo secondo e terzo elemento, restituirli.
E nella classe LinkedList ci sono dei meotdi per restituire il massimo e il minimo.

[Darèios89]

Sono abbastanza dubbioso.

[Darèios89]

Continuando a ragionare su questo esercizio, ho pensato di creare la classe Tripla, che conterrà un oggetto di tipo int[] come tu avevi detto e in cui memorizzerò gli elementi.
E poi di inserirlo nella lista.
Mi chiedevo delle cose:

se inserisco nelle liste un oggetto di tipo int[] ci potrebbero essere problemi con il TIPO dato che la classe LinkedList ha nodi di tipo Node mentre il mio oggetto è un array di int?
Altra cosa più grave, mi confondo un pò sulle interfacce, nell' esercizio bisogna implementarne due: Node e LinkedList.
Ora avrei pensato che deve essere la classe Tripla ad utilizzarle e a ridefinire i metodi.
Ma non capisco come si fa. Le interfacce contengono solo intestazioni di metodi.
Quindi per fare funzionare la lista devo creare la variabile testa, coda, il costruttore.
Come faccio nella classe Tripla? Posso scrivere il tutto lì e usare i costruttori delle altre classi per definire la testa la coda eccetera?
A me ha dato errori.
Quindi il problema è come scrivere il corpo dei metodi nella classe che implementa le interfacce, utilizzare il costruttore per definire testa coda il puntatore al nodo successivo....

[andbin]

Originariamente inviato da Darèios89
se inserisco nelle liste un oggetto di tipo int[] ci potrebbero essere problemi con il TIPO dato che la classe LinkedList ha nodi di tipo Node mentre il mio oggetto è un array di int?

Visto che da quanto hai detto, la lista linkata la devi implementare tu, allora vediamo le cose in questa ottica. Lo scopo e il significato di un oggetto "Node" all'interno di una lista linkata dovrebbe essere quello di mantenere al suo interno principalmente 2 (almeno) informazioni: un riferimento al "vero" oggetto che è il elemento i-esimo nella lista (che potresti anche vedere nel modo più generico come Object) e un "qualcosa" che permetta di "puntare" al successivo Node, se esiste. E quest'ultimo ovviamente è appunto un reference di tipo .... Node.

Pertanto, qui parlo più in generale, non confondere gli oggetti "elementi" della lista e gli (eventuali) oggetti interni alla collezione che servono a modellare e gestire la sua struttura dati. Sono due cose distinte.

Originariamente inviato da Darèios89
Altra cosa più grave, mi confondo un pò sulle interfacce, nell' esercizio bisogna implementarne due: Node e LinkedList.
Ora avrei pensato che deve essere la classe Tripla ad utilizzarle e a ridefinire i metodi.
Ma non capisco come si fa. Le interfacce contengono solo intestazioni di metodi.
Quindi per fare funzionare la lista devo creare la variabile testa, coda, il costruttore.
Come faccio nella classe Tripla? Posso scrivere il tutto lì e usare i costruttori delle altre classi per definire la testa la coda eccetera?

No, qui c'è ancora più confusione.
Innanzitutto bisognerebbe vedere come deve essere gestita la lista nei confronti degli oggetti Node. Cioè vedere se chi usa poi la implementazione di quella lista deve "sapere" dei Node e trattarli in qualche modo (crearli, ecc...) oppure no.

Tipicamente sarebbe meglio di no. Prendiamo come esempio proprio la collezione standard java.util.LinkedList. Essa è appunto una lista "linkata" e usa internamente degli oggetti Entry (che a parte il nome sarebbero praticamente i tuoi Node).
Ebbene, l'uso di queste Entry è totalmente nascosto, dall'esterno non si vede nulla.
La classe Entry tra l'altro è una nested-class oltretutto privata dentro LinkedList:

public class LinkedList<E> ...... {
    ......

    private static class Entry<E> {
        E element;
        Entry<E> next;
        Entry<E> previous;
  .......

E in java.util.LinkedList non c'è alcun metodo che permetta di "sapere" alcunché sulle Entry (né aggiungerle, ottenerle, cambiarle direttamente ecc...). LinkedList offre solo i metodi per gestire gli oggetti "elementi" della lista mentre tutto ciò che è la gestione dei nodi (crearli, "incatenarli" tra di loro, ecc...) è un affare interno a LinkedList.

Nel tuo caso deve essere così?? Non è detto che deve sempre essere così. Questo è un approccio estremo che consente di "incapsulare" tutto ciò che è possibile. Ma si potrebbe anche permettere agli utilizzatori della lista di gestire in qualche modo i nodi. E qui bisogna appunto solo stabilire cosa e come dovrebbe essere permesso di gestire i nodi.

Fino ad adesso hai solo parlato di 2 interfacce Node e LinkedList ma senza dire molto di più. Hai già le informazioni su quali metodi esatti devono dichiarare? Se li hai, postali. Così si può vedere cosa deve essere possibile e quali sono le relazioni tra i due tipi.

[Darèios89]

Ecco, ti posto in due immagini il testo dell'esercizio.
Premesso che è colpa mia, perchè non ho ben guardato nel libro e oggi pomeriggio il mio collega mi ha fatto notare che lì sono trattate le interfacce, quindi domani mattina studierò la relativa sezione.
Intanto se tu mi sai dare qualche suggerimento, mi fa piacere visto che in generale sono negato in programmazione e sicuramente avrò qualche dubbio anche dopo la lettura del testo.

Grazie:

http://www.allfreeportal.com/imghost...4Immagine1.JPG

http://www.allfreeportal.com/imghost...6Immagine2.JPG

[andbin]

Originariamente inviato da Darèios89
Intanto se tu mi sai dare qualche suggerimento, mi fa piacere visto che in generale sono negato in programmazione

http://www.allfreeportal.com/imghost...6Immagine2.JPG

In particolare da questa seconda immagine si possono già subito dedurre un po' di cose, che chiariscono il contesto e gli obiettivi (anche se ci sono ancora dei dubbi).

1)
La interfaccia Node è stata pensata per essere "specializzata" per questo esercizio ben preciso, dove devi "modellare" una "tripla" di valori. Infatti Node dichiara i metodi setFirst() .... setThird() ... getFirst() .... che sono quelli per gestire i 3 valori.
Pertanto tutta questa gestione di Node e LinkedList è dedicata e specifica, quindi non per realizzare una lista linkata "generica" (nel senso che può essere usata per qualunque tipo di oggetti).

Purtroppo vedo delle incongruenze in quella dichiarazione di Node:
a) c'è un void setNext(); che non ha alcun parametro. Se ricevesse un Node avrebbe senso .... così come si vede adesso no.
b) i metodi getXXX hanno un parametro int i. Questi "getter" non dovrebbero avere alcun parametro, quindi non si capisce perché c'è quel parametro che non ha alcun senso.

2)
La interfaccia LinkedList mi pare che "quadra" più o meno, nel senso che anche qui vedo delle incongruenze e alcune cose poco chiare:
a) getMin()/getMax() dice: il più piccolo e il più grande della lista. Ma .... basato su che cosa il piccolo/grande?? E poi comunque questi due metodi hanno come tipo di ritorno void, quindi che "get" è se non ritorna nulla??

3)
Questi Node e LinkedList sono interfacce, quindi chiaramente devi creare delle classi che implementano queste interfacce.

Per implementare Node puoi creare una classe es. appunto Tripla. Quindi un oggetto Tripla è un nodo! Ed è chiaro che in Tripla ci devono essere le variabili di istanza per memorizzare i 3 valori e ovviamente anche il Node "next". È la implementazione che deve appunto fornire lo "storage" di queste informazioni.

Per implementare LinkedList puoi creare una classe es. ListaTriple (cambia nome come vuoi o eventualmente se/come ti è stato suggerito). Al suo interno come "storage", cioè i campi di istanza che rappresentano il suo stato, dovrai avere come minimo il riferimento al Node di "head" (testa). Eventualmente anche il Node tail ma bisogna vedere come implementi la lista (potresti scegliere: scansiono la lista fino alla fine per avere il tail oppure tengo e aggiorno un tail man mano che aggiungo).

---

La mia impressione, comunque, è che o è stata fatta una svista (di stampa) pazzesca oppure chi ha scritto queste due interfacce non aveva le idee chiare ..... (io sarei per la seconda ... ma potrei sbagliarmi, anzi spero ).

[Darèios89]

Ma, che devo dirti, io già sono abbastanza confuso, il testo è un esercizio dato dal professore, che è uno in gamba, quindi mi stupisco di come abbia scritto questa "roba".
Effettivamente ci sono cose stranissime a leggere bene.
Per quanto riguarda il massimo e il minimo.....sono allibito...
Sto provando a scrivere qualcosa....poi non ho ben capito il metodo della classe Node, setNext(), setta il valore del next, ma che vuol dire?
Per quanto riguarda i metodi setFirst(), setSecond che tu dicevi non prendono parametri.
Potrebbe essere che prendono un inte perchè si legga da file la riga e per ogni elemento che si parsa in int, si passa come parametro al metodo per dirgli setta come primo elemento questo int i?
Ma un nodo può avere quella terna?
Cioè io pensavo potesse avere un valore solo e poi il riferimento al nodo successivo, quindi può avere un terna di valori

[andbin]

Originariamente inviato da Darèios89
non ho ben capito il metodo della classe Node, setNext(), setta il valore del next, ma che vuol dire?

Se setNext avesse come parametro un Node (non è così vedendo quel documento), allora nella tua implementazione del Node dovrebbe settare il riferimento al nodo successivo. Come ho già detto sopra, la tua implementazione deve contenere i 3 valori e il riferimento al nodo successivo.

Originariamente inviato da Darèios89
Per quanto riguarda i metodi setFirst(), setSecond che tu dicevi non prendono parametri.

No. I setXXX è giusto che ricevano il valore, sono i getXXX che in quel documento ricevono un int i che invece, a rigor di logica, non ci dovrebbe essere.

Originariamente inviato da Darèios89
Potrebbe essere che prendono un inte perchè si legga da file la riga e per ogni elemento che si parsa in int, si passa come parametro al metodo per dirgli setta come primo elemento questo int i?
Ma un nodo può avere quella terna?

Lo ripeto ancora, mettiamola così: una classe es. Tripla che implementa Node. Ok? Bene, ogni oggetto di tipo Tripla dovrebbe contenere i 3 valori (accessibili con i getter/setter) e un riferimento al Node successivo (idem con il getter/setter).