Unidad 1 Introducción a las estructuras de Datos
Objetivo: Relacionar la importancia de los TDA para la definición de estructuras de datos
Instrucciones:
- Revisar el video con la presentación sobre las estructuras de datos https://www.youtube.com/watch?v=Aqftq6nlgnM y analizar si hay algún error
- Revisar la imagen del TDA bolsa
- Investigar o modelar las estructuras de datos asignadas que estén estructuradas de forma similar como la imagen que representa el TDA Bolsa o lo más cercano posible, estas son las estructuras asignadas al grupo (aquí se asignarán los ejercicios a cada quien)
- ALBERTO TOLENTINO, ANGEL M:
- buscar el tda trie(conjuntos de palabras) con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- BENITEZ JUAREZ, MARCO ANTONIO:
- buscar el tda archivo con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- BLANCO ACOSTA, MANOLO E:
- buscar el tda cuadtree(representación de imágenes) con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- CASTILLO GUZMAN, IAN YAEL:
- buscar el tda grafo con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- CRUZ VAZQUEZ, ERIK I.:
- buscar el tda montículo con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- FLORES SERRANO, JESUS ANTONIO:
- buscar el tda tabla hash con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- GARATE CRUZ, SEBASTIAN D:
- buscar el tda árbol b con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- GARCIA MARTINEZ, LUIS ANTONIO.:
- buscar el tda tabla cola de doble extremo dequeue con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- LEZAMA CRUZ, JOSE M.
- buscar el tda lista doblemente ligada con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- LOPEZ VICENTE, WEYMAN N:
- buscar el tda cola de prioridad con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- MENDOZA HERNANDEZ, DANIEL:
- buscar el tda multipila con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- MORA CONTRERAS, CARLOS U.:
- buscar el tda diccionario con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- OSIO CARMONA, FERNANDO D.:
- buscar el tda cola circular con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- PALENCIA VAZQUEZ, HUGO A.
- buscar el tda pila con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- PEREZ ARCE, GABRIELA:
- buscar el tda arreglo con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- RAMIREZ LUIS, CESAR J.:
- buscar el tda base de datos con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- RAMOS ROJAS, EMMANUEL:
- buscar el tda de una cola circular doblemente ligada con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- RODRIGUEZ MARTINEZ, ADRIAN:
- buscar el tda árboles avl con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- ROMERO DE LA ROSA, ALEXIS:
- buscar el tda cola con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- TRINIDAD FLORES, ALEJANDRO:
- buscar el tda lista ligada con sus operaciones asociadas (no implementación sino definiciones como en la bolsa)
- Presentar en las revisiones de la semana el TDA asignado con todas sus operaciones.
- Para los que quieran revisar más aquí les dejo un video con la presentación formal sobre las estructuras de datos o las diapositivas
Evidencia
TDA
Tipo: Pila
ResponderEliminarDefinición: Colección con la particularidad de que todas las inserciones y borrados se hacen por el punto denominado tope de la pila.
Sintaxis:
CrearPila()->Pila {precondición: n/a, postcondición: devuelve una pila vacía}
borrarPila(Pila)->void {precondición: Bolsa Existente, postcondición: libera la memoria ocupada por la pila}
PilaVacia->Pila
PilaLlena->Pila
esVacia(Pila)->bool {precondición: Bolsa Existente, postcondición: devuelve verdadero si la Pila no tiene elementos, falso en otro caso}
esLlena(Pila)->bool {precondición: Bolsa Existente, postcondición: devuelve verdadero si la Pila tiene el máximo de elementos, falso en otro caso}
push(Pila,Valor)->Pila {precondición: La pila no está llena, postcondición: añade el elemento en el tope de la bolsa}
pop(Pila)->Pila, valor {precondición: La pila no está vacía, postcondición: devuelve el elemento al tope de la pila y elimina el elemento al tope de la pila}
tope(Pila)->valor {precondición: La pila no está vacía, postcondición: devuelve el elemento al tope de la pila}
precondición: Bolsa Existente
Semántica:
CrearPila()=PilaVacia
esVacia(CrearPila())=Verdadero
esVacia(push(CrearPila(),e))=Falso
pop(PilaVacia)=Error
pop(push(CrearPila(),e))=e
push(PilaLlena,e)=Error
Tipo de Dato Abstracto (TDA) Lista Ligada
ResponderEliminarDefinición:
El TDA Lista Ligada es una colección ordenada de elementos en la que cada elemento (nodo) apunta al siguiente
mediante una referencia, formando una secuencia dinámica. A diferencia de su implementación concreta, el TDA
Lista Ligada define una estructura abstracta que permite inserciones, eliminaciones y búsquedas eficientes,
además de admitir elementos repetidos.
https://drive.google.com/file/d/1nOXyD-opVx0fnvyFaxfsVHIHfk-TY7n2/view?usp=drive_link
Tipo
ResponderEliminarTabla Hash
Definición
Una Tabla Hash es una estructura abstracta de datos que permite almacenar pares clave-valor
de forma eficiente. La idea principal es que a cada clave se le asocia un valor, y se puede
acceder a ese valor rápidamente usando la clave, sin necesidad de recorrer toda la estructura.
Sintaxis:
CrearTablaHash() → TablaHash
Insertar(tabla: TablaHash, clave: Clave, valor: Valor) → TablaHash
Actualizar(tabla: TablaHash, clave: Clave, nuevo_valor: Valor) → TablaHash
Eliminar(tabla: TablaHash, clave: Clave) → TablaHash
Obtener(tabla: TablaHash, clave: Clave) → Valor
ContieneClave(tabla: TablaHash, clave: Clave) → Bool
EsVacia(tabla: TablaHash) → Bool
Claves(tabla: TablaHash) → Conjunto
Valores(tabla: TablaHash) → Conjunto
Semántica
CrearTablaHash()
Resultado: Una tabla hash vacía.
Postcondición: EsVacia(tabla) = verdadero
Insertar(tabla, clave, valor)
Precondición: ¬ContieneClave(tabla, clave)
Postcondición: ContieneClave(resultado, clave) ∧ Obtener(resultado, clave) = valor
Actualizar(tabla, clave, nuevo_valor)
Precondición: ContieneClave(tabla, clave)
Postcondición: Obtener(resultado, clave) = nuevo_valor
Eliminar(tabla, clave)
Precondición: ContieneClave(tabla, clave)
Postcondición: ¬ContieneClave(resultado, clave)
Obtener(tabla, clave)
Precondición: ContieneClave(tabla, clave)
Resultado: Valor asociado a la clave dada.
ContieneClave(tabla, clave)
Resultado: Verdadero si la clave existe en la tabla; falso en caso contrario.
EsVacia(tabla)
Resultado: Verdadero si la tabla no contiene claves.
Claves(tabla)
Resultado: Conjunto de todas las claves almacenadas en la tabla.
Valores(tabla)
Resultado: Conjunto de todos los valores almacenados en la tabla.
Tipo: Grafo
ResponderEliminarDEFINICION: Estructuras de datos que representan relaciones entre objetos, llamados vertices, conectados por lineas llamadas aristas.
SINTAXIS:
CrearGrafo()->Grafo
GrafoVacio()->Grafo
GrafoLleno()->Grafo
AgregarVertice(Grafo, vertice) ->Grafo
EliminarVertice(Grafo, vertice)->Grafo
AgregarArista(Grafo, vertice1, vertice2)->Grafo
EliminarArista(Grafo, vertice1, vertice2)->Grafo
SonAdyacentes(Grafo, vertice1, vertice2)->Boolean
EsVacio(Grafo)->Boolean
SEMANTICA: g es Grafo, v, v1, v2 son vertices
CrearGrafo()= GrafoVacio{precondicion: n/a, postcondicion: devuelve un grafo vacio}
EsVacio(AgregarVertice(CrearGrafo())=Verdadero{precondicion: existe un grafo, postcondicion: verdadero si el grafo no tiene aristas}
EliminarVertice(GrafoVacio(), v)= Error {precondicion: el grafo no esta vacio(tiene vertices), postcondicion: elimina el vertice v del grafo}
AgregarVertice(GrafoLleno(), v)= Error {precondicion: el grafo no esta lleno, postcondicion: añade el vertice v al grafo}
AgregarArista(g, v1, v2)= Error {precondicion: ambos vertices existen en el grafo, postcondicion: añade una arista que une v1 y v2}
SonAdyacentes(g, v1, v2)= Verdadero {precondicion:ambos vertices existen en el grafo, postcondicion: verdadero si hay conexion entre v1 y v2}
Tipo:
Eliminartda tabla cola de doble extremo dequeue
Definicion:
TDA Deque es un tipo abstracto que amplía las capacidades de las pilas y colas al permitir trabajar por ambos extremos. Se define solo por sus operaciones y comportamientos esperados
Sintaxis :
CrearDeque() → Deque
DequeVacio → Deque
DequeLleno → Deque
InsertarFrente(Deque, elemento) → Deque
InsertarFinal(Deque, elemento) → Deque
EliminarFrente(Deque) → Deque
EliminarFinal(Deque) → Deque
Frente(Deque) → Elemento
Final(Deque) → Elemento
EsVacio(Deque) → Boolean
Tamaño(Deque) → Entero
Semantica:
CrearDeque() = DequeVacio
EsVacio(CrearDeque()) = Verdadero
EsVacio(InsertarFrente(d, e)) = Falso
EsVacio(InsertarFinal(d, e)) = Falso
EliminarFrente(DequeVacio) = Error
EliminarFinal(DequeVacio) = Error
Frente(InsertarFrente(d, e)) = e
Final(InsertarFinal(d, e)) = e
Tamaño(CrearDeque()) = 0
Tamaño(InsertarFrente(d, e)) = Tamaño(d) + 1
Tamaño(EliminarFinal(InsertarFinal(d, e))) = Tamaño(d)
TIPO:archivo https://drive.google.com/file/d/1RIN5Gsn1n6N-cfxyawKPmcLd2ccC0RzY/view?usp=drivesdk
ResponderEliminarTipo: Trie
ResponderEliminarDefinición: Estructura de datos en forma de árbol que almacena palabras, permitiendo operaciones de inserción, búsqueda y eliminación basadas en prefijos.
Sintaxis:
CrearTrie() → Trie
Insertar(Trie, palabra) → Trie
BuscarPalabra(Trie, palabra) → Boolean
BuscarPrefijo(Trie, prefijo) → Boolean
Eliminar(Trie, palabra) → Trie
ContarPalabras(Trie) → entero
Semántica:
Sea T un Trie, p, prefijo palabras o cadenas válidas (no vacías, sin caracteres inválidos).
CrearTrie() = TrieVacio
(precondición: — ; postcondición: devuelve un trie vacío sin palabras)
EsVacio(TrieVacio) = Verdadero
(precondición: existencia del trie; postcondición: devuelve verdadero si no contiene palabras)
Insertar(T, p) = T’
(precondición: T existe, p válida; postcondición: T’ contiene todas las palabras de T y p)
BuscarPalabra(T, p) = Verdadero o Falso
(precondición: T existe, p válida; postcondición: indica si p está en T)
BuscarPrefijo(T, prefijo) = Verdadero o Falso
(precondición: T existe, prefijo válido; postcondición: indica si existe al menos una palabra en T que comience con prefijo)
Eliminar(T, p) = T’
(precondición: T existe, p válida y presente en T; postcondición: T’ es igual a T pero sin p, si estaba)
ContarPalabras(T) = n
(precondición: T existe; postcondición: devuelve el número total de palabras en T)
Tipo: Arreglo
ResponderEliminarDefinición: Es una colección ordenada de elementos homogéneos, del mismo tipo, numérico o alfanumérico, reconocidos por un nombre en común donde cada elemento se accede mediante un índice.
Sintaxis:
CrearArreglo(n) → Arreglo
Longitud(Arreglo) → Entero
Obtener(Arreglo, índice) → Elemento
Modificar(Arreglo, índice, elemento) → Arreglo
Insertar(Arreglo, índice, elemento) → Arreglo
Eliminar(Arreglo, índice) → Arreglo
Mover(Arreglo, origen, destino) → Arreglo
Recorrer(Arreglo) → Lista
Buscar(Arreglo, elemento) → Índice
Ordenar(Arreglo) → Arreglo
Operaciones(Arreglo, función) → Resultado
Semántica:
CrearArreglo(n) = a vacío de longitud n { precondición: n ≥ 0, postcondición: crea un arreglo con n posiciones vacías }
Longitud(CrearArreglo(5)) = 5 { precondición: existencia de un arreglo, postcondición: devuelve su longitud }
Obtener(Insertar(CrearArreglo(3), 0, e), 0) = e { precondición: 0 ≤ índice < longitud del arreglo, postcondición: devuelve el elemento en la posición dada }
Modificar(Insertar(CrearArreglo(3), 1, e), 1, f) = a’ donde Obtener(a’, 1) = f { precondición: 0 ≤ índice < longitud, postcondición: cambia el valor en la posición }
Eliminar(Insertar(CrearArreglo(3), 1, e), 1) = a vacío en la posición 1 { precondición: 0 ≤ índice < longitud, postcondición: elimina el valor en la posición }
Insertar(CrearArreglo(2), 5, e) = Error { precondición: índice fuera de rango, postcondición: operación inválida }
Mover(Insertar(CrearArreglo(3), 0, e), 0, 2) = a’ donde Obtener(a’, 2) = e { precondición: 0 ≤ origen, destino < longitud, postcondición: mueve el valor de una posición a otra }
Recorrer(Insertar(Insertar(CrearArreglo(2), 0, e), 1, f)) = [e, f] { precondición: arreglo no vacío, postcondición: devuelve todos los elementos del arreglo en orden }
Buscar(Insertar(CrearArreglo(3), 2, x), x) = 2 { precondición: elemento x en el arreglo, postcondición: devuelve índice donde se encuentra }
Ordenar([3,1,2]) = [1,2,3] { precondición: arreglo con elementos comparables, postcondición: devuelve el arreglo ordenado }
Operaciones([1,2,3], suma) = 6 { precondición: función definida para los elementos, postcondición: aplica la función y devuelve resultado }
Tipo: ColaCircular
ResponderEliminarDefinición: Estructura lineal FIFO (First-In First-Out) con capacidad fija donde el
último elemento está conectado al primero
Sintaxis:
CrearColaCircular(tamaño) → ColaCircular
ColaVacia → ColaCircular
ColaLLena → ColaCircular
Encolar(ColaCircular, elemento) → ColaCircular
Desencolar(ColaCircular) → ColaCircular
EsVacia(ColaCircular) → Boolean
EsLLena(ColaCircular) → Boolean
Frente(ColaCircular) → elemento
Semántica: cc es ColaCircular, e es elemento
CrearColaCircular(n) = ColaVacia {pre: n>0 (el tamaño debe ser positivo), post: crea
cola circular vacía de capacidad n}
EsVacia(CrearColaCircular(n)) = Verdadero { post: Siempre verdadero para una cola
recién creada}
EsLLena(CrearColaCircular(n)) = Falso {post: Siempre falso para una cola recién
creada}
Encolar(ColaVacia, e) = cc con e como único elemento {pre: ¬EsLLena(cc) (la cola no
está llena), post: e es añadido al final}
Desencolar(Encolar(ColaVacia, e)) = ColaVacia {pre: ¬EsVacia(cc) (la cola no está
vacía), post: e es el elemento más antiguo en cc}
Frente(Encolar(ColaVacia, e)) = e {pre: ¬EsVacia(cc), post: devuelve primer elemento
sin modificar cc}
Encolar(ColaLLena, e) = Error {pre: ¬EsLLena(cc), post: añade e al final}
Desencolar(ColaVacia) = Error {pre: ¬EsVacia(cc), post: elimina y devuelve el primer
elemento}
Buscar el TDA cola con sus operaciones.
ResponderEliminarTDA TIPO COLA.
Definición: Colección ordenada de elementos que sigue el principio FIFO (First In, First Out - Primero en Entrar, Primero en Salir).
Sintaxis:
CrearCola() → Cola
ColaVacia() → Cola
Encolar(Cola, elemento) → Cola
Desencolar(Cola) → Cola
Primero(Cola) → elemento
EsVacia(Cola) → Boolean
EsLlena(Cola) → Boolean
Semántica:
c es una Cola, e es un elemento.
CrearCola() = ColaVacia {precondición: n/a postcondición: Devuelve una cola vacía}
EsVacia(CrearCola())= Verdadero
{precondición: La cola existe, postcondición: Verdadero si no tiene elementos, falso en caso contrario}
EsVacia(Encolar(ColaVacia, e))= Falso
{precondición: Ninguna, postcondición: La cola ya no está vacía}
Primero(Encolar(ColaVacia, e))= e
{precondición: La cola no está vacía, postcondición: Devuelve el primer elemento insertado}
Desencolar(ColaVacia) = Error
{precondición: La cola no está vacía, postcondición: Elimina el primer elemento de la cola}
Desencolar(Encolar(c, e))= c (si c estaba vacía)
{precondición: La cola no está vacía, postcondición: Elimina el elemento más antiguo}
Encolar(ColaLlena, e)= Error
{precondición:La cola no está llena, postcondición: Añade e al final de la cola}
Tipo: ÁrbolAVL
ResponderEliminarDefinición: Es un árbol binario de búsqueda balanceado, donde la diferencia de altura entre subárboles
izquierdo y derecho no supera 1.
Sintaxis:
CrearAVL() → ÁrbolAVL
ÁrbolVacio → ÁrbolAVL
Insertar(ÁrbolAVL, elemento) → ÁrbolAVL
Eliminar(ÁrbolAVL, elemento) → ÁrbolAVL
Buscar(ÁrbolAVL, elemento) → Booleano
EsVacio(ÁrbolAVL) → Booleano
Altura(ÁrbolAVL) → Entero
Balancear(ÁrbolAVL) → ÁrbolAVL
Semántica:
• a es un árbol AVL
• e es un elemento
CrearAVL() = ÁrbolVacio
(precondición: ninguna, postcondición: devuelve un árbol vacío)
EsVacio(CrearAVL()) = Verdadero
(precondición: el árbol existe, postcondición: verifica que está vacío)
Buscar(CrearAVL(), e) = Falso
(precondición: el árbol existe, postcondición: el árbol vacío no contiene elementos)
Insertar(ÁrbolVacio, e) = a'
(precondición: el árbol está vacío, postcondición: devuelve un árbol con un solo nodo e)
Eliminar(CrearAVL(), e) = Error
(precondición: el árbol está vacío, postcondición: no se puede eliminar de un árbol vacío)
Buscar(Insertar(a, e), e) = Verdadero
(precondición: a es un árbol, postcondición: e fue insertado correctamente)
Altura(CrearAVL()) = 0
(precondición: el árbol existe, postcondición: árbol vacío tiene altura cero)
Balancear(a) = a'
(precondición: a puede estar desbalanceado, postcondición: a' es una versión balanceada de a)
Tipo: Lista doblemente ligada.
ResponderEliminarDefinición: Conjunto de nodos enlazados secuencialmente. Cada nodo contiene tres campos: dos para los enlaces, que son referencias al nodo siguiente y al anterior en la secuencia de nodos y otro para el almacenamiento de la información.
SINTAXIS
CrearLista() → Lista ListaVacia → Lista
InsertarInicio(Lista, Elemento) → Lista EliminiarInicio(Lista) → Lista Eliminarfinal(Lista) → Elemento
EsVacia(Lista) → Boolean Longitud(Lista) → Entero
Buscar(Lista, Elemento) → boolean EliminarElemento(Lista, Elemento) → Lista
RecorrerAdelante(Lista) → Secuencia[Elemento] RecorrerAtras(Lista) → Secuencia[Elemento]
SEMANTICA
Notación: L = Lista, e, f = elementos
CrearLista() = Listavacia {Precondición: Ninguna. Postcondición: retorna unalista vacia(cabeza = null, cola = null)}
EsVacia(CrearLista()) = Verdadero {Precondición: L existe. Postcondición: Verdadero si no tiene nodos, Falso en caso contrario.}
InsertarInicio(CrearLista(), e) = (e, CrearLista()){Precondición: L existe. Postcondición: Agrega e al final de L}
EliminarFinal(CrearLista()) {Precondición: ¬EsVacia(L). Postcondición: Elimina y retorna el primer elemento de L}
Longitud(CrearLista()) = Falso {Precondición: L existe. Postcondición: Retorna la cantidad de elementos en L.
Buscar(CrearLista(), e) = verdadero {Precondición: L existe. Postcondición: Retorna verdadero si e esta en L.}
EliminarElemento(CrearLista(), e) = CrearLista() {Precondición: L existe. Postcondición: Elimina la primera ocurrencia de e en L.}
RecorrerAdelante(CrearLista()) = Verdadero {Precondición: L existe. Postcondición: Retorna elementos desde cabeza hasta cola.}
RecorrerAtras(CrearLista()) = Verdadero {Precondición: L existe. Postcondición: Retorna elementos desde cola hasta cabeza.}
EliminarInicio(ListaVacia) = ERROR EliminarFinal(ListaVacia) = ERROR
Ejercicio:
ResponderEliminar• buscar el tda cola de prioridad con sus operaciones asociadas (no
implementación sino definiciones como en la bolsa)
TIPO: COLA
Definición: una estructura lineal que sigue el principio FIFO,(FIRST IN, FIRST OUT),El
primer elemento que se añade a la cola, es el primero en ser removido, es como una
fila, En la que los elementos se añaden al final y se retiran del principio
Sintaxis:
CrearCola() → ColaPrioridad
ColaVacia() → colaPrioridad
Insertar(ColaPrioridad, Prioridad, factor ) → ColaPrioridad
Eliminar(ColaPrioridad) → ColaPrioridad
primero(ColaPrioridad) → factor
vacia(ColaPrioridad) → Booleano
Semántica:
CrearCola() = ColaVacia
Precondición: cero. postcondición: devuelve una cola vacia)
Vacia(CrearCola()) = verdadero
Vacia(Insertar(c, a, d)) = falso
Primero(Insertar(ColaVacia, a, d)) = Falso
(Precondición: No esta vacia postcondición: devuelve el elemnto en mayor prioridad)
Eliminar(ColaVacia) =error
(Precondición: no esta vacia)
Insertar(Insertar(ColaVacia, a1 2),a2, 5)
→Primero = a2 (tiene mayor Prioridad)
Insertar(ColaPrioridad, a, d):
(Precondición: cero, postcondición: añade a con prioridad d a la cola)