Programacion III

Índex
​Estructuras de datos
Tipos de datos
Hardware y software
Listas enlazadas ó ligadas
Pila
Cola
Cola de prioridad
Tablas de dispersión y funciones hash
Grafo
Arbol binario
Búsqueda y Ordenamiento

🫧🫧
Ordenamiento
Bubble sort (burbuja)
Quick sort 🏃🏿‍♂️💨
Arboles binarios 🌿🌿
Shell sort 🐚🐚
Intercalación 🧱🧱
Búsqueda
Búsqueda secuencial
Búsqueda secuencial indexada
Búsqueda binaria
Arboles binarios
Recursion
Tipos de datos abstractos

​Estructuras de datos
Unidad basica de información: bit

1 bit → 2 posiciones ( 0 y 1 )
n bits → 2n posiciones
Tipos de datos
Enteros positivos 00100110 → 21 + 22 + 25 = 2 + 4 + 32 = 38
Enteros negativos
complemento a uno: el primer digito representa positivo o negativo, en caso de ser
negativo se invierten todos los valores de los otros BITS. Con n bits se puede
representar desde −2n−1 − 1 hasta 2n−1 − 1
complemento a dos: Se suma un 1 a la representacion del complemento a 1 del
numero negativo. Con n bits se puede representar desde −2n−1 hasta 2n−1 − 1
Reales
La técnica mas utilizada: punto flotante
El numero real se representa por un número llamado mantisa, multiplicado por una
base 10 elevada a una potencia entera llamada exponente (Ej:
387, 53 = 38753 × 10−2)
Normalmente se usan 32 bits: mantisa(24), exponente(8). Permite representar
numeros entre 223−1 × 10127 hasta 10−128
Cadena de caracteres
Si 8 bits representan un caracter, entonces se pueden representar hasta 256
caracteres diferentes (algunas computadoras usan 7 ó 10 bits)
Definimos BYTE al grupo de bits que permiten representar un caracter de
computadora

La cadena de bits 00100110 puede ser el numero 38 (entero), 28 (decimal) o el símbolo &
(caracter)

Hardware y software
La memoria de la computadora es un grupo de bits
Estos se agrupan en unidades mas grandes bytes
Toda computadora tiene un conjunto de tipos de datos nativos (es decir, que se construyó
para operar con determinado tipos de datos)

Implantación:

Debemos separar el concepto de TIPO DE DATOS que se representa en una computadora,

por el de TIPO DE DATO ABSTRACTO
Implantación de hardware: se diesña y construye el circuito necesario para ejecutar la
operacion requerida
Implantación de software: se escribe un programa que consta de instrucciones existentes
en le hardware para interpretar en la forma deseada las cadenas de caracteres y ejecutar
las operaciones requeridas
Tipo de datos abstracto (ADT):
Es una coleccion de valores y un conjunto de operaciones con esos valores

La coleccion y las operaciones forman una construccion matematica que puede implantarse
utilizando una estructura de datos particular, ya sea de Hw ó Sw

Al definir un ADT no nos importa la eficiencia en tiempo y espacio

Listas enlazadas ó ligadas

Definición

estructura de datos en la que cada elemento (llamado nodo) tiene dos partes:

uno que almacena la información dato

puntero que apunta al nodo siguiente

Es una estructura de datos dinámica, ya que el número de nodos puede variar dramáticamente

Operaciones

crearNode() crea un nodo vacío

setInfo(x) guarda información en el atributo dato del nodo
getInfo() retorna la información del atributo dato
setPuntero(p) guarda info. en el atributo puntero del nodo
getPuntero() retorna la información del atributo puntero

El acceso es de orden O(n) , ya que se debe recorrer en forma secuencial

La eliminación también, pero es fácil de realizar ya que no implica ningún reordenamiento de
los nodos (como en caso de un vector común), simplemente un cambio de punteros: el
anterior debe apuntar al siguiente (y el siguiente al anterior en las doble enlazadas)

Añadir/eliminar el nodo inicial (y el nodo final en las doblemente enlazadas) es sencillo ya que
se accede a el directamente

