Upload
sebastian-peralta
View
108
Download
0
Embed Size (px)
Citation preview
Estructuras de Datos. Ejercicios
Algoritmos
Departamento de ComputaciónUniversidade da Coruña
19 de octubre de 2011
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Colas
A partir de la siguiente estructura de datos para la implementación delistas enlazadas:
t ipo PNodo = puntero a NodoNodo = registro
Elem : TipoElementoSig : PNodo
f i n registroCola = PNodo
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Colas
A) Escriba el pseudocódigo de las siguientes operaciones:
CrearCola(p) que crea una cola vacía.EsColaVacia(p) que comprueba si la cola está vacía.Insertar(x,p) que inserta x en la cola.Primero(p) que devuelve el elemento de la cabeza de la cola.Sacar(p) que elimina la cabeza de la cola.
Si utilizase algún procedimiento auxiliar, refleje también supseudocódigo.
B) Indique, razonando su respuesta sobre el pseudocódigo, lacomplejidad computacional de cada una de las operacionesanteriores.
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
procedimiento CrearCola ( p )p := n i l
f i n procedimiento
funcion EsColaVacia ( p ) : t e s tdevolver p = n i l
f i n funcion
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
procedimiento CrearCola ( p )p := n i l {O(1)}
f i n procedimiento
funcion EsColaVacia ( p ) : t e s tdevolver p = n i l
f i n funcion
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
procedimiento CrearCola ( p )p := n i l {O(1)}
f i n procedimiento {O(1)}
funcion EsColaVacia ( p ) : t e s tdevolver p = n i l
f i n funcion
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
procedimiento CrearCola ( p )p := n i l {O(1)}
f i n procedimiento {O(1)}
funcion EsColaVacia ( p ) : t e s tdevolver p = n i l {O(1)}
f i n funcion
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
procedimiento CrearCola ( p )p := n i l {O(1)}
f i n procedimiento {O(1)}
funcion EsColaVacia ( p ) : t e s tdevolver p = n i l {O(1)}
f i n funcion {O(1)}
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
procedimiento CrearNodo ( x , tmp )nuevo ( tmp ) ;si tmp = n i l entonces
error Memoria agotadasino
tmp ^ . Elem := x ;tmp ^ . Sig := n i l ;
f i n procedimiento
procedimiento I n s e r t a r ( x , p )CrearNodo ( x , tmp ) ;si EsColaVacia ( p ) entonces
p := tmp ;sino
q := p ;mientras q ^ . Sig <> n i l hacer
q := q ^ . Sig ;q ^ . Sig := tmp ;
f i n procedimiento
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
procedimiento CrearNodo ( x , tmp )nuevo ( tmp ) ; {O(1)}si tmp = n i l entonces
error Memoria agotada {O(1)}sino
tmp ^ . Elem := x ; {O(1)}tmp ^ . Sig := n i l ; {O(1)}
f i n procedimiento
procedimiento I n s e r t a r ( x , p )CrearNodo ( x , tmp ) ;si EsColaVacia ( p ) entonces
p := tmp ;sino
q := p ;mientras q ^ . Sig <> n i l hacer
q := q ^ . Sig ;q ^ . Sig := tmp ;
f i n procedimiento
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
procedimiento CrearNodo ( x , tmp )nuevo ( tmp ) ; {O(1)}si tmp = n i l entonces {O(1)}
error Memoria agotada {O(1)}sino
tmp ^ . Elem := x ; {O(1)}tmp ^ . Sig := n i l ; {O(1)}
f i n procedimiento
procedimiento I n s e r t a r ( x , p )CrearNodo ( x , tmp ) ;si EsColaVacia ( p ) entonces
p := tmp ;sino
q := p ;mientras q ^ . Sig <> n i l hacer
q := q ^ . Sig ;q ^ . Sig := tmp ;
f i n procedimiento
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
procedimiento CrearNodo ( x , tmp )nuevo ( tmp ) ; {O(1)}si tmp = n i l entonces {O(1)}
error Memoria agotada {O(1)}sino
tmp ^ . Elem := x ; {O(1)}tmp ^ . Sig := n i l ; {O(1)}
f i n procedimiento {O(1)}
procedimiento I n s e r t a r ( x , p )CrearNodo ( x , tmp ) ;si EsColaVacia ( p ) entonces
p := tmp ;sino
q := p ;mientras q ^ . Sig <> n i l hacer
q := q ^ . Sig ;q ^ . Sig := tmp ;
f i n procedimiento
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
procedimiento CrearNodo ( x , tmp )nuevo ( tmp ) ; {O(1)}si tmp = n i l entonces {O(1)}
error Memoria agotada {O(1)}sino
tmp ^ . Elem := x ; {O(1)}tmp ^ . Sig := n i l ; {O(1)}
f i n procedimiento {O(1)}
procedimiento I n s e r t a r ( x , p )CrearNodo ( x , tmp ) ; {O(1)}si EsColaVacia ( p ) entonces
p := tmp ;sino
q := p ;mientras q ^ . Sig <> n i l hacer
q := q ^ . Sig ;q ^ . Sig := tmp ;
f i n procedimiento
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
procedimiento CrearNodo ( x , tmp )nuevo ( tmp ) ; {O(1)}si tmp = n i l entonces {O(1)}
error Memoria agotada {O(1)}sino
tmp ^ . Elem := x ; {O(1)}tmp ^ . Sig := n i l ; {O(1)}
f i n procedimiento {O(1)}
procedimiento I n s e r t a r ( x , p )CrearNodo ( x , tmp ) ; {O(1)}si EsColaVacia ( p ) entonces
p := tmp ; {O(1)}sino
q := p ; {O(1)}mientras q ^ . Sig <> n i l hacer
q := q ^ . Sig ; {O(1)}q ^ . Sig := tmp ; {O(1)}
f i n procedimiento
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
procedimiento CrearNodo ( x , tmp )nuevo ( tmp ) ; {O(1)}si tmp = n i l entonces {O(1)}
error Memoria agotada {O(1)}sino
tmp ^ . Elem := x ; {O(1)}tmp ^ . Sig := n i l ; {O(1)}
f i n procedimiento {O(1)}
procedimiento I n s e r t a r ( x , p )CrearNodo ( x , tmp ) ; {O(1)}si EsColaVacia ( p ) entonces
p := tmp ; {O(1)}sino
q := p ; {O(1)}mientras q ^ . Sig <> n i l hacer {O(n)}
q := q ^ . Sig ; {O(1)}q ^ . Sig := tmp ; {O(1)}
f i n procedimiento
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
procedimiento CrearNodo ( x , tmp )nuevo ( tmp ) ; {O(1)}si tmp = n i l entonces {O(1)}
error Memoria agotada {O(1)}sino
tmp ^ . Elem := x ; {O(1)}tmp ^ . Sig := n i l ; {O(1)}
f i n procedimiento {O(1)}
procedimiento I n s e r t a r ( x , p )CrearNodo ( x , tmp ) ; {O(1)}si EsColaVacia ( p ) entonces {O(1)}
p := tmp ; {O(1)}sino
q := p ; {O(1)}mientras q ^ . Sig <> n i l hacer {O(n)}
q := q ^ . Sig ; {O(1)}q ^ . Sig := tmp ; {O(1)}
f i n procedimiento
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
procedimiento CrearNodo ( x , tmp )nuevo ( tmp ) ; {O(1)}si tmp = n i l entonces {O(1)}
error Memoria agotada {O(1)}sino
tmp ^ . Elem := x ; {O(1)}tmp ^ . Sig := n i l ; {O(1)}
f i n procedimiento {O(1)}
procedimiento I n s e r t a r ( x , p )CrearNodo ( x , tmp ) ; {O(1)}si EsColaVacia ( p ) entonces {O(1)}
p := tmp ; {O(1)}sino
q := p ; {O(1)}mientras q ^ . Sig <> n i l hacer {O(n)}
q := q ^ . Sig ; {O(1)}q ^ . Sig := tmp ; {O(1)}
f i n procedimiento {O(n)}
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
funcion Primero ( p )s i EsColaVacia ( p ) entonces
error Cola vacíasino
devolver p ^ . Elemf i n funcion
procedimiento Sacar ( p )s i EsColaVacia ( p ) entonces
error Cola vacía ;sino
tmp := p ;p := p ^ . Sig ;l i b e r a r ( tmp ) ;
f i n procedimiento
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
funcion Primero ( p )s i EsColaVacia ( p ) entonces
error Cola vacía {O(1)}sino
devolver p ^ . Elem {O(1)}f i n funcion
procedimiento Sacar ( p )s i EsColaVacia ( p ) entonces
error Cola vacía ;sino
tmp := p ;p := p ^ . Sig ;l i b e r a r ( tmp ) ;
f i n procedimiento
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
funcion Primero ( p )s i EsColaVacia ( p ) entonces {O(1)}
error Cola vacía {O(1)}sino
devolver p ^ . Elem {O(1)}f i n funcion
procedimiento Sacar ( p )s i EsColaVacia ( p ) entonces
error Cola vacía ;sino
tmp := p ;p := p ^ . Sig ;l i b e r a r ( tmp ) ;
f i n procedimiento
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
funcion Primero ( p )s i EsColaVacia ( p ) entonces {O(1)}
error Cola vacía {O(1)}sino
devolver p ^ . Elem {O(1)}f i n funcion {O(1)}
procedimiento Sacar ( p )s i EsColaVacia ( p ) entonces
error Cola vacía ;sino
tmp := p ;p := p ^ . Sig ;l i b e r a r ( tmp ) ;
f i n procedimiento
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
funcion Primero ( p )s i EsColaVacia ( p ) entonces {O(1)}
error Cola vacía {O(1)}sino
devolver p ^ . Elem {O(1)}f i n funcion {O(1)}
procedimiento Sacar ( p )s i EsColaVacia ( p ) entonces
error Cola vacía ; {O(1)}sino
tmp := p ; {O(1)}p := p ^ . Sig ; {O(1)}l i b e r a r ( tmp ) ; {O(1)}
f i n procedimiento
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
funcion Primero ( p )s i EsColaVacia ( p ) entonces {O(1)}
error Cola vacía {O(1)}sino
devolver p ^ . Elem {O(1)}f i n funcion {O(1)}
procedimiento Sacar ( p )s i EsColaVacia ( p ) entonces {O(1)}
error Cola vacía ; {O(1)}sino
tmp := p ; {O(1)}p := p ^ . Sig ; {O(1)}l i b e r a r ( tmp ) ; {O(1)}
f i n procedimiento
Algoritmos Estructuras de Datos. Ejercicios
Ejercicio 1: Resolución
funcion Primero ( p )s i EsColaVacia ( p ) entonces {O(1)}
error Cola vacía {O(1)}sino
devolver p ^ . Elem {O(1)}f i n funcion {O(1)}
procedimiento Sacar ( p )s i EsColaVacia ( p ) entonces {O(1)}
error Cola vacía ; {O(1)}sino
tmp := p ; {O(1)}p := p ^ . Sig ; {O(1)}l i b e r a r ( tmp ) ; {O(1)}
f i n procedimiento {O(1)}
Algoritmos Estructuras de Datos. Ejercicios