Upload
alejandro-garces
View
238
Download
0
Embed Size (px)
DESCRIPTION
Conceptos básicos de Listas, Pila y colas.
Citation preview
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 1/18
Algoritmos y Estructuras de Datos
3. Estructuras de Datos Básicas
3.3. Listas
Introducción
Una lista enlazada o encadenada es una colección de elementos ó nodos, en donde cada uno contiene
datos y un enlace o liga.Un nodo es una secuencia de caracteres en memoria dividida en campos (de cualquier tipo). Un nodo
siempre contiene la dirección de memoria del siguiente nodo de información si este existe.
Un apuntador es la dirección de memoria de un nodoLa figura siguiente muestra la estructura de un nodo:
El campo liga, que es de tipo puntero, es el que se usa para establecer la liga con el siguiente nodo de lalista. Si el nodo fuera el último, este campo recibe como valor NIL (vacío).
A continuación se muestra el esquema de una lista :
Forma de declarar una lista enlazadastruct nodo {
char dato[10];
struct nodo *link;};
struct nodo *lista; /* lista es un puntero a nodo*/
Ej. Referenciar un miembro de nodo:
lista->dato =”hola”;
lista->link = NULL; */ lista está apuntando a vacío*/
Inicialización y Borrado de variables de tipo Puntero
Cuando se quiere usar una variable tipo puntero no basta sólo con declararla, es necesario asignarle un
espacio en memoria. La funcion new
, asigna almacenamiento para una variable de un tipo determinadoy guarda la dirección de la celda de memoria en la variable.
Ej. Asignación de memoria para un nodo: lista = new nodo;
Por otro lado, cuando la variable se deja de usar, se debe liberar la posición de memoria ocupada por la
variable, para ello se utiliza el procedimiento delete.
Ej. Libera la posición de memoria ocupada por un nodo: delete lista;
DATO LINK
Juan Luis María Sofía NULL
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 2/18
Operaciones en Listas Encadenadas
Las operaciones que podemos realizar sobre listas encadenadas son las siguientes:
• Recorrido. Esta operación consiste en visitar cada uno de los nodos que forman la lista. Pararecorrer todos los nodos de la lista, se comienza con el primero, se toma el valor del campo liga
para avanzar al segundo nodo, el campo liga de este nodo nos dará la dirección del tercer nodo,
y así sucesivamente.• Inserción. Esta operación consiste en agregar un nuevo nodo a la lista. Para esta operación se
pueden considerar tres casos:
o Insertar un nodo al inicio.o Insertar un nodo antes o después de cierto nodo.o Insertar un nodo al final.
• Borrado. La operación de borrado consiste en quitar un nodo de la lista, redefiniendo las ligas
que correspondan. Se pueden presentar cuatro casos:o Eliminar el primer nodo.
o Eliminar el último nodo.
o Eliminar un nodo con cierta información.o
Eliminar el nodo anterior o posterior al nodo cierta con información.• Búsqueda. Esta operación consiste en visitar cada uno de los nodos, tomando al campo liga
como puntero al siguiente nodo a visitar.
Algoritmos sobre listas lineales
Las listas lineales encadenadas siempre deben mantener un puntero al inicio el cual se llama raiz o
tope. Se usará la variable TOP para referenciar al primer nodo de la lista y TOP->dato y TOP->link
para hacer referencia al dato almacenado y al link al siguiente nodo respectivamente.
struct nodo {
char dato;
struct nodo *link;};
Algoritmo de Creación
struct nodo *Crea_lista_final()/*donde p es de tipo puntero a nodo}*/
{ struct nodo *p, *top, *q; /*top es un puntero al inicio de la lista de nodos*/
int respuesta; /*q es de tipo puntero a nodo*/
TOP = NULL;
respuesta = 1;
while (respuesta)
{ p = new nodo;
cout << “Dato”;cin >> p->dato;
if (top == NULL)
{ top = p;
q = p;}
else
{ q->link = p;
p->link = NULL;
q = p; }
cout << “Otro nodo? (si=1; no=0)”;
cin >> respuesta;
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 3/18
}
return(top);
}
struct nodo *Crea_lista_inicio()/*donde p es de tipo puntero a nodo}*/
{ struct nodo *top; /*top es un puntero al inicio de la lista de nodos*/
int respuesta;
top = NULL;respuesta = 1;
while (respuesta)
{ p = new nodo;
cout << “Dato”;
cin >> p->dato;
if (top == NULL)
top = p;
else
{ p->link = top;
top = p;}
cout << “Otro nodo? (si=1; no=0)”;
cin >> respuesta;
}return(top);
}
Algoritmo para Recorrido
Recorre_lista(struct nodo *top) /*top es un puntero al inicio de una lista*/
{ struct nodo *p;
p = top;
while (p <> NULL)
{ cout << p->dato;
p = p->link;}
}
Algoritmo para insertar un nodo a una lista que ya existe y que está apuntada por top
inserta_final_lista(struct nodo *top)
{ struct nodo *p, *q;
p = top;
while (p->link <> NULL)
p = p->link;
q = new nodo;
cout << “Dato”;
cin >> q->dato;
p->link = q;
q->link = NULL;
}
inserta_inicio_lista(top)
{ struct nodo *p;
p = new nodo;
cout << “Dato”;
cin >> p->dato;
p->link = top;
top = p;
}
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 4/18
Algoritmo para insertar un nodo antes/después de 'X' información
Inserta_antes_despues(struct nodo *top, char x)
{ struct nodo *p, *q;
int respuesta;
p = top;
cout << “antes(1)/después(0))
cin >> respuesta;
if (respuesta)
{ while (p <> NULL)
{ if (p->dato == x)
{ q = new nodo;
cout << “Dato”;
cin >> q->dato;
q->link = p;
if (p == top)
top = q;
else
r->link = q;
}else
{ r = p;
p = p->link;}}
}else
{ while (p <> NULL)
{ if (p->dato == x)
{ q = new nodo;
cout << “Dato”;
cin >> q->dato;
if (p == top || p->link==NULL)
{ p->link = q;
q->link = NULL;}
else
{ q->link = p->link;
p->link = q;}}else
p = p->link;
}
}
}
Algoritmo para borrar un nodo que tiene el dato ‘X’
elimina_nodo (struct nodo *top, char x)
{ struct nodo *p, *q;
p = top;
while (p <> NULL)
{ if(p->dato == x)if (p == top)
if (p->link == NULL) top = NULL;
else top = top->link;
else
q->link = p->link;
delete p;
else
{ q = p;
p = p->link;}
}
}
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 5/18
Listas Circulares
Las listas circulares tienen la característica de que el último elemento de la lista apunta al primero. Lasiguiente figura es una representación gráfica de una lista circular.
Algunos algoritmos sobre listas circulares son:
Algoritmo de creación
struct nodo *Crea_lista_circular_final()/*donde p es de tipo puntero a nodo}*/
{ struct nodo *p, *top, *q; /*top es un puntero al inicio de la lista de nodos*/
int respuesta; /*q es de tipo puntero a nodo*/
top = NULL;
respuesta = 1;
while (respuesta)
{ p = new nodo;
cout << “Dato”;cin >> p->dato;
if (top == NULL)
{ top = p;
q = p;}
else
{ q->link = p;
q = p; }
p->link = top;
cout << “Otro nodo? (si=1; no=0)”;
cin >> respuesta;
}
return(top);
}
Algoritmo para recorrer la lista
Recorre_circular(struct nodo *top)
{ struct nodo *p;
p = top;
if (p <> NULL)
{ cout << p->dato;
p = p->link;}
while (p <> top && p <> NULL)
{ cout << p->dato;
p = p->link;}
}
Algoritmo para borrar un nodo que contiene la información ‘X’
Elimina_circular(struct nodo *top, char x)
{ struct nodo *p, *q, *r;
q = top; r = top; p = top;
while (q->link <> top) /*posiciona el puntero q al final de la lista*/
q = q->link;
do {
if (p->dato == x)
Juan Luis María Sofía
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 6/18
{ if (p == top)
if (top->link=top)
top = NULL;
else
{ top = top->link;
q->link = top;}
else
r->link = p->link;
delete p;p = top;
}
else
{ r = p;
p = p->link;}
}
while (p <> top);
}
Listas doblemente encadenadas
Una lista doble, o doblemente ligada es una colección de nodos en la cual cada nodo tiene dos punteros,uno de ellos apuntando a su predecesor (Ant) y otro a su sucesor (Sig). Por medio de estos punteros sepodrá avanzar o retroceder a través de la lista, según se tomen las direcciones de uno u otro puntero.
En estas listas cada nodo conoce quien es el siguiente nodo y quien es el anterior.
NODO
Donde Ant y Sig son punteros a NODO.TOP NULL
NULL FIN
Dado que las listas doblemente encadenadas se pueden recorrer de izquierda a derecha y vise versaEs necesario mantener dos punteros indicando los extremos de la lista, el puntero TOP al inicio y el
puntero FIN al término.
Existen dos tipos de listas doblemente ligadas:
Listas dobles lineales. En este tipo de lista doble, tanto el puntero izquierdo del primer nodocomo el derecho del último nodo apuntan a NULL.
Listas dobles circulares. En este tipo de lista doble, el puntero izquierdo del primer nodo
apunta al último nodo de la lista, y el puntero derecho del último nodo apunta al primer nodo dela lista.
Ant Dato Sig
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 7/18
Procedimiento de crear el primer nodo de una lista doblemente enlazadap1 TOP5 NULL3
1. p =new nodo
2. p->dato= INFO
3. p->sig = NULL
4. p->ant = NULL
5. TOP = p
6. FIN = p NIL4 FIN6
Procedimiento para insertar un nodo al comienzo
1. p = new nodo
2. p->dato= INFO
3. p->sig = TOP
4. p->ant = NULL
5. TOP->ant = p
6. TOP = p
Procedimiento para insertar después de un nodo de referencia
Se recorre la lista hasta encontrar el nodo de referencia, que queda apuntado por q1. p = new nodo;
2. p->dato = INFO
3. p->sig = q->sig
4. p->ant = q
5. q->sig->ant = p
6. q->sig = p
Procedimiento para insertar antes de un nodo de referencia
Se recorre la lista hasta encontrar el nodo de referencia, que queda apuntado por q1. p = new nodo
2. p->dato = INFO
3. p->sig = q
4. p->ant = q->ant
5. q->ant->sig = p
6. q->ant = p
Algoritmo de creación de lista dobles circularestop = NULL
repite
p= new nodo
lee(p->dato)
si top=NULL entonces
p->sig = p
p->ant = p
top = pen caso contrario
p->sig = top
p->ant = top->ant
top->ant = p
p->ant->sig = p
top = p
mensaje(otro nodo?)
lee (respuesta)
hasta respuesta=no
INFO2
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 8/18
Algoritmo para recorrer la lista
• Recorrido a la Derecha • Recorrido a la Izquierda
P = top
repiteescribe(p->dato)
p = p->sig
hasta p = top->ant
P = top
repiteescribe(p->dato)
p = p->ant
hasta p = top->sig
Algoritmo para insertar
Antes de ‘x’ Después de ‘x’
p = top
lee(x)
repite
si p->dato = x entoncesq = new nodo
leer(q->dato)
si p = top entonces
top = q
q->sig = p
q->ant = p->ant
p->sig->ant = q
p->ant = q
p = top
en caso contrario
p = p->sig
hasta p = top
p = top
lee(x)
repite
si p->dato = xentonces
q = new nodo
leer(q->dato)
q->sig = p->sig
q->ant = p
p->sig->ant = q
p->sig = q
p = top
en caso contrario
p = p->sig
hasta p=top
Algoritmo para borrar un nodo
p = top
lee(valor_a_borrar)
repite
si p->dato = valor_a_borrar entonces
p->sig->ant = p->ant
p->ant->sig = p->sig
si p = top entonces
si p->sig = p->ant entonces
top = NULL
en caso contrario
top = top->sig
dispose(p)
p = top
en caso contrario
p = p->sig
hasta p = top
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 9/18
Algoritmos y Estructuras de Datos – Guía de Ejercicios LISTAS
1. Construya un algoritmo para crear una lista lineal que contenga valores numéricos entregados por pantalla.
2. Suponga que ya tiene creada la lista anterior, cree un algoritmo que entregue como resultado la suma totalde los números de los nodos y la cantidad de nodos en la lista.
3. Considere la lista que creó en el ejercicio 1, cree un algoritmo que entregue la suma total de los númerosmayores que 10 y la cantidad de números menores o iguales a 10 que contiene la lista.
4. Considere que tiene una lista lineal que contiene como dato el nombre del mes y la cantidad total de díasque posee:
............ nulo
Cree un algoritmo que recorra la lista anterior y cree una segunda lista sólo con aquellos meses quetengan 31 días.
5. Suponga que tiene una lista que contiene los alumnos que inscribieron la asignatura Informática II en la
primera inscripción de asignaturas. Luego del proceso de reinscripción se generó una segunda lista con losnuevos alumnos que se incorporaron al curso. Ambas listas contienen la misma información: el nombre delalumno y su rut. Cree un algoritmo que agregue al final de la lista inicial los alumnos que se incorporaron alcurso.
6. Suponga que tiene un listado de alumnos de un curso dividido en dos listas lineales. Una lista contienetodos los nombres de los hombres del curso ordenados en forma ascendente y, la otra lista contiene losnombres de las mujeres ordenado en forma ascendente. Escriba un algoritmo que genere una listaresultante con los nombres de todas las personas del curso (hombres y mujeres) ordenado en formaascendente.
7. Un Chef tiene todas los tipos de comidas y los ingredientes que estas contienen, almacenadas en unaestructura utilizando listas encadenadas de la siguiente forma:
Comida
Ingredientes
Suponga:
• La lista de comidas contiene el nombre de la comida, un link a la lista de sus ingredientes y un link a lasiguiente comida.
• La lista de ingredientes contiene el nombre del ingrediente, la cantidad necesaria y un link al siguienteingrediente.
• Una comida puede tiene al menos un ingrediente.
Se pide:
a. Defina formalmente las estructuras de datos necesarias para representar estas listas. (5 ptos).b. Al chef no le queda stock de ‘carne’. Escriba un algoritmo que calcule la cantidad de carne que
necesita comprar el chef para poder preparar todas sus comidas.(20 ptos)c. Calcule el orden del algoritmo. (5 ptos).
Enero 31 Febrero 28 Diciembre 31
Lomo Mignon Pavo Nogado
Champiñones 7 Carne 6 Tocino 1 Pavo 3 Nueces 1
Asado Alemán
Carne 9
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 10/18
8. En una empresa se tiene la información almacenada en listas enlazadas. La información del trabajador estáen una lista con la siguiente estructura:
struct nodo {char nombre[30];char cargo[20];int nro_cargas;struct nodo *link;
}
Además, existe una segunda lista que contiene para cada cargo el sueldo base correspondiente, con lasiguiente estructura:
struct nodo1 {char cargo[20];int sueldo_base;struct nodo *link;
}
a. Cree una tercera lista (nombre del trabajador, sueldo) con el sueldo de cada trabajador, si se sabeque:
sueldo = sueldo_base + nro_cargas*5000
b. Defina todas las estructuras de datos que ocupará.
Supuestos: La lista de trabajadores no está vacía.Todos los cargos aparecen en la lista de sueldo base por cargo (y no repetido).
9. En un colegio se tienen dos cursos de pre-kinder (A y B) cuyos alumnos se encuentran almacenados endos listas lineales que contienen el nombre del alumno y su edad en meses. Existe diferencia entre loscursos producto de que hay niños de edades muy diferentes que están juntos, por lo tanto, se ha decididoreestructurar los cursos de manera tal que en uno de ellos estén los alumnos de hasta 53 meses ( 41/2años) y en el otro los alumnos que tengan más de 53 meses. Se pide:
a) Escribir un algoritmo que genere dos listados (listas encadenadas) de los alumnos separados poredad. (Nota: considere que inicialmente tiene dos listas y debe entregar como resultado otras doslistas diferentes). (18 ptos.)
b) Calcular el orden de ejecución del algoritmo. (5 ptos.)
10. Se tiene una lista lineal doblemente encadenada que contiene números enteros positivos (>0):
a) Construya un algoritmo que elimine de la lista aquellos nodos que contengan números pares. (15ptos.)
La lista puede estar vacía y puede tener o no números pares.
b) Diga cual es el orden de ejecución del algoritmo y por qué. (6 ptos.)
11. Suponga que tiene un listado de “n” alumnos y su nota final almacenada en una estructura tipo listasimplemente encadenada:
c) Construya un algoritmo que calcule el promedio del curso y entregue la cantidad de alumnos connota menor a 4,0 y la cantidad de alumnos con nota mayor o igual a 4,0. (12 ptos.)
d) Especifique claramente la estructura del nodo de la lista. (3 ptos).e) Calcule el orden de ejecución del algoritmo (5 ptos.)
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 11/18
Algoritmos y Estructuras de Datos
3. Estructuras de datos en Memoria Principal
3.1.Tipo de Dato Abstracto Pila (Stack)
Las pilas son otro tipo de estructura de datos lineales, las cuales presentan restricciones en cuanto a laposición en la cual pueden realizarse las inserciones y las extracciones de elementos.
Una pila es una lista de elementos en la que se pueden insertar y eliminar elementos sólo por uno de los
extremos. Como consecuencia, los elementos de una pila serán eliminados en orden inverso al que se
insertaron. Es decir, el último elemento que se metió a la pila será el primero en salir de ella.
En la vida cotidiana existen muchos ejemplos de pilas, una pila de platos en una alacena, una pila de
latas en un supermercado, una pila de papeles sobre un escritorio, golosinas en una máquina de ventasautomáticas, etc.
Debido al orden en que se insertan y eliminan los elementos en una pila, también se le conoce comoestructura LIFO (Last In, First Out: último en entrar, primero en salir).
Representación en Memoria
Las pilas no son estructuras de datos fundamentales, es decir, no están definidas como tales en loslenguajes de programación. Las pilas pueden representarse mediante el uso de:
• Arreglos.
• Listas enlazadas.
• Pilas representadas mediante Arreglos
Se debe definir el tamaño máximo de la pila, además de un apuntador (tope: entero) que indica la cimao el tope de la pila, es decir, dónde se debe insertar el próximo elemento. La representación gráfica de
una pila es la siguiente:
Arreglo : tamaño máximo n=5
tope=1
DATO1
Al utilizar arreglos para implementar pilas, tenemos la limitante de espacio de memoria reservada. Unavez establecido un máximo de capacidad para la pila, ya no es posible insertar más elementos.
Inicialmente el tope debe estar en un extremo del arreglo. De acuerdo a esto existen dos formas deimplementar el arreglo: creciente hacia abajo o creciente hacia arriba:
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 12/18
0 ///////////// push pop 0
1 ///////////// 1
. .
. .
n-3 n-3
n-2 n-2 //////////////// push pop
n-1 n-1 //////////////// Creciente Creciente
hacia abajo hacia arribaPila vacia: tope = 0 Pila vacía: tope = n-1
Pila llena : tope = n Pila llena : tope = -1
Operaciones en Pilas
Tipo
Operación
Operación Dominio Codominio Especificación Descripción
Constructora InicPila Pila Pila *InicPila(void) Crea una pila vacía
Modificadora AdicPila Pila,
TipoP
Pila void AdicPila (Pila *p, TipoP
dato)
Inserta un elemento en el tope
de la pilaModificadora ElimPila Pila Pila void ElimPila (Pila *p) Suprime el elemento que está
en el tope de la pila
Analizadora InfoPila Pila TipoP TipoP InfoPila (Pila *p) Devuelve el elemento que
está en el tope de la pila
Analizadora VaciaPila Pila int int VaciaPila(Pila *p) Devuelve verdadero (1) si la
Pila está vacía y falso (0) en
caso contrario
Analizadora LlenaPila Pila int int LlenaPila(Pila *p) Regresa verdadero (1) si la
Pila está llena y falso (0) si
no lo está
Destructora DestruirPila Pila void DestruirPila(Pila *p)
Implementación de Pilas basadas en Arreglos
Para representar una Pila con arreglos es posible estructurarla como un registro de dos campos: un
arreglo para contener los datos de la pila y un campo para almacenar la posición del elemento superior
de la pila (llamado tope).
Suponga que se quiere implementar una pila de tamaño 30, para almacenar caracteres, entonces:
#include <stdio.h>#include <alloc.h>
#include <conio.h>
#define TAM 30#define TRUE 1
#define FALSE 0
typedef char TipoP;
typedef struct {
TipoP info[TAM];int tope;
}TPila;
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 13/18
TPila *InicPila( ){ TPila *p = (TPila *) malloc (sizeof(TPila));
p->tope = 0; /*Se tiene una pila vacía*/
return(p);}
int VaciaPila(TPila *p){ if (p->tope == 0) return(TRUE);
else return(FALSE);
}
int LlenaPila(TPila *p)
{ if (p->tope == TAM) return TRUE;
else return FALSE;}
void AdicPila(TPila *p, TipoP dato)
{ if (LlenaPila(p))printf("Error, Pila Llena\n");
else {
p->info[p->tope] = dato;p->tope++;
}
}
void ElimPila(TPila *p)
{ if (VaciaPila(p))printf ("Error, Pila Vacía\n");
else
p->tope--; /*Elimina el elemento del tope*/ }
TipoP InfoPila(TPila *p)
{ if (VaciaPila(p)){ printf ("Error, Pila Vacía\n");
return(0);}
elsereturn(p->info[p->tope-1]);
}
void DestruirPila(TPila *p)
{ free(p);
}
void main()
{ TipoP valor;
TPila *pp;char operacion;
int respuesta =1;
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 14/18
pp = InicPila();while(respuesta)
{
printf("Ingrese operacion: \n");printf(" 1: pila vacia\n");
printf(" 2: ingresa un elemento\n");
printf(" 3: devuelve el elemento del tope\n");printf(" 4: elimina un elemento\n");
printf(" 5: pila llena\n");
printf("Operacion: "); scanf("%c",&operacion);
getchar();switch(operacion) {
case '1':
printf("Esta vacia?(1:si; 0:no): %i \n", VaciaPila(pp));break;
case '2':
printf("ingrese elemento: ");
scanf("%c",&valor);getchar();
AdicPila(pp,valor);
break;case '3':
if(!VaciaPila(pp)) printf("El elemento del tope es %c \n", InfoPila(pp));
break;case '4':
ElimPila(pp);
break;case '5':
printf("Esta llena? (1:si; 0:no): %i \n", LlenaPila(pp));
break;}
printf("Desea ingresar otra operacion (0/1): ");
scanf("%i",&respuesta);
getchar();}
}
Ejercicios:
1.- Leer una secuencia arbitraria de caracteres e imprimirla en orden inverso.2.- Revisa paréntesis de una expresión matemática.
Ej. [[2+3]*5+ {(23*12)/(15-{2*4})}]
Solución:- Cada vez que encuentra un paréntesis abierto, lo guarda en la pila.
- Cuando encuentra un paréntesis cerrado saca el elemento del tope de la pila y los compara. Si son del
mismo tipo, continúa la revisión, si no, existe un error en la expresión.- Cuando termina de recorrer la cadena que contiene la expresión, la pila debe quedar vacía, si no,
existe error en la expresión.
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 15/18
Algoritmos y Estructuras de Datos
3. Estructuras de datos en Memoria Principal
3.2. Tipo de Dato Abstracto Fila o Cola FIFO
Las colas son otro tipo de estructura de datos lineales, las cuales presentan restricciones en cuanto a laposición en la cual pueden realizarse las inserciones y las extracciones de elementos.
Una cola es una lista de elementos en la que se insertan elementos por un extremo y se eliminan
elementos por el extremo opuesto. Como consecuencia, los elementos de una cola serán eliminados en
el mismo orden en que se insertaron. Es decir, el primer elemento que se metió a la cola será el primero
en salir de ella. En la vida cotidiana existen muchos ejemplos de colas, una cola para pagar cuentas enel banco, una cola de llamadas telefónicas en una central, una cola de impresión, etc.
Debido al orden en que se insertan y eliminan los elementos en una cola, también se le conoce como
estructura FIFO (First In, First Out: primero en entrar, primero en salir).
Representación en Memoria
Las colas no son estructuras de datos fundamentales, es decir, no están definidas como tales en los
lenguajes de programación. Las colas pueden representarse mediante el uso de :
• Arreglos.
• Listas enlazadas.
• Representación de colas mediante Arreglos
Existen tres métodos diferentes para representar una cola mediante arreglos:
Primer Método:
Se define un arreglo de tamaño máximo y un apuntador al frente de la cola (primer elemento) y uno alfinal de la cola (próximo espacio libre). Cada vez que se inserta un nuevo elemento se incrementa el
apuntador del final hasta que se llega al tamaño máximo más uno. Cada vez que se extrae un elemento
el apuntador al frente debe aumentar en uno hasta que frente es igual a final.
La representación gráfica de una cola es la siguiente:
Arreglo : tamaño máximo 4
0 A frente =0
1 B2 Final = 2
3
El problema con este tipo de representación es que si se inserta el tamaño máximo de elementos delarreglo, no se podrá seguir insertando aunque se hayan extraído elementos.
Ejemplo: Realice en forma gráfica la siguiente secuencia de operaciones: in(A), in(B), in(C), out(A),
in(D), out(B), out(C), in(E), in(F). Registre cada vez los valores de frente y final.
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 16/18
La cola está vacía si frente = final y la cola está llena si final = tam_max. En esta representación tantola inserción de elementos como la eliminación son de O(1).
Segundo Método:
Una forma de solucionar este problema es desplazar los datos hacia arriba cada vez que se extrae un
elemento. De esta forma el dato a extraer siempre estará en la primera posición del arreglo.
Ejemplo: Realice en forma gráfica la siguiente secuencia de operaciones: in(A), in(B), in(C), out(A),in(D), out(B), out(C), in(E), in(F). Registre cada vez los valores de frente y final.
El problema que surge con este método es que la inserción es de O(1) y la extracción se incrementa aO(n) por tener que hacer los corrimientos.
Tercer Método:
Este método consiste en implementar la cola utilizando un buffer circular, en este caso tanto la
inserción como la extracción de elementos se mantienen de O(1).
El apuntador frente siempre está en la posición donde se debe extraer el próximo elemento y el
apuntador final estará en la posición donde se debe insertar el próximo elemento, Si final está en la
posición del tamaño máximo del arreglo debe ser inicializado en el primer elemento del arreglo demanera de continuar circularmente, esto siempre y cuando frente no sea igual al primer elemento, en
cuyo caso la cola estará llena. El apuntador frente debe ser incrementado cada vez que se extrae un
elemento e inicializado en la primera posición del arreglo cuando se extraiga elemento de la últimaposición del arreglo, esto siempre y cuando frente sea distinto de final en cuyo caso la cola estará vacía.
El problema con esta representación es que la condición frente = final se aplica tanto para la cola llena
como para la cola vacía. Para solucionar esto se utiliza una variable para almacenar el número deelementos de la cola. Si la variable es igual a cero la cola está vacía, cuando la variable es igual al
tamaño máximo del arreglo la cola está llena.
Operaciones
Tipo
Operación
Operación Dominio Codominio Especificación Descripción
Constructora InicCola Cola Cola*InicCola(void) Crea una cola vacía
Modificadora AdicCola Cola,
TipoC
Cola void AdicCola (Cola *p,
TipoC dato)
Inserta un elemento en el final de
la cola
Modificadora ElimCola Cola Cola void ElimCola (Cola *c) Suprime el elemento que está en
el frente de la cola
Analizadora InfoCola Cola TipoC TipoC InfoCola (Cola *c) Devuelve el elemento que está
en el frente de la cola
Analizadora VaciaCola Cola int int VaciaCola(Cola *c) Devuelve verdadero (1) si la cola
está vacía y falso (0) en caso
contrario
Analizadora LlenaCola Cola int int LlenaCola(Cola *c) Regresa verdadero (1) si la cola
está llena y falso (0) si no lo está
Destructora DestruirCola Cola void DestruirCola(Cola *c) Libera la memoria
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 17/18
Implementación de Colas basadas en Arreglos
A continuación se muestra la estructura de datos y funciones para representar una cola de enteros de
tamaño 20, por el método 1:
#include <stdio.h>
#include <alloc.h>#include <conio.h>
#define TAM 20
#define TRUE 1#define FALSO 0
typedef int TipoC;
typedef struct {
TipoC info[TAM];
int frente, final;
}TCola;
TCola *InicCola()
{ TCola *c = (TCola *) malloc (sizeof(TCola));c->final = 0;
c->frente = 0;
return(c);}
int VaciaCola(TCola *c)
{ if ((c->final == c->frente))return(TRUE);
else
return(FALSE);}
int LlenaCola(TCola *c)
{ if ((c->final == TAM))
return(TRUE);else
return(FALSE);
}TipoC InfoCola(TCola *c)
{ if (!VaciaCola(c))
return (c->info[c->frente]);}
void AdicCola(TCola *c, TipoC dato)
{ if (!LlenaCola( *c))
c->info[c->final++] = dato;}
void ElimCola(TCola *c){
if (!VaciaCola(c))c->frente++;
}
5/15/2018 Conceptos b sicos de Listas, Pila y colas. - slidepdf.com
http://slidepdf.com/reader/full/conceptos-basicos-de-listas-pila-y-colas 18/18
La estructura de datos y funciones para representar las colas por el método 2 se muestran acontinuación:
#include <stdio.h>#include <alloc.h>
#include <conio.h>
#define TAM 20#define TRUE 1
#define FALSO 0
typedef int TipoC;
typedef struct {
TipoC info[TAM];
int frente, final;}TCola;
TCola *InicCola()
{ TCola *c = (TCola *) malloc (sizeof(TCola));c->final = 0;
c->frente = 0;
return(c);}
int VaciaCola(TCola *c){
if ((c->final == 0))return(TRUE);
else
return(FALSE);}
int LlenaCola(TCola *c)
{ if ((c->final == TAM))return(TRUE);
else
return(FALSE);
}TipoC InfoCola(TCola *c)
{ if (!VaciaCola(c))
return (c.elementos[c.frente]);}
void AdicCola(TCola *c, TipoC dato)
{ if (!LlenaCola(c))c->info[c->final++] = dato;
}
void ElimCola(TCola *c)
{ int i=0;if (!VaciaCola(c))
{ while (i < c->final-1)
c->info[i] = c->info[i+1];c->final--; }
}