estructura de datos
DESCRIPTION
Instituto Tecnológico de Culiacán. Ingeniería en Sistemas Computacionales. Estructura de datos. Material de apoyo Unidad 3. Prof. Felipe E. Muñiz R. TEMARIO. Unidad 3.- Estructuras lineales estática y dinámicas. 3.1 Pilas. 3.2 Colas. 3.3 Listas enlazadas. 3.3.1 Simples. 3.3.2 Dobles. - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/1.jpg)
![Page 2: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/2.jpg)
3.1 Pilas.
3.2 Colas.
3.3 Listas enlazadas.
3.3.1 Simples.
3.3.2 Dobles.
Unidad 3.- Estructuras lineales estática y dinámicas.
![Page 3: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/3.jpg)
Stack (pila)• Una pila (Stack) es un contenedor de
objetos que se insertan y eliminan de acuerdo con el principio: último en entrar primero en salir (LIFO, Last Input First Output)
• Los elementos se insertan de uno en uno (push, apilar)
• Se sacan (extraen) en orden inverso al que se insertaron (pop, desapilar)
• Único elemento que se puede observar (examinar) es top o cima
![Page 4: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/4.jpg)
Aplicaciones
Estructuras auxiliares en numerosos algoritmos y esquemas de programación: Recorridos (profundidad) de árboles y grafos Evaluación de expresiones Conversión entre notaciones de expresiones
(postfija, prefija, infija)
Operación Deshacer en editores de texto Operación Volver Hacia Atrás en un
navegador en la secuencia de páginas web
Stack (pila)
![Page 5: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/5.jpg)
Implementaciones
Mediante un array (T *elementos; int numElementos; int maxElem;) numElementos = 0 pila vacía elementos[0] fondo de la pila elementos[numElementos – 1] cima de la pila
Mediante una lista encadenada (PNodo elementos; int numElementos) No hay limitación de tamaño
Stack (pila)
![Page 6: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/6.jpg)
Tratamiento de expresiones aritméticas (utilizando pilas)
Las expresiones aritmeticas pueden ser representadas en tres notaciones distintas, dos de las cuales se denominan “Polacas”.
Notación Prefija.- El operador se evalúa antes que los operandos.
Prefija: <operador> <operando> <operando>
Infija: <operando> <operador> <operando>
Postfija: <operando> <operando> <operador>
Notación Infija.- El operador se evalúa dentro de los operandos.
Notación Postfija.- El operador se evalúa despues de los operandos.
Ejemplo1:Infija: (x+z)*w/t^y-vPostfija: xz+w*ty^/v-Prefija: -*+xz/w^tyv
Ejemplo2:Infija: (a+b*c)/d*k^1Postfija: abc*+d/k1^*Prefija: /+a*bc*d^k1
![Page 7: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/7.jpg)
Precedencia de los operadores
1) ^ circunflejo2) / *3) + -
La ventaja de utilizar expresiones en notación polaca (prefija o infija) radica en que no son necesarios los paréntesis para indicar el orden de operación, ya que esto queda establecido por la ubicación de los operadores de más alta prioridad, pues se ejecutan primero.Si hubiera en una expresión 2 o más operadores de igual prioridad, se procesa de izquierda a derecha.Las expresiones con paréntesis se ejecutan primero.
![Page 8: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/8.jpg)
Algoritmo para convertir una expresión infija a una expresión de notación polaca postfija
1. Si el símbolo es un “(“, este se mete a la pila de operadores.2. Si el símbolo es un “)”, se saca de la pila todo lo que exista hasta llegar al
primer “(“, los operadores van a la solución, a medida que salen de la pila, el “(“ se saca pero no se agrega a la solución.
3. Si el símbolo es un operador, entonces si el operador en el tope de la pila es de la misma o mayor precedencia, dicho operador se saca y se agrega a la solución, continuando de esta manera hasta que el primer “(“ o un operador de menor precedencia se encuentre en la pila, cuando esta situación ocurre, entonces el operador en turno se mete a la pila.
4. Si el símbolo es un operando, este se agrega directamente a la solución.
Nota: Al terminar de analizar la expresión, sacar todos los símbolos que queden en la pila y agregarlos a la solución.
![Page 9: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/9.jpg)
Queue (cola)• Una cola (Queue) es un contenedor de
objetos que se insertan por el extremo final y extraen por el extremo opuesto: frente
• Siguen el principio de: primero en entrar primero en salir (FIFO, First Input First Output)
• El único elementos observable (accesible) en todo momento es el primero que fue insertado (primero en la secuencia) frente
• TAD Queue cuya extensión da lugar al TAD doble cola (DQueue)
![Page 10: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/10.jpg)
Aplicaciones
Simular situaciones reales: caja del supermercado, surtidor de combustible, etc.
Colas de trabajos a realizar por cualquier dispositivo: una impresora, un disco, etc.
Scheduler: asignación de tiempo de procesador a los procesos en un sistema operativo multiusuario (sin prioridad)
Algoritmos de búsqueda en anchura sobre árboles y grafos
Queue (cola)
![Page 11: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/11.jpg)
Implementaciones Mediante un array (Pila) (T *elementos; int
numElementos; int maxElem;) numElementos = 0 cola vacía frente (front) = elementos[0] final (back/rear) = elementos[numElementos – 1] Coste de las operaciones (Extraer)?
Mediante una lista enlazada (PNodo frente, final; int numElementos) No hay limitación de tamaño
Queue (cola)
![Page 12: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/12.jpg)
• Permite consultar, añadir y eliminar elementos en cualquiera de los dos extremos de la estructura lineal bicola
• Especificación algebraica Ejercicio• Implementaciones:
– Lista simplemente encadenada Problema: Extraer un elemento por la derecha coste O(n)
– Lista doblemente encadenada Ventajas: (1) Todas operaciones coste temporal cte. O(1) y (2) Punteros a primero (front) y último (back) simplifican operaciones de Insertar y Extraer
El TAD Doble Cola
Queue (cola)
![Page 13: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/13.jpg)
ColasLa Cola es una estructura de datos donde la inserción de datos se hace en un extremo del arreglo (el fin de la cola) y la recuperación/borrado de elementos se hace en el otro extremo (el inicio de la cola). Como el primer elemento insertado es el primero en ser recuperado, los desarrolladores se refieren a estas colas como estructuras FIFO (first-in, first-out) (primero en entrar, primero en salir).
Normalmente los desarrolladores trabajan con dos tipos de colas: lineal y circular. En ambas colas, la inserción de datos se realiza en el fin de la cola, se mueven hacia adelante y se recuperan/borran del inicio de la cola. La siguiente figura ilustra las colas lineal y circular:
La cola lineal de la figura anterior almacena cuatro enteros, con el entero 1 en primer lugar. Esa cola está llena y no puede almacenar más datos adicionales porque rear identifica la parte final de la cola. La razón de la posición vacía, que identifica front, implica el comportamiento lineal de la cola. Inicialmente, front y rear identifican la posición más a la izquierda, lo que indica que la cola está vacía. Para almacenar el entero 1, rear avanza una posición hacia la derecha y almacena 1 en esa posición. Para recuperar/borrar el entero 1, front avanza una posición hacia la derecha.
![Page 14: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/14.jpg)
La cola circular de la figura anterior tiene siete datos enteros, con el entero 1 primero. Esta cola está llena y no puede almacenar más datos hasta que front avance una posición en sentido horario (para recuperar el entero 1) y rear avance una posición en la misma direción (para identificar la posición que contendrá el nuevo entero). Al igual que con la cola lineal, la razon de la posición vacía, que identifica front, implica el comportamiento circular de la cola. Inicialmente, front y rear identifican la misma posición, lo que indica una cola vacía. Entonces rear avanza una posición por cada nueva inserción. De forma similar, front avanza una posición por cada recuperación/borrado.
Las colas son muy útiles en varios escenarios de programación, uno de ellos es:
Trabajos de impresión:Como una impresora normalmente es más lenta que un ordenador, un sistema operativo maneja los trabajos de impresión en un subsistema de impresión, que inserta esos trabajos de impresión en una cola. El primer trabajo en esa cola se imprime primero, y así sucesivamente.
![Page 15: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/15.jpg)
Listas.Existe una gran variedad de estructuras denominadas listas.
Lista simplemente enlazada.La más básica es la simplemente enlazada. Que puede definirse como la secuencia de cero (lista vacía) o más elementos de un determinado tipo. Los elementos quedan ordenados linealmente por su posición en la secuencia. Se requiere sólo un enlace entre un elemento y su sucesor.
Los arreglos tienen un segmento contiguo en la memoria.
En las listas debe asumirse que el espacio de un nodo no es contiguo con otro; por estarazón no basta incrementar en uno, el puntero a un nodo, para obtener la dirección de inicio del nodo siguiente.
Cada nodo está conectado con el siguiente mediante un puntero que es un campo del nodo.
Los elementos del arreglo se direccionan en tiempo constante, O(1). Los elementos de las listas tienen un costo de acceso O(n), en peor caso.
![Page 16: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/16.jpg)
Las operaciones sobre listas deben considerar que ésta puede estar vacía, y que esto puede requerir un tratamiento especial.
Los siguientes diagramas ilustran una lista vacía y una lista con tres elementos. Si los nodos se crean en el heap, la variable lista debe estar definida en el stack, o en la zona estática, con el tipo puntero a nodo.
Note que el programador no dispone de nombres de variables para los nodos, éstos sólo pueden ser accesados vía puntero (esto debido a que en el momento de la compilación no se conocen las direcciones de los nodos; estas direcciones serán retornadas en tiempo de ejecución).
![Page 17: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/17.jpg)
TAD Lista• LISTA = colección de elementos homogéneos entre los que existe
una relación lineal– Cada elemento de la lista, a excepción del primero, tiene un
único predecesor– Cada elemento de la lista, a excepción del último, tiene un único
sucesor• Nodos y enlaces
![Page 18: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/18.jpg)
Listas: descripción lógica• Orden de nodos afecta a la función de acceso
– Según orden de inserción– Según clave
• Ejemplo
Lista de calificaciones ::= <Alumno> + {<Alumno>}
<Alumno>::= <<DNI>> + <<NIA>> + <Apellido1> + <Apellido2> + <Nombre> + <Calificación>
![Page 19: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/19.jpg)
Listas: descripción lógica• Listas Arrays
– Listas son flexibles y permiten cambio de implementación• Operaciones
– Insertar, Borrar, Modificar, etc.• Tipos de listas
– Simples– Ordenadas– Pilas– Colas– Doblemente enlazadas (LDE)– Circulares
![Page 20: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/20.jpg)
Implementaciones
····UNG
i = min +1 +2 ... ... ... max
posición = i
elem[i] =
tamaño = 3
i = 1 2 3 4 5 … max
posición = i
elem[i] =
tamaño = 3
G 4 · · · · N 5 U 0 · · · ··
IUNG
i = 1 2 3 4 5 6 7 8
posición = i
elem[i] =
tamaño = 4max = 4
TONS
tamaño = 3max = 8
Vector original
Vector ampliado
G I
U
N
S null
posición
tamaño = 5
Estática Dinámica
Enlaza
da
Secuencial
![Page 21: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/21.jpg)
Listas Simples• Lista Simple = colección de elementos homogéneos cuya relación
lineal es determinada por la posición del elemento en la lista• Comienzo + Enlace al siguiente ( puntero)
• Definición:<listaSimple> ::= <comienzo> + {<nodo>}<nodo> ::= <informacion> + <enlace><informacion> ::= <<dato>>{<<dato>>}<enlace> ::= (<<ReferenciaNodo>> | NULL)<comienzo> :: =<enlace>
![Page 22: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/22.jpg)
TAD Lista Simple: operaciones
asignarInfo(referenciaNodo, valorInformacion)
asignarEnlace(referenciaNodo, valorEnlace)
Modificación de los nodos
info(referenciaNodo) Informacionsiguiente(referenciaNodo) enlace
Acceso a los nodos
recorrer(nombreLista) Recorrido de la lista
buscar(nombreLista, dato) informacionbuscar(nombreLista, dato) referenciaNodopertenece(nombreLista,informacion) Booleano
borrar(nombreLista, valorInfo) Borrado de nodos
insertar(nombreLista, valorInfo, posicion)
insertar(nombreLista, valorInfo)
listaVacia(nombreLista) BooleanolistaVacia(referenciaNodo) BooleanolistaLlena(nombreLista) Booleano
Comprobación del estado
crearLista (nombreLista)Creación de una lista
Inserción de nodos
Búsqueda de un nodo
![Page 23: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/23.jpg)
Listas Simples• Aclaraciones a las operaciones:
– listaLlena sólo tiene sentido si lista es acotada– acceso y modificación serán métodos get y put
• Ejemplo y pseudocódigo– insertar (nombreLista, valorInfo, posición)– insertar (nombreLista, valorInfo)– borrar (nombreLista, valorInfo)– buscar (nombreLista, dato) información– recorrer (nombreLista)
• Inserción: casos…
![Page 24: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/24.jpg)
![Page 25: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/25.jpg)
![Page 26: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/26.jpg)
Listas Ordenadas• La posición de cada nodo viene determinada por el valor de uno o
más campos obligatorios de información del nodo denominados clave
• No se permite tener dos nodos con la misma clave
• Definición
<listaOrdenada> ::= <comienzo> + {<nodo>}
<comienzo> ::= <enlace>
<enlace> ::= (<<ReferenciaNodo>> | NULL)
<nodo> ::= <clave> + <informacion> + <enlace>
<clave> ::= <<dato>>{<<dato>>}
<informacion> ::= {<<dato>>}
![Page 27: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/27.jpg)
TAD Lista Ordenada: operaciones
asignarClave(referenciaNodo, valorClave)
asignarInfo(referenciaNodo, valorInformacion)
asignarEnlace(referenciaNodo, valorEnlace)
Modificación de los nodos
clave(referenciaNodo) Claveinfo(referenciaNodo) Informacionsiguiente(referenciaNodo) enlace
Acceso a los nodos
recorrer(nombreLista Recorrido de la lista
buscar(nombreLista, valorClave) Informacionbuscar(nombreLista, valorClave)ReferenciaNodopertenece(nombreLista,valorClave) Booleano
borrar(nombreLista, valorClave)Borrado de nodos
insertar(nombreLista, valorClave, valorInfo)
listaVacia(nombreLista) BooleanolistaVacia(referenciaNodo) BooleanolistaLlena(nombreLista) Booleano
Comprobación del estado
crearLista (nombreLista)Creación de una lista
Inserción de nodos
Búsqueda de un nodo
![Page 28: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/28.jpg)
Pilas• Pila = colección ordenada de elementos homogéneos en la que
sólo se pueden añadir y eliminar elementos por el principio de la misma (cabecera) filosofía LIFO
• Definición
<pila> ::= <cabecera> + {<nodo>}
<cabecera> ::= <enlace>
<enlace> ::= (<<ReferenciaNodo>> | NULL)
<nodo> ::= <informacion> + <enlace>
<informacion> ::= <<dato>>{<<dato>>}
![Page 29: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/29.jpg)
TAD Pila: operaciones
pop(nombrePila) informacionExtracción de nodos
push(nombrePila, valorInfo)Inserción de nodos
pilaVacia(nombrePila) BooleanopilaLlena(nombrePila) Booleano
Comprobación del estado
crearPila (nombrePila)Creación de pila
asignarInfo(referenciaNodo, valorInformacion)
asignarEnlace(referenciaNodo, valorEnlace)Modificación de los nodos
info(referenciaNodo) Informacionsiguiente(referenciaNodo) Enlace
Acceso a los nodos
cabecera(nombrePila) informacionAcceso a la cabecera*
* Opcional: Accede a la cabecera sin eliminarla
![Page 30: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/30.jpg)
TAD Pila: ejemplos de aplicación
Vuelta atrás en un navegador web
Comando “undo” en un editor
Secuencia de métodos activos en la Java Virtual Machine:
main() {int i = 5;foo(i);}
foo(int j) {int k;k = j+1;bar(k);}
bar(int m) {…}
bar PC = 1 m = 6
foo PC = 3 j = 5 k = 6
main PC = 2 i = 5
• Cuando se invoca un método, se inserta en la pila una nueva entrada
• Por cada método se guardan:variables localesvalor devueltocontador de programa
• Cuando el método finaliza se saca ese elemento de la pila y se devuelve el control al método que esté en la cabecera
![Page 31: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/31.jpg)
Colas• Cola = colección ordenada de elementos homogéneos en la que sólo se pueden
añadir elementos por el final y se eliminan por el principio (frente) filosofía FIFO
• Definición
<cola> ::= <frente> + <final> + {<nodo>}
<frente> ::= <enlace>
<enlace> ::= (<<ReferenciaNodo>> | NULL)
<final> ::= <enlace>
<nodo> ::= <informacion> + <enlace>
< informacion > ::= <<dato>>{<<dato>>}
![Page 32: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/32.jpg)
TAD Cola: operaciones
desencolar(nombreCola) informacionExtracción de nodos
encolar(nombreCola, valorInfo)Inserción de nodos
colaVacia(nombreCola) BooleanocolaLlena(nombreCola) Booleano
Comprobación del estado
crearCola (nombreCola)Creación de cola
asignarInfo(referenciaNodo, valorInformacion)
asignarEnlace(referenciaNodo, valorEnlace)Modificación de los nodos
info(referenciaNodo) Informacionsiguiente(referenciaNodo) Enlace
Acceso a los nodos
cabecera(nombreCola) informacionAcceso a la cabecera*
* Opcional: Accede a la cabecera sin eliminarla
![Page 33: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/33.jpg)
TAD Cola: casos particulares• Colas circulares
– Implementación estática como array– Referencia al primero y al último– Aritmética módulo C (Capacidad de la cola)– Llevar la cuenta del número de elementos
![Page 34: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/34.jpg)
TAD Cola: casos particulares• Colas de prioridad
![Page 35: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/35.jpg)
TAD Cola: ejemplos de aplicación
• Listas de espera• Acceso a recursos compartidos dedicados (v.g., impresoras)• Multiprogramación de la CPU
![Page 36: Estructura de datos](https://reader034.vdocumento.com/reader034/viewer/2022050908/56814621550346895db32a47/html5/thumbnails/36.jpg)
Listas Doblemente Enlazadas• Relación lineal en ambos sentidos• Enlace a predecesor y antecesor en cada nodo• Recorrido puede ser en ambos sentidos• Pueden ser simples u ordenadas
• Definición:<lde> ::= <comienzo> + {<nodo>}<comienzo> :: = <enlace><enlace> ::= (<<ReferenciaNodo>> | NULL)<nodo> ::= <informacion> + <predecesor> + <sucesor><predecesor> ::= <enlace><sucesor> ::= <enlace><informacion> ::= <<dato>>{<<dato>>}