Algunos tipos de listas son:

Simplemente enlazada
 posee un puntero al nodo siguiente

Doblemente enlazada
posee punteros al siguiente y al anterior
permite "volver atras", es mas iterable

Circular simplemente enlazada

Definición

lista finita en la que cada nodo tiene un sucesor

permite recorrer la lista "en círculos", ya que el nodo final apunta al nodo inicial

Circular doblemente enlazada

como la circular, pero con sucesor y anterior

Pila
 Definición

colección ordenada de elementos en la que pueden insertarse y suprimirse elementos por

un extremo llamado tope

Aplica la propiedad llamada LIFO (Last In, First Out), es decir, el último en entrar es el primero
en salir.

Operaciones

crearPila() crea una pila vacía

isEmpty() responde si la pila esta vacia
push(x) inserta el elemento x en la pila
pop() saca un elemento de la pila
peek() devuelve el valor del tope de la pila, sin modificar la pila (a veces peek())

Cada nodo posee un dato y un puntero al siguiente , donde el primer nodo apunta a
NULL

Para desapilar tomamos el dato y establecemos como ultimo nodo al apuntado por
siguiente

El orden de las operaciónes es O(n) ya que se debe iterar sobre cada elemento, además de
que se debe crear una pila extra para apilar los elementos que de vayan desapilando,
consumiendo mas memoria

Cola
Definición

colección ordenada de elementos de la que se pueden borrar elementos en un extremo

(frente de la cola) o insertarlos en el otro (final de la cola)

Aplica la propiedad FIFO (First In, First Out), el primero en entrar es el primero en salir.
Funciona como una cola del supermercado o del peaje

Operaciones

crearCola() crea una cola vacía

isEmpty() responde si la cola está vacía
poner(x) inserta el elemento x en la cola
sacar() saca un elemento de la cola

Posee un puntero al primer y último nodos

Si se desean añadir nodos hacemos que apunten al último nodo , si se desean retirar nodos
los vamos retirando desde el primer nodo

La eficiencia es de orden O(n) ya que recorremos secuencialmente la cola hasta encontrar la

información deseada. Además consume mas memoria ya que requerimos de una cola adicional
para almacenar los nodos que vamos retirando
Cola de prioridad

Definición

estructura de datos en la que el ordenamiento de los elementos se determina por el

resultado de las operaciones básicas

Pueden ser de tipo ascendente o descendente

En este tipo de cola los valores con mayor prioridad son eliminados primero

Tablas de dispersión y funciones hash

Definición: tabla de dispersión

estructuras de datos que se usa para almacenar pares clave - valor

cada elemento se asocia a una clave (que lo debe identificar unívocamente), número
entero positivo perteneciente a un rango de valores pequeño

Definición: hashing

técnica usada para insertar, borrar y encontrar datos en tiempo promedio constante
O(1), donde la estructura central es la tabla hash
una tabla hash podía pensarse como un arreglo de tamaño fijo conteniendo llaves
(datos), la llave suele ser una cadena con algún valor asociado
cada llave es mapeada a un número entero en el rango de 0 a n − 1 (n es el tamaño
de la tabla), el cual indicará la celda donde la información debe residir
el mapeo clave - numero es llamado función de hash, que debe ser simple de
calcular y asegurar que llaves distintas correspondan a celdas distintas (no es posible
porque las llaves son ∞ y las celdas son finitas)
Una colisión es cuando dos claves diferentes apuntan al mismo lugar en la tabla. Para
prevenirlas podemos:

elegir una buena función hash , la cual asegure una buena dispersión de las claves y
sea rápida de calcular
la tabla debe tener el tamaño suficiente, idealmente mas del doble de la cantidad de
datos que se esperan almacenar
el tamaño de la tabla debe ser un número primo, ya que esto asegura una mejor
dispersión

En el mejor de los casos el tiempo promedio de cada operación es de O(1) (tiempo

constante), pero la eficiencia se puede degradar rapidamente si ocurren muchas colisiónes,
convirtiendo el orden a O(n)

