Download TALLER_I - Universidad Autónoma de Madrid

UNIVERSIDAD AUTÓNOMA DE MADRID
ESCUELA POLITÉCNICA SUPERIOR
INGENIERÍA DE TELECOMUNICACIÓN
ASIGNATURA: ESTRUCTURA DE DATOS Y ALGORITMOS (EDA)
REUNIÓN DE EXPERTOS – APRENDIZAJE COOPERATIVO
TALLER I
OBJETIVO GENERAL:
 Que los estudiantes comprendan y apliquen los cuatro modelos: Pila, Cola, Lista y
Árbol Binario.
OBJETIVOS ESPECÍFICOS:
 Que cada experto sea capaz de:
1. Comunicar lo que ha aprendido a sus compañeros de equipo.
2. Explicar el tema asegurándose que ha sido comprendido por todos los
integrantes del equipo.
CONSIGNA:
 Realizar los ejercicios/problemas del siguiente taller.
MATERIAL A ENTREGAR:
1. Memoria con las respuestas a los ejercicios/problemas planteados en el Taller I.
2. Consignar en la memoria (como un apartado final) el número de horas adicionales
al de las sesiones teóricas que les ha llevado completar este taller. Especificar estas
horas por integrante y en equipo. Además, escribir cómo se han organizado para
realizar este trabajo propuesto y las incidencias del trabajo en equipo (si se aplica).
CRITERIOS DE ÉXITO:
El equipo ha presentado la memoria con las soluciones de los ejercicios/problemas del
Taller I en forma grupal.
FECHA DE ENTREGA: Lunes 7 de mayo de 2007
1
EJERCICIOS/PROBLEMAS:
PARTE A. PILAS
1) Para las expresiones siguientes, dar las evoluciones sobre una pila de la aplicación a las mismas
del algoritmo de traducción de infijo a sufijo. Presentar dichas evoluciones en tres columnas
que en cada paso contengan respectivamente el carácter que se lee, la traducción parcial y el
estado de la pila:
a)
(A–B)*(C–(D+E)^(F–G));
b)
A*((B+C)^(D–E)*F);
c)
(A+B)*(C–D^E)^F;
2) Identificar con un comentario las sentencias que se pueden abstraer o determinar como
funciones del TAD pila en el siguiente código. Además, comentar qué hace este programa.
# include <stdio.h>
# include <string.h>
# define MAX 100
int ChqPar( const char * cad ) {
int pp;
char memoria[MAX];
const char * p;
if (cad == 0) return 0;
if (! strlen(cad)) return 1;
pp = -1;
for (p = cad; *p; ++p) {
if (*p == '(' || *p == '[' || *p == '{') {
if ((pp + 1) >= MAX) return 0;
memoria[++pp] = *p;
}
else if (*p == ')' || *p == ']' || *p == '}') {
if (pp == -1) return 0;
if (memoria[pp] == '(' && *p == ')' ||
memoria[pp] == '[' && *p == ']' ||
memoria[pp] == '{' && *p == '}')
--pp;
else return 0;
}
}
return pp == -1;
}
2
3) Una implementación de pilas tienen como única interfaz las funciones:
status IniPila( pila P );
// Inicializa una pila
boolean EsVaciaPila( pila P ); // Comprueba si la pila está vacía.
// Devuelve V si la pila está vacía; F en caso contrario
status Push( dato D, pila P );
// Inserta el dato D en el top de la pila
// Devuelve OK si inserta correctamente; sino, ERROR
status Pop( dato D, pila P );
// Extrae el elemento D desde el top de la pila
// Devuelve OK si extrae; ERROR si no puede devolver
Pila es un tipo abstracto de datos y dato es un tipo de dato. Status sólo tiene dos valores
ERROR y OK y es un tipo enumerado. Bolean sólo tiene dos valores V y F y es de tipo
enumerado. Dar el código de una función de prototipo: status InvertirPila( pila A ); que reciba
una tal pila A y resitúe en ella sus elementos en orden inverso al inicial (es decir, se tiene que
hacer que en la pila que se recibe como parámetro se invierta el orden de sus elementos),
controlando los errores que correspondan. Se supone que la pila no tiene límite, es decir nunca
se llena.
4) Una implementación de pilas de datos enteros tiene como única interfaz las funciones:
status IniPila( pila P );
// Inicializa una pila
boolean EsVaciaPila( pila P ); // Comprueba si la pila está vacía.
// Devuelve V si la pila está vacía; F en caso contrario
status Push( entero E, pila P ); // Inserta el elemento E en el top (o la cima) de la pila
// Devuelve OK si inserta correctamente; sino, ERROR
status Pop( entero E, pila P );
// Saca el elemento que ocupa el top de la pila
// y lo sitúa en el elemento pasado como parámetro
// Devuelve OK si extrae; ERROR si no puede devolver
Pila es un tipo abstracto de datos y entero es un tipo de dato. Status sólo tiene dos valores
ERROR y OK y es un tipo enumerado. Boolean sólo tiene dos valores V y F y es de tipo
enumerado. Dar el código de una función de prototipo: status PMax( entero E, pila S ); que
escriba sin extraerlo en el dato E el máximo elemento de una pila S cuyos datos son todos
positivos, realizando el control y corrección de errores pertinentes. Para ello, se supone que Pop
devuelve error si la pila está vacía y que k Pops sobre una pila pueden seguirse por p  k Pushes
sobre la misma pila sin causar errores.
5) Una implementación de pilas tiene como única interfaz las funciones:
status IniPila( pila P );
// Inicializa una pila
boolean EsVaciaPila( pila P );
// Comprueba si la pila está vacía.
// Devuelve V si la pila está vacía; F en caso contrario
status Push( elemento E, pila P ); // Inserta el elemento E en el top (o la cima) de la pila
// Devuelve OK si inserta correctamente; sino, ERROR
3
status Pop( elemento E, pila P ); // Saca el elemento que ocupa el top de la pila
// y lo sitúa en el elemento pasado como parámetro
// Devuelve OK si extrae; ERROR si no puede devolver
Pila es un tipo abstracto de datos y elemento es un tipo de dato. Status sólo tiene dos valores
ERROR y OK y es un tipo enumerado. Boolean sólo tiene dos valores V y F y es de tipo
enumerado. Dar el código de una función de prototipo: status SwapPU( pila P ); que reciba una
pila P y la transforme situando en su top el elemento que entró en primer lugar y en su fondo el
elemento que ocupaba el top al llamar a la función. Todos los demás elementos, si los hay,
deberían quedar en el mismo orden en que estaban en la pila original. Se debe realizar el control
y corrección de errores pertinentes. Para simplificar el problema suponer que: (i) un Push
precedido de un Pop no causa errores; (ii) la pila tiene 2 o más elementos.
6) Utilizando la función malloc, dar el código de una función de prototipo:
status PilaIni( pila * ps, int numDatos ); que inicialice una tal pila con espacio suficiente para
almacenar numDatos elementos. Escribir una función de nombre PilaReset que libere la
memoria ocupada por la pila anterior. ¿Qué datos podría recibir y devolver dicha función? Dar
su prototipo y escribir su código C. Comentar en este código cuál es el prototipo de la función
free y qué es lo que realiza exactamente free.
PARTE B. COLAS
7) Suponiendo que el 1 es el primer elemento y 3 el último, indicar la evolución de la cola circular
Q cuyo estado se refleja en el diagrama inferior tras las siguientes operaciones:
i) ColaIns( 4, Q );
iv) ColaIns( 5, Q );
ii) ColaExt( D, Q );
v) ColaIns( 6, Q );
1
2
iii) ColaExt( D, Q );
vi) ColaIns( 7, Q ) ;
3
8) Sobre la cola circular Q del esquema inferior se efectúan las siguientes operaciones:
i) ColaIns( 3, Q );
ii) ColaRem( A, Q ); iii) ColaIns( 4, Q );
iv) ColaIns( 5, Q);
Indicar para cada operación la posición front (F) y rear (R) y el estado de la cola. ¿Cuál es el
valor final de la variable A?
R
F
2
1
9) Una implementación de colas tiene como única interfaz las funciones:
status IniCola( cola Q );
// Inicializa una cola
boolean EsVaciaCola( cola Q );
// Comprueba si la cola está vacía.
// Devuelve V si la cola está vacía; F en caso contrario
status ColaIns( dato D, cola Q );
// Inserta el dato D en la cola
// Devuelve OK si inserta correctamente; sino, ERROR
4
status ColaExt( dato D, cola Q );
// Extrae el elemento inicial de la cola y sitúa su dato en D
// Devuelve OK si extrae; ERROR si no puede devolver
int Cola Cuenta( cola Q );
// Devuelve el número de elementos en la cola
Cola es un tipo abstracto de datos y dato es un tipo de dato. Status sólo tiene dos valores
ERROR y OK y es un tipo enumerado. Boolean sólo tiene dos valores V y F y es de tipo
enumerado. Se supone que una inserción precedida de una extracción sobre la misma cola no
causa error. Dar el código de una función de prototipo: status JuntaColas( cola A, cola B ); que
reciba dos tales colas A, B y modifique la primera situando a continuación de su último
elemento los de la cola B (que debe quedar vacía, si la unión de colas se efectúa con éxito) en
su orden propio. La función sólo debe utilizar las primitivas anteriores y hacer el control y
recuperación de errores pertinentes.
10) Se implementa una cola circular mediante una tabla de dimensión 5 y se inicializa dando a front
y a rear el valor 0. Además, si se intenta efectuar en la cola una operación no factible, el
programa de implementación lo indica, pero admite continuar el trabajo con ella. Indicar la
ubicación de front y rear tras las siguientes operaciones, considerando si pueden llevarse a cabo.
i)
Dos adds, dos removes, tres adds, un remove, tres adds, un remove;
ii) Dos adds, un remove, tres adds, cuatro removes.
11) De una implementación del TAD Cola se dispone solamente de las primitivas:
status IniCola( cola Q );
// Inicializa una cola
boolean EsVaciaCola( cola Q );
// Comprueba si la cola está vacía
// Devuelve V si la cola está vacía; F en caso contrario
status ColaIns( dato D, cola Q );
// Inserta el dato D en la cola
// Devuelve OK si inserta correctamente; sino, ERROR
status ColaExt( dato D, cola Q );
// Extrae el elemento inicial de la cola y sitúa su dato en D.
// Devuelve OK si extrae; ERROR si no puede devolver
Definiendo el tipo de dato como int, dar el pseudocódigo de una función:
int InsertaOrdenada( int D, cola Q ) que actualice Q poniendo D detrás de todos los datos con
menor o igual valor y delante de todos los datos con mayor valor, es decir, si extrajésemos
todos los datos de la cola Q, obtendríamos una sucesión de enteros, ordenada de menor a
mayor.
PARTE C. LISTAS
12) Sobre la siguiente lista simplemente enlazada con cabecera L del esquema inferior se efectúan
las siguientes operaciones: (i) ListaInsertaFinal(3, L); (ii) ListaInsertaInicio(4, L); (iii)
ListaExtraeFinal(3, L); (iv) ListaBusca(4, L), aquí también decir qué es lo que devolvería esta
operación; y (v) ListaReset(L). Dar para cada operación el estado de la lista y las posiciones de
los punteros.
5
cabecera
•
L
13) Dar el prototipo y el código para la función ListaInsIni, que inserta un elemento al inicio de la
lista. Colocar números a los parámetros de la función y a las sentencias y realizar el esquema
gráfico que muestre la evolución del segmento de datos, de la pila de la función ListaInsIni y
del heap según los números colocados.
14) Escribir el pseudocódigo de:
(i) una función Le2Lc( lista l ) que reciba una lista enlazada apuntada por l y la transforme
en una lista enlazada circular también apuntada por l;
(ii) una función Lc2Le( lista l ) que reciba una lista enlazada circular apuntada por l y la
transforme en una lista enlazada simple también apuntada por l.
Suponer para ello que se identifica una lista con un puntero a un nodo, que NULL indica
una lista vacía, y la disponibilidad de las siguientes instrucciones:
Info( l ) devuelve el campo info del nodo apuntado por l;
Next( l ) devuelve un puntero del nodo siguiente a l;
Del( l ) elimina el nodo apuntado por l.
15) Escribir una función C que reciba un puntero a una lista doblemente enlazada e intercambie las
posiciones de sus nodos primero y último, considerando posibles situaciones de error.
16) Escribir funciones C que inserte un dato en el lugar i-ésimo de una lista doblemente enlazada, y
también que lo extraiga de dicho lugar.
17) Implementar una función C de prototipo: status ListaExtIni( Lista * pl, int * pd ), que elimine el
primer nodo de una lista doblemente enlazada apuntada por pl, almacenando el dato en dicho
nodo en la variable apuntada por pd. Lista es un puntero a una estructura de tipo NODO. Status
sólo tiene dos valores ERROR y OK y es un tipo enumerado. Dar para ello un esquema que
recoja la situación inicial de la lista, su situación final, e indique los pasos realizados.
18) Una implementación de listas enlazadas (LE) permite insertar y extraer elementos en su inicio y
final. Si se quiere usar como estructura de datos para pilas, discutir razonadamente la ubicación
de su top. Discutir razonadamente la conveniencia de usar una LE o una LE circular como
estructura de datos para colas.
19) Estudiar, analizar y revisar las primitivas implementadas para listas enlazadas dadas en el
material adjunto en teoría. Realizar una tabla resumen.
20) Estudiar, analizar y revisar las primitivas de pilas y colas implementadas sobre las primitivas de
listas enlazadas especificadas en el material adjunto en teoría. Realizar una tabla resumen.
6
PARTE D. ÁRBOLES
21) Construir los árboles de expresión de las expresiones sufijo inferiores, indicando para cada uno
de sus elementos el estado de la pila usada para gestionar dicha traducción en cada caso. Para
ello se ha de construir las mencionadas expresiones mediante dos columnas que contengan
respectivamente el carácter que se lee y el estado de la pila:
a) A B ^ C + D * E F ^ * ;
b) A B + C D E ^ F + – * ;
Una vez construidos los árboles de expresión, indicar cómo se obtendría las expresiones prefijo
equivalentes y dar a continuación dichas expresiones. Además, dar los recorridos en orden
simétrico y posterior de los árboles resultantes.
22) Para el siguiente árbol, dar sus recorridos en orden previo, posterior y por nivel.
1
4
2
3
5
7
6
23) Sobre un árbol binario, realizar el código de una función de prototipo:
int NodosCaminoMin( Tarbol A ); que determine el número de nodos existentes en el camino
más corto desde la raíz a una hoja.
24) En una implementación de árboles binarios, se utilizan: info( T ) para obtener el valor en su
campo info, y izq( T ), der( T ) para acceder a sus subárboles izquierdo y derecho. Se dispone
también de una función int NumElem( T ) que devuelve el número de nodos de un árbol T y de
otra bool ABVacio( T ) que devuelve V o F según T esté o no vacío.
Dar razonadamente el pseudocódigo de una función int NumElemMen( T, K ) que devuelve el
número de nodos de un árbol binario de búsqueda T cuyos campos info son menores o iguales
que la clave K.
25) Sobre un árbol binario, realizar una operación que determine el número de nodos que son
completos. Se dice que un nodo es completo, si siempre tiene los dos, el izquierdo y el derecho.
26) Determinar la suma de los nodos de un árbol binario dado, que NO sean nodos hoja.
27) Definir qué se entiende por árbol binario de búsqueda. Dar una nueva definición en este caso
recursiva. Describir brevemente el mecanismo de construcción de un árbol binario de búsqueda.
¿Cómo se puede conseguir un listado ordenado de sus elementos? Dadas las listas:
a) 20 10 7 8 35 4 12 11,
b) 5 13 1 4 7 15 3 9 2 6.
7
Construir sus árboles binarios de búsqueda, indicando el estado de los mismos tras cada
inserción. Dar los resultados de su recorrido en orden simétrico.
28) Dado un árbol binario de búsqueda con elementos de tipo entero, implementar una función que
determine el número de elementos del árbol cuyo valor se encuentre entre dos límites dados.
Por ejemplo, para un árbol A y el intervalo [2, 25], se obtendría como resultado el total de los
elementos del árbol A que sean mayores o iguales a 2 y menores o iguales a 25. El prototipo de
la función a desarrollar es:
int ElementosEnIntervalo( Tarbol A, int inf, int sup );
29) Supongamos que cada nodo de un árbol binario de búsqueda (ABB) además de la información
de un tipo base cualquiera, tiene un campo llamado tamaño que guarda información del número
de nodos de su subárbol izquierdo. Escribir el código de una función recursiva en C de
prototipo:
int InsertarABBTamanio( Tarbol * A, Tdato elem );
que inserte un nuevo nodo en un árbol de este tipo, implementado dinámicamente y suponiendo
que los elementos pueden venir repetidos y, en este caso, no se insertan en el árbol. La función
debe devolver 1 si todo ha ido bien, o 0 si se produce algún error.
Se disponen de las siguientes funciones de la interfaz del TAD ABB en la librería
arbol_basico.h :
/*********************************************************************
Nombre: Insertar
Descripción: inserta en el ABB apuntado por pab un nodo que contiene el dato indicado
como argumento
Argumentos de entrada: el dato a insertar y un puntero al árbol
Retorno: BIEN O ERROR según tenga éxito o no la inserción
*********************************************************************/
ESTADO insertar ( Tdato, ABB * );
/*********************************************************************
Nombre: ArbolVacio
Descripción: comprueba si el árbol está vacío
Argumentos de entrada: puntero a árbol
Retorno: SI cuando el árbol está vacío, NO en caso contrario
*********************************************************************/
BOOLEANO ArbolVacio( ABB * );
/*********************************************************************
Nombre: GetNodoABB
Descripción: obtiene memoria dinámica para un nodo
Argumentos de entrada: puntero a puntero al nodo
Retorno: BIEN si la reserva se produce de forma correcta, ERROR en caso contrario
*********************************************************************/
ESTADO GetNodoABB( nodoABB ** );
8
/*********************************************************************
Nombre: IniArbol
Descripción: inicializar a vacío el árbol
Argumentos de entrada: puntero a árbol
Retorno: OK, si se realiza correctamente
*********************************************************************/
ESTADO IniArbol( ABB * );
/*********************************************************************
Nombre: EnOrden
Descripción: recorre el árbol binario según el criterio "inorder" e imprime cada nodo por
pantalla
Argumentos de entrada: puntero al árbol a recorrer
Retorno: ninguno
*********************************************************************/
void EnOrden( ABB * );
/*********************************************************************
Nombre: Buscar
Descripción: busca el nodo que contenga la clave indicada como argumento
Argumentos de entrada: puntero al árbol en el que buscar y clave a buscar
Retorno: un puntero al nodo que contiene la clave, NULL si no se encuentra
*********************************************************************/
ABB Buscar( ABB *, Tdato );
/*********************************************************************
Nombre: EnOrdenReves
Descripción: recorre el árbol binario según el criterio "inorder" de forma inversa e imprime
cada nodo por pantalla
Argumentos de entrada: puntero al árbol a recorrer
Retorno: ninguno
*********************************************************************/
void EnOrdenReves( ABB * );
/*********************************************************************
Nombre: LiberarArbol
Descripción: libera la memoria dinámica asignada a un árbol
Argumentos de entrada: puntero al árbol a liberar
Retorno: ninguno
*********************************************************************/
void LiberarArbol( ABB * );
9
/*********************************************************************
Nombre: EliminarNodo
Descripción: elimina un nodo del árbol, reestructurando los demás
Argumentos de entrada: puntero al árbol y clave del nodo a eliminar
Retorno: puntero al nodo eliminado, NULL si no ha dicho nodo
*********************************************************************/
ABB EliminarNodo( ABB *, Tdato );
/*********************************************************************
Nombre: BuscarMin
Descripción: busca el nodo que contenga la clave de menor valor
Argumentos de entrada: puntero al árbol en el que buscar
Retorno: un puntero al nodo que contiene la clave, NULL si es árbol vacío
*********************************************************************/
ABB BuscarMin( ABB * );
/*********************************************************************
Nombre: Comparar
Descripción: realiza una comparacion de elemizq con elemder, y devuelve:
< 0, == 0 o > 0 dependiendo de si elemizq es menor que, igual a, o mayor que
elemder, respectivamente
Argumentos de entrada: elemizq y elemder
Retorno: devuelve un entero < 0, == 0 o > 0
*********************************************************************/
int Comparar( Tdato elemizq, Tdato elemder );
PARTE E. INTEGRACIÓN
30) En una sucursal bancaria se pueden realizar ingresos, reintegros y consultas. La sucursal
dispone de dos ventanillas, una de las cuales puede atender cualquier operación
(VENTANILLA GENERAL), mientras que la otra sólo puede realizar ingresos
(VENTANILLA DE INGRESOS). Los clientes, caracterizados por su NIF y la operación que
desean realizar, se atienden según el orden de llegada, y pueden ser atendidos indistintamente
por una u otra ventanilla en función de que estén libres en ese momento.
Si un cliente es atendido por la ventanilla de ingresos y no desea realizar esa operación, se pasa
a una dependencia donde esperan en orden de llegada todos los clientes en la misma situación.
Todos los clientes de esta dependencia serán atendidos por la ventanilla general. Además,
tienen preferencia sobre los clientes que aún no han visitado ninguna ventanilla.
Por otro lado, se almacena cada operación realizada en la sucursal ordenada por el NIF
del cliente. Por cada operación se guarda el NIF del cliente y la operación realizada.
Se pide:
a) Realizar las declaraciones de las estructuras de datos más adecuadas para almacenar la
información del problema, identificándolas con los TAD’s que conoces. Razonar
brevemente la respuesta.
10
b) Utilizando las operaciones básicas para el manejo de los TAD’s definidos en el apartado a).
Diseñar e implementar dos operaciones, una para atender un cliente en la ventanilla general,
AtencionVGeneral, y otra para atenderlo en la ventanilla de ingresos, AtencionVIngresos.
Ambas operaciones reciben la/s estructura/s de cliente/s, atienden a uno sólo de esos posibles
clientes y almacenan la operación que ha realizado el cliente.
Las operaciones básicas NO es necesario implementarlas, otras operaciones deben
implementarse.
31) Con el fin de mejorar el servicio de autobuses universitario, cierto ayuntamiento y cierta
universidad firman un convenio para simular dicho servicio. En la simulación se trabaja con dos
estructuras básicas: la estructura parada, que representa las personas que esperan un autobús, y
la estructura autobús, que representa las personas que están dentro del autobús.
En la simulación hay dos premisas que cumplir: asumiendo un comportamiento civilizado para
ambas partes, nadie se “cuela” en la parada y nadie “viaja de pie” en el autobús. Se supone
que en el autobús hay f filas y c columnas de asientos. Cuando el autobús llegue a la parada, los
asientos estarán ocupados o libres de manera aleatoria.
Se pide:
a) Definir las estructuras de datos más adecuadas para simular una parada y un autobús.
b) Implementar en pseudocódigo la operación CogerAutobus, cuyo objetivo es recoger
personas de la parada y acomodarlas en el autobús.
NOTA: las operaciones básicas de los TAD estudiados en teoría y, o, prácticas NO se necesitan
implementar, pero cualquier otra operación debe de ir acompañada de su implementación en
pseudocódigo.
32) Proponer cuatro problemas sobre los TAD y estructuras de datos aprendidos: Pilas, Colas,
Listas y Árboles. Describir detalladamente sus soluciones correspondientes.
11
SOLUCIONES PROPUESTAS:
PARTE A. PILAS
Problema 1:
a)
(A–B)*(C–(D+E)^(F–G));
Lee
(
A
B
)
*
(
C
(
D
+
E
)
^
(
F
G
)
)
;
Pila
Traducción Parcial
A
A
AB
ABABABAB-C
AB-C
AB-C
AB-CD
AB-CD
AB-CDE
AB-CDE+
AB-CDE+
AB-CDE+
AB-CDE+F
AB-CDE+F
AB-CDE+FG
AB-CDE+FGAB-CDE+FG-^AB-CDE+FG-^-*
(
(
((*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
(
(
(
(
(
(
(
(
(
(
(
(
(
(
-
(
(
(+
(+
^
^(
^(
^(^(^
12
b)
A*((B+C)^(D–E)*F);
Leo
A
*
(
(
B
Traducción Parcial
A
A
A
A
AB
Pila
+
AB
ABC
ABC+
ABC+
ABC+
ABC+D
*((+
*((+
*(
*(^
*(^(
*(^(
ABC+D
ABC+DE
ABC+DEABC+DE-^
ABC+DE-^F
ABC+DE-^F*
ABC+DE-^F**
*(^(*(^(*(^
*(*
*(*
*
C
)
^
(
D
E
)
*
F
)
;
c)
*
*(
*((
*((
(A+B)*(C–D^E)^F;
Leo
(
A
Traducción Parcial
+
A
AB
AB+
AB+
(+
(+
AB+
AB+C
*(
*(
AB+C
AB+CD
AB+CD
AB+CDE
*(*(*(-^
*(-^
AB+CDE^AB+CDE^AB+CDE^-F
AB+CDE^-F^*
*
*^
*^
B
)
*
(
C
D
^
E
)
^
F
;
A
Pila
(
(
*
13
Problema 2:
/*
Este programa realiza una comprobación elemental de corrección de
paréntesis, llaves y corchetes con control de errores (equilibrio de
símbolos). Se usa una pila implementada en una tabla de char, y un índice que servirá como
puntero de pila. El puntero de pila apunta al elemento del tope, o -1
si la pila está vacía. Devuelve 0 en caso de error y 1 en caso de que todo esté correcto. Si la
cadena no esta inicializada devuelve error y si la cadena es vacía devuelve 1 indicando que es
correcta. Se inicializa una pila, se leen los caracteres hasta el final de la cadena de char. Si el
caracter es de apertura, se mete en la pila. Si es de clausura y la pila esta vacía indica un error.
Si no, se saca un elemento de la pila. Si
el elemento sacado no es el correspondiente símbolo de apertura, se anuncia un
error. Al final de la cadena, si la pila no esta vacía se indica un error, es decir, si la pila está
vacía devuelve 1 indicando que todo está legal. Por tanto, el programa comprueba distintos
tipo de errores: cadena sin inicializar, aparición de ‘)’, ‘]’ o ‘}’ sin haber aparecido antes uno
de apertura, que para cada símbolo de apertura exista otro del mismo tipo de clausura.
*/
# include <stdio.h>
# include <string.h>
# define MAX 100
int ChqPar( const char * cad ) {
int pp;
char memoria[MAX];
const char * p;
if (cad == 0) return 0;
if (! strlen(cad)) return 1;
pp = -1; /* INICIALIZA PILA */
for (p = cad; *p; ++p) {
if (*p == '(' || *p == '[' || *p == '{') {
if ((pp + 1) >= MAX) return 0; /* Comprueba PILA LLENA */
memoria[++pp] = *p; /* PUSH */
}
else if (*p == ')' || *p == ']' || *p == '}') {
if (pp == -1) return 0; /* Comprueba PILA VACÍA */
if (memoria[pp] == '(' && *p == ')' ||
memoria[pp] == '[' && *p == ']' ||
memoria[pp] == '{' && *p == '}')
--pp; /* POP */
else return 0;
}
}
return pp == -1; /* SI LA PILA ESTÁ VACÍA, ESTÁ TODO LEGAL */
}
14
Problema 3:
status InvertirPila(pila A) {
if (IniPila(S1) == ERROR)
return ERROR;
if (IniPila(S2) == ERROR)
return ERROR;
while(EsVaciaPila(A) == F) {
Pop(D, A);
if (Push(D, S1) == ERROR) {
// rellenar A desde S1
Push(D, A);
while(EsVaciaPila(S1) == F) {
Pop(D, S1);
Push(D, A);
}
return ERROR;
}
}
while(EsVaciaPila(S1) == F) {
Pop(D, S1);
if (Push(D, S2) == ERROR) {
// rellenar S1 desde S2
Push(D, S1);
while(EsVaciaPila(S2) == F) {
Pop(D, S2);
Push(D, S1);
}
// rellenar A desde S1
while(EsVaciaPila(S1) == F) {
Pop(D, S1);
Push(D, A);
}
return ERROR;
}
}
while(EsVaciaPila(S2) == F) {
Pop(D, S2);
Push(D, A);
}
return OK;
}
15
Problema 4:
status PMax( entero E, pila S ) {
E = -1;
if (IniPila( S1 ) == ERROR)
return ERROR;
while ( EsVaciaPila( S ) == F ) {
Pop( D, S );
if ( D > E ) E = D;
if ( Push( D, S1) == ERROR ) {
Push( D, S );
while ( EsVaciaPila( S1 ) == F ) {
Pop( D, S1 );
Push( D, S );
}
return ERROR;
}
}
while ( EsVaciaPila( S1 ) == F ) {
Pop( D, S1 );
Push( D, S );
}
return OK;
}
16
Problema 5:
STATUS SwapPU( pila P ) {
pila Pila_aux;
elemento top, fondo, D;
if (IniPila(Pila_aux) == ERROR) {
printf("Error: No se puede inicializar la pila");
return ERROR;
}
if (Pop(top, P)==ERROR)
return ERROR;
while (EsVaciaPila(P)==F) {
if (Pop(D, P)==ERROR)
return ERROR;
if (Push(D, Pila_aux)==ERROR)
return ERROR;
}
if (Pop(fondo, Pila_aux)==ERROR)
return ERROR;
if (Push(top, P)==ERROR) return ERROR;
while (EsVacia(Pila_aux)==F) {
if (Pop(D, Pila_aux)==ERROR)
return ERROR;
if (Push(D, P)==ERROR)
return ERROR;
}
if (Push(fondo, P)==ERROR)
return ERROR;
return OK;
}
17
Problema 6:
status PilaIni( pila * ps, int numDatos ){
/*Apunta primera posicion libre*/
ps->tope=0;
/*Reservamos memoria para la pila*/
ps->datos=(TIPO_INFO_PILA *) malloc( numDatos *sizeof(TIPO_INFO_PILA));
/*Comprobamos que se ha reservado memoria*/
if (ps->datos == NULL)
return ERROR;
return BIEN;
}
void PilaReset (PILA * pila){
/*Comprobamos que existe la pila*/
if (pila->datos == NULL)
return;
/*Liberamos memoria reservada dinámicamente con malloc*/
free(pila->datos); // void free(void *ptr);
pila->datos=NULL;
pila->tope=0;
}
18
PARTE B. COLAS
Problema 7:
i)
1
f
2
1
f
2
3
r
3
r
ii)
2
f
3
3
f
4
3
f
4
5
4
5
r
3
f
4
5
r
3
f
iv)
r
vi)
4
D
1
D
2
r
iii)
v)
4
6
6
r
Error Cola
Llena!
Problema 8:
2
r
i)
2
3
r
ii)
iii)
iv)
2
f
3
2
f
3
2
f
3
1
f
A -----
1
f
A -----
A
1
A
1
r
4
r
Error Cola
Llena!
4
r
19
Problema 9:
/* JuntaColas */
status JuntaColas (Cola A, Cola B)
{
Dato D;
if (EsColaVacia(B))
return OK;
else
do{
if(!ColaExt(D,B)){
printf("Imposible extraer");
return ERROR;
}
else
if(!ColaIns(D,A)){
printf("Imposible insertar");
return ERROR;
}
}while(!EsColaVacia(B));
return OK;
}
20
Problema 10:
i)
add
add
f,r
x
f
x
f
rem
r
x
r
x
f
r
rem
f,r
add
x
f
add
add
r
x
f
x
x
f
x
x
x
f
x
x
f
x
x
f
x
x
f,r
x
rem
r
add
x
r
add
x
r
x
r
add
x
x
x
rem
x
x
x
r
r
ERROR
x
f
21
Problema 11:
int InsertaOrdenada (int D, cola Q)
{
status ESTADO;
int extraido;
int flag=0;
cola AUX;
if (EsVaciaCola(Q) == V) {
if (ColaIns(D,Q)==ERROR)
return ERROR;
return OK;
}
ESTADO = IniCola (AUX);
if (ESTADO == ERROR) {
printf(“Error al inicializar cola auxiliar\n”)
return 0;
}
while(EsVaciaCola(Q) == F)
{
ESTADO = ColaExt(extraido,Q) ;
if (ESTADO == ERROR){
printf(“Se intenta extraer de una cola vacia\n”);
return 0;
}
if (D>= extraido) {
ESTADO = ColaIns(extraido,AUX) ;
if (ESTADO = = ERROR)
return 0;
}
else if(D<extraido && flag == 0) {
ESTADO = ColaIns(D,AUX) ;
if (ESTADO = = ERROR)
return 0;
ESTADO = ColaIns(extraido,AUX) ;
if (ESTADO = = ERROR)
return 0;
flag = 1;
}
else {
ESTADO = ColaIns(extraido,AUX) ;
if (ESTADO = = ERROR)
return 0;
}
}
while (EsVaciaCola(AUX) == F)
{
ESTADO = ColaExt(extraido,AUX) ;
if (ESTADO = = ERROR)
return 0;
ESTADO = ColaIns(extraido,Q) ;
if (ESTADO = = ERROR)
{
printf(“No se puede insertar en la cola \n”)
return 0;
}
22
}
return 1;
}
PARTE C. LISTAS
Problema 12:
Problema 13:
1
2
Status ListaInsIni (gen *pg, lista *pl)
{
nodo *pn;
3
if ( getNodo(&pn)==ERROR )
return ERROR;
pn->info = *pg;
4
5
pn->next=*pl;
*pl=pn;
6
return OK;
}
23
24
Problema 14:
i) Basta encontrar el último elemento y se rectifican los punteros adecuados
Le2Lc( lista l )
si l != NULL :
l1 = l ; // l1: variable auxiliar para recorrer l
mientras Next( l1 ) != NULL :
l1 = Next( l1) ;
// l1 apunta al último elemento
Next( l1 ) = l ;
l = l1 ;
ii) Basta rectificar los punteros adecuados
Lc2Le( lista l )
si l != NULL :
l1 = Next ( l ) ;
// l1 apunta al primer nodo
Next( l ) = NULL ;
// l es el último nodo de un le
l = l1 ;
// l apunta al primer nodo
Problema 15:
/* Swap LDE */
status swapLDE(Lista pL)
{
Nodo *aux1, *aux2;
if (!(getNodo(&aux1)){
printf("Error de reserva");
return ERROR;
}
if (!(getNodo(&aux2)){
printf("Error de reserva");
return ERROR;
}
//Extraer los nodos primero y ultimo
if(!(ListaExtIni(aux2, pL)){
printf("Error de extraccion");
return ERROR;
}
if(!(ListaExtFin(aux1, pL)){
printf("Error de extraccion");
return ERROR;
}
//Insertarlos cambiados
if(!(ListaInsIni(aux1, pL)){
printf("Error de extraccion");
return ERROR;
}
if(!(ListaInsFin(aux2, pL)){
printf("Error de extraccion");
return ERROR;
}
return OK;
}
25
Problema 16:
/* Insertar i-esimo: Inserta el dato D antes de la posición legal i en LDE sin nodo cabecera*/
status InsertarIEsimo(dato D, Posicion i, Lista L) {
Posicion pn=NULL;
if (!(getNodo(&pn)) {
printf("Error de memoria");
return ERROR;
}
pn->info=D;
pn->ant=i->ant;
i->ant->sig=pn;
pn->sig=i;
i->ant=pn;
return OK;
}
/* Extraer i-esimo: Extrae el dato D de la posición legal i en LDE sin nodo cabecera y elimina esta posición de
la lista */
status ExtraerIEsimo(dato D, Posicion i , Lista L) {
Posicion pn=NULL;
D=i->elemento;
if (i->ant != NULL)
pn = i->sig;
i->ant->sig=pn;
else
L=i->sig;
L->ant=NULL;
if (i->sig != NULL)
pn=i->ant;
i->sig->ant=pn;
free(i);
i=NULL;
return OK;
}
26
Problema 17:
/* Extraer del Inicio en LDE*/
status ListaExtIni( Lista * pl, int * pd ) {
if ( *pl == NULL )
return ERROR;
else {
*pd=(*pl)->info;
*pl=(*pl)->siguiente;
free((void*) (*pl)->anterior);
(*pl)->anterior=NULL;
}
return OK;
}
27
PARTE D. ÁRBOLES
Problema 21:
a) A B ^ C + D * E F ^ *;
28
Solución: ((A^B+C)*D)*E^F
29
b) A B + C D E ^ F + – * ;
Solución: (A+B)*(C-(D^E+F)
30
Las expresiones prefijo se obtienen, haciendo un recorrido preorden.
Orden previo:
a)
b)
Orden simétrico:
a) ((A^B+C)*D)*E^F;
b) (A+B)*(C-(D^E+F);
Orden posterior:
a) AB^C+D*EF^*;
b) AB+CDE^F+-*;
Problema 22:
1
4
2
3
5
7
6
orden previo: 1 2 3 4 5 6 7
orden posterior: 3 2 6 5 7 4 1
orden por nivel: 1 2 4 3 5 7 6
Problema 23:
int NodosCaminoMin( Tarbol A ) {
if (A == NULL)
return 0;
if (A->izda !=NULL && A->dcha !=NULL)
return (1 + Min(NodosCaminoMin (A->izda), NodosCaminoMin (A->dcha)));
else if (A->izda ==NULL && A->dcha ==NULL)
return 1;
else if (A->izda ==NULL)
return (1 +NodosCaminoMin (A->dcha));
else if (A->dcha ==NULL)
return (1 +NodosCaminoMin (A->izda));
}
31
Problema 24:
* Opción 1:
int NumElemMen( T, K ) {
if (T == NULL)
return 0;
if (info < K)
return (1+ NumElemMen(izq( T ), K )+ NumElemMen(der( T ), K ));
else if (info = K)
return (1+ NumElemMen(izq( T ), K ));
else
return NumElemMen(izq( T ), K);
}
* Opción 2: usando las funciones int NumElem( T ) y bool ABVacio( T )
int NumElemMen( T, K ) {
if (ABVacio( T )==TRUE)
return 0;
if (info(T) < K)
return (1+ NumElem(izq( T ) )+ NumElemMen(der( T ), K ));
else if (info(T) == K)
return (1+NumElem(izq( T )));
else
return NumElemMen(izq( T ), K );
}
Problema 25:
int NodosCompletos( T ) {
if (T == NULL)
return 0;
if (izq(T)!=NULL && der(T)!=NULL)
return (1+ NodosCompletos (izq( T ))+ NodosCompletos (der( T )));
else
return 0;
}
32
Problema 26:
int SumaNodos( T ) {
if (T == NULL)
return 0;
if (izq(T)==NULL && der(T)==NULL)
return 0 ;
else if (izq(T)!=NULL && der(T)!=NULL)
return (info(T)+ SumaNodos (izq( T ))+ SumaNodos (der( T )));
else if (izq(T)==NULL)
return (info(T)+ SumaNodos (der( T )));
else if (der(T)==NULL)
return (info(T)+ SumaNodos (izq( T )));
}
Problema 27:
Un árbol binario de búsqueda es aquel que dado un nodo, todos los datos del subárbol izquierdo son
menores que los datos de ese nodo, mientras que todos los datos del subárbol derecho son mayores que sus
propios datos.
33
34
Problema 28:
int ElementosEnIntervalo( Tarbol A, int inf, int sup ) {
if (A == NULL)
return 0;
if (info(A) < sup && info(A) > inf)
return (1 + ElementosEnIntervalo (izq( A ),inf,sup) + ElementosEnIntervalo (der( A
),inf,sup));
else if (info(A) == inf)
return (1 + ElementosEnIntervalo (der( A ),inf,sup));
else if (info(A) == sup)
return (1 + ElementosEnIntervalo (izq( A ),inf,sup));
else
return 0;
}
Problema 29:
int InsertarABBTamanio( Arbol *A, Tdato elem){
int comparación, flag;
if (ArbolVacio(A)==SI) {
if (GetNodoABB(&A)==ERROR)
return 0;
(*A)->info = elem;
(*A)->tamanio = 0;
(*A)->hijo_izdo = NULL;
(*A)->hijo_dcho = NULL;
return 1;
}
else {
comparacion = Comparar(elem, (*A)->info);
if(comparación ==0)
return 0;
else if (comparación <0) {
flag = InsertarABBTamanio((*A)->hijo_izdo, elem);
if (flag ==1)
(*A)->tamanio = (*A)->tamanio+1;
return flag;
}
else
return InsertarABBTamanio((*A)->hijo_dcho, elem);
}
}
35
PARTE E. INTEGRACIÓN
Problema 30:
/* Problema 1 INTEGRACION */
/* A */
typedef struct {
char NIF[10];
char oper;
}Tcliente;
typedef struct TNODO{
struct TNODO * sig;
}TNodo
typedef struct{
TNodo * p;
TNodo *u;
}TCola;
typedef TNodo * TLista;
/* B */
void AtencionVGeneral(TCola *qbanco, TCola *qdepend, Tlista loper)
{
bool resp;
EsColaVacia(*qdepend, resp);
if(!resp)
AtenderCliente(*qdepend, loper);
EsColaVacia(*qbanco, resp);
if(!resp)
AtenderCliente(*qbanco, loper);
}
36
void AtenderCliente(TCola *q, TLista l)
{
TCliente c;
PrimeroCola(*q,c);
EliminarCola(*q);
AnadirListaOrden(l,c);
}
void AtencionVIngresos(TCola *qbanco, TCola *qdepend, Tlista loper)
{
bool resp;
TCliente c;
EsColaVacia(qbanco, resp);
if(!resp)
{
PimeroCola(qbanco, c);
EliminarCola(qbanco);
if(c.oper = 'I')
AnadirListaOrden(loper, c);
else
AnadirCola(qdepend, c);
}
}
37
Problema 31:
/* Problema 2 INTEGRACION */
/* A */
//Constantes
#define f <valorf>
#define c <valorc>
//Estructuras
typedef struct{
char pasajero;
int ocupado;
}Asiento;
typedef struct PERSONA{
char identif;
struct PERSONA * sig
}Persona;
typedef struct{
Persona * prim;
Persona * ult;
}Parada;
Asiento Autobus[f][c];
/* B */
/* Suponiendo que la cola de la parada del autobus no se modifica admitiendo
nuevas perseonas duante la realizacion del proceso "CogerAutobus" */
void CogerAutobus(Asiento *autobus [][], Parada *p)
{
char individuo;
int libres;
bool resp;
EsVacia(p, resp);
libres=AsientosLibres(autobus);
38
do{
PrimeroCola(*p, individuo);
OcuparAsiento(autobus, individuo);
libres--;
Eliminar (*p);
EsVacia(*p, resp);
}while(libres > 0 && resp==false);
}
int AsientosLibres(Asiento *autobus [][])
{
int fila, col, asientos=0;
for(fila=0;fila<f;fila++)
for(col=0;col<c;col++)
if(aubous[fila][col]->ocupado==0)
asientos++;
return asientos;
}
void OcuparAsiento(Asiento *autobus[][], char indiv)
{
int fil=0;
int col=0;
bool encontrado=false;
do{
do{
if(autobus[fil][col]->ocupado==0)
{
autobus[fila][col]->ocupado=1;
autobus[fila][col]->pasajero=indiv;
encontrado=true;
}
col++;
}while(col<c && encontrado==false);
fila++;
}while(fil<f && encontrado ==false);
}
39