Story Transcript
Contenidos
Estructuras de Datos y Algoritmos
1
• Listas • Pilas • Colas
Tema 3. Listas, pilas y colas
Iván Cantador David Vallet, José R. Dorronsoro Escuela Politécnica Superior
Universidad Autónoma de Madrid
Contenidos
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
2
Listas. Definición
3
• Colección secuencial de objetos donde: • Todos menos uno tienen un objeto siguiente • Todos menos uno tienen un objeto anterior
• Listas • Pilas • Colas
• Permite la representación secuencial ordenada de cualquier objeto • Insertando o extrayendo objetos del principio/final • Insertando o extrayendo objetos en cualquier punto
• Puede entenderse como una meta-EdD más que como un TAD • e.g. pilas, colas, colas de prioridad, etc. Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Listas. Funciones primitivas
4
Listas. Estructura de datos: array
5
• Opción 1: tabla/array de elementos • Funciones primitivas básicas
T=
status listaInicializar(Lista L) boolean listaVacia(Lista L) status listaInsertarIni(Lista L, generic e) status listaExtraerIni(Lista L, generic e) status listaInsertarFin(Lista L, generic e) status listaExtraerFin(Lista L, generic e)
0 // // // //
Inserta al Extrae del Inserta al Extrae del
inicio inicio final final
1
2
3
siguiente(T[i]) ≡ T[i + 1]; anterior(T[i])≡ T[i – 1] • Ventajas - Fácil implementación - Memoria estática
• Inconvenientes
• … y otras
- Desperdicio de espacio - Ineficiencia al insertar en el inicio y posiciones intermedias: mover todos los elementos a la derecha una posición (solución: lista circular )
// Inserta el elemento e en la posicion pos d la lista L status listaInsertarPos(Lista L, generic e, int pos) // Inserta el elemento e en la lista L en orden status listaInsertarOrden(Lista L, generic e) ...
… inserción
106
0
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Listas. Estructura de datos: lista enlazada (LE) 6
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Listas. Estructura de datos: LE estática • Estructura estática para LE
• Opción 2: Lista Enlazada (LE)
• Tabla de nodos
• Listas de nodos • Nodo
0
- Campo info: contiene el objeto/dato a guardar - Campo next: apunta al siguiente nodo de la lista
i= 1
1
n= 4
2
n= 6
3 4
n= 2
5
info
next
• Lista enlazada: colección de nodos enlazados donde el último apunta a NULL y se tiene un puntero al nodo inicial
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
6
n= -1
7
next • Ventajas: Memoria estática info • Desventajas: 1) Desperdicio de memoria, 2) Complejidad, e.g., ¿siguiente nodo libre? Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
7
Listas. Estructura de datos: LE dinámica
8
Memoria dinámica
9
• Los nodos se crean/destruyen dinámicamente • Uso de memoria dinámica • Creación de nodo ≡ malloc • Liberación de nodo ≡ free
• Reserva de memoria: malloc void *malloc(size_t n)
• Liberación de memoria: free
• Ventajas
nodo
free(void *ptr)
• Sólo se tiene reservada la memoria que se necesita en cada momento • Se pueden albergar tantos elementos como la memoria disponible permita • Insertar/extraer nodos no requiere desplazamientos de memoria
• Realoje de memoria: realloc void *realloc(void *ptr, size_t n)
• Desventajas • Bueno para acceso secuencial; malo para acceso aleatorio Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Implementación en C: estructura de datos
10
Implementación en C: creación de nodos • Creación de un nodo Nodo *crearNodo() { Nodo *pn = NULL; pn = (Nodo *) malloc(sizeof(Nodo)); if (pn==NULL) return NULL; pn->next = NULL; return pn; }
• Estructura de datos typedef struct { generic info; struct Nodo *next; } Nodo;
• Ejemplo de llamada
typedef struct _Nodo { generic info; struct _Nodo *next; } Nodo;
info
next
Nodo *n = NULL; n = crearNodo(); if (n == NULL){ // CdE }
llamada a crearNodo n
crearNodo pn
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
memoria
11
Implementación en C: liberación de nodos
12
• Liberación de un nodo void liberarNodo( Nodo *pn ) { liberarInfo(pn); // Libera memoria en info si necesario free(pn); // Libera nodo pn = NULL; }
• Ejemplo de llamada Nodo *n = NULL; n= crearNodo(); if (n == NULL) { // CdE } liberarNodo(n);
llamada a liberarNodo
Implementación en C: lista enlazada
13
• Lista enlazada • Colección de nodos enlazados • El último nodo apunta a NULL • La lista es un puntero al nodo inicial
memoria lista
n
• Tipo de dato Lista ≡ Puntero al nodo inicial typedef Nodo* Lista;
liberarNodo pn Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Implementación en C: lista enlazada // Primitivas de Nodo Nodo *crearNodo() void liberarNodo(Nodo *pn) // Primitivas de Lista status listaInicializar(Lista *pl) boolean listaVacia(Lista *pl) status listaInsertarIni(Lista *pl, generic *x) status listaExtraerIni(Lista *pl, generic *x) status listaInsertarFin(Lista *pl, generic *x) status listaExtraerFin(Lista *pl, generic *x)
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
14
Implementación en C: listaInicializar • Inicializar lista status listaInicializar(Lista *pl) { *pl = NULL; return OK; }
NULL
lista
typedef Nodo *Lista; status listaInicializar(Nodo **pl) { *pl = NULL; return OK; }
llamada a listaInicializar l
• Ejemplo de llamada Lista l; listaInicializar(&l); pl listaInicializar
Importante: para mayor legibilidad, en las implementaciones que siguen NO se realiza control de argumentos de entrada ¡habría que hacerlo! Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
15
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Implementación en C: listaVacia
16
Implementación en C: listaInsertarIni
17
• Idea • Lista vacía boolean listaVacia(Lista *pl) { if (*pl==NULL) return TRUE; return FALSE; }
1) Crear un nuevo nodo 2) Hacer que este nodo apunte al principio de la lista 3) El nuevo nodo es ahora el principio de la lista
NULL
lista
• Pseudocódigo status listaInsertarIni(Lista l, generic x) { Nodo n = crearNodo(); if (n==NULL) devolver ERROR;
• Ejemplo de llamada llamada a listaVacia
Lista l; ... if listaVacia(&l) { ... }
next(n) = l; info(n) = x; l = n; devolver OK;
l listaVacia
l
}
pl
3)
2)
l 1)
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Implementación en C: listaInsertarIni • Implementación
n Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
18
Implementación en C: listaInsertarIni • Implementación
status listaInsertarIni(Lista *pl, generic *x) { Nodo *pn = NULL; pn = crearNodo(); if (pn==NULL) return ERROR; pn->next = *pl; pn->info = *x; *pl = pn; return OK;
pn->next = *pl; pn->info = *x; *pl = pn; return OK;
}
1
2
status listaInsertarIni(Lista *pl, generic *x) { Nodo *pn = NULL; pn = crearNodo(); if (pn==NULL) return ERROR;
llamada
e
}
l
• Ejemplo de llamada listaInsertarIni
Lista l; Generic e; ... listaInsertarIni(&l, &x);
x 2
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
pl 1
19
Implementación en C: listaInsertarIni
20
• Implementación
21
• Implementación
status listaInsertarIni(Lista *pl, generic *x) { Nodo *pn = NULL; 3 pn = crearNodo(); if (pn==NULL) return ERROR; pn->next = *pl; pn->info = *x; *pl = pn; return OK;
Implementación en C: listaInsertarIni
llamada
status listaInsertarIni(Lista *pl, generic *x) { Nodo *pn = NULL; pn = crearNodo(); if (pn==NULL) return ERROR;
4 pn->next = *pl; 5 pn->info = *x; e
}
*pl = pn; return OK;
l
llamada
e
}
listaInsertarIni
l
4
listaInsertarIni
x
pl
x
pl e
3
5
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Implementación en C: listaInsertarIni
Implementación en C: listaInsertarIni
23
• Alternativa implementación: uso de marcos
• Implementación
#define next(pn) (pn)->next #define info(pn) (pn)->info
status listaInsertarIni(Lista *pl, generic *x) { Nodo *pn = NULL; pn = crearNodo(); if (pn==NULL) return ERROR; pn->next = *pl; pn->info = *x; 6 *pl = pn; return OK;
22
llamada
e
}
status listaInsertarIni(Lista *pl, generic *x) { Nodo *pn = NULL; pn = crearNodo(); if (pn==NULL) return ERROR;
l
next(pn) = *pl; info(pn) = *x; *pl = pn; return OK;
6 listaInsertarIni
x
}
pl e
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
• Ventajas • Más parecido al pseudocódigo; más fácil de entender/manejar • Se puede hacer (más o menos) independiente de la EdD Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Implementación en C: listaInsertarIni
24
Implementación en C: listaExtraerIni
25
• Otro ejemplo de uso de macros #define info(A) A->info
• Si en el código encontramos info(abcde) abcde->info • Si encontramos info(*ppn) *ppn->info /* ¡Problema! ‘->’ se aplica antes */ • Solución: redefinir la macro como sigue:
• Implementar la función listaExtraerIni status listaExtraerIni(Lista *pl, generic *x)
#define info(A) (A)->info
Ahora: info(*ppn) (*ppn)->info
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Implementación en C: listaExtraerIni
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
26
Implementación en C: listaExtraerIni • Implementación
• Idea: 1) Devolver el campo info del primer nodo 2) Hacer que la lista apunte al siguiente nodo 3) Eliminar el primer nodo
status listaExtraerIni(Lista *pl, generic *x) { Nodo *pn = NULL; if (listaVacia(pl)==TRUE) return ERROR; pn = *pl; *pl = next(*pl); *x = info(*pl); liberarNodo(pn); return OK;
• Pseudocódigo status listaExtraerIni(Lista l, generic x) { if (listaVacia(l)) devolver ERROR; n = l; l = next(n) x = info(n) liberarNodo(n) liberarNodo l devolver OK; } 2)
/* ¡Ojo! Lista es Nodo** */
}
• Ejemplo de llamada Lista l; generic g; ... listaExtraerIni(&l, &g);
l x
1)
3) Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
27
Implementación en C: listaExtraerIni • Implementación
1
28
}
status listaExtraerIni(Lista *pl, generic *x) { Nodo *pn = NULL; if (listaVacia(pl)==TRUE) return ERROR;
/* ¡Ojo! Lista es Nodo** */
3 pn = *pl;
}
l
g
listaExtraerIni
x 2
llamada
l
g
e
listaExtraerIni
pl
x
e
pl
3
pn
1
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Implementación en C: listaExtraerIni • Implementación
30
Implementación en C: listaExtraerIni • Implementación
status listaExtraerIni(Lista *pl, generic *x) { Nodo *pn = NULL; if (listaVacia(pl)==TRUE) return ERROR;
status listaExtraerIni(Lista *pl, generic *x) { Nodo *pn = NULL; if (listaVacia(pl)==TRUE) return ERROR;
/* ¡Ojo! Lista es Nodo** */
pn = *pl; *pl = next(*pl); 5 *x = info(*pl); liberarNodo(pn); return OK;
4 *pl = next(*pl); *x = info(*pl); liberarNodo(pn); return OK; }
/* ¡Ojo! Lista es Nodo** */
*pl = next(*pl); *x = info(*pl); liberarNodo(pn); return OK;
llamada
pn = *pl;
29
• Implementación
2
status listaExtraerIni(Lista *pl, generic *x) { Nodo *pn = NULL; if (listaVacia(pl)==TRUE) return ERROR; pn = *pl; *pl = next(*pl); *x = info(*pl); liberarNodo(pn); return OK;
Implementación en C: listaExtraerIni
4 }
llamada
l
g
listaExtraerIni
x
/* ¡Ojo! Lista es Nodo** */
5 llamada
e
pl
listaExtraerIni
e g
x
l
pl
pn Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
e
pn Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
31
Implementación en C: listaExtraerIni
32
• Implementación
}
33
• Implementación
status listaExtraerIni(Lista *pl, generic *x) { Nodo *pn = NULL; if (listaVacia(pl)==TRUE) return ERROR; pn = *pl; *pl = next(*pl); *x = info(*pl); 6 liberarNodo(pn); return OK;
Implementación en C: listaExtraerIni status listaExtraerIni(Lista *pl, generic *x) { Nodo *pn = NULL; if (listaVacia(pl)==TRUE) return ERROR;
/* ¡Ojo! Lista es Nodo** */
llamada
pn = *pl; *pl = next(*pl); *x = info(*pl); liberarNodo(pn); 7 return OK; }
e g
l
/* ¡Ojo! Lista es Nodo** */
llamada
e
e g
l
6 listaExtraerIni
x
listaExtraerIni
pl
x
pl
pn Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Implementación en C: listaExtraerFin
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
34
Implementación en C: listaInsertarFin
35
• Idea: 1) Crear un nuevo nodo y asignar campo info
• Si lista vacía: 2) Asignar el nuevo nodo como primer nodo de la lista
• Si lista no vacía:
• Implementar la función listaInsertarFin
2) Recorrer la lista hasta encontrar el último nodo 3) Hacer que el último nodo apunte al nuevo nodo
status listaInsertarFin(Lista *pl, generic *x)
Lista vacía
Lista no vacía
l
l
3)
2)
l Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
1)
l Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
2)
1)
Implementación en C: listaInsertarFin
36
• Implementación
Implementación en C: listaInsertarFin • Implementación (lista vacía)
status listaInsertarFin(Lista *pl, generic *x) { Nodo *pn = NULL, *qn = NULL;
37
1 2
status listaInsertarFin(Lista *pl, generic *x) { Nodo *pn = NULL, *qn = NULL;
pn = crearNodo(); if (pn==NULL) return ERROR; pn->info = *x;
pn = crearNodo(); if (pn==NULL) return ERROR; pn->info = *x;
if (listaVacia(pl)==TRUE){ *pl = pn; return OK; } for (qn=*pl; qn->next!=NULL; qn=qn->next) ; qn->next = pn; return OK;
2 casos 1) Lista vacía 2) Lista no vacía
}
}
if (listaVacia(pl)==TRUE){ *pl = pn; return OK; } for (qn=*pl; qn->next!=NULL; qn=qn->next) ; qn->next = pn; return OK;
g
l
x 2
pl 1
llamada
• Ejemplo de llamada
listaInsertarFin
Lista l; generic g; ... listaInsertarFin(&l, &g); Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Implementación en C: listaInsertarFin
38
• Implementación (lista vacía)
}
39
• Implementación (lista vacía)
status listaInsertarFin(Lista *pl, generic *x) { Nodo *pn = NULL, *qn = NULL;
3
Implementación en C: listaInsertarFin status listaInsertarFin(Lista *pl, generic *x) { Nodo *pn = NULL, *qn = NULL;
pn = crearNodo(); if (pn==NULL) return ERROR; pn->info = *x;
pn = crearNodo(); if (pn==NULL) return ERROR; pn->info = *x;
if (listaVacia(pl)==TRUE){ *pl = pn; return OK; } for (qn=*pl; qn->next!=NULL; qn=qn->next) ; qn->next = pn; return OK;
if (listaVacia(pl)==TRUE){ *pl = pn; 4 return OK; } for (qn=*pl; qn->next!=NULL; qn=qn->next) ; qn->next = pn; return OK;
g
}
l
llamada
g
4
l
llamada 3
listaInsertarFin x
pl pn
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
g
listaInsertarFin x
pl pn
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
g
Implementación en C: listaInsertarFin • Implementación (lista no vacía)
40
Implementación en C: listaInsertarFin • Implementación (lista no vacía)
1 2
status listaInsertarFin(Lista *pl, generic *x) { Nodo *pn = NULL, *qn = NULL;
status listaInsertarFin(Lista *pl, generic *x) { Nodo *pn = NULL, *qn = NULL;
pn = crearNodo(); if (pn==NULL) return ERROR; pn->info = *x;
3
if (listaVacia(pl)==TRUE){ *pl = pn; return OK; } for (qn=*pl; qn->next!=NULL; qn=qn->next) ; qn->next = pn; return OK;
}
g
}
l
g
l
llamada
listaInsertarFin
listaInsertarFin x 2
pl 1
x
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
pl
3 pn
g
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Implementación en C: listaInsertarFin
42
• Implementación (lista no vacía)
Implementación en C: listaInsertarFin
43
• Implementación (lista no vacía)
status listaInsertarFin(Lista *pl, generic *x) { Nodo *pn = NULL, *qn = NULL;
}
pn = crearNodo(); if (pn==NULL) return ERROR; pn->info = *x; if (listaVacia(pl)==TRUE){ *pl = pn; return OK; } for (qn=*pl; qn->next!=NULL; qn=qn->next) ; qn->next = pn; return OK;
llamada
4
41
status listaInsertarFin(Lista *pl, generic *x) { Nodo *pn = NULL, *qn = NULL;
pn = crearNodo(); if (pn==NULL) return ERROR; pn->info = *x;
pn = crearNodo(); if (pn==NULL) return ERROR; pn->info = *x;
if (listaVacia(pl)==TRUE){ *pl = pn; return OK; } for (qn=*pl; qn->next!=NULL; qn=qn->next) ; qn->next = pn; return OK;
if (listaVacia(pl)==TRUE){ *pl = pn; return OK; } for (qn=*pl; qn->next!=NULL; qn=qn->next) ; qn->next = pn; return OK;
g
5 }
l
llamada
g
l
llamada
listaInsertarFin x
qn pl pn
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
4 listaInsertarFin g
x
qn pl pn
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
5 g
Implementación en C: listaInsertarFin
44
Implementación en C: listaExtraerFin
45
• Implementación con macros status listaInsertarFin(Lista *pl, generic *x) { Nodo *pn=NULL, *qn=NULL; pn = crearNodo(); if (pn==NULL) return ERROR; info(pn) = *x; if (listaVacia(pl)==TRUE) { *pl = pn; return OK; } for(qn=*pl; next(qn)!=NULL; qn=next(qn)); next(qn) = pn; return OK;
• Implementar la función listaExtraerFin status listaExtraerFin(Lista *pl, generic *x)
}
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Implementación en C: listaExtraerFin
46
• Idea:
47
• Implementación status listaExtraerFin(Lista *pl, generic *x) { Nodo *pn = NULL; if( listaVacia(pl)==TRUE ) return ERROR; /* Caso 1 nodo */ if( (*pl)->next==NULL ) { *x = (*pl)->info; liberarNodo(*pl); *pl = NULL; return OK; } /* Caso varios nodos */ for(pn=*pl; pn->next->next!=NULL; pn=pn->next) ; *x = pn->next->info; liberarNodo(pn->next); pn->next = NULL; return OK; }
Si se tiene un nodo 1) Eliminar ese nodo y dejar lista vacía Si se tiene más de un nodo 1) Recorrer la lista hasta llegar al penúltimo nodo 2) Liberar el último nodo 3) Hacer que el “penúltimo” nodo apunte a NULL x
1)
l
l
Implementación en C: listaExtraerFin
1)
x
l
3) Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
2)
• Ejemplo de llamada Lista l; generic g; ... listaExtraerFin(&l, &g); Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
2 casos 1) Lista de un nodo 2) Lista de varios nodos
Implementación en C: listaExtraerFin
48
• Implementación (lista de un nodo)
Implementación en C: listaExtraerFin
49
• Implementación (lista de un nodo) status listaExtraerFin(Lista *pl, generic *x) { Nodo *pn = NULL; if( listaVacia(pl)==TRUE ) return ERROR; /* Caso 1 nodo */ if( (*pl)->next==NULL ) { *x = (*pl)->info; 2 liberarNodo(*pl); *pl = NULL; return OK; } /* Caso varios nodos */ for(pn=*pl; pn->next->next!=NULL; pn=pn->next) ; *x = pn->next->info; 2 liberarNodo(pn->next); e pn->next = NULL; g l e return OK; }
status listaExtraerFin(Lista *pl, generic *x) { Nodo *pn = NULL; if( listaVacia(pl)==TRUE ) return ERROR; /* Caso 1 nodo */ if( (*pl)->next==NULL ) { 1 *x = (*pl)->info; liberarNodo(*pl); *pl = NULL; return OK; } /* Caso varios nodos */ for(pn=*pl; pn->next->next!=NULL; pn=pn->next) ; *x = pn->next->info; 1 e liberarNodo(pn->next); pn->next = NULL; g l e return OK; }
llamada
llamada
listaInsertarFin
listaInsertarFin x
pl
x
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Implementación en C: listaExtraerFin • Implementación (lista de un nodo) status listaExtraerFin(Lista *pl, generic *x) { Nodo *pn = NULL; if( listaVacia(pl)==TRUE ) return ERROR; /* Caso 1 nodo */ if( (*pl)->next==NULL ) { *x = (*pl)->info; liberarNodo(*pl); 3 *pl = NULL; return OK; } /* Caso varios nodos */ for(pn=*pl; pn->next->next!=NULL; pn=pn->next) ; *x = pn->next->info; 3 liberarNodo(pn->next); e pn->next = NULL; g l return OK; }
llamada
listaInsertarFin
pl
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
50
Implementación en C: listaExtraerFin • Implementación (lista de varios nodos) status listaExtraerFin(Lista *pl, generic *x) { Nodo *pn = NULL; if( listaVacia(pl)==TRUE ) return ERROR; /* Caso 1 nodo */ if( (*pl)->next==NULL ) { *x = (*pl)->info; liberarNodo(*pl); *pl = NULL; return OK; } /* Caso varios nodos */ 1 for(pn=*pl; pn->next->next!=NULL; pn=pn->next) ; *x = pn->next->info; liberarNodo(pn->next); pn->next = NULL; g l return OK; }
llamada
listaInsertarFin x
pl
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
51
x
pl
1 pn
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
e
Implementación en C: listaExtraerFin
52
• Implementación (lista de varios nodos)
Implementación en C: listaExtraerFin
53
• Implementación (lista de varios nodos)
status listaExtraerFin(Lista *pl, generic *x) { Nodo *pn = NULL; if( listaVacia(pl)==TRUE ) return ERROR; /* Caso 1 nodo */ if( (*pl)->next==NULL ) { *x = (*pl)->info; liberarNodo(*pl); *pl = NULL; return OK; } /* Caso varios nodos */ for(pn=*pl; pn->next->next!=NULL; pn=pn->next) ; 2 *x = pn->next->info; liberarNodo(pn->next); 2 e pn->next = NULL; g l return OK; }
status listaExtraerFin(Lista *pl, generic *x) { Nodo *pn = NULL; if( listaVacia(pl)==TRUE ) return ERROR; /* Caso 1 nodo */ if( (*pl)->next==NULL ) { *x = (*pl)->info; liberarNodo(*pl); *pl = NULL; return OK; } /* Caso varios nodos */ for(pn=*pl; pn->next->next!=NULL; pn=pn->next) ; *x = pn->next->info; e 3 liberarNodo(pn->next); pn->next = NULL; g l return OK; }
e
llamada
3 e
llamada
listaInsertarFin
listaInsertarFin x
pl
x
pn
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
54
• Implementación (lista de varios nodos)
llamada
pn
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Implementación en C: listaExtraerFin status listaExtraerFin(Lista *pl, generic *x) { Nodo *pn = NULL; if( listaVacia(pl)==TRUE ) return ERROR; /* Caso 1 nodo */ if( (*pl)->next==NULL ) { *x = (*pl)->info; liberarNodo(*pl); *pl = NULL; return OK; } /* Caso varios nodos */ for(pn=*pl; pn->next->next!=NULL; pn=pn->next) ; *x = pn->next->info; liberarNodo(pn->next); e 4 pn->next = NULL; g l return OK; }
pl
Implementación en C: listaExtraerFin • Implementación con macros
4
status listaExtraerFin(Lista *pl, generic *x) { Nodo *pn = NULL; if( listaVacia(pl)==TRUE ) return ERROR; /* Caso 1 nodo */ if( (*pl)->next==NULL ) { *x = info(*pl); liberarNodo(*pl); *pl = NULL; return OK; } /* Caso varios nodos */ for(pn=*pl; next(pn)!=NULL; pn=next(pn)) ; *x = info(next(pn)); liberarNodo(next(pn)); next(pn) = NULL; return OK; }
listaInsertarFin x
pl
pn
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
55
Implementación en C: listaLiberar
56
Tipos de listas enlazadas
57
• Listas simplemente enlazadas
• Implementación usando primitivas status listaLiberar(Lista *pl){ generic g; while (!listaVacia(pl)) { listaExtraerIni(&g, pl); } }
• Listas circulares simplemente enlazadas
• Implementación accediendo a la estructura status listaLiberar(Lista *pl){ nodo *pn = NULL; while (*pl != NULL){ pn= *pl; *pl= next(*pl); liberarNodo(pn); } }
• Listas doblemente enlazadas
• Implementación recursiva status listaLiberar(Lista *l){ // condición de parada if (*l == NULL) return OK; // llamada recursiva else { listaLiberar(&next(l)); liberarNodo(*l); return OK; } }
• Listas circulares doblemente enlazadas
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Listas doblemente enlazadas
58
Contenidos
59
• Estructuras de datos typedef struct _NodoDE { struct _NodoDE *prev; generic info; struct _NodoDE *next; } NodoDE;
• Listas • Pilas • Colas
typedef NodoDE* ListaDE;
prev
info
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
next
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Pilas
60
• Pila • stack en inglés • LIFO - Last Input, First Output (el último que entra, el primero que sale)
Pilas. Estructura de datos y primitivas
61
• Estructura de datos mediante un array #define MAX_SIZE 256 typedef struct { generic datos[MAX_SIZE]; int top; // última posición } Pila;
top
• Primitivas • • • • • Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Pilas. Implementación status pilaInicializar(Pila *ps) { if (!ps) return ERROR; ps->top = -1; return OK; } boolean pilaVacia(Pila *ps) { if (!ps) return TRUE; if (ps->top == -1) return TRUE; return FALSE; }
62
top
2
boolean pilaLlena(Pila *ps) { if (!ps) return TRUE; if (ps->top == MAX_SIZE-1) return TRUE; return FALSE; }
Pila Llena
Pila vacía
3
1 0 -1
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
datos status pilaInicializar(Pila s): Inicializa una pila s boolean pilaVacia(Pila s): Comprueba si una pila s está vacía boolean pilaLlena(Pila s): Comprueba si una pila s está llena status push(Pila s, generic g): Inserta el elemento g en la pila s status pop(Pila s, generic g): Extrae el elemento que ocupa el top de la pila s y lo guarda en g
top
Pilas. Implementación status push(Pila *ps, generic *pg){ if (pilaLlena(ps)==TRUE) return ERROR; ps->top++; ps->datos[ps->top] = *pg; return OK; } status pop(Pila *ps, generic *pg){ if (pilaVacia(ps)==TRUE) return ERROR; *pg = ps->datos[ps->top]; ps->top--; return OK; }
63
pop(pila, g)
push(pila, g)
top
top
g
g
datos
datos
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Pilas. Aplicaciones
64
Pilas. Aplicación: balanceo de paréntesis
• Determinar si una expresión (p.e. una operación aritmética) contiene el mismo número de paréntesis de apertura que de cierre
• Balanceo de paréntesis • Evaluación de expresiones infijo, prefijo, posfijo (o sufijo) • Conversión entre expresiones infijo, prefijo, posfijo
( 3 * 4 / ( 6 - 1 ) ) CORRECTA 2 + ( 5 / ( 4 + 7 ) INCORRECTA 6 * 4 + 9 ) INCORRECTA
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Pilas. Aplicación: balanceo de paréntesis
66
Pilas. Aplicación: balanceo de paréntesis
• Pseudocódigo (sin CdE) status balanceoParentesis(CC S) { pilaInicializar(p); mientras (it=leerSimbolo(S)) != EOS si esParentesisApertura(it) push(p,it) else si esParentesisCierre(it) si pilaVacia(p) == TRUE devolver ERROR pop(p,e)
// leer siguiente símbolo de S
• Ejemplo 1: ( 3 * 4 / ( 6 - 1 ) )
si pilaVacia(p) == TRUE devolver OK devolver ERROR
Símbolo
}
• Ejemplo 2: 2 + ( 5 / ( 4 + 7 ) • Ejemplo 3: 6 * 4 + 9 ) Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
65
( 3 * 4 / ( 6 1 ) )
Pila de paréntesis ( ( ( ( ( (( (( (( (( (
• Determinar si una expresión (p.e. una operación aritmética) contiene el mismo número de paréntesis de apertura que de cierre, distinguiendo ‘()’, ‘{}’, ‘[]’ { 3 * 4 / ( 6 - 1 ) } CORRECTA 2 + ( 5 / [ 4 + 7 ) ) INCORRECTA 6 * 4 + 9 } INCORRECTA
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
67
Pilas. Aplicación: balanceo de paréntesis
68
• Pseudocódigo incompleto (sin CdE)
69
• Pseudocódigo (sin CdE)
status balanceoParentesis(CC S) { pilaInicializar(p); mientras (it=leerSimbolo(S)) != EOS si esParentesisApertura(it) push(p,it) else si esParentesisCierre(it) si pilaVacia(p) == TRUE devolver ERROR pop(p,e)
Pilas. Aplicación: balanceo de paréntesis status balanceoParentesis(CC S) { pilaInicializar(p);
// leer siguiente símbolo de S
mientras (it=leerSimbolo(S)) != EOS si esParentesisApertura(it) push(p,it) else si esParentesisCierre(it) si pilaVacia(p) == TRUE devolver ERROR pop(p,e)
si pilaVacia(p) == TRUE devolver OK devolver ERROR
// leer siguiente símbolo de S
si (it==')' AND e!='(') OR (it==']' AND e!='[') OR (it=='}' AND e!='{')
devolver ERROR; si pilaVacia(p) == TRUE devolver OK devolver ERROR
}
}
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Pilas. Aplicación: balanceo de paréntesis • Pseudocódigo (sin CdE)
70
Pilas. Expresiones infijo, posfijo, prefijo • Notación infijo
status balanceoParentesis(CC S) { pilaInicializar(p); mientras (it=leerSimbolo(S)) != EOS si esParentesisApertura(it) push(p,it) else si esParentesisCierre(it) si pilaVacia(p) == TRUE devolver ERROR pop(p,e)
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
// leer siguiente símbolo de S
si sonParentesisPareja(it,e) == FALSE devolver ERROR;
• Los operadores se indican entre operandos: A+B • La habitual
• Notación posfijo • Los operadores se indican después de los operandos: AB+ • La más “práctica” para un ordenador
• Notación prefijo • Los operadores se indican antes de los operandos: +AB
si pilaVacia(p) == TRUE devolver OK devolver ERROR
• Ejemplo
}
• Ejemplo 4: { 3 * 4 / ( 6 - 1 ) } • Ejemplo 5: 2 + ( 5 / [ 4 + 7 ) ) Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
• En infijo: 2 - 3 * (4 + 1) • En posfijo: 2 3 4 1 + * • En prefijo: - 2 * 3 + 4 1 Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
71
Pilas. Aplicación: evaluación de expr. posfijo
72
• Ejemplos
Pilas. Aplicación: evaluación de expr. posfijo
73
• Pseudocódigo (sin CdE)
• Ejemplo 6: 2 3 + 3 1 + +
1 3 2
2
5
3
3
4
5
5
5
9
Símbolo
Operando 1
2 3 + 3 1 + +
Operando 2
Valor
2
3
5
3 5
1 4
4 9
status evaluarPosfijo(CC S, Entero r) { pilaInicializar(p); mientras (it=leerSimbolo(S)) != EOS // leer siguiente símbolo de S si esOperando(it) push(p,it) else si esOperador(it) pop(p,op2) pop(p,op1) e = evaluar(op1,op2,it) push(p,e) pop(p,r) • Ejemplo 8: 1 6 * 2 1 / 3 4 - + devolver OK Pila de Símbolo Operando 1 Operando 2 Valor } operandos
Pila de operandos 2 2,3 5 5,3 5,3,1 5,4 9
• Ejemplo 7: 1 2 * 4 2 / 3 4 + 5 * - + Símbolo
Operando 1
1 2 * 4 2 / 3 4 + 5 * +
Operando 2
1
2
Valor
2
4
2
2
3
4
7
7 2 2
5 35 -33
35 -33 -31
Pila de operandos 1 1,2 2 2,4 2,4,2 2,2 2,2,3 2,2,3,4 2,2,7 2,2,7,5 2,2,35 2,-33 -31
1 6 * 2 1 / 3 4 +
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Pilas. Aplicación: evaluación de expr. posfijo
6
6
2
1
2
3 2
4 -1
-1 1
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
74
• Pseudocódigo (con CdE)
Pilas. Aplicación: conversión infijo-posfijo • Ejemplo: A + B * C
status evaluarPosfijo(CC S, Entero r) { if (pilaInicializar(p)== ERR)) devolver ERROR mientras (it = leerItem(S)) != EOS si esOperando(it) si (push(p,it) == ERROR) // ERROR 1: la pila está llena vaciarPila(p) devolver ERROR else si esOperador(it) si (pop(p,op2) == OK) && (pop(p,op1) == OK) e = evaluar(op1,op2,it) push(p,e) else // ERROR 2: no hay suficientes operandos en la pila vaciarPila(p) devolver ERROR
• A + B * C => AB+C* • A +(B * C)=> ABC*+
• Hay que tener en cuenta: • Precedencia de operadores • Asociatividad de operaciones precedencia
+
operador
asociatividad
() [] . ->
izquierda-derecha
* / %
pop(p, r) si (pilaVacia(p) == FALSE) //ERROR 3: la pila al final no está vacía devolver ERROR
+ izquierda-derecha &&
}
• Ejemplo 9: 1 6 * 2 + /
1
||
• Ejemplo 10: 1 6 * 2 1 / 3 4 - + Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
1 1,6 6 6,2 6,2,1 6,2 6,2,3 6,2,3,4 6,2,-1 6,1 ERROR!!
-
=
derecha-izquierda
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
75
Pilas. Aplicación: conversión infijo-posfijo
76
• Idea inicial
A * B + C / E => AB*CE/+ Traducción parcial A A AB AB ABC ABC*+
Pila de OPERADORES
Símbolo A * B + C / E EOS
+ + + * + *
• Posible algoritmo 1. Si el símbolo actual it es operando: “imprimir” it a cadena traducción 2. Si it es operador: push(pila, it) 3. Al final: vaciar pila e imprimiendo elementos en cadena traducción
• Teniendo en cuenta precedencia de operadores A * B + C / E => AB*CE/+
+ + + / + /
• Los operadores de mayor precedencia salen antes de pila • A igual precedencia, sale antes el que se leyó antes
78
Pilas. Aplicación: conversión infijo-posfijo • Teniendo en cuenta precedencia de operadores
Pila de OPERADORES
Símbolo A + B * C D EOS
* * + + + / + /
Traducción parcial A A AB AB ABC ABC*+ ABC*+D ABC*+D-
Pila de OPERADORES + + + * + * -
• Algoritmo 2
Si it es operando, imprimir it Un operador leído saca de la pila operadores de mayor o igual precedencia
1. 2.
>: el más preferente sale antes =: por la regla de asociatividad izquierda-derecha, también sale antes
3.
* * * * * *
A + B * C – D => ABC*+D-
• Algoritmo 1. 2.
Pila de OPERADORES
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Pilas. Aplicación: conversión infijo-posfijo Traducción parcial A A AB AB* AB*C AB*C AB*CE AB*CE/+
Traducción parcial A A AB AB ABC ABC ABCE ABCE/+* MAL
• Ajustes al algoritmo
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Símbolo A * B + C / E EOS
77
• Otro ejemplo
A + B * C => ABC*+ Símbolo A + B * C EOS
Pilas. Aplicación: conversión infijo-posfijo
Al final, vaciar la pila de operandos e imprimir Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Si it es operando, imprimir it Un operador leído saca de la pila operadores de precedencia mayor o igual >: El más preferente sale antes =: Por regla de asociatividad izquierda-derecha también sale antes
3.
Al final, vaciar la pila de operandos e imprimir Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
79
Pilas. Aplicación: conversión infijo-posfijo
80
Pilas. Aplicación: conversión infijo-posfijo
81
• Pseudocódigo (sin CdE) status infijoAPosfijo(CC S1, CC S2) pilaInicializar(p); mientras (it=leerItem(S1)) != EOS si esOperando(it) == TRUE print(S2,it); else si esOperador(it) == TRUE mientras (pilaVacia(p)==FALSE) && (prec(it) AB*CD+/EF-*
A * B / (C + D) * (E – F) Símbolo
• ‘(‘ se introduce en la pila • cuando se encuentra ‘)’ se sacan todos los operadores hasta ‘(‘
• ¿Hay que tener en cuenta el balanceado de paréntesis? • El algoritmo de conversión lo tendrá en cuenta Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Pila de OPERADORES
/( • Ejemplo: A * C+B / [CD+] *AB*C [EF-] => AB*[CD+]/[EF-]* AB*C /(+
• En la práctica:
• En la práctica:
Traducción parcial
• Clave: tratar lasA expresionesA entre paréntesis como * A * expresiones enBsi misma ABse traducen *antes de seguir la / AB* / traducción general ( AB* /( D ) * ( E F ) EOS
AB*CD AB*CD+ AB*CD+/ AB*CD+/ AB*CD+/E AB*CD+/E AB*CD+/EF AB*CD+/EFAB*CD+/EF-*
/(+ / * *( *( *(*(*
• ‘(‘ se introduce en la pila • cuando se encuentra ‘)’ se sacan todos los operadores hasta ‘(‘
• ¿Hay que tener en cuenta el balanceado de paréntesis? • El algoritmo de conversión lo tendrá en cuenta Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Pilas. Aplicación: conversión infijo-posfijo
84
• Con paréntesis…
• Posfijo infijo
A * B / (C + D) * (E – F) Símbolo A * B / ( * CB / + D ) * ( E F ) EOS
Traducción parcial
Pila de OPERADORES
A • Clave: tratar las expresiones entre paréntesis como A * expresiones en si misma antes de seguir la AB se traducen * AB* / traducción general AB* /(
• Ejemplo: A
AB*C AB*CD AB*CD+ AB*CD+/ AB*CD+/ AB*CD+/E AB*CD+/E AB*CD+/EF AB*CD+/EFAB*CD+/EF-*
1) Evaluar la expresión posfijo 2) Poner las operaciones entre paréntesis dentro de la pila
• Ejemplo: AB/CD+/EF-* Símbolo
Expresión 1
Expresión 2
Valor
A
AB*C /( [CD+] * [EF-] => AB*[CD+]/[EF-]*
• En la práctica:
Pilas. Aplicación: conversión pre/posfijo-infijo85
B
/(+ /(+ / * *( *( *(*(*
/
A, B A
B
(A/B)
C
(A/B), C, D
+
C
D
(C+D)
/
(A/B)
(C+D)
((A/B)/(C+D))
E
• ¿Hay que tener en cuenta el balanceado de paréntesis? Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
(A/B), (C+D) (A/B)/(C+D)) ((A/B)/(C+D)), E
F
• El algoritmo de conversión lo tendrá en cuenta
(A/B) (A/B), C
D
• ‘(‘ se introduce en la pila • cuando se encuentra ‘)’ se sacan todos los operadores hasta ‘(‘
Pila de EXPRESIONES A
((A/B)/(C+D)), E, F
-
E
F
*
((A/B)/(C+D)) (E-F)
(E –F)
((A/B)/(C+D)), (E-F)
((A/B)/(C+D))*(E-F)
((A/B)/(C+D))*(E-F)
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Pilas. Aplicación: conversión posfijo-prefijo
86
Pilas. Implementación con listas enlazadas
• Se puede seguir la misma estrategia de evaluación para otras conversiones • Posfijo prefijo 1) Evaluar la expresión posfijo 2) Poner las operaciones en formato prefijo
• Ejemplo: AB*CD+/ Símbolo
Expresión 1
Expresión 2
Valor
A B *
Pila de EXPRESIONES A A, B
A
B
*AB
C
*AB
status pilaInicializar(Pila *ps) boolean pilaVacia(Pila *ps) boolean pilaLlena(Pila *ps) status push(Pila *ps, generic *pg) status pop(Pila *ps, generic pg)
*AB, C
D
*AB, C, D
+
C
D
+C D
/
*AB
+CD
/*AB+CD
*AB, +CD /*AB+CD
• Otra opción: posfijo infijo prefijo Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
87
Pilas. Implementación con listas enlazadas
88
Contenidos
89
typedef Lista Pila; status pilaInicializar(Pila *ps) { return listaInicializar(ps); } boolean pilaVacia(Pila *ps) { return listaVacia(ps); } boolean pilaLlena(Pila *ps) { return FALSE; } status push(Pila *ps, generic *pg) { return listaInsertarIni(ps, listaInsertarIni pg); } status pop(Pila *ps, generic *pg) { return listaExtraerIni(ps, pg); }
• Listas • Pilas • Colas
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Colas
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
90
• Cola • queue en inglés • FIFO-First Input, First Output (el primero que entra, el primero que sale)
Colas
91
• Colas en el mundo real: para pagar en comercios, comprar tickets para un espectáculo, sacar dinero de un cajero, … • Una cola gestiona un acceso concurrente a un único recurso
• En Informática, existen muchos ejemplos de uso de colas • Impresoras - El primer trabajo en llegar es el primero que se imprime: First Come, First Served (FCFS)
• Acceso a servidores • Uso del procesador - En sistemas operativos (mono-tarea) se realizaban procesamientos secuenciales de programas
• ¡OJO! No todos los elementos a procesar son igual de importantes colas de prioridad Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Colas
92
Colas. Funciones primitivas
93
• Lista de objetos en la que… • la inserción se realiza por un único punto: rear / tail / fin • la extracción se realiza por un único punto: front / head / inicio 1. Cola Vacía
4. Sale Alice
rear front
• Primitivas
front
rear
• • • •
status colaInicializar(Cola q): Inicializa una pila s boolean colaVacia(Cola q): Comprueba si una cola q está vacía boolean colaLlena(Cola q): Comprueba si una cola q está llena status colaInsertar(Cola q, generic g): Inserta el elemento g en la cola q en el rear de la cola • status colaExtraer(Cola q, generic g): Extrae el elemento que ocupa el front de la cola q y lo guarda en g
B
2. Entra Alice (A)
front
rear
5. Llega Charlie (C)
C
A
3. Entra Bob (B)
front
rear
B
front
rear
6. Sale Bob
A
B front
rear
C Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Colas. Estructura de datos: array
94
Colas. Estructura de datos: array
95
• Ejemplo de ejecución de operaciones en una cola • Estructura de datos mediante un array #define MAX_SIZE 256 typedef generic; typedef struct { generic datos[MAX_SIZE]; int front; // primer elemento int rear; // último elemento } Cola;
rear
1) 2) 3) 4) 5) 6)
colaInializar(q) colaInsertar(q, 5) colaInsertar(q, 3) colaExtraer(q, e) colaExtraer(q, e) colaInsertar(q, 7)
f
f=r 4)
1)
f 2)
r
5
5)
f
r 3
6)
front
datos
• Problemas: • Limitación del número máximo de elementos • Desperdicio de espacio
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
3 f=r
5 f
3)
r
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
7
r?
Colas. Estructura de datos: array
96
Colas. Estructura de datos: array circular • Cola circular …
• Soluciones al desperdicio de espacio
N-1
0
97
1 2
0
1
2
3
…
N-1 3
1) Cada vez que se extrae un elemento, se desplazan todos los datos una posición en el array • Ineficiente 2) Cuando rear llega al final del array, se desplazan todos los elementos una posición en el array • (menos) Ineficiente 3) Implementación de la cola como un array circular • Más eficiente
…
• ¿Cómo implementarla? • Incrementando front y rear módulo MAX_SIZE front = (front+1) % MAX_SIZE rear = (rear+1) % MAX_SIZE
• Problema vigente • Limitación del número máximo de elementos
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Colas. Estructura de datos: array circular
98
Pilas. Implementación con arrays circulares
• Ejemplo de ejecución de operaciones 1) 2) 3) 4) 5) 6) 7) 8)
colaInicializar(q) colaInsertar(q, 5) colaInsertar(q, 3) colaExtraer(q, e) colaExtraer(q, e) colaInsertar(q, 7) colaInsertar(q, 2) colaInsertar(q, 1)
f=r
f=r vacía
1)
f 2)
5
5
r 3
r 7)
2
• Conflicto cola llena/vacía • front == rear ¿Cola vacía o llena? • Solución: sacrificar un hueco libre en el array - Prohibir la inserción cuando sólo queda un hueco - 7) es cola llena - Una cola tiene espacio para (MAX_SIZE -1) elementos Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
f 7
llena
f=r
r
3
8)
status colaInicializar(Cola *pc) { pc->rear = pc->front = 0; }
7
6)
f 4)
f
r
r
f 3)
vacía
5)
2
1
7
¿vacía? ¿llena?
boolean colaVacia(Cola *pc) { if (pc->rear == pc->front) return TRUE; return FALSE; } boolean colaLlena(Cola *pc) { if (((pc->rear + 1) % MAX_SIZE) == pc->front) return TRUE; return FALSE; }
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
r 5
f 2
99
Pilas. Implementación con arrays circulares status colaInsertar(Cola *pc, generic *pg) { if (colaLlena(pc) == TRUE) return ERROR; pc->datos[pc->rear]= *pg; pc->rear = (pc->rear + 1) % MAX_SIZE; return OK; } status colaExtraer(Cola *pc, generic *pg) { if (colaVacia(pc) == TRUE) return ERROR; *pg = pc->datos[pc->front]; pc->front = (pc->front + 1) % MAX_SIZE; return OK; }
f=r
100
r
5
3
101
f
r
7
f
Colas. Implementación con listas enlazadas
f
r
3
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Colas. Implementación con listas enlazadas
status colaInicializar(Cola *pc) boolean colaVacia(Cola *pc) boolean colaLlena(Cola *pc) status colaInsertar(Cola *pc, generic *pg) status colaExtraer(Cola *pc, generic pg)
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
102
Colas. Implementación con listas enlazadas
103
typedef Lista Cola; status colaInicializar(Cola *pc) { return listaInicializar(pc); } boolean colaVacia(Cola *pc) { return listaVacia(pc); } boolean colaLlena(Cola *pc) { return FALSE; } status colaInsertar(Cola *pc, generic *pg) { return listaInsertarFin(pc, listaInsertarFin pg); } status colaExtraer(Cola *pc, generic *pg) { return listaExtraerIni(pc, pg); } Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
• Inconveniente: la función de inserción es ineficiente, pues recorre toda la lista para insertar un elemento al final de la misma • Solución: usar una lista circular typedef ListaCircular Cola; status colaInsertar(Cola *pc, generic *pg) { return listaCircularInsertarFin(pc, pg); }
Estructura de Datos y Algoritmos Escuela Politécnica Superior Universidad Autónoma de Madrid
Estructuras de Datos y Algoritmos Tema 3. Listas enlazadas, pilas y colas
Iván Cantador David Vallet, José R. Dorronsoro Escuela Politécnica Superior
Universidad Autónoma de Madrid