Las técnicas para resolver colisiónes se pueden agrupar en dos clases:

Open hashing consta en usar listas para todos los elementos que pertenezcan a una
misma celda. Su inconveniente es que se debe tener espacio adicional para enlazar cada
nodo con su siguiente
Closed hashing se intentan celdas alternativas hasta encontrar una vacía, formalmente:

hi(x) = (Hash(x) + fi(i)) mod n

Con f(0) = 0, siendo f la función estrategia de manejo de colisiones

Una estrategia es realizar exploración lineal, donde se intentan las celdas siguientes hasta
 encontrar una vacía, pero el inconveniente es cuando la tabla está a mas de la mitad
llena, lo cual aumenta considerablemente el tiempo de las operaciones

Grafo

Definición

es una estructura formada por un conjunto de nodos (o vértices) y otro de arcos (o

aristas), donde las aristas se representan como un par de nodos

Si los pares de nodos son pares ordenados decimos que el grafo es dirigido
Los nodos pueden no tener arcos asociados

Ejemplo de grafo
 Ejemplo de grafo dirigido

Grado cantidad de aristas incidentes en un nodo

Grado interno cantidad que inciden llegando
Grado externo cantidad que inciden saliendo

Se pueden asociar numeros a cada arco, formando un grafo con peso ó red, donde cada
numero se denominna peso

Se llama camino o trayectoria de longitud k al conjunto de k aristas que unen k+1 nodos

Camino simple es un camino donde todos los nodos (excepto quizás el primero y ultimo) son
diferentes

Ciclo es un camino simple con el primer y último nodos iguales

Se dice que dos nodos son adyacentes si estan directamente conectados por una sola arista

Se pueden usar matrices para implementar el grafo, pero hay que conocer de antemano la
cantidad de nodos que va a haber, y puede ocupar mucha memoria
El cierre transitivo de un grafo es un nuevo grafo resultante de agregar todas las aristas
necesarias para que exista un camino directo entre dos nodos que ya poseían un camino
indirecto
Otra forma es usando listas ligadas para los nodos y aristas

El orden de acceso y consumo de recursos depende de la manera en que lo implementemos

Arbol binario
Es un tipo de grafo que se define de manera recursiva:

Definición

Es un conjunto finito de elementos (denominados nodos) que, o está vacío, o está dividido
en tres subconjuntos:

El primer subconjunto contiene un solo nodo llamado raíz

Los otros dos se llaman subarbol derecho y subarbol izquierdo, y son a su vez arboles
binarios (pueden estar vacíos)
 Arbol binario

Arbol binario Arbol binario

Subarbol Subarbol Subarbol

Raíz Raíz Subarbol
izquierdo derecho izquierdo derecho

Subarbol Subarbol
Raíz
izquierdo derecho

cada nodo posee unicamente dos nodos descendientes, llamados subarbol derecho e
subarbol izquierdo

Recorrer un arbol

Recorrer un arbol se puede hacer de 3 formas:

PRE-orden raiz <-- -->

IN-orden <-- raiz -->
POST-orden <-- --> raiz

La representacion mas usada es la ligada o dinámica, donde cada nodo o celda tiene la sig.
forma:
 Operaciones

Sea p un puntero a un nodo, las operaciones son:

getInfo(p) retorna el contenido del nodo

getleft(p) retorna el puntero al hijo izquierdo del nodo
getRight(p) retorna el puntero al hijo derecho del nodo

Estas operaciones retornan valores nulos si no tiene hijo izquierdo o derecho, o no tiene
hermano. Para ello podemos implementar funciones como Isleft(p) e Isright(p) que
indican si el nodo es realmente hijo izq./der.
Otras funciones son:

crearArbol(x) crea un arbol binario con la informacion x y retorna un puntero

setLeft(p, x) crea un nuevo hijo izq. con la información x , conectado a un padre que
no tiene hijo izquierdo mediante el puntero p
setRight(p, x) crea un nuevo hijo der. con la información x , conectado a un padre
que no tiene hijo derecho mediante el puntero p

El nivel de un arbol se define como:

