Download 1) Implementar el TAD Pilas utilizando memoria estática. Se

8QLYHUVLGDG5H\-XDQ&DUORV
,QJHQLHUtD7pFQLFDHQ,QIRUPiWLFDGH*HVWLyQ
$VLJQDWXUD(VWUXFWXUDVGH'DWRV\GHOD,QIRUPDFLyQ
+2-$'(352%/(0$61ž
3LODV\&RODV
1) Implementar el TAD 3LODV utilizando memoria estática. Se recuerda que una forma de implementar
una pila con memoria estática es mediante un vector de elementos y la posición del último elemento
ocupado (que será la cima de la pila).
2) (Febrero 01) Dada la especificación algebraica del TAD 3LODV, se extiende dicha especificación con la
operación 0LVWHULR, cuya sintaxis y semántica se describe a continuación:
3$5È0(7526*(1e5,&26
23(5$&,21(6
Propiedad: TipoElemento -> Booleano
),13$5È0(7526
Misterio: TipoPila -> TipoPila
Misterio (CrearPilaVacia) = CrearPilaVacia
Misterio (Apilar(e, pila)) =
6, Propiedad(e) !
Apilar(e, Misterio(pila))
_CrearPilaVacia
a) Sea 3 la pila de números naturales obtenida partiendo de una pila vacía y apilando
sucesivamente los elementos 5,4,3 y 10, y 3 la pila obtenida partiendo de una pila vacía y
apilando sucesivamente los elementos 10, 6, 1 y 2. Aplicar las ecuaciones de la operación
0LVWHULR paso a paso, en ambos casos, suponiendo que el parámetro genérico 3URSLHGDG es una
operación que devuelve cierto si y sólo si el número natural de entrada es menor o igual que 5.
b) Explicar en una frase qué hace, en el caso general, dicha operación. ¿Qué haría si en su semántica
se sustituye la última línea de la segunda ecuación por Misterio(pila)?
3) (Junio 01) Se desea extender el TAD 3LODV y su implementación en $GD con la operación
denominada (OLPLQDU1, que recibe como entrada una pila QRYDFtD y un número positivo Q y devuelve
como salida la pila resultante de eliminar de la pila de entrada el elemento situado en la posición Q (la
cima de la pila es el elemento situado en la posición 1). En caso de que la posición especificada no
exista, el resultado será la pila de entrada. Ejemplos: Si las pilas se representasen enumerando sus
elementos uno detrás de otro y empezando por la cima:
([e1,e2,e3], 1) = [e2,e3]
(OLPLQDU1([e1,e2,e3], 3) = [e1,e2]
([e1,e2,e3], 2) = [e1,e3]
(OLPLQDU1([e1,e2,e3], 5) = [e1,e2,e3]
(OLPLQDU1
(OLPLQDU1
a) Especificar algebraicamente la extensión propuesta.
b) Implementar en $GD la extensión anterior mediante un paquete hijo del paquete 3LODV del que
se deberá facilitar tanto su interfaz (fichero DGV) como su cuerpo (fichero DGE). Se deberán
cumplir obligatoriamente los tres siguientes requisitos: (1) la implementación deberá hacerse
LWHUDWLYDPHQWH; (2) debe PRGLILFDU la pila de entrada en lugar de crear una nueva y (3) QRVHGHEH
XWLOL]DU la representación interna del TAD.
1
4) (Febrero 01) Se considera una cola de caracteres, implementada mediante un YHFWRU FLUFXODU FRQ
FDPSRORQJLWXG, cuya situación, después de realizar una serie de operaciones, es la siguiente:
1
2
3
4
5
6
7
8
9
10
A
B
C
D
E
F
G
H
I
J
primero = 3
último = 8
longitud = 6
Se pide:
a) Partiendo del estado anterior, describir las situaciones intermedias de la estructura después de
aplicar de forma consecutiva FDGDXQD de las operaciones que se indican a continuación. En caso
de que alguna de estas operaciones no pueda llevarse a cabo, se indicará el motivo y se ignorará,
continuando por la siguiente.
Insertar(K) ; Eliminar ; Insertar(L) ; Insertar(M) ; Insertar(N) ; Insertar(O) ; Insertar(P) ; Eliminar
b) Una vez realizadas las operaciones anteriores, ¿cuál sería el resultado de ejecutar la operación
3ULPHUR&ROD?
c) Indicar, MXVWLILFDQGR la respuesta, cómo debe declararse el tipo de datos 7LSR&ROD PRIVATE o
LIMITED PRIVATE, al implementar una cola en $GD mediante un vector circular con campo
longitud.
5) Implementar el TAD &RODV utilizando una lista como representación interna.
6) (Septiembre 01) El presente ejercicio se refiere al TAD &RODVGH3ULRULGDG. Se recuerda que cuando el
tipo de datos que representa las prioridades, 7LSR3ULRULGDG, es un tipo de datos discreto, una posible
forma de implementar dicho TAD es mediante un vector cuyos índices son los elementos de
7LSR3ULRULGDG y donde en cada posición se mantiene una cola (normal) con todos los elementos que
tienen esa misma prioridad.
Dada la implementación en $GD del TAD &RODV implementado con el TAD /LVWDV (ejercicio
anterior) construir un paquete en $GD que implemente el TAD &RODV GH 3ULRULGDG de forma que
7LSR3ULRULGDG sea un tipo de datos discreto y la representación interna consista en el vector de colas
citado.
7) En la implementación del TAD &RODV mediante un vector y campo longitud no es necesario el
campo ILQDO. Modificar la implementación vista en clase eliminando dicho campo.
2
8) Se dispone de un fichero de texto compuesto por dígitos, colocados en varias líneas. Los
dígitos de cada línea se corresponden con un número entero. Se desea realizar la suma de
todos esos números. Puesto que cada número puede tener una gran cantidad de dígitos, es
posible que no quepa en una variable de tipo entero, por lo que tenemos que construir un
algoritmo que sume las unidades, después las decenas junto con el acarreo de las unidades,
etc. Además hay que tener en cuenta que los números pueden tener distinta cantidad de
dígitos y que el primero que aparece es el de mayor peso. Una forma de realizar la suma entre
dos números es la siguiente: (1) almacenar el primer número en una pila de dígitos de forma
que en la cima quede el dígito de menor peso (unidades); (2) almacenar el segundo número en
una cola de dígitos de forma que el primer elemento de la cola sea el dígito de las unidades;
(3) realizar P veces (siendo P el mínimo de las longitudes) lo siguiente: sacar un dígito de la
pila, uno de la cola, sumarlos junto con el posible acarreo producido en el paso anterior, e
introducir la unidad resultante de nuevo en la cola, guardando el posible acarreo para el paso
siguiente; (4) si la pila no está vacía o la cola tiene todavía dígitos correspondientes al número
inicial, sacarlos e introducirlos en la cola (teniendo en cuenta otra vez los posibles acarreos
producidos por el acarreo resultante del paso (3)). Al terminar el paso (4) la cola contendrá la
suma de los dos números originales.
Así, para sumar todos los números del fichero bastará con partir de una cola vacía, y, para
cada número leído del fichero: almacenarlo en una pila y aplicar el algoritmo anterior para
sumar la pila con la cola. Al final, la cola contendrá la suma de todos los números leídos del
fichero.
Escribir un programa en Ada95 que implemente el proceso anterior utilizando los TAD
Colas y Pilas, mostrando por pantalla la suma de los números.
3