Ejercicios Resueltos de Estructuras de Datos y Algoritmos en Java
public class ABBDeInteger extends ABB {
Public ABBDeInteger() { súper(); } public boolean caminoQueSuma(int s) {
return caminoQueSuma(s, this.Raíz);
}
Protected boolean caminoQueSuma(int s, NodoABB actual) {
If (actual == null) { return false; }
S -= actual.Dato;if (s == 0) { return true; } if (s < 0) { return false; }if (s <= actual.Dato) { return caminoQueSuma(s, actual.Izq); }
Return caminoQueSuma(s, actual.Izq) || caminoQueSuma(s, actual.Der);
}
} x = talla(actual)// T McaminoQueSuma(x) = k.
T P
CaminoQueSuma (x) = 2 * T P
CaminoQueSuma(x / 2) + k’. // TcaminoQueSuma (x) ∈ Ω(1) y TcaminoQueSuma(x) ∈ O(x).(coste)
public String verticesCercanos(int v, int n) {distanciaMin = new double[numVertices()];for (int i = 1; i < numVertices(); i++) { distanciaMin[i] = INFINITO;}
DistanciaMin[v] = 0;q = new ArrayCola();q.Encolar(v);String res = "[";while (!Q.EsVacia()) {int u = q.Desencolar();if (distanciaMin[u] < n) {ListaConPI l = adyacentesDe(u);
For (l.Inicio(); !L.EsFin(); l.Siguiente()) {int w = l.Recuperar().GetDestino();if (distanciaMin[w] == INFINITO) {distanciaMin[w] = distanciaMin[u] + 1;res += "(" + w + ", " + (int)distanciaMin[w] + ") ";q.Encolar(w);}
}
}
}
Return res.Trim() + "]";
public static Map tifones(Map m) {
Map res = new TablaHash(m.talla());
ListaConPI l = m.Claves();
L.Inicio();
While (!L.EsFin()) {
String tifón = l.Recuperar();
Integer anyo = m.Recuperar(tifón);
Integer frec = res.Recuperar(anyo);
If (frec == null) res.Insertar(anyo, 1); else res.Insertar(anyo, ++frec);
}
Return res;
},>,>,>,>
public ListaConPI colisisonanCon(C c) {
ListaConPI l = new LEGListaConPI();
If (recuperar(c) == null) return l;
Int pos = indiceHash(c);
ListaConPI> aux = elArray[pos];
For (aux.Inicio(); !Aux.EsFin(); aux.Siguiente()) {
C colisiona = aux.Recuperar().Clave;
If (!Colisiona.Equals(c) l.Insertar(colisiona);
}
Return l;
}//cubetasPI
,>,>,>,>
,>,>,>,>
public ListaConPI colisisonanCon(C c) {
ListaConPI l = new LEGListaConPI();
If (recuperar(c) == null) return l;
Int pos = indiceHash(c);
EntradaHash> aux = elArray[pos];
For (; aux != null; aux = aux.Siguiente) {
C colisiona = aux.Clave;
If (!Colisiona.Equals(c) l.Insertar(colisiona);
}
Return l;
}//cubetasenlazadas,>
,>,>,>,>
,>,>,>,>
public static > E sucesor(ColaPrioridad cP, E k) {
If (cP.EsVacia()) return null;
E min = cP.RecuperarMin();
If (min.CompareTo(k) > 0) res = min;
Else {
Min = cP.EliminarMin();
Res = succesor(cP, k);
CP.Insertar(min);
}
Return res;
}//pilarecursion
,>,>,>,>,>
,>,>,>,>,>
public static > E sucesor(ColaPrioridad cP, E k) {
E res = null;
Pila aux = new ArrayPila();
While (!CP.EsVacia() && cP.RecuperarMin().CompareTo(k) <= 0) {
E min = cP.EliminarMin();
Aux.Apilar(min);
}
If (!CP.EsVacia()) res = cP.RecuperarMin();
While (!Aux.EsVacia()) cP.Insertar(aux.Desapilar());
Return res;
}//pilaauxiliar
,>,>,>,>,>
,>,>,>,>,>
public void insertarNuevo(E e) {
If (talla == 0 || e.CompareTo(elArray[talla]) >= 0)
Insertar(e);
Else {
E max = elArray[talla--];
Insertar(e);
Insertar(max);
}
}
,>,>,>,>,>
,>,>,>,>,>