La raíz tiene nivel 0

Cada nodo es un nivel más que su padre
Al insertar un valor, los valores mas pequeños que el actual se colocan siempre a la izuierda, y
los mayores a la derecha, esto mantiene ordenados los elementos

Un arbol binario completo de profundidad d es un arbol estrictamente binario cuyas hojas

están todas en el nivel d

El arbol se dice desbalanceado cuando para algún nodo se cumple que el nivel de los
subarboles difiere en más de 1 unidad:
Cuando un arbol está desbalanceado el orden de las operaciones se degrada a O(n) . Esto
puede suceder cuando se cargan datos que ya están ordenados

Existe un tipo de arbol que es el arbol AVL, el cual se ajusta con cada inserción o eliminación
manteniendo la diferencia de altura <= 1

Es una estructura dinámica, esto quiere decir que es muy sencillo realizar operaciones de
inserción y eliminación
Búsqueda y Ordenamiento
Los conceptos están relacionados. No se ordena si no se va a buscar, y no se puede buscar de
manera eficiente sin antes haber ordenado

Un archivo de tamaño n es una secuencia de n elementos r[0], r[1], ... , r[n-1] ,

cada elemento se denomina registro

cada registro tiene asociada una llave ó clave k[i] que suele ser un campo del archivo

Definición

Se dice que el archivo está ordenado según la llave "k" si para todos los registros se
cumple que i < k => k[i] < k[j]

Ordenamiento interno: cuando se cargan y ordenan los registros en memoria

Ordenamiento externo: si los registros están en un almacenamiento auxiliar

Método Memoria Orden

burbuja 🫧 muy poca O(n²)
quick sort 🏃🏿‍♂️💨 mucha (recursivo) O(n. log2(n))
arbol binario 🌿 media (recursivo) depende
shell sort 🐚 mucha (recursivo) O(log2(n))
intercalación 🧱 mucha (recursivo) O(n. log2(n))

Ordenamiento
Bubble sort (burbuja) 🫧🫧
Definición

consiste en pasar varias veces por el archivo en forma secuencial, intercambiando cada
valor con su siguiente en caso que estén desordenados
Fácil de programar, no consume mucha memoria, pero su orden es de O(n2)

Quick sort 🏃🏿‍♂️💨

Definición

sea un Arreglo y n el número de elem. del arrelgo, elegir un elem. p (supongamos, en

la posición j ), entonces:

todos los elementos en las posiciónes de 0 a j-1 son menor-iguales a p

todos los elementos en las posiciónes j+1 a n-1 son mayor-iguales a p

Al elemento p se lo llama pivot

Esta rutina se puede llamar de manera recursiva, pero puede consumir mucha memoria
Como valor de pivote se puede utilizar el promedio de los valores del arreglo, esto mejora la
eficiencia

El orden es de O(n. log2(n))

Arboles binarios 🌿🌿
En el caso que los datos ingresen ordenados será un proceso de orden O(n2)
Si el arbol está balanceado entonces el orden es O(n. log2(n))

Shell sort 🐚🐚
Método de ordenamiento por disminución del incremento, en el cual dividimos el archivo
original en subarchivos

Definición

se parte de un valor de incremento k , que es el paso que se da entre los elementos

los pasos para realizarlo son:

1. Dividir el conjunto de datos en subarchivos, donde cada uno tiene n/k elem.
 2. Ordenar cada subarchivo individualmente
3. Reducir el tamaño de los subarchivos de forma progresiva
4. Repetir los pasos 2 y 3 hasta que k = 1

Util para archivos moderadamente grandes, orden de O(n. log2(n))

A medida que el incremento decrece el archivo se encuentra mas ordenado

Intercalación 🧱🧱

Definición

proceso de combinar dos o mas archivos ordenados en un tercer archivo ordenado

Podemos implementarlo dividiendo el archivo en pares adyacentes, entonces tendremos n/2

subarchivos de tamaño 2

Orden de O(n. log2(n)), requiere mas memoria para el armado de cada subarchivo

Búsqueda

Terminología
 la búsqueda exitosa se llama recuperación
