02/10/2015
Ing. Edgar Ruiz Lizama
1
EL TAD LISTA
El Tipo Abstracto de Datos LISTA es un estructura de datos básica
que permite crear, insertar, modificar, buscar y eliminar datos o
registros a una lista. Una lista en esencia es una secuencia de datos
sucesivos.
a1 , a 2 , a 3 ,  , a n
Donde el primer elemento es a1 y el último es an. Adicionalmente su
tamaño es n. Una lista es finita y además es flexible porque puede
crecer y acortarse a voluntad.
02/10/2015
Ing. Edgar Ruiz Lizama
2
inicio
pollo
4.50
carne
7.90
arroz
1.60
NULL
El gráfico muestra una lista enlazada con tres elementos o nodos
donde cada nodo tiene tres componentes: un campo que es una
cadena de caracteres, un campo que es un flotante y un tercer
campo que es una dirección o link para el siguiente nodo.
La lista gráfico puede declararse como sigue:
struct listaNodo{
char articulo[15];
float precio;
struct listaNodo *sig; // es recursiva
}
typedef listaNodo *inicio;
inicio -> articulo = strcpy(“pollo”,”papas”);
inicio -> precio = 0.80;
02/10/2015
Ing. Edgar Ruiz Lizama
3
Operaciones básicas con el TDA LISTA
1) Crear nodo.
2) Insertar nodo.
3) Eliminar nodo.
4) Buscar.
5) Recorrer nodo.
6) Lista vacía.
Crear Nodo
Al construir una lista enlazada lo primero que debe hacerse
es crear una lista vacia. Esto se logra estableciendo el primer
nodo a NULL.
Algoritmo crearLista()
{
inicio=NULL;
}
02/10/2015
Ing. Edgar Ruiz Lizama
4
Insertar Nodo
Para adicionar un nodo al TAD lista se hará al comienzo de la
lista (puede hacerse en cualquier lugar). Los pasos a seguir
son:
1) Crear un nuevo nodo.
2) Llenar el nodo con los datos que se va ha almacenar.
3) Hacer que el nuevo nodo apunte al primer nodo de la lista.
4) Hacer que el primer nodo puente al nuevo nodo.
Ejemplo grafico:
Sea la lista de enteros 5, 15 y se desea insertar el entero 10.
inicio
5
15
NULL
02/10/2015
Ing. Edgar Ruiz Lizama
5
1) Crear nuevo nodo.
P
Nuevo
NULL
//P es un apuntador
temporal a la lista de
Nodos.
2) Llenar el nodo.
P
Nuevo
10
NULL
3)
inicio
5
15
NULL
P
10
Nuevo
02/10/2015
Ing. Edgar Ruiz Lizama
6
4)
inicio
5
15
NULL
P
10
Nuevo
Los 4 pasos anteriores se resumen en el siguiente pseudocódigo
Algoritmo Insertar Nodo
{
p = new Nodo
info(p) = Elemento de datos a insertar
sig(p) = inicio
inicio = p
}
02/10/2015
Ing. Edgar Ruiz Lizama
7
La clase básica es la siguiente:
struct Nodo {
int info;
Nodo *sig;
};
class Lista {
Nodo *inicio;
public:
Lista();
~Lista();
void insertarNodo(int dato);
void eliminarNodo(int dato);
void recorrerLista();
int listaVacia();
}
02/10/2015
Ing. Edgar Ruiz Lizama
8
// el constructor de la lista
Lista :: Lista()
{
inicio = NULL;
}
// destructor de la lista
Lista :: ~Lista()
{
Nodo *p;
Nodo *temp;
p = inicio;
while(p != NULL) /*eliminar nodo a nodo */
{
temp = p -> sig;
delete p;
p = temp;
}
}
02/10/2015
Ing. Edgar Ruiz Lizama
9
// operación insertar nodo
void Lista :: insertarNodo(int dato)
{
Nodo *p;
p = new Nodo;
// paso 1
p -> info = dato;
// paso 2
p -> sig = inicio;
// paso 3
inicio = p;
// paso 4
}
02/10/2015
Ing. Edgar Ruiz Lizama
10
Nam e>
Operación eliminar Nodo
El algoritmo básico es el siguiente:
EliminarNodo
{
Buscar en la lista el elemento a eliminar.
Ajusta los punteros de la lista para eliminar el nodo que
contenga el elemento que se va a eliminar.
}
Como puede ver; antes de eliminar se debe de buscar.
N o d o q u e s e v e r ific a
a n tP
02/10/2015
P
Ing. Edgar Ruiz Lizama
11
La búsqueda de un elemento se realiza Nodo a Nodo, de principio
a fin, es decir, es secuencial.
El algoritmo para buscar es el siguiente:
Buscar
{
}
if lista vacia
escribir(“lista vacia...”)
else
// Ubicarse al comienzo de la lista
p = inicio
antp = NULL
encuentra = false //encuentra es una bandera
while(NOT encuentra AND p != NULL)
{
if info(p) == dato
encuentra = true
else
{
//continuar busqueda
antp = p
p = sig(p)
}
}
02/10/2015
Ing. Edgar Ruiz Lizama
12
Después de utilizar el algoritmo de la búsqueda, se usan los
valores de encuentra p y antp para proceder a eliminar el nodo
requerido.
El algoritmo es el siguiente:
Eliminar
{
if(encuentra)
{
if(antp == NULL) //caso del 1er nodo
inicio = sig(p)
else
sig(antp) = sig(p) //eliminacion
}
else
escribir(“No se encuentra en la lista...”)
}
Ahora se puede ajustar la búsqueda con eliminar para escribir un
solo algoritmo: Eliminar Nodo.
02/10/2015
Ing. Edgar Ruiz Lizama
13
El algoritmo básico es el siguiente:
EliminarNodo
{
Buscar en la lista el elemento a eliminar.
Ajusta los punteros de la lista para eliminar el nodo que
contenga el elemento que se va a eliminar.
}
Como puede verse, antes de eliminar se debe de buscar.
sig(antp)=sig(p)
ant P
02/10/2015
P
Ing. Edgar Ruiz Lizama
14
El algoritmo básico es el siguiente:
Algoritmo EliminarNodo
{
Algoritmo Buscar
Algoritmo Eliminar
}
El código:
// Operación EliminarNodo()
void Lista :: eliminarNodo(int dato)
{
int encuentra = false;
Nodo *p, *antP;
p = inicio;
antP = NULL;
02/10/2015
Ing. Edgar Ruiz Lizama
15
// buscar elemento a eliminar
if( listaVacia() )
cout<<“Lista vacia!…”<<endl;
else
{
while(!encuentra && p!=NULL)
{
if (p -> info == dato)
encuentra = true;
else
{
antP = p;
p = p-> sig;
}
}
//eliminar nodo si se encuentra
if(encuentra)
{
if(antP == NULL)
{
inicio = p-> sig;
delete p;
}
else
{
antP -> sig = p -> sig;
delete p;
}
}
else
cout<<“El dato”<<dato<<“no se encuentra”<<endl;
} // fin de 1er if
}
02/10/2015
Ing. Edgar Ruiz Lizama
16
Recorrer Lista
El recorrido de la lista es secuencial y se realiza de prinicipio a
fin. El objetivo del recorrido es visitar cada nodo y enviar su(s)
dato(s) hacia el flujo de salida. El seudocódigo es:
RecorrerLista
{
if(lista No vacia)
{
p = inicio
while( p !== NULL)
{
mostrar info(p)
p= sig(p) //ir al siguiente nodo
}
}
else
escribir (“Lista vacia”)
}
02/10/2015
Ing. Edgar Ruiz Lizama
17
El código
// Operación recorrer lista()
void Lista :: recorrerLista()
{
Nodo *p;
p = inicio;
if(!listaVacia())
{
while(p!=NULL)
{
cout<<p -> info<<“-> “;
p = p -> sig;
}
cout<<“NULO”<<endl;
}
else
cout<<“lista Vacia…!”<<endl;
}
02/10/2015
Ing. Edgar Ruiz Lizama
18
Lista Vacía
Consiste en averiguar si la lista tiene o no elementos. Para ello
se devuelve un valor booleano.
Lista Vacia
{
if (inicio = NULL)
return TRUE
else
return FALSE
}
// código operación listaVacia()
int lista :: listaVacia()
{
if (inicio == NULL)
return true;
else
return false;
}
02/10/2015
Ing. Edgar Ruiz Lizama
19
02/10/2015
Ing. Edgar Ruiz Lizama
20
EL TAD PILA
( STACK)
Una pila es una versión restringida de una lista
enlazada. A una pila se le pueden añadir y retirar nodos
únicamente por su extremo superior. Por esta razón el TDA
Pila se le conoce como estructura de datos del tipo LIFO
(Last In First Out) esto quiere decir; último en entrar,
primero en salir. Una pila se referencia mediante un
apuntador al extremo superior de la misma. El último nodo
de la pila se define a NULL para indicar que se trata del
último elemento de la estructura (parte inferior de la pila).
02/10/2015
Ing. Edgar Ruiz Lizama
21
Representación Gráfica
Sea el ingreso de cadena de caracteres “AMOR” los
cuales se almacenan uno a uno en una pila.
TOP
R
A
O
Para sacar los
caracteres de la
pila, se hacen uno
a uno
M
A
PILA
M
O
R
INVERTIR
PILA
Mediante listas enlazadas se tiene
TOP
R
O
M
A
NULL
02/10/2015
Ing. Edgar Ruiz Lizama
22
Al puntero al extremo superior de la pila se le denomina también
cima o tope
Operaciones Básicas en una pila
1.
2.
3.
4.
Operación Push o Apilar
Operación Pop o Desapilar
Operación Pila Vacía o Empty
Operación Stacktop
02/10/2015
Ing. Edgar Ruiz Lizama
23
Operaciones Básicas
1 Operación Push o Apilar. Significa ingresar un nuevo nodo a la
pila. Esto se realiza por el extremo superior o tope.
Ejm: Insertar el carácter “I” a la pila del gráfico: push (p, carácter)
TOP
R
O
M
NULL
I
02/10/2015
A
Ing. Edgar Ruiz Lizama
24
2 Operación Pop o Desapilar. Significa retirar un nodo de la
pila. Esto se realiza también por el extremo superior o tope.
Ejm: Retirar un nodo de la pila anterior: pop(p)
TOP
I
R
O
M
A
NULL
02/10/2015
Ing. Edgar Ruiz Lizama
25
Operaciones Básicas
3 Operación Pila Vacía o Empty. La operación empty(p) devuelve
un valor de verdad si la pila p está vacía o no. La operación push se
puede aplicar a cualquier pila, pero la operación pop no puede
aplicarse a una pila vacía pues no habrían elementos que remover.
El intento de aplicar pop a una pila vacía ocasiona un error
conocido como “underflow” o “bajo flujo” por ello antes de hacer
pop a una pila se debe verificar si ella está vacía o no.
4 Operación Stacktop. Permite averiguar que elemento está en la
parte superior de la pila sin removerlo. La operación stacktop(p)
consta de dos operaciones en secuencia:
1. Pop(p) y
2. Push(p,i).
02/10/2015
Ing. Edgar Ruiz Lizama
26
Esto se resume en lo siguiente:
i = stacktop(p);
lo cual equivale a hacer las dos lineas siguientes:
i = pop (p);
push(p,i);
Al igual que con pop, la operación stacktop también debe evitar el
subdesbordamiento o underflow.
02/10/2015
Ing. Edgar Ruiz Lizama
27
IMPLEMENTACION DEL TDA PILA
• La implementación del TAD pila se
puede hacer con:
1) Arreglos
2) Listas enlazadas
Programa que utiliza una clase llamada stack para almacenar
caracteres en un arreglo.
#include<iostream.h>
#include<stdlib.h>
const int TAM = 10;
02/10/2015
Ing. Edgar Ruiz Lizama
28
// declaración de la clase stack
class stack {
char stck[TAM]; //array para guardar caracteres
int icp; //indice a la cabeza o tope de la pila
public:
void inicio();
// inicializa o crea la pila
void push(char ch);
// meter o insertar carácter
char pop();
// retirar carácter
};
// inicializar la pila
void stack :: inicio()
{
icp = 0;
}
// Operación push
void stack :: push(char ch)
{
if (icp == TAM)
{
cout<<“Pila llena… overflow”<<endl;
return; //también puede usar exit(1)
}
stck[icp] = ch;
icp++;
} 02/10/2015
Ing. Edgar Ruiz Lizama
29
// operación pop
char stack::pop()
{
if(icp == 0)
{
cout<<“Pila vacía… Underflow”<<endl;
return 0; //devulve nulo
}
icp--;
return stck[icp];
}
// funcion principal
int main() //pila1.cpp
{
stack p1,p2; //llenar dos pilas
int i;
// inicializar p1 y p2
p1.inicio(); p1.inicio();
// insertando caracteres
a
a
p1.push(‘p’); p2.push(‘a’);
m
p
p1.push(‘p’); p2.push(‘a’);
p1.push(‘m’); p2.push(‘a’);
a
a
p1.push(‘m’); p2.push(‘a’);
m
p
p1
02/10/2015
Ing. Edgar Ruiz Lizama
p2
30
// sacar de pila
// para p1
for (i = 0; i < 4; i++)
cout<<“pila1: ”<<p1.pop()<<endl;
cout<<endl;
//para p2
for (i = 0; i < 4; i++)
cout<<“pila2: ”<<p2.pop()<<endl;
cout<<endl;
system(“PAUSE”);
}
02/10/2015
Ing. Edgar Ruiz Lizama
31
IMPLEMENTACIÓN DEL TAD PILA
MEDIANTE UNA LISTA ENLAZADA
La declaracion básica es:
struct pilaNodo {
int numero;
struct pilaNodo *sig;
}
typedef struct pilaNodo PILANODO;
tipedef PILANODO *PILANODO; // puntero a PILANODO
02/10/2015
Ing. Edgar Ruiz Lizama
32
Operación Push.
Representación gráfica.- Sea la pila con datos: 11, 7. Se desea insertar el 5.
FASE 1
*c im a P tr
7
11
NULL
*n e w P tr
5
NULL
02/10/2015
Ing. Edgar Ruiz Lizama
33
FASE 2
*cim aP tr
7
11
NULL
*new P tr
5
02/10/2015
Ing. Edgar Ruiz Lizama
34
El código de la operación push
void push(PILANODOPTR *cimaPtr, int info)
{
PILANODOPTR newPtr; // declarar nuevo nodo
newPtr = newPILANODO; /* asignar memoria dinamica al nuevo
nodo */
if(newPtr != NULL)
{ newPtr -> numero = info; //guardar info en nuevo nodo (a)
newPtr -> sig = *cimaPtr; // (b)
*cimaPtr = newPtr; //(c)
}
else
cout<<info<<“no insertado, no hay memoria disponible”
<<endl;
}
02/10/2015
Ing. Edgar Ruiz Lizama
35
Operación Pop.
Representación gráfica.- Hacer pop a la pila anterior.
*c im a P tr
F a s e in ic ia l
5
7
11
NULL
*c im a P tr
(a )
5
7
11
NULL
*te m p P tr
02/10/2015
Ing. Edgar Ruiz Lizama
36
El código de Pop
int pop(PILANODOPTR *cimaPtr)
{
PILANODOPTR tempPtr; // crear puntero temporal
int popValor; // variable que almacena el entero a retirar
tempPtr = *cimaPtr; //(a)
popValor = (*cimaPtr) -> numero; //valor a retirar
*cimaPtr = (*cimaPtr) -> sig;
delete(tempPtr);
return popValor;
}
int esVacia(PILANODOPTR *cimaPtr)
{
if(cimaPtr == NULL)
return true;
else
return false;
}
02/10/2015
Ing. Edgar Ruiz Lizama
37
APLICACIONES PRACTICAS DEL TAD
PILA
En computación son diversos las aplicaciones del TDA Pila.
1) Validación de expresiones.
2) Evaluación de expresiones en sus formas: infija, prefija y
posfija.
3) Modelación de la memoria por parte del sistema operativo.
4) Eliminar la recursividad para lograr una versión iterativa de
algunos algoritmos recursivos.
02/10/2015
Ing. Edgar Ruiz Lizama
38
ALGORITMO DE LA PILA
PARA COMPROBAR SIGNOS DE COLECCION
Antes de evaluar una expresión, el compilador debe examinar
si dicha expresión es válida o no. Para hacerlo procede a
analizar los símbolos de colección como {, }, [, ], ( y ) o
similares.
Sea la expresión:
7-((x*((x+y)/(5-3))+y)/(4-2.5))
02/10/2015
Ing. Edgar Ruiz Lizama
39
Para comprobar si dicha expresión es correcta se realiza lo
siguiente:
1) Averiguar si hay la misma cantidad de paréntesis izquierdos y
derechos.
2) Cada paréntesis derecho esta precedido por un paréntesis
izquierdo.
Volviendo a la expresión:
7 - ( ( x * ( ( x + y ) / ( 5 - 3 ) ) + y ) / ( 4 - 2.5 ) )
0 0 122 2 34 4 4 4 3344 4 43 2 2 21 1 2 2 2 2 1 0
contador = 0
Por lo que la expresión es correcta!.
02/10/2015
Ing. Edgar Ruiz Lizama
40
Pseudocódigo para el algoritmo
Examinar expresion
{ valido = TRUE // supone que la cadena es válida
s = pila vacia
while( no hayamos leido toda la cadena)
{
leer el siguiente simbolo de la cadena
if(simbolo ==‘(‘or simbolo==‘[‘or simbolo==‘{‘)
push(s,simbolo)
if(simbolo ==‘)‘or simbolo==‘]‘or simbolo==‘}‘)
{
if(empty(s)
valido = FALSE
else
{
i = pop(s)
if( i no es el correspondiente simbolo que
abre a simbolo)
valido = FALSE
}
}
}
if(!empty(s))
valido = FALSE
if(valido)
cout<<“Expresion correcta”<<endl;
else
cout<<“Expresion incorrecta”<<endl;
}
02/10/2015
Ing. Edgar Ruiz Lizama
41
NOTACION POLACA o REVERSE POLISH NORM (RPN)
La expresión en posfija se le conoce como Notación Polaca o
Reverse Polish Norm (RPN).
El algoritmo para evaluar expresiones posfija, consiste en lo
siguiente:
Cada operador en una cadena posfija hace referencia a los dos
operandos anteriores de la cadena. Suponga que cada vez que se lee
un operando lo agregamos a la pila, cuando se llega a un operador,
los operandos serán los dos elementos superiores de la pila.
Después se remueve estos dos elementos, se ejecuta la operación
indicada sobre ellos y se agrega el resultado a la pila para que esté
disponible como operando del operador siguiente.
02/10/2015
Ing. Edgar Ruiz Lizama
42
Pseudocódigo
Algoritmo RPN
{
Opndstk = la pila vacia
// explora la cadena leyendo un elemento cada vez hacia simbolo
while(no sea fin de la cadena)
{
simbolo = siguiente carácter en la entrada
if(simbolo es un operando)
push(opndstk,simbolo)
else
{
//simbolo es un operador
opnd2 = pop(opndstk)
opnd1 = pop(opndstk)
valor = resultado de aplicar a opnd1 y opnd2
push(opndstk,valor)
}
}
return (pop(opndstk));
}
02/10/2015
Ing. Edgar Ruiz Lizama
43
Ejemplo:
Solución
Evaluar la expresión posfija utilizando el algoritmo
anterior.
623+-382/+*2^3+
simbolo
6
2
3
+
3
8
2
/
+
*
2
^
3
+
02/10/2015
oprid1
oprid2
valor
2
6
6
6
6
8
3
1
1
7
7
49
3
5
5
5
5
2
4
7
7
2
2
3
5
1
1
1
1
4
7
7
7
49
49
52
Ing. Edgar Ruiz Lizama
pila
opridstk
6
6,2
6,2,3
6,5
1
1,3
1,3,8
1,3,8,2
1,3,4
1,7
7
7,2
49
49,3
52
44
Puede realizarse el cambio de notación en las expresiones. Por
ejemplo, si se quiere cambiar A+B/C a su forma posfija, se debe
tener en cuenta la precedencia de los operadores. En el cado de + y /
se ejecuta primero / (en ausencia de paréntesis).
Infija
A+B/C
Posfija
A+(B/C)
A+(BC/)
A(BC/)+
ABC/+
Comentario
Se añaden paréntesis.
Se pasa a posfija dentro del paréntesis.
El paréntesis y su contenido se tratan como un operando.
Se eliminan los paréntesis.
Si la expresión es (A+B)/C se tiene
Infija
(A+B)/C
02/10/2015
Posfija
(A+B)/C
(AB+)/C
(AB+)C/
AB+C/
Comentario
Pasando a posfija dentro del paréntesis.
tomando el paréntesis como un operando y pasando a posfija.
Quitando paréntesis.
Ing. Edgar Ruiz Lizama
45
REGLA
Cuando se examina operadores de la misma procedencia, se supone
que el orden es de izquierda a derecha, excepto en el caso de la
exponenciación en donde el orden se de derecha a izquierda. Por lo
que A+B+C significa (A+B)+C, en tanto que A^B ^C significa A
^(B ^C). Observe que el uso de paréntesis ayuda a eliminar la
precedencia predeterminada.
02/10/2015
Ing. Edgar Ruiz Lizama
46
02/10/2015
Ing. Edgar Ruiz Lizama
47
EL TAD COLA
Una cola es un caso especial de una lista, donde sólo se
permite la inserción de elementos al final y la eliminación
(sacar elementos de la cola) se realiza únicamente por el frente.
A las colas también se les conoce como estructuras dinámicas
de datos del tipo “primero en entrar, primero en salir” FIFO
(First In First Out).
02/10/2015
Ing. Edgar Ruiz Lizama
48
Representación Gráfica del TAD COLA
*colaPtr
*cabezaPtr
P
A
J
NULL
Operaciones en una COLA
Las operaciones básicas definidas para la cola son:
1) Frente o front.- Averiguar por el elemento que está al
frente.
2.) Poner en cola o encolar (enqueue); es decir colocar
elemento al final.
3) Sacar de cola o desencolar (dequeue); es decir sacar el
elemento que está al frente.
4) Cola vacía o empty.
02/10/2015
Ing. Edgar Ruiz Lizama
49
Aplicación práctica
Preparar un programa
caracteres alfabéticos
básicas de una cola:
verificar si la cola está
actual.
que permita manipular una cola de
y permita realizar las operaciones
enqueue y dequeue; además, debe
o no vacía e imprimir siempre la cola
Declaración de la cola
La declaración de la cola de caracteres es la siguiente:
struct colaNodo { /* es recursiva; se referencia asi misma */
char letra;
struct colaNodo *nextPtr;
};
typedef struct colaNodo COLANODO;
typedef COLANODO *COLANODOPTR;
02/10/2015
Ing. Edgar Ruiz Lizama
50
Operación poner en cola; enqueue o encolar
Supóngase que se tienen en cola los caracteres P, A, N y se
quiere poner en la cola el carácter S. Esta situación se
representa gráficamente como:
*cabezaPtr
*colaPtr
*newPtr
N
S
(a)
P
A
NULL
*cabezaPtr
NULL
*colaPtr
*newPtr
N
S
(b)
P
A
NULL
02/10/2015
Ing. Edgar Ruiz Lizama
51
El código para la operación enqueue es:
/* Insertar un carácter en la cola */
void encolar(COLANODOPTR * cabezaPtr, COLANODOPTR *colaPtr, char carac)
{
COLANODOPTR newPtr;
// newPtr = new COLANODO;
if(newPtr != NULL)
{
/*hay espacio disponible */
newPtr -> letra = carac;
newPtr -> nextPtr = NULL;
if(esVacia(*cabezaPtr))
*cabezaPtr = newPtr;
else
*colaPtr -> nextPtr = newPtr;
*colaPtr = newPtr;
}
else
cout<<carac<<“no insertado,no hay memoria disponible”<<endl;
}
02/10/2015
Ing. Edgar Ruiz Lizama
52
Operación sacar de cola; dequeue o desencolar
Supóngase ahora que se quiere sacar un elemento de la cola
actual P, A, N, S; el carácter que sale es P. Esta situación se
representa en la figura siguiente:
*cabezaPtr
*colaPtr
(a)
P
A
N
S
NULL
*cabezaPtr
*colaPtr
(b)
*tempPtr
P
A
N
S
NULL
02/10/2015
Ing. Edgar Ruiz Lizama
53
El código para la operación dequeue es:
/* Borrar un elemento de la cola */
char desencolar(COLANODOPTR *cabezaPtr, COLANODOPTR *colaPtr)
{
char carac;
COLANODOPTR tempPtr;
carac = (*cabezaPtr) -> letra;
tempPtr = *cabezaPtr;
*cabezaPtr = (*cabezaPtr) -> nextPtr;
if(*cabezaPtr == NULL)
*colaPtr = NULL;
delete tempPtr;
return carac;
}
02/10/2015
Ing. Edgar Ruiz Lizama
54
EL TAD COLA COMO UN ARREGLO
El TAD COLA puede implementarse como un arreglo donde la
variable front contiene la posición dentro del arreglo para el
elemento primero o inicial de la cola y la variable rear para el
último elemento del arreglo.
Sea una cola q de enteros la cual se declara como:
Const int MAXCOLA = 100;
struct queue {
int items[MAXCOLA];
int front, rear; // indices
};
struct queue q; // cola q
q.front = q.rear = MAXCOLA-1;
02/10/2015
Ing. Edgar Ruiz Lizama
55
q.items
4
3
2
Q.front = q.rear = 4
1
0
Debido a que q.front y q.rear “apunten” a MAXCOLA - 1 la cola
esta vacía al comienzo.
La función empty se codifica como sigue:
int empty(struct queue *pq)
{
return((pq -> front == q -> rear)?true:false);
}
02/10/2015
Ing. Edgar Ruiz Lizama
56
Una vez definida la función empty se puede probar con el
siguiente bloque.
if(empty(pq))
/* cola vacia */
else
/* cola no vacia */
La operación remove (q) remueve el elemento al frente de la cola
y se codifica como:
int remove(struct queue *pq)
{
if(empty(pq))
{
cout<<“cola underflow!…”<<endl;
exit(1);
}
if(pq -> front == MAXCOLA - 1)
pq -> front = 0;
else
(pq -> front)++;
return(pq -> items[pq -> front]);
}
02/10/2015
Ing. Edgar Ruiz Lizama
57
La operación insert(q,x) o enqueue permite insertar un elemento
al final de la cola. Se codifica como:
void insert(struct queue *pq, int x)
{
/* hacer espacio para un elemento nuevo */
if(pq -> rear ==MAXCOLA - 1)
pq -> rear = 0;
else
(pq -> rear)++;
// comprobar que no hay desbordamiento
if(pq -> rear == pq -> front)
{
cout<<“cola en overflow!…”<<endl;
exit(1);
}
pq -> items[pq -> rear] = x;
}
02/10/2015
Ing. Edgar Ruiz Lizama
58
REFERENCIAS
STAGUAARD, ANDREW “Técnicas Estructuradas y Orientadas a
Objetos: Una Introducción utilizando C++". Editorial Prentice Hall
Hispanoamericana. México, 1998.
LANGSAM, AUGENSTEIN, TENENBAUM “Estructuras de Datos con
C/C++” Editorial Prentice-Hall Hispanoamericana. México 1996.
H.M. DEITEL y P.J. DEITEL “Como Programar en C++” 4ta Ed. Editorial
Prentice-Hall Hispanoamericana, México 2003.
CAIRO OSVALDO y GUARDATI SILVIA “Estructura de Datos” 2da.
Ed. Editorial McGraw Hill. México 2002.
JOYANES AGUILAR, LUIS "Programación en C++: Algoritmos y
Estructura de Datos" 1ra. Ed. Editorial McGraw Hill. Madrid, 2002.
RUIZ LIZAMA EDGAR “Curso de Lenguaje C” Facultad de Ingeniería
Industrial UNMSM. Lima 1999.
02/10/2015
Ing. Edgar Ruiz Lizama
59
Descargar

Listas en Cpp - eruizl professor