Sadasd

Estructuras de Datos y de la Información Universidad Europea de Madrid

Ejercicios Tema3: Listas, Pilas y Colas

1.

Dado el TAD Polinomio(correspondiente a los polinomios con exponentes enteros no negativos de un única variable x), se pide: A. implementar la clase Polinomio con las siguientes operaciones: • Crear (P): inicializa P al polinomio cero. • Grado (P): devuelve el grado delpolinomio P. • Asignar (P, I, valor): asigna valor al coeficiente del término de grado I del polinomio P. • Obtener (P,I): devuelve el valor del coeficiente del término de grado I en el polinomio P. Realizar la implementación utilizando alguna de las estructuras lineales vistas en clase. Razonar la elección de dicha estructura. B. Agregar a la clase Polinomio la operación SUMA, que deberá sumar dospolinomios y devolver el resultado en uno nuevo, y tiene la siguiente signatura: SUMA: POLINOMIO x POLINOMIO POLINOMIO Agregar a la clase Polinomio la operación PRODUCTO, que deberá multiplicar dos polinomios y devolver el resultado en uno nuevo, y tiene la siguiente signatura: PRODUCTO: POLINOMIO x POLINOMIO POLINOMIO

C.

Nota: Implementar los métodos de los apartados B y C para que seanindependientes de la implementación elegida.

2.

En un procesador de texto se quiere implementar un mecanismo de desplazamiento vertical de la pantalla (scrolling) que permita descender por el texto, guardando las líneas que van desapareciendo por la parte de arriba de la pantalla, y ascender por el texto, guardando las líneas que van desapareciendo por la parte inferior de la pantalla. Sugerirvarias representaciones que utilicen las diferentes estructuras lineales vistas en clase. Dada una cadena de caracteres que representa una expresión aritmética en notación posfija, redactar un programa que convierta dicha expresión a notación infija. Los caracteres que pueden formar parte de una expresión son '+', '-', '*', '/', que representan los operadores correspondientes, o bien caracteresalfabéticos cualesquiera que representan variables. Por ejemplo, 'X' representa la variable X, etc. Los nombres de las variables no pueden tener más de un carácter. La expresión no contendrá ningún espacio en blanco, tabulador, salto de línea, etc. Para realizar la transformación a notación infija se recorrerá la cadena de izquierda a derecha. Cuando se detecte un operador, se sustituirán los dosoperandos situados inmediatamente antes del operador por una cadena formada por '(operando1 operador operando2)', por ejemplo: XY+ se sustituirá por (X+Y)

3.

Nótese que cada operando puede ser o bien una letra o bien una expresión entre paréntesis (consecuencia de una transformación anterior). A continuación se seguirá el proceso hacia la derecha hasta que se acabe la cadena. Por ejemplo, si lacadena de entrada es: XY-XY*YZ+/+ la salida será ((X-Y)+((X*Y)/(Y+Z))) Sugerencia: Utilizar una pila de cadenas de caracteres para ir almacenando los operandos y considerar implementadas todas las operaciones de pilas. Curso 2006-07 Pág. 1 de 4

Estructuras de Datos y de la Información Universidad Europea de Madrid

Ejercicios Tema3: Listas, Pilas y Colas

4. 5.

Construir un procedimientoque evalue una expresión en postfija. Supóngase un nuevo TAD denominado ColaDF (cola de doble fin) que es una variación del TAD Cola en el que se pueden añadir y suprimir elementos por ambos extremos. Definir las operaciones necesarias, implementarlas utilizando representaciones secuencial y enlazada y comparar la eficiencia. Una tienda dispone de dos almacenes, cada uno de los cuales tienealmacenados una serie de productos. Sea L1 la lista de productos del almacén 1 representada en forma enlazada y ordenada por orden alfabético creciente. Sea L2 la lista equivalente para el almacén 2, ordenada de la misma forma. Se pide: A. B. Escribir el procedimiento Total que tenga como entradas las listas L1 y L2 y como salida la lista unión de ambas, es decir, una lista con todos los productos...