algoritmo de búsqueda: algoritmo que acepta un argumento a y trata de encontrar
un registro cuya llave sea a . puede retornar un puntero o NULL
búsqueda interna: el registro está en memoria
búsqueda externa: el registro está en almacenamiento auxiliar
llave: se asocia a cada registro y ayuda a diferenciarlos
llave primaria: identificador único para cada registro en la tabla
llave secundaria: identificador que no identifica de manera unica a los registros
llave interna se almacena a una distancia especifica del registro
llave externa incluye un apuntador al registro
busqueda e inserción: cuando al no encontrar el registro

Muchas veces al no encontrar el registro correspondiente se desea insertar una llave con el
valor indicado (busqueda e inserción)

Método Programación Memoria Mejor caso Peor caso

secuencial muy fácil muy poca O(n/2) O(n)
sec. indexada facil poca (depende de las tablas) O(n/2) O(n/2)
binaria media media (recursivo) O(log2(n)) O(log2(n))
arboles bin. media mucha (recursivo) O(log2(n)) O(log2(n))

Búsqueda secuencial
La busqueda secuencial consiste en recorrer el arreglo hasta encontrar la clave deseada,
entonces retornamos el índice, sino retornamos -1 . Formalmente:

Definición

sea k un arreglo de n llaves, r arreglo de n registros de forma que k(i) es llave del
registro r(i) , sea KEY el argumento de la busqueda, si k(i) = KEY para algun i
entre 0 y n-1 , entonces retornamos i , sino retornamos -1

Orden promedio de O(n/2), O(n) en el peor caso (si el dato se encuentra al final o no se
encuentra)

Es muy fácil de programar y consume casi nada de memoria, y se puede usar en caso que no
esten en orden los datos
Se puede mejorar moviendo el último puntero localizado al primer lugar, lo que se conoce
como moverse al frente. Es mejor cuando la distribución de la probabilidad cambia

Otra forma sería moviendo el puntero localizado a su posición siguiente, esto se llama
transposición. Este es mas eficiente en archivos grandes donde no cambia la distribución de
probabilidad

Búsqueda secuencial indexada

Definición

Consiste en agrupar un grupo de peticiones. Podemos hacerlo de la siguiente manera:

Se divide el arreglo en bloques

Se crea un tabla adicional (llamada index) que mapea el último valor de cada bloque
con un puntero al valor inicial de cada bloque
Cuando se realiza una búsqueda, primero se consulta el index para determinar en
qué bloque puede estar el elemento buscado

por ejemplo, si tenemos una lista ordenada L con valores en el rango de 1 - 10000
podemos crear otra tabla con 10 entradas, para asi dividir la tabla original en 10 partes

Reduce considerablemente el tiempo de búsqueda, al poder saber "donde buscar"

Búsqueda binaria

Definicion

1. Se compara el elemento buscado con el elemento del medio del arreglo

2. Si son iguales se ha encontrado el elemento y se devuelve su posición
3. Si el elem. buscado es menor se realiza una búsqueda binaria en la mitad izquierda
del arreglo
4. Si el elem. buscado es mayor se realiza una búsqueda binaria en la mitad derecha del
arreglo

Se repiten los pasos 1 - 4 hasta encontrar el elemento o determinar que no está

Es el método mas eficiente para buscar en una tabla secuencial sin usar auxiliares

Consiste en dividir en dos el archivo, reduciendo en un factor de 2 la cantidad de elementos a

comparar
Este método se puede aplicar tanto a la tabla secuencial como para la tabla index

Solo se puede utilizar para tablas organizadas como arreglos, pero en este tipo de tablas se
dificulta la inserción y eliminación

Con cada iteración se va reduciendo en 2 la cantidad de comparaciones, por lo que el orden es

O(log2(n))

Arboles binarios

Terminologías

La altura o profundidad de un arbol esta dada por el nivel maximo de sus hojas
La altura de un arbol nulo se define como -1
Un arbol binario balanceado es un arbol en el cual en el cual las alturas de los dos
subarboles de todo nodo difieren a lo sumo en 1
El balance de un nodo se define como la altura del subar. izq. menos altura del
subar. der.

