Download Estructuras de Datos II Boletín nº 2 TAD lineales: Pila, Cola y Lista

Estructuras de Datos II
(I.T. Informática de Gestión y Sistemas)
Boletín nº 2
TAD lineales:
Pila, Cola y Lista
Nota. Para poder probar las soluciones que propongáis a los problemas de los
bloques I, III y V podéis utilizar los contenedores stack, queue y list de la
STL. También podéis implementar vuestros propios tipos a partir del
material de teoría.
I. Utilización de los TAD Pila y Cola
1. Escribe un algoritmo que indique si en una expresión matemática los paréntesis están
equilibrados, es decir, a cada paréntesis abierto le corresponde uno cerrado del
mismo tipo, estando bien anidados. La expresión puede contener cualquiera de los
siguientes paréntesis: (), [] y {}. Supón que la expresión viene dada en forma de
cadena de caracteres.
2. Escribe un algoritmo que convierta una expresión en notación infija a notación postfija
(también llamada notación polaca inversa, RPN).
3. Escribe un algoritmo que evalúe la expresión en notación postfija obtenida en el
ejercicio anterior.
4. El lenguaje M ‘abc mirror’, es un lenguaje especial de strings formado por las letras
[‘a’,’b’,’c’,’m’] donde cada string es de la forma LmR, siendo L un string de uno o más
abcs, m una marca intermedia y R el inverso del string L. Escribe un algoritmo capaz
de reconocer secuencias del lenguaje M.
bool CompruebaM(const string& cad)
var
char letra
int i = 0
Pila<char> pila
bool parteL = verdadero
fvar
inicio
si cad.length() < 3 entonces // el string no tiene al menos 3 letras
devuelve falso
fsi
Estructuras de Datos II
Curso 2005/06
hacer
letra = cad[i]
si parteL entonces
si (letra == 'a') ∨ (letra == 'b') ∨ (letra == 'c') entonces
pila.apilar(letra)
sino si (letra == 'm') entonces
parteL = falso
sino
devuelve falso
fsi
sino
si (¬pila.esVacia()) ∧ (letra == pila.cima()) entonces
pila.desapilar()
sino
devuelve falso
fsi
fsi
i++
mientras i < cad.length()
devuelve pila.esVacia()
fin
5. Escribe un algoritmo que devuelva cierto si todos los elementos de una pila son
positivos, suponiendo que la pila almacena valores del tipo Integer.
6. Los datos se almacenan en la memoria de la computadora utilizando una
representación binaria. Esto significa que la representación de los enteros en base 10
que se utiliza en los programas debe convertirse a la representación en base 2. Uno
de los algoritmos que realiza esta conversión consiste en dividir repetidamente el
entero entre 2, siendo los restos de dichas divisiones los dígitos del número en la
representación en base 2. Escribe un algoritmo que convierta un entero positivo en
base 10 a base 2 y muestre el resultado.
7. En Correos un funcionario ha cerrado una ventanilla y la gente de la cola tiene que
juntarse con la gente en la cola de otra ventanilla. Esta situación motiva la
introducción de dos nuevas operaciones para colas:
void concatenar(Cola& q1, const Cola& q2)
{ añade q2 al final de q1 }
const Cola& barajar(const Cola& q1, const Cola& q2)
{ mezcla los elementos de q1 con los elementos de q2, de manera que los elementos de q2 ocupen
posiciones impares y los elementos de q1 ocupen las posiciones pares }
II. Implementación del TAD Cola
8. El TAD Cola admite una implementación eficiente mediante un tabla circular. Usa
esta estructura de datos para implementar las operaciones del tipo vistas en clase.
Universidad de Huelva
Página 2
Estructuras de Datos II
Curso 2005/06
III. Utilización del TAD Lista
(usa iteradores para resolver estos problemas)
9. Escribe una función que dadas dos listas, L1 = (x1, x2, …, xn) y L2 = (y1, y2, ..., ym),
obtenga una lista Z mezcla de ambas. Esto es, Z = (x1, y1, x2, y2, ..., xm, ym, xm+1, xm+2,
..., xn) si m ≤ n o Z = (x1, y1, x2, y2, ... , xn, yn, yn+1, yn+2, ..., ym) si m > n.
10. Escribe un algoritmo que, dadas dos listas ordenadas de menor a mayor, devuelva
otra lista con todos los elementos de las dos listas originales y ordenada también de
menor a mayor.
11. Escribe un algoritmo que dada una lista L devuelva otra lista R conteniendo los
elementos repetidos de L. Por ejemplo, si L almacena los valores 5, 2, 7, 2, 5, 5, 1,
debe construirse una lista R con los valores 5, 2. Si en L no hay elementos repetidos,
R será la lista vacía.
12. Escribe una función que dada una lista L devuelva otra lista I, inversa de L.
13. Escribe un algoritmo que dada una lista L y un valor devuelva dos listas, cada una de
ellas conteniendo, respectivamente, los elementos de L mayores y menores al valor
proporcionado.
14. Escribe una función que dada una lista L, mueva un elemento de posición i, n lugares
hacia delante, si es posible, o al final de L, en caso contrario.
Pseudocódigo
template <typename T>
void mover(Lista<T>& L, int pos, int lugares)
var
int i;
Lista<T>::Iterador it1, it2;
fvar;
inicio
i=1;
it1 = L.ponerIterador(pos);
it2 = it1;
mientras i < lugares+2 ∧ it1 ≠ L.final() hacer
it1.avanzar(L);
i++;
fmientras;
L.insertar(it1, L.observar(it2));
L.eliminar(it2);
fin;
C++ (usando el TAD Lista proporcionado en clase)
template <typename T>
void mover(Lista<T>& L, int pos, int lugares) {
typename Lista<T>::Iterador it1 = L.ponerIterador(pos);
typename Lista<T>::Iterador it2 = it1;
for (int i=1; i < lugares+2 && it1 != L.final(); i++)
it1.avanzar(L);
L.insertar(it1, L.observar(it2));
L.eliminar(it2);
}
Universidad de Huelva
Página 3
Estructuras de Datos II
Curso 2005/06
C++ (usando el TAD list de la STL)
template <typename T>
void mover_STL(list<T>& L, int pos, int lugares) {
typename list<T>::iterator it1 = L.begin();
for (int i=1; i<pos; i++) it1++;
typename list<T>::iterator it2 = it1;
for (int i=1; i < lugares+2 && it1 != L.end(); i++)
it1++;
L.insert(it1, *it2);
L.erase(it2);
}
15. Las listas SelfOrganizing se caracterizan porque cada uno de sus nodos contiene un
campo frecuencia, que indica el número de veces que el nodo ha sido recuperado.
Además, la lista se mantiene en orden descendente según el valor de este campo
frecuencia. Después de cada consulta, el nodo modifica su posición en la lista
colocándose delante de los que tienen un número de accesos inferior a él. Los
nuevos elementos añadidos a la lista se colocan al final con frecuencia 1. Implementa
la operación de consulta observa que devuelve el elemento de la posición i de una
lista SelfOrganizing.
IV. Implementación del TAD Lista
16. Escribe un método que añada un elemento al final de una lista suponiendo las
siguientes implementaciones de la misma:
a) Lista lineal simplemente enlazada con referencia al primer elemento de la
misma.
CLASE NODO
CLASE LISTA
template <typename T>
class Nodo {
typedef Nodo<T>* PtrNodo;
public:
Nodo(const T& objeto);
Nodo(const T& objeto, PtrNodo psig);
Nodo(const Nodo& n);
const T& getObj() const;
PtrNodo getSig() const;
void setObj(const T& objeto);
void setSig(PtrNodo psig);
private:
T obj;
PtrNodo sig;
}
template <typename T>
class Lista {
typedef Nodo<T>* PtrNodo;
public:
void añadirFinal(const T& objeto);
// operaciones del TAD
private:
PtrNodo primero;
int num;
}
Universidad de Huelva
Página 4
Estructuras de Datos II
Curso 2005/06
void añadirFinal(const T& objeto);
var
PtrNodo aux n;
fvar;
inicio
n = nuevo Nodo(objeto);
si esVacia() entonces
primero = n;
sino
aux = primero;
mientras aux ->getSig() ≠ NULO hacer
aux = aux->getSig();
fmientras;
aux->setSig(n);
fsi;
num++;
fin;
b) Lista circular simplemente enlazada.
c) Lista doblemente enlazada con referencias al primer y último elemento de
la misma.
Define las clases que utilices en cada caso.
17. Escribe un método que elimine el último elemento de una lista suponiendo las
siguientes implementaciones de la misma:
a) Lista lineal enlazada con referencias al primer y ultimo elemento de la
misma.
b) Lista lineal enlazada con referencia al primer elemento de la misma y nodo
cabecera.
Define las clases que utilices en cada caso.
18. Dados dos elementos adyacentes (consecutivos) apuntados por p y q, intercámbialos
ajustando sólo los punteros y no los datos. Hazlo suponiendo las siguientes
situaciones:
a) Una lista enlazada de modo simple con un puntero al primer elemento.
b) Una lista doblemente enlazada con un puntero al primer elemento.
19. Tenemos una colección de datos de alumnos que nos interesa ordenar por dos
campos: Nombre y Número de Matrícula. La solución escogida ha sido utilizar una
lista enlazada donde cada nodo tiene dos campos de enlace: uno para ordenar
ascendentemente los nodos según su nombre y otro para ordenar descendentemente
los nodos según el número de matrícula del alumno. Define los tipos de datos
necesarios y escribe un método que inserte un nuevo elemento en la estructura. Este
tipo de listas ordenadas por más de un criterio se denominan multilistas.
Universidad de Huelva
Página 5
Estructuras de Datos II
Curso 2005/06
20. Supongamos la siguiente estructura para almacenamiento de una secuencia de
elementos clasificados en orden ascendente. Cada elemento está enlazado con su
anterior y su siguiente. Se mantiene, además, un puntero a la posición central de la
secuencia. ¿Qué ventajas e inconvenientes tiene esta estructura? Define los tipos de
datos más adecuados para soportar esta estructura. Implementa una operación que
permita insertar un elemento e. Las inserciones se realizan manteniendo el orden de
los elementos y el apuntador al elemento central.
L
B
O
S
21. Sea la siguiente lista circular doblemente enlazada que utiliza nodo cabecera. Define
los tipos de datos utilizados e implementa todas las operaciones del TAD Lista.
V. Definición de TAD usando el TAD Lista
22. Una lista de frecuencias es un TAD que mantiene un listado alfabético de todas las
palabras que aparecen en un conjunto de textos. Por razones de eficiencia, y
pensando que se va a utilizar dicho tipo para almacenar frecuencias de palabras de
muchos documentos, se ha optado por utilizar varias listas pequeñas ordenadas en
lugar de una sola lista con todas las palabras. De esta forma, se tendrá una lista
ordenada de las palabras que comienzan por 'a', otra lista ordenada con las palabras
que empiezan por 'b', y así sucesivamente. Por tanto, tendremos un array con índices
'a'..'z', conteniendo cada una de estas listas. Además, para cada palabra,
necesitamos almacenar el número de cada uno de los documentos en los que
aparece y con qué frecuencia. Implementa el TAD lista de frecuencias.
23. Se trata de desarrollar un TAD Mercado que modele el comportamiento de un
mercado de trabajo simplificado, donde las personas pueden ser contratadas y
despedidas por empresas. Para ello se ha pensado utilizar una lista ordenada de
empresas (ascendentemente por su nombre), de manera que a cada empresa de la
lista se le asocia una lista ordenada de empleados contratados (también,
ascendentemente por su nombre).
Universidad de Huelva
Página 6
Estructuras de Datos II
Curso 2005/06
La información que interesa disponer de las empresas es su nombre, y la lista de
empleados contratados. De los empleados se conoce su nombre.
Se ha considerado interesante poder hacer las siguientes operaciones con el
mercado:
void contrata(const string& nomEmpresa, const string& nomEmpleado)
throw (EmpresaInexistenteExcepcion, EmpleadoYaContratadoExcepcion)
Modifica el mercado de trabajo, efectuando la contratación de nomEmpleado como empleado de
nomEmpresa. La empresa debe pertenecer al mercado de trabajo, mientras que el trabajador no
debe aparecer como empleado de la misma.
void despide(const string& nomEmpresa, const string& nomEmpleado)
throw (EmpresaInexistenteExcepcion, EmpleadoNoContratadoExcepcion)
Modifica el mercado de trabajo, efectuando el despido de nomEmpleado que es empleado de
nomEmpresa.
void nuevaEmpresa(const string& nomEmpresa) throw (EmpresaYaExisteExcepcion)
Añade una nueva empresa al mercado de trabajo.
bool esEmpleado(const string& nomEmpresa, const string& nomEmpleado)
throw (EmpresaInexistenteExcepcion)
Indica si nomEmpleado es empleado de nomEmpresa.
bool esPluriempleado(const string& nomEmpleado) throw (EmpleadoNoContratadoExcepcion)
Indica si nomEmpleado es empleado de más de una empresa.
Se pide construir una clase que, usando el TAD Lista, implemente el TAD Mercado.
24. Se desea implementar un TAD Consultorio que modele el comportamiento de un
consultorio médico. Para ello se ha pensado utilizar una lista ordenada de médicos
(ascendentemente por su nombre), de manera que a cada médico de la lista se le
asocia su cola de pacientes en espera de ser atendidos.
La información que nos interesa de los médicos es su nombre y la cola de pacientes
en espera. De los pacientes nos interesa su nombre.
Se ha considerado interesante poder hacer las siguientes operaciones con el
consultorio:
void nuevoMedico(const string& nomMed) throw (MedicoYaExisteExcepcion)
Modifica el consultorio, añadiendo un nuevo médico que antes no figuraba en el consultorio.
void pideConsulta(const string& nomMed, const string& nomPac) throw (MedicoInexistenteExcepcion)
Modifica el consultorio, haciendo que el paciente de nombre nomPac se ponga a la espera para ser
atendido por el médico nomMed. El médico debe pertenecer al consultorio.
const string& siguientePaciente(const string& nomMed)
throw (MedicoInexistenteExcepcion, SinPacientesExcepcion)
Devuelve el paciente a quien le toca el próximo turno para ser atendido por el médico nomMed. Éste
debe pertenecer al consultorio y tener algún paciente por atender.
void atiendeConsulta(const string& nomMed)
throw (MedicoInexistenteExcepcion, SinPacientesExcepcion)
Modifica la estructura consultorio, eliminando el paciente al que le toca turno para ser atendido por el
médico nomMed. Éste debe pertenecer al consultorio y tener algún paciente por atender.
Universidad de Huelva
Página 7
Estructuras de Datos II
Curso 2005/06
bool tienePacientes(const string& nomMed) throw (MedicoInexistenteExcepcion)
Devuelve si hay o no pacientes a la espera de ser atendidos por un médico, el cual debe pertenecer
al consultorio.
Se pide construir una clase que, usando los TAD Lista y Cola, implemente el TAD
Consultorio.
A continuación aparece implementada la clase Médico y el método pideConsulta de la clase Consultorio.
El resto de métodos de esta clase quedan propuestos para el alumno.
CLASE MÉDICO
typedef string Paciente;
typedef cola<Paciente> CP;
class Medico{
public:
Medico(const string& nombre);
CP& getPacientes();
const string& getMedico() const;
void setPacientes(const CP& c);
void setMedico(const string& nombre);
private:
string nm;
CP
pacientes;
};
Medico(const string& nombre): nm(nombre), pacientes()
inicio
fin;
CP& getPacientes()
inicio
devolver pacientes;
fin;
const string& getMedico() const {
inicio
devolver nm;
fin;
void setPacientes(const CP& c) {
inicio
pacientes = c;
fin;
void setMedico(const string& nombre) {
inicio
nm = nombre;
fin;
Universidad de Huelva
Página 8
Estructuras de Datos II
Curso 2005/06
CLASE CONSULTORIO
typedef lista<Medico> LM;
typedef LM::iterador ILM;
class Consultorio {
public:
Consultorio();
void pideConsulta(const string& nomMed, const string& nomPac)
throw (MedicoInexistenteExcepcion);
// resto de métodos
private:
LM consulta;
};
void pideConsulta(const string& nomMed, const string& nomPac)
throw (MedicoInexistenteExcepcion){
var
ILM it;
fvar;
inicio
it = consulta.pricipio();
mientras it ≠ consulta.fin() ∧ it->getMedico() < nomMed hacer
it .avanzar(consulta);
fmientras;
si it == consulta.fin() ∨ it->getMedico() > nomMed entonces
lanzar MedicoInexistenteExcepcion(nomMed);
fsi;
it->getPacientes().añadir(nomPac);
fin;
Universidad de Huelva
Página 9