Algoritmos y Estructuras de Datos Departamento de Computación
Facultad de Ciencias Exactas y Naturales
Guı́a Práctica
Universidad de Buenos Aires
TADs básicos
Esta sección contiene la definición de muchos de los TADs que vamos a ver en la materia:
Conjunto
Diccionario
Cola
Pila
Cola de prioridad
Secuencia
TAD Conjunto<T> {
obs elems: conj<T>
proc conjVacı́o(): Conjunto<T>
asegura {[Link] = hi}
proc pertenece(in c: Conjunto<T>, in e: T): bool
asegura {res = true ↔ e ∈ [Link]}
proc agregar(inout c: Conjunto<T>, in e: T)
requiere {c = C0 }
asegura {[Link] = C0 .elems ∪ hei}
proc sacar(inout c: Conjunto<T>, in e: T)
requiere {c = C0 }
asegura {[Link] = C0 .elems − hei}
proc unir(inout c: Conjunto<T>, in c0 : Conjunto<T>)
requiere {c = C0 }
asegura {[Link] = C0 .elems ∪ c0 .elems}
proc restar(inout c: Conjunto<T>, in c0 : Conjunto<T>)
requiere {c = C0 }
asegura {[Link] = C0 .elems − c0 .elems}
proc intersecar(inout c: Conjunto<T>, in c0 : Conjunto<T>)
requiere {c = C0 }
asegura {[Link] = C0 .elems ∩ c0 .elems}
proc agregarRápido(inout c: Conjunto<T>, in e: T)
requiere {c = C0 ∧ e ∈
/ [Link]}
asegura {[Link] = C0 .elems ∪ hei}
no(in c: Conjunto<T>): Z
proc tama~
asegura {res = |[Link]|}
}
1
TAD Diccionario<K,V> {
obs data: dict<K,V>
proc diccionarioVacı́o(): Diccionario<K,V>
asegura {[Link] = {}}
proc está(in d: Diccionario<K,V>, in k: K): bool
asegura {res = true ↔ k ∈ [Link]}
proc definir(inout d: Diccionario<K,V>, in k: K, in v: V)
requiere {d = D0 }
asegura {[Link] = setKey(D0 .data, k, v)}
proc obtener(in d: Diccionario<K,V>, in k: K): V
requiere {k ∈ [Link]}
asegura {res = [Link][k]}
proc borrar(inout d: Diccionario<K,V>, in k: K)
requiere {d = D0 ∧ k ∈ [Link]}
asegura {[Link] = delKey(D0 .data, k)}
proc definirRápido(inout d: Diccionario<K,V>, in k: K, in v: V)
requiere {d = D0 ∧ k ∈
/ [Link]}
asegura {[Link] = setKey(D0 .data, k, v)}
proc tama~
no(in d: Diccionario<K,V>): Z
asegura {res = |[Link]|}
}
TAD Cola<T> {
obs s: seq<T>
proc colaVacı́a(): Cola<T>
asegura {res.s = hi}
proc vacı́a(in c: Cola<T>): bool
asegura {res = true ↔ c.s = hi}
proc encolar(inout c: Cola<T>, in e: T)
requiere {c = C0 }
asegura {c.s = concat(C0 .s, hei)}
proc desencolar(inout c: Cola<T>): T
requiere {c = C0 }
requiere {c.s 6= hi}
asegura {c.s = subseq(C0 .s, 1, |C0 .s|)}
asegura {res = C0 [0]}
proc proximo(in c: Cola<T>): T
requiere {c = C0 }
requiere {c.s 6= hi}
asegura {res = C0 .s[0]} }
TAD Pila<T> {
obs s: seq<T>
proc pilaVacı́a(): Pila<T>
asegura {res.s = hi}
2
proc vacı́a(in p: Pila<T>): bool
asegura {res = true ↔ p.s = hi}
proc apilar(inout p: Pila<T>, in e: T)
requiere {p = P0 }
asegura {p.s = concat(P0 .s, hei)}
proc desapilar(inout p: Pila<T>): T
requiere {p = P0 }
requiere {p.s 6= hi}
asegura {p.s = subseq(P0 .s, 0, |P0 .s| − 1)}
asegura {res = P0 .s[|P0 .s| − 1]}
proc tope(in p: Pila<T>): T
requiere {p = P0 }
requiere {p.s 6= hi}
asegura {res = P0 .s[|P0 .s| − 1]} }
TAD ColaPrioridad<T> {
obs d: dict<T, R>
proc ColaPrioridadVacı́a(): ColaPrioridad<T>
asegura {res.d = {}}
proc vacı́a(in c: ColaPrioridad<T>): bool
asegura {res = true ↔ c.d = {}}
proc apilar(inout c: ColaPrioridad<T>, e: T, in pri: R)
requiere {c = C0 }
requiere {e ∈/ c.d}
asegura {c.d = setKey(C0 .d, e, pri)}
proc desapilarMax(inout c: ColaPrioridad<T>): T
requiere {c = C0 }
requiere {c.d 6= {}}
asegura {c.d = delKey(C0 .d, res)}
asegura {tieneP riM ax(C0 .d, res)}
proc cambiarPrioridad(inout c: ColaPrioridad<T>, e: T, in priR)
requiere {c = C0 }
requiere {e ∈ c.d}
asegura {c.d = setKey(C0 .d, e, pri)}
pred tienePriMax(d: dict<T, R>, e: T)
{e ∈ d ∧L (∀e0 : T )(e0 ∈ d →L d[e] ≥ d[e0 ])}
}
TAD Secuencia<T> {
obs s: seq<T>
proc secuenciaVacı́a(): Secuencia<T>
asegura {res.s = hi}
proc agregarAdelante(inout s: Secuencia<T>, in e: T)
requiere {s = S0 }
asegura {s.s = concat(hei, S0 .s)}
3
proc agregarAtrás(inout s: Secuencia<T>, in e: T)
requiere {s = S0 }
asegura {s.s = concat(S0 .s, hei)}
proc vacı́a(in s: Secuencia<T>): bool
asegura {res = true ↔ s.s = hi}
proc fin(inout s: Secuencia<T>)
requiere {s = S0 }
requiere {|s.s| > 0}
asegura {s = tail(S0 )}
proc comienzo(inout s: Secuencia<T>)
requiere {s = S0 }
requiere {|s.s| > 0}
asegura {s = head(S0 )}
proc primero(in s: Secuencia<T>): T
requiere {|s.s| > 0}
asegura {res = s[0]}
proc último(in s: Secuencia<T>): T
requiere {|s.s| > 0}
asegura {res = s[|s| − 1]}
proc longitud(in s: Secuencia<T>): Z
asegura {res = |s.s|}
proc obtener(in s: Secuencia<T>, in i: Z): T
requiere {0 ≤ i < |s.s|}
asegura {res = s[i]}
proc eliminar(inout s: Secuencia<T>, in i: Z)
requiere {s = S0 }
requiere {0 ≤ i < |s.s|}
asegura {s.s = concat(subseq(S0 .s, 0, i − 1), subseq(S0 .s, i + 1, |S0 .s|))}
proc copiar(in s: Secuencia<T>): Secuencia<T>
asegura {res.s = s.s}
proc modificarPosición(inout s: Secuencia<T>, in i: Z, in e: T)
requiere {s = S0 }
requiere {0 ≤ i < |s.s|}
asegura {s.s = concat(subseq(S0 .s, 0, i − 1), hei, subseq(S0 .s, i + 1, |S0 .s|))}
proc concatenar(inout s: Secuencia<T>, in s0 : Secuencia<T>)
requiere {s = S0 }
asegura {s.s = concat(S0 .s, s0 .s)} }