Los arboles balanceados ofrecen un orden de O(log2(n)), si no O(n)

Si un arbol minimiza la cantidad esperada de comparaciones se dice óptimo, el algoritmo mas

rapido en producir un arbol óptimo es del orden O(n2), aunque hay algunos cercanos al orden
O(n)

Para mantener balanceado un arbol se pueden realizar rotaciones izquierdas o derechas,

manteniendo el tiempo de busqueda promedio en O(log2(n)), en las eliminaciones se pueden
requerir mas rotaciones

Arbol de busqueda multivias

Definicion

Arbol en el cual cada nodo tiene n o menos subarboles (que pueden estar vacíos) y
contiene una llave menos que la cantidad de subarboles

Arboles B

Definicion
 Es un arbol de busquedas multivias balanceado de orden n en el cual cada nodo raiz
contiene al menos n/2 llaves

Para mantener el arbol balanceado se intenta que los nodos de cada subarbol mantengan un
numero similar de llaves para cada subnivel, de manera que cuando el arbol tiende a
desbalancearse se deben subdividir los nodos y realizar rotaciones

Recursion
Definición

Una definición recursiva dice como obtener conceptos nuevos empleando el mismo
concepto que intenta describir (lo que se conoce como definición inductiva)

Un razonamiento recursivo tiene dos partes:

Caso base: no es recursivo, es el punto de partida como de terminación de la

definición, ya que definimos explícitamente los elementos o valores
Regla recursiva: el resto de elementos o valores se definen en términos de los
valores ya definidos

Los algoritmos recursivos ofrecen soluciones elegantemente simples, permiten expresar

procedimienntos o conceptos complejos de forma mas simple

Una definición recursiva difiere de una definición circular en que se tiene una forma de escapar
de su expansión infinita, este escape se encuentra en la definición o porción de código no
recursivo o terminal de la definición

Definiciones

Recursividad de cola: cuando una llamada recursiva es la última posición ejecutada del
procedimiento
Recursión directa: cuando un procedimiento incluye una llamada a si mismo
Recursión indirecta: cuando un procedimiento que llama a otro procedimiento y este
causa que el procedimiento original sea invocado
La recursividad es "mas segura" que un ciclo infinito, ya que con la recursión llegará un punto
en el que el ordenador se queda sin memoria, terminando la ejecución y previniendo que la
maquina se quede "colgada"

Cuando un procedimiento recursivo se llama a si mismo varias veces, en cada llamada se crean
copias independientes de las variables declaradas en el procedimiento

Propiedades

no debe generar una llamada infinita a si mismo

una función recursiva f debe definirse en términos que no impliquen a f en al
menos un argumento o grupo de argumentos
debe existir una salida de la secuencia de llamadas recursivas
cualquier caso de definición recursiva tiene que reducirse a la larga a alguna
manipulación de uno o casos mas simples no recursivos

Tipos de datos abstractos

Nota: Algunos los hice yo porque no están en las presentaciones, cambié la sintaxis porque el
profesor dijo que no importaba mucho

lista

abstract type <T>Lista

CrearLista() -> *Lista
GuardarInfo(T)
VerInfo() -> T
GuardarPuntero(*Lista)
VerPuntero() -> *Lista
end type

Pila

abstract type <T>Pila

CrearPila() -> *Pila
PilaVacia() -> bool
Poner(T)
Sacar() -> T
 ValorTope() -> T
end type

Cola

abstract type <T>Cola

CrearCola() -> *Cola
ColaVacia() -> bool
Poner(T)
Sacar() -> T
end type

Arbol

abstract type <T>ArbolBin

MakeTree(T) -> *ArbolBin

Info(*ArbolBin) -> T
Left(*ArbolBin) -> *ArbolBin
Right(*ArbolBin) -> *ArbolBin

SetLeft(*ArbolBin, x)
SetRight(*ArbolBin, x)

IsLeft(*ArbolBin) -> bool

IsRight(*ArbolBin) -> bool
end type