contenido definición y operaciones implementación estática...
TRANSCRIPT
1
Estructura de DatosTema 1: Pilas
Presenta: David Martínez Torres
Universidad Tecnológica de la Mixteca
Instituto de Computación
Oficina No. 37
1
Contenido
1. Definición y operaciones
2. Implementación estática
3. Implementación dinámica
4. Casos de estudio
2
2
1. Definición y operaciones
Una Pila es una colección ordenada de elementos en la que se pueden insertar y suprimir por un extremo, llamado tope.
Por tal razón se conoce como una estructura de datos LIFO (last-in, first-out)
3
Operaciones básicas
Insertar elementos a la pila push(pila,elemento);
Eliminar elementos de la pila elemento=pop(pila);
Determinar si la pila esta vacía bandera=vacia(pila);
Determinar si la pila está llena bandera=llena(pila);
push(s,H);
push(s,I);
push(s,J);
pop(s);
pop(s);
push(s,K);
pop(s);
pop(s);
push(s,G);
4
3
Aplicaciones usando pilas
Apilar libros, CD’s.
Problema de torres de Hanoi, sistema de estacionamiento
Leer una secuencia de caracteres desde teclado e imprimirlos al revés
Expresión matemática que contenga paréntesis anidados correctamente.
Convertir expresiones de notación infija a prefija, a postfija y viceversa.
5
2. Implementación estática
Representación estática: Usando arreglos
6
4
Representación estática: Usando arreglos. Ej 1
#define TAM 100
typedef struct{
int tope;
int elementos[TAM];
}tipoPila;
7
Ejemplo de implementación estática
#define TAM 100
typedef struct{
int tope;
int elementos[TAM];
}tipoPila;
void push (tipoPila *pila, int dato);
int pop (tipoPila * pila);
int main(){
tipoPila pila={-1,{0}};
…
} 8
5
Ejemplo de implementación estática
void push (tipoPila *pilaT, int dato){
(pilaT->tope)++;
pila->elementos[pilaT->tope]=dato;
}
int pop (tipoPila * pilaT){
int dato;
dato=pila->elementos[pilaT->tope];
pilaT->tope--;
return dato;
}9
Ejemplo de implementación estática
int llena(tipoPila pila){
int bandera=0;
if (pila.tope==TAM-1)
bandera = 1;
return bandera;
}
10
6
Ejemplo de implementación estática
int vacia(tipoPila pila) {
int bandera=0;
if (pila.tope==-1)
bandera = 1;
return bandera;
}
11
Pilas estáticas
Ejercicio. Realizar la implementación de un estacionamiento. Debe contener un menú de opciones y cobrar $10 por hora
Considere el siguiente diseño de la estructura de datos.
12
7
13
3. Implementación dinámica de Pilas
Estructuras de datos que se adapten a las necesidades reales
Estructuras muy flexibles, ya sea en cuanto al orden, espacio (reservación dinámica de memoria)
Están compuestas de otras pequeñas estructuras a las que llamaremos nodos o elementos, donde cada nodo contiene:
Los datos reales
Uno o más punteros autoreferenciales
3. Implementación dinámica de Pilas
dato sig
Definición de tipo recursivo-
permitido en Ctypedef struct pila {
int dato; struct pila * sig;
}tipoPila;
typedef tipoPila * tipoPilaPtr;
Estructura básica de un nodo para cualquier estructura dinámica sería:
14
8
15
3. Implementacion dinámica
Visualización Gráfica:
tope
2 3
8 2 3
tope
3
tope
tope
Insertar a la pila vacía, el 3, 2 y 8.
typedef struct pila { int dato; struct pila * sig;
}tipoPila;
typedef tipoPila * tipoPilaPtr;
int main(){tipoPilaPtr tope=NULL;…
16
Insertar elementos a la pila
nuevo
dato sig
NULL
tope
5 NULL
void insertar(tipoPilaPtr *tope, int dato){tipoPilaPtr nuevo;//reservar memorianuevo=(tipoPilaPtr) malloc (sizeof(tipoPila));if(nuevo==NULL)
printf(“No hay memoria”);else {
nuevo->dato=dato;
nuevo->sig=*tope;*tope=nuevo;}
}
typedef struct pila { int dato; struct pila * sig;
}tipoPila;
typedef tipoPila * tipoPilaPtr;void insertar(tipoPilaPtr *tope, int dato);
int main(){tipoPilaPtr tope=NULL;…}
9
Eliminar un elemento
int eliminar(tipoPilaPtr *tope){
tipoPilaPtr temp;
int num;
temp=*tope;
num=temp->dato;
*tope=(*tope)->sig;
free(temp);
return num;
}
17
Funcion vacia e imprimir
Ahora escriba el programa del estacionamiento pero con pilas dinámicas.
18
10
4. Casos de estudio
1. Programa que convierta expresiones de notación infija a posfija.
2. Sistema de un estacionamiento, verificar el desarrollo o ampliarlo.
19
4. Ejemplo: Notación infija, postfija y prefija
Aplicación que representa los diferentes tipos de pilas con sus operaciones
Importante en Matemáticas, Teoría matemática de la computación, Sistemas operativos, Compiladores, etc.
Los prefijos “pre-”, “post-” e “in-”, se refiere a la posición relativa del operador con respecto a los operandos en una expresión.
En una conversión entre notaciones, se respeta el orden de aparición de los operandos.
20
11
Consideraciones en notación infija
La posición y precedencia de los operadores, así como si son asociativos por la izquierda o por la derecha
Operadores: Suma, resta, multiplicación, división y exponenciación ($)
Orden de precedencia: exponenciación
multiplicación/división
suma/resta
Todos son asociativos por la izquierda, excepto la exponenciación que es asociativo por la derecha
21
Notación infija
También conocida como interfija, donde en una expresión los operadores se encuentran en medio
Ejemplos:
a+b
(a+b)*(c-d)
22
12
Notación prefija
En esta notación, el operador precede a los operandos
No usa paréntesis
Ejemplos:
+AB
-+ABC
*+AB-CD
23
Notación postfija
Aquí los operadores de expresiones se encuentran al final de los operandos
No usa paréntesis
Ejemplos:
AB+
ABC*+
AB+CD-*
24
13
Ejercicios: Infija-Postfija
INFIJA
A+B
A+B-C
(A+B)*(C-D)
A$B*C-D+E/F/(G+H)
((A+B)*C-(D-E))$(F+G)
A-B/(C*D$E)
POSTFIJA
AB+
AB+C-
AB+CD-*
AB$C*D-EF/GH+/+
AB+C*DE- -FG+$
ABCDE$*/-
25
Ejercicios: Infija-Prefija
INFIJA
A+B
A+B-C
(A+B)*(C-D)
A$B*C-D+E/F/(G+H)
((A+B)*C-(D-E))$(F+G)
A-B/(C*D$E)
PREFIJA
+AB
-+ABC
*+AB-CD
+-*$ABCD//EF+GH
$-*+ABC-DE+FG
-A/B*C$DE
26
14
Algoritmo para convertir una expresión infija a postfijaopstk= la pila vacía;while (no es fin de entrada){
symb = siguiente carácter en la entradaif(symb es un operando)
agrega symb a la cadena postfijaelse {
while(!empty(opstk) && prcd(stacktop(opstk), symb)) {topsymb=pop(opstk);agrega topsymb a la cadena postfija;}/*fin while*/
if( empty(opstk) || symb != ‘)’ )push(opstk, symb);
else /*extraer el paréntesis que abre y descartarlo*/topsymb=pop(opstk);
}/*fin else*/}/*fin while*/
/*extracción de los operadores restantes*/while(!empty(opstk)){
topsymb=pop(opstk);agregar topsymb a la cadena postfija}
Ej: (2+3)*(4-2)
27
Reglas de precedencia de operadores
La función prcd acepta dos caracteres y es verdadera si el primer símbolo tiene precedencia respecto al segundo:
prcd( '*','+‘ ) = TRUEprcd( '+','+‘ ) = TRUEprcd( '+','*‘ ) = FALSEprcd( op, ‘)’ ) = TRUE para cualquier operador op que no
sea ‘(’prcd( op, ‘(’ ) = FALSE para cualquier operador op que no
sea ‘)’prcd( ‘(’, op ) = FALSE para cualquier operador opprcd( ‘)’, op ) = undefined para cualquier operador op (un
intento de comparar estos dos operadores indicará un error)
28
15
Algoritmo para evaluar una expresión postfija
opndstk=la pila vacía// recorre la cadena elemento a elementowhile (no se detecte el final de la entrada){
symb=siguiente carácter de entrada;if(symb es un operando)
push(opndstk, symb);else { //symb es un operador
opnd2=pop(opndstk);opnd1=pop(opndstk);value=resultado de aplicar symb a opnd1 y opnd2push(opndstk, value);
} /*fin else*/}/*fin while*/return(pop(opndstk));}
Ej. 2 3 + 4 2 - *
29
Ejemplo de representación estática
#define TAM 100#define INT 1#define FLT 2#define STRING 3struct Elemento{
int tipo-elem;union {
int ival;float fval;char val[5];}element;
};
typedef struct{int tope;struct Elemento elementos [TAM];}tipoPila; 30
16
Ejemplo de representación dinámica
#define INT 1#define FLT 2#define STRING 3struct Elemento{
int tipo-elem;union {
int ival;float fval;char val[5];}element;
};
typedef struct Pila{struct Elemento dato;struct Pila *sig;}tipoPila; 31
4. Estacionamiento de coches
Funcionalidades.
(menú de opciones) Entradas de coches, salidas de coches, consulta de un coche, listado de coches en el estacionamiento y entradas $ por día
Al ingresar el coche, se imprime un ticket con el número de coche y la hr de entrada.
Al recoger el coche, se solicita el ticket y se genera el costo, considerando 10 pesos la hora. No se cobra por fracciones de minutos.
Se puede salir del sistema si existen coches en el estacionamiento (guardar en archivo)
El sistema genera las entradas $ por día.32
17
Referencias
1. Tenenbaum, Aaron & Langsam, Yedidyah & Augenstein, Moshe “Estructuras de Datos en C”. Prentice-Hall, México 1997.
2. Deitel & Deitel “Como programar en C/C++”. Prentice-Hall, México
3. Wirth, Niklaus “Algoritmos y estructura de Datos”. Prentice-Hall, México.
33