Buon ferragosto a tutti
@ mxa grazie
Ricapitolando devo fare un programma che risolva il problema dello steiner tree.
per l'implementazione del grafo ho scritto questa interfaccia
codice:
public interface Grafo{
public Object insertNodo(Object e);//restituisce un riferimento al nodo creato
public void insertArco(int head, int tail, Double w);
public void deleteNodo(int index);
public void deleteArco(int head, int tail);
public boolean adiacente(int head, int tail);
public ListaCollegata visitaBFS(int index);//restituisce la lista dei nodi in una visita BFS //a partire dal nodo di indice index
public ListaCollegata visitaDFS(int index);//restituisce la lista dei nodi in una visita DFS //a partire dal nodo di indice index
}
dove gli oggetti nodo e arco li ho scritti
codice:
public class arco {
Object peso;
nodo iniziale;
nodo finale;
arco(nodo i, nodo f, Object p){
iniziale =i;
finale=f;
peso=p;
}
}
public class nodo {
int indice;
Object elem;
nodo(Object e, int i){
elem =e;
indice=i;
}
}
poi ho in mente di implementare questa interfaccia utilizzando una normale lista ( implementata da me ) per memorizzare i vari nodi e archi che ci sono, ho ritenuto che usando una lista doubling( una lista che non si basa sui puntatori ma su un array ) avrei sprecato solo molta memoria
il codice della lista è questo
codice:
public class lista {
public record first=null,last=null;
public void stampa(){
record corrente=first;
System.out.println(" lista= ");
while(corrente!=null){
System.out.println(corrente.elem+"");
corrente=corrente.succ;
}
System.out.println();
};
public boolean èVuoto(){
if (first==null) return true;
else return false;
};
public Object trovaPrimo(){
if (èVuoto()) return null;
else
return first.elem;
};
public Object trovaUltimo(){
if (èVuoto()) return null;
else return last.elem;
};
public void inserisciUltimo(Object el){
record nuovo=new record (el);
if (èVuoto()) first=last=nuovo;
else{
last.succ=nuovo;
nuovo.prec=last;
last=nuovo;
}
};
public void inserisciPrimo(Object el){
record nuovo=new record(el);
if (èVuoto()) first=last=nuovo;
else{
nuovo.succ=first;
first.prec=nuovo;
first=nuovo;
}
};
public Object cancPrimo(){
if (èVuoto()) return null;
else{
Object el=first.elem;
first=first.succ;
if (first!=null)first.prec=null;
else last=null;
return el;
}
};
public Object cancUltimo(){
if(èVuoto()) return null;
else{
Object el=last.elem;
last=last.prec;
if(last!=null) last.succ=null;
else first=null;
return el;
}
}
public void canc(record rec){
if (rec==null) return;
else{
if(rec.prec!=null) rec.prec.succ=rec.succ;
else first=rec.succ;
if(rec.succ!=null) rec.succ.prec=rec.prec;
else last=rec.prec;
}
}
public record trovaPrimoRec(){
if (èVuoto()) return null;
else return first;
}
public record trovaUltRec(){
if(èVuoto()) return null;
else return last;
}
}
gli oggetti record sono:
codice:
public class record {
public Object elem;
public record succ;
public record prec;
public record(Object el){
elem=el;
succ=null;
prec=null;
};
}
non conosco questo comando
enum state (Active, canc)
potreste spiegarmelo per favore, è utilizzato in questo codice del mio libro
codice:
public class Nodo{
public enum STATE {ACTIVE, CANC};
public int index;
public Object elem;
public STATE state;
public Nodo(int i, Object e){
index = i;
elem = e;
state = STATE.ACTIVE;
}
}
Grazie in anticipo. Stefano
P.S in settimana non ci sarò appena torno vi aggiorno col continuo del lavoro
Rispondi quotando
