URJC _Universidad Rey Juan Carlos_ _ Ingeniería Informática _ Apuntes_practicas y exámenes de pascal _ Estructura

Esta es una vista previa del archivo. Inicie sesión para ver el archivo original

Estructura de Datos/Practicas y ejercicios/EjercicioConcesionarios_Soto_Junio2013_ED_Vicalvaro.pdf
 Estructuras de Datos 
14 de Junio de 2013 
Ejercicio 
La asociación de vendedores de coches en España quiere tener automatizado todo el proceso 
de acceso a la información relacionada con la venta de coches por toda la geografía española. 
Para ello deben tener registrada toda la información de los diferentes concesionarios de venta 
de coches en todo el país. 
Algunos concesionarios sólo venden coches de una marca, mientras que otros pueden vender 
coches de varias marcas. Cada concesionario tendrá una dirección postal diferente, y pueden 
tener más o menos coches en venta, pudiendo variar la cantidad de coches que venden 
constantemente y, en el caso de concesionarios que venden más de una marca, también 
pueden aumentar o eliminar las marcas que venden. 
A su vez, pueden surgir nuevos concesionarios de venta en aquellas zonas donde el mercado 
lo demande, o cerrar algunos concesionarios si no son rentables. 
Se proporciona la siguiente interfaz para el TAD TCoche. Además se muestra cómo la marca 
de los coches se identificará en la aplicación mediante un código numérico entero. 
 
 
 
 
 
 
 
 
Se pide: 
a) Definir los tipos TConcesionario y TRedConcesionarios. Explicar de forma 
razonada la definición de tipos que se haga en cada caso. Se pretende que el acceso 
a la información de los concesionarios, así como la modificación de esta 
información sea lo más eficiente posible. 
b) Implementar una operación para añadir un nuevo concesionario a la red de 
concesionarios. Se indicará cuál es su dirección postal, además del listado de marcas 
(o una única marca) de coches que podrá vender. Se valorará positivamente la 
eficiencia a la hora de hacer esta operación. 
c) Implementar una operación que permita añadir un nuevo coche para vender en un 
concesionario determinado. Se indicará por lo tanto la dirección postal del 
concesionario donde se añadirá un nuevo coche, la marca del coche y el propio 
coche a vender. 
c) Implementar una operación para eliminar la venta de coches de una determinada 
marca de un concesionario determinado. Para ello se proporciona la dirección del 
concesionario y la marca cuyos coches se dejan de vender en el concesionario. En 
caso de quedarse sin ninguna marca, el concesionario se cerrará. 
 
Nota: Todas las operaciones nuevas que vayan surgiendo, tanto del TAD TCoche, como de 
los TADs TConcesionario y TRedConcesionarios, deberán implementarse, asegurando que 
cada operación es implementada en el TAD que le corresponde. 
INTERFACE 
TYPE 
TCoche = RECORD 
 modelo: string; 
 color: string; 
END; 
PROCEDURE Inicializar (VAR c:TCoche; mod, col: STRING); 
PROCEDURE InicializarTeclado(VAR c: TCoche); 
PROCEDURE Imprimir(c: TCoche); 
… 
 
IMPLEMENTATION … END. 
CÓDIGOS DE LAS 
MARCAS DE COCHES: 
1 -> Toyota 
2 -> Renault 
3 -> Mercedes 
4 -> Audi 
5 -> Mazda 
6 -> Opel 
7 -> Kia 
… 
Estructura de Datos/Practicas y ejercicios/ejercicio_prueba_escrita_mayo2014_GII_vicalvaro.pdf
 
Estructuras de Datos 
 Mayo de 2014 
 
1) (Prueba escrita práctica, 4 puntos) El mundial de fútbol se acerca. Se desea modelar el 
campeonato a través de la estructuración de las diferentes selecciones. Ya se conoce que 
los grupos A-H serán los siguientes: 
Grupo A: Brasil, Croacia, Camerún, México. 
Grupo B. España, Chile, Australia, Holanda. 
Grupo C. Colombia, Costa de Marfil, Japón, Grecia. 
Grupo D. Uruguay, Italia, Costa Rica, Inglaterra. 
Grupo E. Suiza, Ecuador, Honduras, Francia. 
Grupo F. Argentina, Nigeria, Irán, Bosnia – Herzegovina. 
Grupo G. Alemania, Ghana, Estados Unidos, Portugal. 
Grupo H. Bélgica, Algeria, Corea del Sur, Rusia. 
Además, supongamos que cada selección puede llevar un máximo de 23 jugadores (mínimo 
15), 3 técnicos (mínimo 1) y 2 médicos (no hay mínimo), pero cada comité nacional decide 
cómo llenarlo (dentro de los mínimos y máximos, por ejemplo 15, 1, 0 de cada tipo, 20, 2, 1, o 
cualquier otra combinación válida). 
a) (0.5 puntos) Escriba el código en Pascal para definir una estructura eficiente que pueda 
contener toda la información de los 8 Grupos, de manera que se tenga acceso en O(1) a cada 
grupo mediante su identificador de Grupo (char) y acceso a cada selección dentro del grupo 
en O(n) mediante el nombre de la selección (de tipo TCountryTeam definido en otra unidad 
independiente y básicamente de tipo string). Dentro de la selección se podrá iterar por la 
lista de convocados de forma lineal. Para desglosar los miembros convocados entre jugadores, 
técnicos y médicos se utilizará un tipo TMemberType con una codificación que indicará ‘P’= 
player (jugador), . ‘T’= tech (técnico), ‘D’= doctor (médico), para cada miembro del equipo. La 
información personal de cada miembro vendrá dada por un tipo TMember definido en otra 
unidad (habrá que dejar disponible pero no hará falta crear). 
b) (1 punto) Escriba el código en Pascal de los subprogramas necesarios para insertar en la 
estructura anterior los equipos en sus correspondientes grupos. Como no se conocen qué 
miembros seleccionados irán en cada equipo, bastará con introducir los nombres de los 
equipos y dejar su estructura de equipo vacía. 
c) (1.5 punto) Escriba el código en Pascal de los subprogramas necesarios para insertar en cada 
equipo la información de sus miembros teniendo en cuenta que se deja disponible un 
subprograma con prototipo: 
PROCEDURE ReadMemberFromDisk(country: TCountryTeam; VAR member: 
TMember; VAR type:TMemberType; VAR error: Boolean) que cada vez que se le 
invoca con el identificador de una selección (TCountryTeam) devuelve, o bien la información 
personal del miembro, su tipo (‘P’, ‘T’, ‘D’) y error a FALSE, o directamente basura y error a 
TRUE si no hay más información que cargar para esa determinada selección. 
d) (1 punto) Se dispone de una función que devuelve el número de goles que ha marcado un 
miembro TMember de tipo ‘P’ (jugador, “player “como TMemberType) que se le pasa. 
Supongamos su prototipo: 
FUNCTION GetGoalsNumber(player: TMember): integer; 
Se pide crear el listado de selecciones (de tipos TCountryTeam) más goleadoras (de mayor a 
menor). Los goles de cada selección se calcularán mediante la suma de goles de todos sus 
jugadores. 
Estructura de Datos/Practicas y ejercicios/ExamenMayo2015_GII_vicalvaro.pdf
 
Estructuras de Datos 
 Mayo de 2015 
 
APELLIDOS: __GII __GII+ADE NOMBRE: 
TITULACIÓN: DNI: 
Duración: 1:45 h. 
Calificación: 
 Se recuerda que, según la guía docente, el 15% de la nota final se corresponde con pruebas 
prácticas realizadas, 25% con prueba escrita teórica y 60% con prueba escrita práctica. Se 
sugiere dejar 1 hora de esfuerzo en la resolución del ejercicio 5. Contestar en la hoja de 
enunciados los 4 primeros ejercicios. 
 
1) (Prueba escrita teoría, 0.5 puntos) Resuma brevemente las características más importantes 
de un grafo ponderado y dirigido en representación estática frente a su representación 
dinámica. A continuación defina un tipo Grafo en representación de listas de adyacencia 
con un TElemento genérico definido en otra unidad. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2) (Prueba escrita teoría, 1 punto) Calcule, mediante el método de expansión de recurrencias 
visto en clase, la complejidad algorítmica en notación O() del algoritmo del Búsqueda 
binaria o dicotómica en el que se busca un elemento en una lista de valores ordenados. 
Además, si se dispone de un array de 4096 valores, ¿cuántas llamadas recursivas se deben 
realizar para llegar al caso base? Justifique matemáticamente su respuesta. 
 
 
 
 
 
 
 
 
 
 
 
 
 
3) (Prueba escrita teoría, 1 punto) Especificar algebraicamente, tal y como se ha visto en clase, 
la sintaxis y la semántica de las operaciones Espejo y Postorden de árboles binarios.
Utilice 
las operaciones de la especificación de árboles binarios vista en clase que necesite. 
 
 
 
 
 
 
 
4) (Prueba escrita práctica, 2 puntos) Defina el tipo de dato para crear una estructura 
dinámica doblemente enlazada tipo FIFO (first input, first output) cuyo orden de 
complejidad en inserción y extracción sea de O(1). El tipo elemento que guarde puede ser 
de tipo TElemento genérico (que estaría definido en otra unidad). A continuación, realizar 
los procedimientos de Insertar y Eliminar. 
 
 
 
 
 
 
 
 
 
 
 
 
 
5) (Prueba escrita práctica, 4 puntos) ELECCIONES 
Como estamos en temporada de elecciones se desea modelar un novedoso problema de 
sistemas electorales. 
 
En el país de Nunca Jamas, los ciudadanos pueden distribuir su voto entre varios candidatos, 
reflejando así sus preferencias con gran precisión, tal como expresa su lema “Una persona, 
cien votos”, característico de aquel pequeño país. Además, pueden emitirse fantásticos votos 
de castigo (negativos). 
 
Para votar, los Nuncajamasienses rellenan una papeleta en la que reparten un máximo de 100 
puntos (positivos o negativos, cuenta en valor absoluto) entre los partidos políticos que se 
presentan a los comicios. La validez de una papeleta consiste en que la suma de los valores 
absolutos de los puntos asignados a los candidatos no supere los 100 puntos. 
 
Desgraciadamente el número de partidos políticos es desconocido hasta el día de la votación, 
aunque los aspirantes a presidentes son viejos conocidos de todos y definen el nombre de su 
partido, tales como los famosos partidos MarianoGarzón, PabloSanchez, PedroIglesias, 
AlbertRajoy, AlbertoDiez, RosaRivera, y otros muchos que a veces se presentan. 
 
Por si fuera poco, y para la desgracia de los Nuncajamasienses, las papeletas que depositan en 
las urnas tienen un campo de DNI y edad del votante, que sirven para invalidar votos repetidos 
o de menores de 25 años (y posiblemente para aplicarles algún tipo de castigo), y espacio para 
apuntar los votos que se asignan a cada partido (dado que no se sabe cuántos partidos se 
presentan pero todos tienen que recibir puntos, ya sean negativos, cero o positivos). Para 
controlar el peligro de votos repetidos hay un censo con la información de todos los 
ciudadanos. 
 
Para el recuento de votos, si bien todos cuentan, no lo hacen por igual, sino que lo hacen 
proporcionalmente a la edad del votante. Cada voto va pesado por un factor 0,01*edad (de 
manera que un voto de ciudadano de 30 años cuenta 0,3 mientras que de uno de 100 cuenta 
1,0 puntos). 
 
El mecanismo electoral pone a cero una tabla de marcadores con el nombre del partido y los 
votos que va obteniendo al objeto de contar los puntos de cada candidato. Se pide: 
 
a) [0.5 punto] Definir en PASCAL los tipos de datos para la papeleta, la tabla de marcadores 
con nombre de partido y puntuación entera para el recuento final, y una estructura para el 
censo electoral, que registre el DNI de cada votante, su edad, un campo para conocer si ha 
votado o no, y los puntos que ha asignado a cada candidato electoral. Esta última 
estructura fue creada por los Servicios Inteligentes de Nunca Jamás como estructura de 
búsqueda en la que, en casos habituales, suele ser más rápida que el listado (aunque no se 
garantice). Hacer también el subprograma para inicializar una tabla de marcadores a cero y 
un subprograma que, dada una papeleta, la valide o invalide (devolviendo un valor 
booleano). 
 
 
b) [1 puntos] Escribir los tipos de datos y los subprogramas necesarios para que se registre en 
la estructura del censo electoral el voto válido de un ciudadano. Inicialmente el censo 
tiene los datos de sus ciudadanos (DNI, nombre, edad y el campo de haber votado a falso) 
salvo la puntuación que asigna a los partidos. Todos los votos que se registran se suponen 
válidos. Para registrar el voto en el censo se busca al ciudadano por DNI y, si no ha votado 
antes y es una papeleta válida, se inserta la información de su papeleta (nadie sabe lo que 
le pasa a un ciudadano que vota por duplicado o incorrectamente, pero nada bueno, su 
campo de voto queda a falso para siempre). 
 
 
c) [1.5 punto] Escribir los subprogramas necesarios para que, dada una tabla de marcadores 
y la estructura de censo electoral, añada los puntos consignados en el censo de todos los 
ciudadanos que han votado a la tabla de marcadores. Como se sabe, los puntos que 
corresponden a un candidato se calculan multiplicando los puntos que tiene asignados en 
la papeleta multiplicados por la edad del votante con su factor de corrección. 
 
 
d) [1 punto] Tradicionalmente, el candidato ganador quiere conocer la identidad de sus 
ciudadanos más devotos para colocarlos en los puestos más destacados de su gobierno. 
Para ello, los Servicios Secretos utilizan el censo para la identificación de los 10 votantes 
que más puntos han aportado (teniendo en cuenta su edad) a la elección del ganador. 
Define tipos de datos, si fuera necesario, y escribe un subprograma que devuelva la 
estructura que guarde los 10 votantes que más han colaborado al triunfo del ganador 
junto con la puntuación, ordenados de mayor a menor aportación. 
Estructura de Datos/Practicas y ejercicios/hojaProblemasComplejidad.pdf
 1 
Universidad Rey Juan Carlos 
1º GII/GII+ADE (Vicálvaro) 
 
Asignatura: Estructuras de Datos 
 
HOJA DE PROBLEMAS Nº 1: Complejidad de Algoritmos 
____________________________________________________________ 
 
Estudio de la complejidad (tiempo de ejecución en el peor caso) de algoritmos. 
 
1) Calcular la complejidad de los siguientes trozos de algoritmos en función de n. 
 
a) x := 0; 
PARA i DESDE 1 HASTA n HACER 
 PARA j DESDE 1 HASTA n HACER 
PARA k DESDE 1 HASTA n HACER 
 x := x + 1; 
 
b) x := 0; 
SI (n MOD 2 /= 0) ENTONCES 
 PARA i DESDE 1 HASTA n HACER 
 PARA j DESDE 1 HASTA i HACER 
 x := x + 1; 
SI NO 
 X := -1; 
 
c) x := 0; 
PARA i DESDE 1 HASTA n HACER 
 PARA j DESDE 1 HASTA n
2
 HACER 
 PARA k DESDE 1 HASTA n
3
 HACER 
 x := x + 1; 
 
d) x := 0; 
PARA i DESDE 1 HASTA n HACER 
 PARA j DESDE 1 HASTA i HACER 
 PARA k DESDE j HASTA n HACER 
 x := x + 1; 
 
2) Algoritmo iterativo para hallar el máximo de un vector v con n elementos. 
 
máximo := v(1); 
PARA i DESDE 2 HASTA n HACER 
 SI v(i)>máximo ENTONCES máximo := v(i) 
 
3) Algoritmo para ordenar de menor a mayor un vector v con n elementos (ordenación por selección). 
(se supondrá que la operación Intercambiar tiene un tiempo de ejecución constante). 
 
PARA i DESDE 1 HASTA n-1 HACER 
 pmin := i; 
 PARA j DESDE i+1 HASTA n HACER 
 SI v(j) < v(pmin) ENTONCES pmin := j; 
 Intercambiar(v(i), v(pmin)); 
 2 
4) Algoritmo para ordenar de menor a mayor un vector v con n elementos (ordenación por el método de 
inserción). 
 
PARA i DESDE 2 HASTA n HACER 
 pos := i; 
 x := v(i); 
 seguir := CIERTO; 
 MIENTRAS pos>1 y seguir HACER 
 SI x < v(pos-1) ENTONCES 
v(pos) := v(pos-1) 
SI NO seguir:= FALSO; 
 pos := pos – 1; 
 v(pos):= x; 
 
5) Algoritmo para ordenar de menor a mayor un vector v con n elementos (ordenación por el método de 
la burbuja). (se supondrá que la operación Intercambiar tiene un tiempo de ejecución constante). 
 
paso := 1; 
intercambio := CIERTO; 
MIENTRAS (paso <= n-1) Y intercambio HACER 
 intercambio := FALSO; 
 PARA i DESDE 1 HASTA n-paso HACER 
 SI v(i) > v(i+1) ENTONCES 
 Intercambiar(v(i),v(i+1)); 
 Intercambio := CIERTO; 
 paso := paso + 1; 
 
6) Algoritmo para buscar secuencialmente un elemento en un vector v con n elementos. 
 
FUNCIÓN Buscar (v:TipoVecor; buscado:TipoElemento) DEVUELVE Booleano 
i := 1; 
MIENTRAS (i<=n) Y (v(i)/=buscado) HACER 
 i := i + 1; 
 DEVOLVER i<=n; 
 
7) Algoritmo iterativo para buscar un elemento en un vector ordenado v con n elementos mediante 
búsqueda binaria. 
 
FUNCIÓN Pertenece(v:TipoVector;buscado:TipoElemento)
DEVUELVE Booleano 
bajo := 1; 
alto := n; 
encontrado := CIERTO; 
REPETIR 
 medio := (bajo + alto) DIV 2; 
 SI v(medio) = buscado ENTONCES 
encontrado := CIERTO; 
 SI NO 
SI v(medio)<buscado ENTONCES 
 bajo := medio + 1; 
SI NO 
 alto := medio – 1; 
 HASTA QUE encontrado O bajo>alto; 
DEVOLVER encontrado; 
 3 
8) Algoritmo recursivo para buscar un elemento en un vector ordenado v con n elementos mediante 
búsqueda binaria. 
 
FUNCIÓN Pertenece(v:TipoVector; comienzo, final: TipoPosicion; 
buscado:TipoElemento) DEVUELVE Booleano 
 
 SI comienzo = final ENTONCES 
DEVOLVER v(comienzo)=buscado; 
 SI NO 
 medio := (comienzo + final) DIV 2; 
 SI buscado = v(medio) ENTONCES 
 DEVOLVER CIERTO 
 SI NO 
 SI buscado < v(medio) ENTONCES 
 DEVOLVER Pertenece(v,comienzo,medio-1,buscado) 
 SI NO 
 DEVOLVER Pertenece(v,medio+1,final,buscado) 
 
 
9) Algoritmo iterativo para hallar el factorial de un número natural n 
 
fact := 1; 
PARA i DESDE 1 HASTA n HACER 
 fact := fact * i; 
 
10) Algoritmo recursivo para hallar el factorial de un número natural n 
 
FUNCIÓN Factorial (n: Natural) DEVUELVE Natural 
SI n=0 ENTONCES 
 DEVOLVER 1; 
SI NO 
 DEVOLVER n*Factorial(n-1); 
 
 
11) Algoritmo para hallar el n-ésimo elemento de la sucesión de Fibonacci 
 
La sucesión de Fibonacci se define, para números naturales, de la siguiente forma: 
 






e.o.c)2Fibonacci()1Fibonacci(
1 si1
)Fibonacci(
n-n-
n
n 
 
Un algoritmo para calcular el n-ésimo término de la sucesión es el siguiente: 
 
SI n<=1 ENTONCES 
 fib_n := 1; 
SI NO 
 fib_menor := 1; 
 fib_mayor := 1; 
 PARA i DESDE 2 HASTA n HACER 
 aux := fib_menor; 
 fib_menor := fib_mayor; 
 fib_mayor := aux + fib_mayor; 
 fib_n := fib_mayor; 
Estructura de Datos/Practicas y ejercicios/Informacion de la reserva de NIIRONENORDUNA - ALBERTO SEBASTIAN - YL9PIR.pdf
Gracias por volar con Norwegian
 
Norwegian Air Shuttle - PB 115, N-1366 Lysaker, Noruega - Tel: 815 21 815 - Número Org.: NO 965 920 358 MVA - http://www.norwegian.com/
IVA no. Dinamarca CVR-/SE nr.32083927 / Suecia SE 516405399201 / Finlandia FI 23617257 / Francia FR 03 810456822 / UK 159 6755 56 / España N0282664B
NIIRONENORDUNA/ALBERTO SEBASTIAN 
Helsinki - Madrid 
D86151 - 24 ago 2016 - 13:55 - LowFare 
	
Travel Document - Información de la Reserva
	
Booking reference Número de reserva YL9PIR
Passenger Pasajero NIIRONENORDUNA/ALBERTO SEBASTIAN
Flight Vuelo D86151 - 24 ago 2016
Departure Salida 13:55 Helsinki (HEL) Terminal 2
Arrival Llegada 17:10 Madrid (MAD) Terminal 2
Seat Asiento No seat reservation /Sin reserva de asiento
Cabin baggage Equipaje de mano x 1, 10 Max kg, Max 55 x 40 x 23 cm
Checked baggage Equipaje facturado x 1, 20 Max kg, por maleta
Price category Tipo de tarifa LowFare/LowFare
Document number Número de documento 328-7201683923
Comment Comentario Printed/Impreso - 08 jul 2016
	
Información importante Cómo cambiar una reserva
Todos los pasajeros deberán presentar un documento identificativo válido y los
documentos de viaje para todos los vuelos. Para información específica sobre estos
requisitos, contacte con las autoridades pertinentes (por ejemplo, embajada/consulado).
 
 
¿Viaja solo con equipaje de mano? Vaya directo a la puerta de embarque cuando viaje
dentro de los países nórdicos o de los países nórdicos a Europa (excepto Reino Unido).
Todos los equipajes debe ser etiquetados con el nombre, la dirección y el teléfono del
pasajero.
 
Los mostradores de facturación abren 2 horas antes de la hora de salida programada (3
horas para los vuelos hacia/desde Dubái, Israel, Tailandia, Caribe y Estados Unidos).
Los mostradores de facturación (incl. la facturación de equipaje) cierran 30 minutos
antes de la hora de salida en vuelos domésticos (países nórdicos), 1 hora antes en
vuelos hacia/desde Dubái, Israel, Tailandia, Caribe y Estados Unidos, y 45 minutos
antes para el resto de vuelos. NOTA: Pasajeros con necesidades especiales, equipajes
especiales y menores no acompañados deberán hacer el check-in al menos 1 hora
antes de la hora de salida programada.
 
Los pasajeros deben presentarse en la puerta de embarque al menos 20 minutos antes
de la salida programada para vuelos dentro de los países nórdicos y 30 minutos antes
para el resto de vuelos.
 
Los cambios se pueden realizar hasta 30 minutos antes de la hora de salida
programada. Se aplicarán los cargos correspondientes. Los cambios pueden hacerse
online a través de Mis Reservas. Se aplicará un cargo adicional a los cambios
realizados a través de nuestro Call Center o en el aeropuerto.
 
Condiciones diferentes pueden aplicarse a los billetes reservados como parte de un
paquete hotel/vuelo y/o a través de una agencia de viajes. Otros términos y condiciones
también se aplican a las reservas de grupos. Consulte
http://www.norwegian.com/en/flight/group-travel/
 
Servicios de Internet
www.norwegian.no / www.norwegian.se / www.norwegian.dk/ www.norwegian.com
 
Servicios móviles (en noruego)
m.norwegian.no
 
Call Center: 24 horas, 7 días a la semana
Noruega: 815 21 815 (+47 21 49 00 15 desde el extranjero)
Suecia: +46 (0) 770 45 77 00 Finlandia: +358 (0) 9 2310 1600
Dinamarca: +45 70 80 78 80
Estados Unidos: 1-800-357-4159
 
A menos que se indique lo contratio, este vuelo será operado por Norwegian Air
Shuttle, Norwegian Air International o Norwegian Air Norway en nombre de Norwegian
Air Shuttle.
Para términos y condiciones, visite www.norwegian.com
 
Estructura de Datos/Practicas y ejercicios/Practica 0.pdf
Práctica 0. Punteros 
Estructuras de Datos 
 
Objetivo 
Se trata de que el alumno empiece a familiarizarse con los punteros en Pascal. 
 
Enunciado 
Una empresa con ciertas dificultades económicas quiere tener un registro de empleados para 
poder procesar la información relativa a su sueldo más fácilmente y así saber si tiene que 
reasignar a empleados a diferentes departamentos medidas. 
 
De cada empleado se quiere guardar su nombre, su edad y su sueldo, por lo que se tendrá un 
registro de N empleados que tiene la empresa. El objetivo es ordenar la información en orden 
ascendente de acuerdo al salario de cada uno, pero para hacerlo más eficiente, en lugar de 
almacenar éstos en un array de empleados, se tendrá un array de punteros a empleados, para 
que cada vez que haya movimiento en la ordenación, no se hagan continuamente copias de los 
datos sino que se cambien los punteros, resultando así más eficiente. La Figura 1 ilustra el 
posible intercambio de punteros. 
 
 
Figura 1. Ordenar la información de los empleados 
 
Lo que se pide es, crear un programa que haga lo siguiente: 
 Crear los diferentes empleados, para lo cual pedirá los datos por teclado. 
 Mostrar por pantalla el listado de los empleados de la empresa. 
 Ordenar los empleados en función de su sueldo (de menor a mayor). 
 Mostrar por pantalla el listado de empleados ordenado. 
 Eliminar del registro aquellos empleados que superen un salario determinado. 
 Mostrar por pantalla el registro de empleados. 
Estructura de Datos/Practicas y ejercicios/Practica1_costecomputacional.pdf
Práctica 0c: Análisis de rendimiento y complejidad 
Estructuras de Datos – 1º GII/GIS 
 
 
En esta práctica se desea evaluar el coste computacional de diversos algoritmos midiendo 
tiempos de ejecución para diferentes tamaños de problema. 
 
Para ello será necesario hacer uso de la unidad de Pascal Sysutils. Las unidades en Pascal se 
pueden utilizar para importar a un proyecto tipos y subprogramas previamente creados y 
compilados
1
. Para utilizar una unidad en un programa principal (u otra unidad) basta invocar 
“USES NombreUnidad;” en la cabecera del módulo, de manera que para utilizar las 
definiciones de Sysutils sería necesario escribir algo como: 
 
PROGRAM Complejidad; 
USES Sysutils; 
 
Una vez importada la unidad tendremos disponibles una variedad muy interesante de 
subprogramas que tienen que ver
con funcionalidad del sistema (ficheros, cadenas de 
caracteres, funcionalidad horaria, etc.
2
). Para el propósito de esta práctica se utilizará la parte 
específica de la unidad dedicada a funcionalidad de manejo de variables temporales y fechas: 
http://www.freepascal.org/docs-html/rtl/sysutils/datetimeroutines.html 
 
En particular, se puede observar el prototipo de la función Now y la función 
DateTimeToTimeStamp: 
 
 
 
 
 
 
1
 La creación de unidades será motivo de las próximas prácticas. 
2
 Más información en: http://www.freepascal.org/docs-html/rtl/sysutils/index-5.html 
http://www.freepascal.org/docs-html/rtl/sysutils/datetimeroutines.html
http://www.freepascal.org/docs-html/rtl/sysutils/index-5.html
 
Como se puede comprobar, la llamada a la función Now no recibe argumentos y devuelve un 
valor de tipo TDateTime que representa la fecha y hora en un valor numérico de doble 
precisión. Este tipo puede ser descompuesto en TTimeStamp, más manejable, a través de la 
función DateTimeToTimeStamp. El tipo TTimeStamp es un registro con campos Date y 
Time como fecha y hora del sistema, y representados por sendos LongInt. 
 
Si la fecha no nos interesa porque queremos cronometrar simplemente porciones de código en 
ejecución nos bastaría la parte de tipo Time, que como a cualquier registro se accede a través 
de la notación “.” como registro.time. 
 
Por ejemplo considérese el siguiente código: 
 
PROGRAM Complejidad; 
USES Sysutils; 
CONST 
N = 1000000; 
VAR 
ts, ts2: TTimeStamp; 
i, x: longint; 
BEGIN 
ts := DateTimeToTimeStamp(Now); 
x := 0; 
FOR i := 1 TO N DO 
x := x + 1; 
ts2 := DateTimeToTimeStamp (Now); 
writeln('tiempo: ',ts2.time - ts.time, ' ms'); 
END. 
 
A partir de aquí ya es posible evaluar el coste computacional de diferentes algoritmos para 
diferentes tamaños de problema. Los tiempos que devuelvan serán posteriormente 
representados en una gráfica N-T (tamaño del problema, N, en abscisas y tiempo, T, en 
ordenadas). Por ejemplo para unas ejecuciones con diversos valores de la constante podemos 
obtener los siguientes resultados
3
: 
 
 
 
N Tiempo (ms) 
10.000.000 55 
100.000.000 191 
1000.000.000 1871 
5.000.000.000 9312 
7.000.000.000 13084 
1E+10 18584 
 
 
Se pide hacer en Pascal un cuerpo de programa principal que utilice un tipo Array definido por 
el usuario del siguiente modo: 
 
 
3
 Para este ejemplo se ha hecho uso de un doble bucle porque la variable iteradora sólo admite valores del rango 
longint (32 bits, hasta 2
31
-1 =~ 2147 millones ). Existe el tipo Cardinal para aumentar a unos 4000 millones. 
0
2000
4000
6000
8000
10000
12000
14000
16000
18000
20000
0 2E+09 4E+09 6E+09 8E+09 1E+10
T (ms) 
N 
const 
N = 1048576; {2^20} 
type 
TAlmacen = array [1..N] of integer; 
var 
coleccion: TAlmacen; 
 
A continuación codifique 4 subprogramas: 
1) Búsqueda secuencial (O(n)): itera a lo largo del array hasta encontrar el elemento que 
se busca. En el peor de los casos nunca lo encuentra: 
 
function Busqueda_secuencial(var c: TAlmacen): boolean; 
 
2) Busqueda binaria (O(log n)): en un array previamente ordenado busca un elemento 
comenzando por la posición central del array y evaluando si se ha encontrado, si no, 
sigue buscando en la mitad restante que interese (mitad mayor o mitad menor). En el 
peor de los casos nunca lo encuentra. 
3) Ordenación directa (O(n2)): se realiza mediante 2 bucles (ordenación por intercambio 
directo, inserción directa, etc.), por ejemplo haciendo N pasadas de intercambios entre 
elementos vecinos (siendo N el tamaño del array). 
4) Ordenación por mezcla (O(n log n)): algoritmo multipasada. En la primera pasada se 
ordena un elemento con su respectivo vecino (longitud 1) “recorriendo ambas 
posiciones por separado” (elementos en posiciones i e i+1, siendo i mod 2 = 0, 
ordenando 2 elementos entre sí), en la segunda pasada el array está ordenado por 
parejas y se ordenan dobles parejas mediante 2 recorridos de 2 elementos (longitud 2, 
ordena 4 elementos entre sí), en la siguiente pasada igual con 2 recorridos sobre 4 
elementos (longitud 4, ordenando 8 elementos entre sí), y así sucesivamente hasta 
terminar con 2 recorridos de cada mitad de elementos del array (longitud N/2) para 
ordenar todos los valores. Ejemplo: 
 
Recorridos de longitud 1: 
6 3 8 5 2 9 7 4 
 
3 6 5 8 2 9 4 7 
 
Recorridos de longitud 2: 
3 6 5 8 2 9 4 7 
 
3 5 6 8 2 4 7 9 
 
Recorridos de longitud 4: 
3 5 6 8 2 4 7 9 
 
2 3 4 5 6 7 8 9 
 
 
A continuación mide el tiempo (T) invertido con cada subprograma probando con diferentes 
tamaños del array (N) definido anteriormente y haz una representación gráfica de cada 
comportamiento. 
 
Estructura de Datos/Practicas y ejercicios/Practica4b_listas.pdf
Práctica 4b - Listas 
Estructuras de Datos 
 
 
En esta práctica se profundizará más sobre el aprendizaje de listas, implementando 
algunas de sus posibles versiones, para después hacer uso de las mismas. La práctica 
consta de dos partes: 
 
Primera parte 
 
El comportamiento de un TAD Lista viene determinado por su especificación formal. 
Siguiendo la especificación formal vista en clase se pide implementar lo siguiente: 
 
a) Implementación de la unidad uListaEst, como una lista estática que simule 
memoria dinámica utilizando un array como almacén para guardar los nodos. 
b) Implementación de la unidad uListCircular como una lista circular con 
enlace simple y puntero al último elemento. Una posible representación gráfica 
se puede ver a continuación: 
 
 
 
 
 
 
 
 
En ambos casos los elementos de las listas serán de tipo TElem, cuyo TAD estará 
definido en una unidad diferente (uElem). 
 
Segunda parte 
 
Se quiere comprobar si una subcadena está contenida dentro de una cadena. Dado que el 
tipo para representar cadenas en Pascal es el tipo String, que tiene un tamaño máximo y 
se quiere poder utilizar cadenas de cualquier tamaño sin tener ningún tipo de limitación, 
se opta por representar las cadenas mediante listas, donde cada elemento de la lista será 
un carácter (el TElem será de tipo Char en este caso). Así, la posible secuencia de 
acciones que debe tener el programa que se pide es la siguiente: 
 
 
1. Crear la cadena (crear una lista con el contenido de la cadena). 
2. Crear la subcadena (crear una lista con el contenido de la subcadena). 
3. Comprobar si la subcadena está contenida en la cadena. 
4. Eliminar ambas cadenas (eliminar las dos listas). 
 
 
Se deberá extender el TAD TListaEst y TListaCircular para añadir la operación 
de poder recuperar el elemento que se encuentre en una posición determinada de la lista. 
A continuación, se presenta la especificación algebraica para dicha operación: 
 
 
 
 
lista 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Un ejemplo de salida de diferentes ejecuciones se presenta a continuación: 
 
 
 
 
 
 
Nota 1: Se considera necesario un nivel elevado de encapsulación y abstracción. 
 
Nota 2: Se hará uso de las normas de estilo dictadas en clase (cabecera del fichero, interfaz de la unidad 
con precondiciones, postcondiciones, excepciones, implementaciones con el análisis de complejidad de 
cada operación, nombres coherentes de variables y operaciones,...) 
 
Plantilla de cabecera del fichero: 
{********************************************************************************* 
* * 
* Módulo: * 
* Tipo: Programa() Interfaz-Implementación TAD () Otros() * 
* Autor/es: * 
* Fecha de actualización: * 
* Descripción: * 
* * 
**********************************************************************************} 
*********************************************************************************} 
La cadena [n,o,c] SI está contenida en la cadena [r,i,n,o,c,e,r,o,n,t,e] 
La cadena
[n,o,c] NO está contenida en la cadena [c,a,s,a] 
La cadena [p,e,p,e] SI está contenida en la cadena [h,o,l,a, ,p,e,p,e] 
… 
OPERACIONES 
 
(* operación observadora no selectora *) 
PARCIAL GetElemPos: TipoLista x Natural  TipoElemento 
 
VARIABLES 
 lista: TipoLista; 
 p: Natural; 
 
ECUACIONES DE DEFINITUD 
 SI ((p > 0) Y (p <= Longitud(lista))  
 DEF (GetElemPos (lista, p)) 
ECUACIONES 
GetElemPos(Construir(e, lista), p) = SI p=1  
e 
 | GetElemPos (lista, p-1) 
… 
Estructura de Datos/Practicas y ejercicios/PracticaArbolesNew.pdf
Práctica Árboles Binarios de Búsqueda
Estructuras de Datos
Implementación del árbol binario de búsqueda
Crearemos la unidad UArbolBB que implemente el TAD Árbol Binario de Búsqueda
respetando la ya conocida especificación algebraica.
ESPECIFICACIÓN ArbolBinarioBusqueda
 PARÁMETROS GENÉRICOS
 TIPOS TipoElemento
 FIN PARÁMETROS
 TIPOS TipoArbolBin
 OPERACIONES
 (* constructoras generadoras *)
CrearArbolBinVacio: à TipoArbolBin
ConstruirArbolBin: TipoArbolBin x TipoElemento x TipoArbolBin à TipoArbolBin
 (* observadoras selectoras *)
PARCIAL Raiz: TipoArbolBin à TipoElemento
PARCIAL HijoIzdo: TipoArbolBin à TipoArbolBin
PARCIAL HijoDcho: TipoArbolBin à TipoArbolBin
 (* observadoras no selectoras *)
EsArbolBinVacio: TipoArbolBin à Booleano
PARAMETROS GENERICOS
 OPERACIONES
 Mayor: TipoElemento x TipoElemento à Booleano
FIN PARAMETROS
Pertenece: TipoArbolBin x TipoElemento à Booleano
PARCIAL Minimo: TipoArbolBin à TipoElemento
(* constructoras no generadoras *)
Insertar: TipoElemento x TipoArbolBin à TipoArbolBin
Eliminar: TipoElemento x TipoArbolBin à TipoArbolBin
VARIABLES
r, e: TipoElemento;
i, d: TipoArbolBin;
ECUACIONES DE DEFINITUD
DEF(Minimo(ConstruirArbolBin(i, r, d)))
DEF(Raiz(ConstruirArbolBin(i, r, d)))
DEF(HijoIzdo(ConstruirArbolBin(i, r, d)))
DEF(HijoDcho(ConstruirArbolBin(i, r, d)))
ECUACIONES
(* observadoras selectoras *)
Raiz(ConstruirArbolBin(i, r, d)) = r
HijoIzq(ConstruirArbolBin(i, r, d)) = i
HijoDer(ConstruirArbolBin(i, r, d)) = d
(* observadoras no selectoras *)
Pertenece (e, CrearArbolBinVacio) = FALSO
Pertenece (e, ConstruirArbonBin(i, r, d)) = SI e=r à
CIERTO
 | SI Mayor(e, r) à
Pertenece(e, d)
 | Pertenece(e, i)
Minimo(ConstruirArbolBin(i, r, d)) =
 SI EsArbolBinVacio(i) à
 r
 | Minimo(i)
EsArbolBinVacio(CrearArbolBinVacio) = CIERTO
EsArbolBinVacio(ConstruirArbolBin(i, r, d)) = FALSO
(* constructoras no generadoras *)
Insertar(e, CrearArbolBinVacio) = ConstruirArbolBin(CrearArbolBinVacio, e, CrearArbolBinVacio)
Insertar(e,ConstruirArbolBin(i, r, d)) = SI (e = r) à
ConstruirArbolBin(i, r, d)
 | SI Mayor(e, r) à
ConstruirArbolBin(i, r, Insertar(e, d))
 | ConstruirArbolBin(Insertar(e, i), r, d)
Eliminar(e, CrearArbolBinVacio) = CrearArbolBinVacio
Eliminar(e, ConstruirArbolBin(i, r, d)) =
 SI (e = r) à
 SI EsArbolBinVacio(d) à
 i
 | ConstruirArbolBin(i, Minimo(d), Eliminar(Minimo(d), d))
 | SI Mayor(e, r) à
 ConstruirArbolBin(i, r, Eliminar(e, d))
 | ConstruirArbolBin(Eliminar(e, i), r, d)
FIN ESPECIFICACION
Uso del árbol binario de búsqueda
Para probar la utilidad del árbol binario se pide desarrollar un programa que clasifique una
lista de tweets por los hashtags que aparecen en ellos. Un tweet es una publicación o
actualización de estado realizada en la red social Twitter. Un tweet es un mensaje de texto
con extensión máxima de 140 caracteres (están permitidos letras, números, signos y
enlaces). Los tweets pueden contener hashtags o etiquetas, que permiten establecer el tema
del que trata el tweet. Hashtag es una palabra compuesta por hash (almohadilla) y tag
(etiqueta) y son palabras que empiezan por el símbolo almohadilla (#), seguido de una
palabra (por ejemplo: #programación, #cloud, etc.). 
Para el desarrollo de la práctica se proporcionan dos ficheros de texto: 
- hashtags.txt, que almacena un hashtag en cada línea
- tweets.txt, que almacena un tweet en cada línea
El etiquetado de tweets lo vamos a implementar como un árbol binario de búsqueda en el
que cada nodo almacene un registro con dos campos:
- hashtag: que almacena un solo hashtag.
- listaTweets: que almacena una lista dinámica de tweets que contengan este
hashtag. La lista debe ser dinámica, ya que no conocemos a priori el número de tweets que
van a contener cada hashtag. Puedes utilizar una implementación de listas que tengas ya
hecha.
Esta representación y la funcionalidad asociada deberá ir implementada en una unidad que
se utilizará como el TipoElemento del árbol binario de búsqueda.
De modo que lo que se pide es:
1.- Construir la estructura fundamental del ABB: para ello, leer la lista de hashtags
proporcionada en hashtags.txt (cada tweet es una línea del fichero de texto) y construir el
árbol binario de búsqueda de hashtags ordenado por orden alfabético. Para la construcción
del ABB, recuerda que sólo debes utilizar la interfaz de la unidad UArbolBB.
2.- Etiquetado de tweets: Una vez construido el árbol, leer cada uno de los tweets
almacenados en tweets.txt (cada tweet es una línea del fichero de texto). Para cada tweet,
buscar los hashtags que contenga y almacenar el tweet en el nodo del ABB que
corresponda al hashtag. Por ejemplo, un tweet como el siguiente 'Sería feliz estando todo
el tiempo de #viajesPorElMundo' debería estar almacenado en la listaTweets del
nodo cuyo valor del campo hashtag coincida con '#viajesPorElMundo'. Por otro lado,
puede suceder que un tweet contenga más de un hastag.
3.- Consultas: como resultado, hemos construido una base de datos de juguete y podemos
implementar la funcionalidad que permita realizar consultas de tweets por hashtag. Es
decir, el usuario podrá preguntar por un hashtag cualquiera y el programa deberá
responder con la impresión por pantalla de los tweets que contienen el hashtag consultado
o, en su caso, que no se ha encontrado ningún tweet con ese hashtag.
4.- ¿Qué diferencia habría si en lugar de un árbol binario de búsqueda utilizamos una lista?
Funciones útiles:
Para el manejo de cadenas, se recomienda el uso de la unidad sysutils y strutils.
En concreto:
- ansicomparetext(s1,s2): función que compara los strings s1 y s2. Si s1=s2
devuelve 0, Si s1<s2, devuelve un entero negativo y si s1>s2, devuelve un entero
positivo. Está en sysutils.
- posEx(c,s): función que devuelve la posición del carácter c dentro de la cadena s.
Está en strutils.
- ExtractSubstr(s,p,delim): función que recibe una cadena s, una posición p y
un conjunto de delimitadores delim y devuelve la palabra que empieza en la posición p de
s. Nota: delim debe ser declarada como una variable de tipo TSysCharSet e
inicializada como delim := [' ']. Está en strutils.
Nota: Como siempre, se hará uso de las normas de estilo dictadas en clase (cabecera del fichero, interfaz de la unidad
con precondiciones, postcondiciones, excepciones, implementaciones con el análisis de complejidad de cada operación,
nombres coherentes de variables y operaciones,...)
Plantilla de cabecera del fichero:
{*********************************************************************************
* Módulo: *
* Tipo: Programa() Interfaz-Implementación TAD () Otros() *
* Autor/es: *
* Fecha de actualización: *
* Descripción: *
*********************************************************************************}
Nino
Resaltado
Arbol Binario de Busqueda
	PARÁMETROS GENÉRICOS
	FIN PARÁMETROS
	OPERACIONES
	VARIABLES
	ECUACIONES DE DEFINITUD
	ECUACIONES
	FIN ESPECIFICACION
Estructura de Datos/Practicas y ejercicios/PracticaGrafosNew.pdf
Práctica Grafos
Estructuras de Datos
Implementación de la unidad grafo
Crearemos la unidad UGrafo que implemente el TAD Grafo. El grao que esperamos
utilizar en esta ocasión es disperso, conexo y no dirigido. El alumno, con estos datos,
debe decidir cuál es la implementación más adecuada.
La interfaz de la unidad debe
permitir la construcción de cualquier grafo. Se sugiere que la unidad grafo disponga de, al
menos, la siguiente funcionalidad accesible en su interfaz:
PROCEDURE CrearGrafoVacio(VAR g:TGrafo);
PROCEDURE InsertarOrigen(VAR g:TGrafo; origen:TElemento);
PROCEDURE InsertarDestino(g:TGrafo; origen:TElemento; destino: 
TElemento);
FUNCTION EsGrafoVacio(g:TGrafo):Boolean;
FUNCTION PerteneceAOrigenes(g:TGrafo; origen:TElemento):Boolean;
FUNCTION PerteneceADestinos(g:TGrafo; origen:TElemento; destino: 
TElemento):Boolean;
PROCEDURE ListaAdyacencia(g:TGrafo; e:TElemento; VAR adyacentes:TLista);
Uso de la unidad grafo
El Metro de Madrid puede representarse como un grafo, en el que las estaciones son los
vértices y las conexiones entre ellas, las aristas. Por ejemplo, una estación como Sol, tiene
seis estaciones adyacentes: Ópera, Sevilla, Callao, Lavapies, Gran Vía y Tirso de Molina
(las dos primeras son de la línea 2, las dos siguiente de la línea 3 y las dos últimas de la
línea 1). Se puede consultar un plano del metro en la siguiente URL:
https://www.metromadrid.es/export/sites/metro/comun/documentos/planos/Planoesquemat
icoespanol.pdf
Para probar la funcionalidad de nuestra implementación del TAD grafo, vamos a modelar
con ella el Metro de Madrid. Para ello, se proporcionan 12 ficheros de texto (desde L01.txt
hasta L12.txt, en formato UTF8, de modo que si utilizas windows, quizá necesites paarlos
a formato ASCII), uno por cada línea de metro, en los que se listan las estaciones que las
componen, una por cada línea del fichero. Se debe observar que las líneas circulares (6 y
12) aparecen con estructura lineal en el archivo, pero nos resultarán igualmente útiles de
esa manera.
Se pide implementar la siguiente funcionalidad:
1.- Construir el grafo del Metro de Madrid: para ello, se debe leer la lista de estaciones de
cada archivo proporcionado. Cada una de las estaciones debe tener al menos los datos de
su nombre y el/los número/s identificativo/s de la/s línea/s a la/s que pertenece. Para la
construcción del grafo, recuerda que debes utilizar exclusivamente la interfaz de la unidad
Ugrafo.
2.- Consultar estaciones: desde el programa principal, permitir al usuario realizar
consultas por estaciones. Para cada estación, se debe mostrar si existe o no en el grafo y,
en caso de existir, las líneas a las que pertenece y las estaciones adyacentes.
3.- Recorrido: Implementar en la unidad UGrafo un recorrido en anchura desde un
origen dado. El recorrido en anchura de un grafo parte de un vértice dado A (cualquiera) y
explora en primer lugar todos los vértices adyacentes. Luego toma uno de esos vértices y
explora todos sus adyacentes no visitados previamente, luego desde otro adyacente del
origen A ya visitado en primera iteración se exploran todos sus adyacentes no visitados en
pasos anteriores y así sucesivamente. Para mantener memoria de los vértices que debemos
https://www.metromadrid.es/export/sites/metro/comun/documentos/planos/Planoesquematicoespanol.pdf
https://www.metromadrid.es/export/sites/metro/comun/documentos/planos/Planoesquematicoespanol.pdf
visitar en cada paso se utilizará una estructura FIFO, y para evitar entrar en ciclos y
revisitar vértices ya visitados previamente se utilizará un conjunto de vértices visitados.
Seguro que ya tienes implementadas estas estructuras auxiliares. Si es así, utiliza esas
implementaciones, recordando ser muy cuidadoso y acceder a su funcionalidad
exclusivamente desde la interfaz proporcionada.
4.- Camino: Implementar también en la unidad UGrafo la funcionalidad necesaria para el
cálculo de un camino entre un vértice origen y un vértice destino (no importa si es de
longitud mínima o no).
Nota: Como siempre, se hará uso de las normas de estilo dictadas en clase (cabecera del fichero, interfaz de la unidad
con precondiciones, postcondiciones, excepciones, implementaciones con el análisis de complejidad de cada operación,
nombres coherentes de variables y operaciones,...)
Plantilla de cabecera del fichero:
{*********************************************************************************
* Módulo: *
* Tipo: Programa() Interfaz-Implementación TAD () Otros() *
* Autor/es: *
* Fecha de actualización: *
* Descripción: *
*********************************************************************************}
Estructura de Datos/Practicas y ejercicios/Practica_1_complejos_vicalvaro.pdf
Práctica 1. Uso de TADs 
Estructuras de Datos 
 
Objetivo: 
Crear la unidad en Pascal que defina el TAD de números complejos, con las siguientes 
operaciones: 
OPERACIONES 
 (* constructoras generadoras *) 
CrearComplejo: Real x Real  TipoComplejo 
 (* observadoras selectoras *) 
ParteReal: TipoComplejo  Real 
ParteImaginaria: TipoComplejo  Real 
 (* observadoras no selectoras *) 
Modulo: TipoComplejo  Real 
 (* constructora no generadora *) 
Conjugado: TipoComplejo  TipoComplejo 
Sumar: TipoComplejo x TipoComplejo  TipoComplejo 
Restar: TipoComplejo x TipoComplejo  TipoComplejo 
Multiplicar: TipoComplejo x TipoComplejo  TipoComplejo 
Dividir: TipoComplejo x TipoComplejo  TipoComplejo 
 
Se recuerda que las fórmulas para el manejo de números complejos son: 
Número complejo: 
z = (re, im) 
Suma de números complejos: 
 212121 , imimrerezz  
Resta de números complejos: 
 212121 , imimrerezz  
Producto de números complejos: 
 2121212121 , imrereimimimrerezz  
Cociente de números complejos: 













2
2
2
2
2121
2
2
2
2
2121
2
1 ,
imre
imrereim
imre
imimrere
z
z
 
Módulo de un número complejo: 
22 imrez  
Conjugado de un número complejo (dado z por la primera definición): 
),( imrez  
Seguidamente crear la implementación de otra unidad que defina una extensión del TAD 
TipoComplejo con la que podamos calcular los parámetros en un circuito eléctrico RCL en 
serie. La Ley de Ohm puede generalizarse para corriente alterna si hacemos una analogía entre 
la resistencia de un circuito de corriente continua y las impedancias en corriente alterna. Para 
el cálculo tanto de las impedancias de los componentes individuales del circuito, como de las 
caídas de potencial en cada componente, frecuencia de resonancia del circuito,... haremos uso 
de las operaciones que habíamos implementado para el manejo de variables TipoComplejo. 
ImpedanciaL: Real X Real  TipoComplejo 
ImpedanciaR: Real  TipoComplejo 
ImpedanciaC: Real X Real  TipoComplejo 
ImpedanciaTotal: TipoComplejo X TipoComplejo X TipoComplejo  TipoComplejo 
FrecuenciaAngular: Real  Real 
Intensidad: TipoComplejo X TipoComplejo  TipoComplejo 
CaidaPotencial: TipoComplejo X TipoComplejo  TipoComplejo 
 
 
Relación entre la frecuencia y la frecuencia angular: 
 2 
Impedancia Resistiva: 
RZR  
Impedancia Capacitiva: 
C
j
Cj
ZC



1 
Impedancia Inductiva: 
LjZL  
Ley de Ohm: 
ZIV  
A continuación crearemos un programa principal que haga uso de las unidades anteriores para 
resolver el siguiente problema (cálculo de caídas de potencial en cada dispositivo del circuito): 
Dado un circuito RCL en serie y una fuente alterna (ver figura superior) se pide realizar un 
programa que permita calcular el potencial en cada uno de los puntos A, B, C y D para valores 
coherentes de V0, , C, L y R (por ejemplo 220V, 50Hz, 1.2 µF, 3 mHr, 5 k). 
Estructura de Datos/Practicas y ejercicios/Practica_5_pilasColas.pdf
Práctica 5. Pilas y Colas 
Estructuras de Datos 
 
Objetivo: 
Implementación de las unidades de Pilas y Colas en versión estática y dinámica. 
 
En esta práctica tendremos que hacer 4 unidades para la realización de Pilas y Colas (2 versiones de 
cada una, estática y dinámica), así como una unidad para definir el TipoElemento. 
 
Unidades Pila: 
Versión estática: usaremos la versión de Pila con un array parcialmente lleno como 
almacén y un índice Cima (0..MAX). 
Versión dinámica:
usaremos una versión de lista enlazada simple con un único puntero de 
enlace y referencia a la estructura. 
Unidades Cola: 
Versión estática: implementaremos la versión circular con un array de dimensión 
predeterminada. 
Versión dinámica: También haremos una versión circular, puesto que en listas ya se pidió 
la realización de estructura lineal doblemente enlazada con puntero cabecera y final. 
 
Para el caso del TipoElemento simularemos una imagen como un array de 640x480 posiciones 
(píxeles) y valores de tipo Byte (primitivo en Pascal) comprendidos entre 0-255. En el contexto de 
una imagen un píxel con valor de 0 representa un tono negro, y uno con un valor de 255 representa 
un tono blanco. Valores intermedios entre 0 y 255 describen tonos grisáceos, más claros cuanto 
mayor es el valor hasta llegar a 255. 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 1: Definción del TipoElemento como una simulación de imagen. 
 
Un vídeo no es otra cosa que una secuencia de imágenes. Por ejemplo, un vídeo consistente en 10 
imágenes o fotogramas es una secuencia de 10 imágenes. Se pide: 
(a) Generar un vídeo de 10 imágenes y almacenarlo en una estructura de cola, llamada videoFwd. 
Los valores de intensidad de los píxeles se pueden generar de manera aleatoria entre 0 y 255, con 
valores fijos para cada imagen, o de la manera que tú elijas. 
(b) Con ayuda de una estructura intermedia de tipo pila, generar otro vídeo y guardarlo en otra 
estructura cola llamada videoRev que contenga los mismos fotogramas que videoFwd, pero 
colocados en orden inverso. 
(c) Como parte opcional, se propone representar gráficamente el vídeo, utilizando los conceptos 
aprendidos en la práctica de Mandelbrot. 
 
unit uElemento; 
interface 
const 
 MAX_RES_X = 640; 
 MAX_RES_Y = 480; 
type 
 TipoElemento = TImagen; 
 TImagen = array[1..640, 1..480] of byte; 
… 
Implementation 
… 
end. 
Estructura de Datos/Practicas y ejercicios/Practica_listas.pdf
Práctica Listas
Estructuras de Datos
El comportamiento de un TAD Lista viene determinado por su especificación formal,
que se muestra a continuación:
ESPECIFICACIÓN Listas
PARÁMETROS FORMALES
TIPOS TipoElemento
FIN PARAMETROS
TIPOS TipoLista
OPERACIONES
(* operaciones constructoras generadoras *)
CrearVacia:  TipoLista
Construir: TipoElemento x TipoLista  TipoLista
(* operaciones observadoras selectoras *)
PARCIAL Primero: TipoLista  TipoElemento
PARCIAL Resto: TipoLista  TipoLista
(* operaciones observadoras no selectoras *)
EsVacia: TipoLista  Booleano
Longitud: TipoLista  Natural
PARCIAL Ultimo: TipoLista  TipoElemento
Pertenece: TipoElemento x TipoLista  Booleano
(* operaciones constructoras no generadoras *)
Concatenar: TipoLista x TipoLista  TipoLista
BorrarElemento: TipoElemento x TipoLista TipoLista
InsertarFinal: TipoElemento x TipoLista  TipoLista
VARIABLES
lista, lista2: TipoLista;
e, e’: TipoElemento;
ECUACIONES DE DEFINITUD
DEF(Primero (Construir (e, lista)))
DEF(Resto (Construir (e, lista)))
DEF(Ultimo (Construir (e, lista)))
ECUACIONES
(* operaciones observadoras selectoras *)
Primero (Construir (e, lista)) = e
Resto (Construir (e, lista)) = lista
(* operaciones observadoras no selectoras *)
EsVacia (CrearVacia) = CIERTO
EsVacia (Construir (e, lista)) = FALSO
Longitud (CrearVacia) = 0
Longitud (Construir (e, lista)) = 1 + Longitud (lista)
Ultimo (Construir (e, lista)) = 
SI EsVacia(lista)  
e
SI NO 
Ultimo (lista)
Pertenece (e, CrearVacia) = FALSO
Pertenece  (e, Construir  (e’, lista))  =   (e = e’) O (Pertenece  (e,
lista))
(* operaciones constructoras no generadoras *)
Concatenar (CrearVacia, lista) = lista
Concatenar (Construir (e, lista), lista2) = 
Construir (e, Concatenar (lista, lista2))
BorrarElemento (e, CrearVacia) = CrearVacia
BorrarElemento (e, Construir (e’, lista)) = 
SI e = e’  
lista
SI NO 
Construir (e’, BorrarElemento (e, lista))
InsertarFinal (e, CrearVacia) = Construir (e, lista)
InsertarFinal   (e,   Construir   (e’,   l))   =   Construir   (e’,
InsertarFinal (e, l))
FIN ESPECIFICACIÓN Listas
Para manejar la implementación de listas, en esta práctica, se pide
a) Implementación de la unidad ListaDin, como una lista dinámica doble enlazada con puntero cabecera
y final.
b) Implementación de la unidad ListaEst, como una lista estática que simule memoria dinámica.
c) Diseñar un programa que lea un fichero binario con tipo base:
     TAlumno=RECORD
        expediente: integer;
        curso: integer;
        nombre: string;
        edad: integer;
        nota: real;
     END;
     TArchivo=FILE OF TAlumno;
y que a partir de los datos leídos en este archivo, por cada implementación, construya una lista de
elementos que contenga a todos los estudiantes y además implemente la funcionalidad necesaria para:
1) Determinar si un estudiante está matriculado.
2) Calcular la nota media de un curso.
3) Determinar el número de estudiantes aprobados por curso.
4) Conocer el nombre del estudiante con notas más elevadas.
5) Obtener el número de expediente del estudiante más joven. 
Nota 1: Se considera necesario un nivel elevado de encapsulación y abstracción.
 
Nota 2: Se hará uso de las normas de estilo dictadas en clase (cabecera del fichero, interfaz de la unidad
con precondiciones, postcondiciones, excepciones, implementaciones con el análisis de complejidad de
cada operación, nombres coherentes de variables y operaciones,...)
Plantilla de cabecera del fichero:
{*********************************************************************************
* *
* Módulo: *
* Tipo: Programa() Interfaz-Implementación TAD () Otros() *
* Autor/es: *
* Fecha de actualización: *
* Descripción: *
* *
*********************************************************************************}
Estructura de Datos/Practicas y ejercicios/Práctica 0b.pdf
Práctica 0.b. Punteros 
Estructuras de Datos 
 
Objetivo: 
Entender los motivos de eficiencia de la reserva de memoria dinámica y el paso de parámetros 
a subprogramas. 
Enunciado: 
Se pretende comprobar las limitaciones de los diferentes espacios de memoria mediante el 
uso de un subprograma recursivo que reserven en cada llamada un array de grandes 
dimensiones. 
Para ello se harán 2 versiones del subprograma, uno pasando por valor un array como 
parámetro (de tal manera que en cada llamada el sistema operativo reservará espacio para él 
en el stack de memoria), y otro pasando por valor un puntero con el que se reservará espacio 
para el array de grandes dimensiones mediante el operador NEW. 
Para controlar el número de llamadas recursivas que se hacen, en el cuerpo del subprograma 
se decrementará una variable entera que se pasará también como parámetro al subprograma 
recursivo. Cuando dicha variable alcance el valor de 0 pasará al caso base que no hará nada 
especial. 
De esta manera, las llamadas los respectivos subprogramas serían algo como: 
Subprograma(contenedor, 100); 
siendo contenedor un array por ejemplo de 20.000 elementos enteros (ocupará del orden 
de 20.000*4 Bytes ~ 80 KB) y el valor 100, por ejemplo, el número de llamadas recursivas que 
deben hacerse para llegar al caso base. 
Subprograma(puntContenedor, 10); 
siendo puntContenedor un puntero de tipo base array de los mismos 20.000 elementos 
enteros y el valor 100, nuevamente, el número de llamadas recursivas que deben hacerse 
para llegar al caso base. En cada llamada se reservará un array del mismo tamaño que el 
anterior. 
 
Estructura de Datos/Temario/Tema0_Punteros_New.pdf
TEMA 0 
Gestión de 
Memoria Dinámica 
ESTRUCTURAS DE DATOS 
1 
Objetivos 
 Tema preliminar para entender el uso de la herramienta 
básica en la gestión de memoria dinámica: punteros 
 
 Objetivos: 
◦ Conocer el concepto de “puntero” 
◦ Entender la gestión dinámica de memoria 
◦ Manejar estructuras estáticas y dinámicas en memoria a través de 
punteros 
◦ Crear y destruir estructuras dinámicas en memoria 
 
2 
Definición del problema
 Las estructuras estáticas (por ejemplo, array) no pueden 
cambiar su tamaño durante la ejecución del programa 
 Cambiar la disposición de los elementos dentro de la 
estructura estática es, a veces, costoso. 
 Ejemplos: 
◦ No se puede redimensionar un array. 
◦ Colocar el último elemento al comienzo del array. 
 Además, hay otros factores importantes a tener en cuenta 
sobre el uso de la memoria en los procesos. 
3 
Definición del problema 
 El espacio de memoria en un sistema está descompuesto 
de forma general en 4 bloques con tamaños diversos 
◦ Segmento de código: asignación automática 
◦ Variables globales: asignación automática 
◦ Stack o pila de memoria: asignación automática 
◦ Heap o montículo de memoria: asignación manual 
 
4 
Imagen extraída de: www.sw-at.com 
Stack 
Heap 
Global 
Código 
http://www.sw-at.com/blog/2011/03/23/where-does-code-execute-process-address-space-code-gvar-bss-heap-stack/
http://www.sw-at.com/blog/2011/03/23/where-does-code-execute-process-address-space-code-gvar-bss-heap-stack/
http://www.sw-at.com/blog/2011/03/23/where-does-code-execute-process-address-space-code-gvar-bss-heap-stack/
Definición del problema 
◦ La memoria local a los subprogramas se gestiona en la pila de 
memoria 
◦ Cada proceso de un programa tiene su propia pila de memoria, por 
lo que en general la pila tiene un tamaño muy limitado 
◦ La memoria dinámica se gestiona en un bloque muy grande de 
memoria (heap/montículo) 
5 
Imagen extraída de: www.sw-at.com 
Stack 
Heap 
Global 
Código 
PROGRAM Memoria; 
VAR 
 precio: real; 
 
FUNCTION CalculoIVA(p: real): real; 
BEGIN 
 CalculoIVA := p*0.21; 
END; 
 
BEGIN 
 precio := 200.25; 
 writeln(‘El IVA es: ’, CalculoIVA(precio)); 
END; 
global 
local 
http://www.sw-at.com/blog/2011/03/23/where-does-code-execute-process-address-space-code-gvar-bss-heap-stack/
http://www.sw-at.com/blog/2011/03/23/where-does-code-execute-process-address-space-code-gvar-bss-heap-stack/
http://www.sw-at.com/blog/2011/03/23/where-does-code-execute-process-address-space-code-gvar-bss-heap-stack/
Definición del problema 
 Para algunos problemas de programación no se conoce en 
tiempo de diseño cuánta memoria necesitaremos ni cómo 
se va a organizar 
 
 Solución: definir y organizar esa memoria en tiempo de 
ejecución 
◦ Para ello, se utilizan estructuras de memoria dinámica 
 
 La gestión de memoria dinámica se realiza a través de 
variables capaces de guardar direcciones de memoria: 
punteros 
6 
¿Qué es eso de...? 
 Memoria dinámica: memoria en la que se puede reservar 
espacio en tiempo de ejecución 
◦ El heap es el bloque del espacio direccionable de memoria dedicado 
para la memoria dinámica 
 
 Estructuras de datos dinámicas: colección de elementos 
(denominados nodos) que se crean o destruyen en tiempo 
de ejecución. 
 
 Variables Dinámicas: Posiciones de memoria reservadas en 
tiempo de ejecución 
 
7 
Punteros 
 Una variable puntero se puede declarar como tipo anónimo, o como 
tipo definido por el usuario 
VAR 
 pointer: ^integer; 
Variable puntero de tipo 
anónimo identificada por 
pointer 
TYPE 
 TPointer = ^integer; 
VAR 
 pointer: TPointer; Variable declarada del 
tipo anterior 
Tipo TPointer definido 
por el usuario para crear 
variables puntero a entero 
8 
Punteros 
 Un tipo puntero se puede usar para declarar variables de ese tipo 
◦ Igual que un tipo Entero se usa para declarar variables de tipo entero (que 
guarda valores de ese tipo) 
 
 
 
 
 
 
 
 
 
◦ Una variable puntero almacena una dirección de memoria donde guardar un 
valor del “tipo base” del puntero (releer hasta estar bien seguro de 
entenderlo) 
TYPE 
 TPrecio = integer; 
VAR 
 precioPan: TPrecio; 
BEGIN 
 precioPan := 85; 
 writeln(precioPan); 
END. 
9 
TYPE 
 TPunteroEntero = ^integer; 
VAR 
 pEntero: TPunteroEntero; 
Punteros 
 Simulación en memoria 
 
85 
??? 
pEntero 
precioPan 
Dirección $3$12 
identificada 
como 
precioPan 
Valor (85) que 
guarda 
precioPan 
10 
TYPE 
 TPrecio = integer; 
 TPunteroEntero = ^integer; 
VAR 
 precioPan: TPrecio; 
 pEntero: TPunteroEntero; 
BEGIN 
 precioPan := 85; 
 writeln(precioPan); 
END. 
Operaciones con punteros 
 Operador @ (Referencia) 
◦ Obtención de la dirección de memoria de una variable 
 
 
 
 
 
 Operador ^ (Desreferencia) 
◦ Acceso al valor de la variable apuntada desde el puntero 
VAR 
 pEntero: ^integer; 
 precioPan: integer; 
BEGIN 
 precioPan := 85; 
 pEntero := @precioPan; 
 ... 
 ... 
 pEntero^ := 100; 
 writeln(precioPan); {imprime 100} 
pEntero^ y 
precioPan son 
sinónimos 
11 
Punteros 
 Simulación en memoria 
 
85 
$3$12 
Valor (85) que 
guarda 
precioPan 
Si pEntero contiene el valor $3$12, y esa es la dirección de memoria de 
la variable precioPan, se dice que pEntero apunta a precioPan 
pEntero 
precioPan 
12 
Dirección $3$12 
identificada 
como 
precioPan 
TYPE 
 TPrecio = integer; 
 TPunteroEntero = ^integer; 
VAR 
 precioPan: TPrecio; 
 pEntero: TPunteroEntero; 
BEGIN 
 precioPan := 85; 
 pEntero := @precioPan; 
 writeln(precioPan); 
END. 
Punteros 
 Simulación en memoria 
 
85 
$3$12 
Valor (85) que 
guarda 
precioPan 
Si pEntero contiene el valor $3$12, y esa es la dirección de memoria de 
la variable precioPan, se dice que pEntero apunta a precioPan 
pEntero 
precioPan 
13 
Dirección $3$12 
identificada 
como 
precioPan 
TYPE 
 TPrecio = integer; 
 TPunteroEntero = ^integer; 
VAR 
 precioPan: TPrecio; 
 pEntero: TPunteroEntero; 
BEGIN 
 precioPan := 85; 
 pEntero := @precioPan; 
 pEntero^ := 100; 
 writeln(precioPan); 
END. Desde pEntero se 
altera el valor de 
precioPan (100) 
100 
Operador @: Ejemplo (1/3) 
Reservamos en tiempo de 
compilación un bloque de memoria 
para un registro y otro para un 
puntero (ESTÁTICOS!!) 
registro 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro= ^tRegistro; 
VAR 
 pRegistro: tPtrRegistro; 
 registro: tRegistro; 
BEGIN 
 ... 
 registro.iniciales:=‘ASM’; 
 registro.identificacion:=23455; 
 ... 
 pRegistro := @ registro; 
 ... 
END. 
pRegistro 
14 
Operador @: Ejemplo (2/3) 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro= ^tRegistro; 
VAR 
 pRegistro: tPtrRegistro; 
 registro: tRegistro; 
BEGIN 
 ... 
 registro.iniciales:=‘ASM’; 
 registro.identificacion:=23455; 
 ... 
 pRegistro := @ registro; 
 ... 
END. 
Inicializamos el registro de la manera 
habitual 
Char[3] 'A' 
'S' 'M' 
23455 
pRegistro 
registro 
15 
Operador @: Ejemplo (y 3/3) 
Apuntamos con el puntero el bloque 
de memoria del registro. Tenemos 
accesible la información del registro 
a través del puntero. 
Char[3] 'A' 
'S' 'M' 
23455 
registro 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro= ^tRegistro; 
VAR 
 pRegistro: tPtrRegistro; 
 registro: tRegistro; 
BEGIN 
 ... 
 registro.iniciales:=‘ASM’; 
 registro.identificacion:=23455; 
 ... 
 pRegistro := @registro; 
 ... 
END. 
pRegistro 
16 
Operador ^: Ejemplo (1/3) 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro= ^tRegistro; 
VAR 
 pRegistro: tPtrRegistro; 
 reg: tRegistro; 
BEGIN 
 ... 
 pRegistro:=@reg; 
 … 
 pRegistro^.iniciales:=‘JJP’; 
 pRegistro^.identificacion:=23456; 
 ... 
END. 
reg 
Reservamos en tiempo de 
compilación un bloque de memoria 
para un registro y otro para un 
puntero (ESTÁTICOS!!) 
pRegistro 
17 
Operador ^: Ejemplo (2/3) 
Apuntamos con el puntero el bloque 
de memoria del registro.
reg 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro= ^tRegistro; 
VAR 
 pRegistro: tPtrRegistro; 
 reg: tRegistro; 
BEGIN 
 ... 
 pRegistro:=@reg; 
 … 
 pRegistro^.iniciales:=‘JJP’; 
 pRegistro^.identificacion:=23456; 
 ... 
END. 
pRegistro 
18 
Operador ^: Ejemplo (y 3/3) 
Accedemos al campo “iniciales” e 
“identificacion”del dato de tipo 
tRegistro y asignamos valores 
(NO asignamos valores al puntero, 
sino al dato al que apunta) 
Char[3] 'J' 
'J' 'P' 
23456 
reg 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro= ^tRegistro; 
VAR 
 pRegistro: tPtrRegistro; 
 reg: tRegistro; 
BEGIN 
 ... 
 pRegistro:=@reg; 
 … 
 pRegistro^.iniciales:=‘JJP’; 
 pRegistro^.identificacion:=23456; 
 ... 
END. 
pRegistro 
19 
Operaciones con Punteros 
 Operaciones permitidas: 
◦ Asignación (:=) 
◦ Comparación (= y <>) 
 
 
 Para realizar estas operaciones los operandos han de ser 
punteros a variables del mismo tipo o NIL. 
 
 
 Los punteros no se pueden leer ni escribir directamente. 
 
20 
Operaciones: ejemplos (1) 
TYPE 
 ptrACaracter = ^char; 
VAR 
 p1,p2: ptrACaracter; 
 c1,c2: char; 
BEGIN 
 c1:='a'; 
 c2:='h'; 
 p1:=@c1; 
 p2:=@c2; 
 ... 
END. 
'a' 
'h' 
c1 
c2 
p1 
p2 
En esta situación: 
p1 = p2 --> FALSE 
p1 <> p2 --> TRUE 
p1^ = p2^ --> FALSE 
21 
Operaciones: ejemplos (2) 
TYPE 
 ptrACaracter = ^char; 
VAR 
 p1,p2: ptrACaracter; 
 c1,c2: char; 
BEGIN 
 c1:='a'; 
 c2:='h'; 
 p1:=@c1; 
 p2:=@c2; 
 p1:=p2; 
 ... 
END. 
'a' 
'h' 
c1 
c2 
p1 
p2 
Asignación de punteros. 
En esta situación: 
p1 = p2 --> TRUE 
p1 <> p2 --> FALSE 
p1^ = p2^ --> TRUE 
22 
Operaciones: ejemplos (3) 
TYPE 
 ptrACaracter = ^char; 
VAR 
 p1,p2: ptrACaracter; 
 c1,c2: char; 
BEGIN 
 c1:='a'; 
 c2:='h'; 
 p1:=@c1; 
 p2:=@c2; 
 p1^:=p2^; 
 ... 
END. 
'h' 
'h' 
c1 
c2 
p1 
p2 
Asignación de valores 
En esta situación: 
p1 = p2 --> FALSE 
p1 <> p2 --> TRUE 
p1^ = p2^ --> TRUE 
23 
Procedimientos y funciones 
 Pueden ser parámetros, por valor y por referencia, de los 
subprogramas. 
 Se pueden devolver como resultado de una función. 
 Aunque f sea una función que devuelva un puntero a un registro, no 
se permite: 
 
 La sintaxis correcta es: 
 
y posteriormente sí se puede acceder al campo: 
varPuntero:=f(parámetrosReales); 
varPuntero^.campoDelReg; 
f(parámetrosReales)^.campoDelReg; 
24 
Paso por valor de punteros 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro = ^tRegistro; 
VAR 
 pRegistro: tPtrRegistro; 
 registro: tRegistro; 
 
PROCEDURE miProc(dato: tPtrRegistro); 
BEGIN 
 ... 
END; 
 
BEGIN 
 registro.iniciales:=‘ASM’; 
 registro.identificacion:=23455; 
 pRegistro := @ registro; 
 miProc(pRegistro); 
 ... 
END. 
El procedimiento recoge una copia 
del puntero, que apunta al mismo 
lugar que el original. 
Cualquier cambio en esa información 
se verá reflejada en la información 
apuntada por el puntero original. 
25 
Paso por valor de punteros 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro = ^tRegistro; 
VAR 
 pRegistro: tPtrRegistro; 
 registro: tRegistro; 
 
PROCEDURE miProc(dato: tPtrRegistro); 
BEGIN 
 ... 
END; 
 
BEGIN 
 registro.iniciales:=‘ASM’; 
 registro.identificacion:=23455; 
 pRegistro := @ registro; 
 miProc(pRegistro); 
 ... 
END. 
Char[3] 'A' 
'S' 'M' 
23455 
pRegistro 
registro 
dato 
Cualquier cambio en esa información 
se verá reflejada en la información 
apuntada por el puntero original. 
26 
Operación new 
new: procedimiento por el que se reserva un espacio de memoria 
dinámica 
 No siempre es obligatorio reservar memoria para utilizar un puntero 
(ver ejemplos anteriores) 
 Sintaxis: 
 
 Semántica: 
◦ reserva espacio de memoria para almacenar un dato del tipo base 
◦ y la variable puntero que se pasa como parámetro se deja apuntando a dicho 
espacio 
 
new(variablePuntero); 
27 
new: ejemplo (1/2) 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro = ^tRegistro; 
 
VAR 
 pRegistro: tPtrRegistro; 
 
BEGIN 
 ... 
 new(pRegistro); 
 ... 
END. 
Declaramos la variable estática (se 
reserva memoria en tiempo de 
compilación) puntero pRegistro 
pRegistro 
28 
new: ejemplo (2/2) 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro = ^tRegistro; 
 
VAR 
 pRegistro: tPtrRegistro; 
 
BEGIN 
 ... 
 new(pRegistro); 
 ... 
END. 
new reserva memoria (para guardar 
un registro de tipo tRegistro) en 
tiempo de ejecución (dinámica) y el 
puntero que le pasamos 
(pRegistro) se deja apuntando a 
esa porción reservada . 
pRegistro 
29 
Operación dispose 
dispose: procedimiento por el que se libera memoria dinámica 
 Sintaxis: 
 
 Semántica: 
◦ Libera el espacio de memoria apuntado por la variable puntero que se pasa 
como parámetro 
dispose(variablePuntero); 
30 
dispose: ejemplo (1/3) 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro = ^tRegistro; 
 
VAR 
 pRegistro: tPtrRegistro; 
 
BEGIN 
 ... 
 new(pRegistro); 
 ... {Utilización de pRegistro} ... 
 dispose(pRegistro); 
 ... 
END. 
Declaramos la variable estática (se 
reserva memoria en tiempo de 
compilación) puntero pRegistro 
pRegistro 
31 
dispose: ejemplo (2/3) 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro = ^tRegistro; 
 
VAR 
 pRegistro: tPtrRegistro; 
 
BEGIN 
 ... 
 new(pRegistro); 
 ... {Utilización de pRegistro} ... 
 dispose(pRegistro); 
 ... 
END. 
pRegistro 
new reserva memoria (para guardar 
un registro de tipo tRegistro) en 
tiempo de ejecución (dinámica) y el 
puntero que le pasamos 
(pRegistro) se deja apuntando a 
esa porción reservada . 
32 
dispose: ejemplo (3/3) 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro = ^tRegistro; 
 
VAR 
 pRegistro: tPtrRegistro; 
 
BEGIN 
 ... 
 new(pRegistro); 
 ... {Utilización de pRegistro} ... 
 dispose(pRegistro); 
 ... 
END. 
pRegistro 
dispose libera la memoria 
apuntada por el puntero. 
33 
Nino
Resaltado
Desreserva el puntero apuntado, no borra ni modifica los datos que habían. 
Apuntar a NIL el puntero para que así no apunte a nada
Nino
Resaltado
Puntero nulo: NIL 
 NIL (Puntero nulo) es una constante de tipo puntero 
 Un puntero NIL, indica que no apunta a ninguna posición 
de memoria 
 
34 
NIL: ejemplo (1/4) 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro = ^tRegistro; 
 
VAR 
 pRegistro: tPtrRegistro; 
 
BEGIN 
 ... 
 new(pRegistro); 
 ... {Utilización de pRegistro} ... 
 dispose(pRegistro); 
 pRegistro := NIL; 
 ... 
END. 
Declaramos la variable estática (se 
reserva memoria en tiempo de 
compilación) puntero pRegistro 
pRegistro 
35 
NIL: ejemplo (2/4) 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro = ^tRegistro; 
 
VAR 
 pRegistro: tPtrRegistro; 
 
BEGIN 
 ... 
 new(pRegistro); 
 ... {Utilización de pRegistro} ... 
 dispose(pRegistro);
pRegistro := NIL; 
 ... 
END. 
pRegistro 
new reserva memoria (para guardar 
un registro de tipo tRegistro) en 
tiempo de ejecución (dinámica) y el 
puntero que le pasamos 
(pRegistro) se deja apuntando a 
esa porción reservada . 
36 
NIL: ejemplo (3/4) 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro = ^tRegistro; 
 
VAR 
 pRegistro: tPtrRegistro; 
 
BEGIN 
 ... 
 new(pRegistro); 
 ... {Utilización de pRegistro} ... 
 dispose(pRegistro); 
 pRegistro := NIL; 
 ... 
END. 
pRegistro 
dispose libera la memoria 
apuntada por el puntero. 
37 
NIL: ejemplo (4/4) 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro = ^tRegistro; 
 
VAR 
 pRegistro: tPtrRegistro; 
 
BEGIN 
 ... 
 new(pRegistro); 
 ... {Utilización de pRegistro} ... 
 dispose(pRegistro); 
 pRegistro := NIL; 
 ... 
END. 
pRegistro 
asignar NIL al puntero, indica que no 
apunta a ninguna dirección de 
memoria. 
38 
Efecto de omitir el dispose 
TYPE 
 tIniciales = string[3]; 
 tRegistro = RECORD 
 iniciales: tIniciales; 
 identificacion: Integer; 
 END; 
 tPtrRegistro = ^tRegistro; 
 
VAR 
 pRegistro: tPtrRegistro; 
 
BEGIN 
 ... 
 new(pRegistro); 
 ... {Utilización de pRegistro} ... 
 pRegistro := NIL; 
 ... 
END. 
pRegistro 
Si, en el código anterior, se omite la 
liberación de memoria (mediante 
dispose), el resultado es que se 
mantiene reservada una porción de 
memoria innaccesible, ya que se ha 
desapuntado con la asignación de 
NIL a pRegistro. 
39 
Resumen y conclusiones 
 variablePuntero ≠ variablePuntero^ 
 Es muy conveniente liberar el espacio de memoria dinámica mediante 
dispose cuando no se vaya a utilizar más 
 Declarar una variable de tipo puntero no siempre es suficiente para 
poder utilizarla 
 Para crear información dinámicamente se debe llamar al 
procedimiento new. 
 Después de llamar a new, el valor al que apunta el puntero es 
indefinido. Para definirlo es necesario asignarle un valor. 
 Se verán usos más interesantes de los punteros a lo largo de esta 
asignatura 
40 
Estructura de Datos/Temario/Tema1_IntroduccionTAD_new.pdf
TEMA 1 
Introducción a los 
TADs 
ESTRUCTURAS DE DATOS 
1 
Objetivos 
 Preliminares, eficiencia y corrección 
◦ Análisis de complejidad algorítmica en notación O() 
 Abstracción de datos 
 Presentar los Tipos Abstractos de Datos (TAD’s) 
 Presentar la especificación algebraica de TAD’s 
 
2 
Contenidos 
 1.1 Preliminares 
◦ Normas de estilo 
◦ Conceptos aprendidos 
◦ Paradigmas y lenguajes de programación 
◦ Eficiencia y corrección 
 1.2 Abstracción de datos y TAD’s 
◦ Diseño basado en abstracciones: abstracción procedimental y de datos 
◦ Definición de TAD’s y realización de TAD’s en Pascal 
◦ Especificación algebraica de TAD’s 
 
3 
1.1 Preliminares 
 ¿Qué debemos saber? 
◦ El lenguaje Pascal 
◦ Entorno EclipseGavab 
◦ https://github.com/codeurjc/eclipse-gavab 
◦ https://bintray.com/sidelab-urjc/EclipseGavab 
◦ Soltura con la sintaxis e instrucciones de control 
◦ Especialmente Arrays, Registros y Punteros 
 Ciclo de Vida del Software 
◦ Análisis: Qué se hace 
◦ Diseño: Cómo se hace 
◦ Codificación: Se hace 
◦ Pruebas: Se prueba y se corrige 
◦ (Mantenimiento: Se corrige y amplía) 
4 
https://github.com/codeurjc/eclipse-gavab
https://github.com/codeurjc/eclipse-gavab
https://github.com/codeurjc/eclipse-gavab
https://github.com/codeurjc/eclipse-gavab
https://bintray.com/sidelab-urjc/EclipseGavab
https://bintray.com/sidelab-urjc/EclipseGavab
https://bintray.com/sidelab-urjc/EclipseGavab
1.1 Preliminares 
 Conceptos aprendidos 
Problema Algoritmo 
Programa 
Atajo tentador 
Fase de implementación 
Fase de resolución 
5 
1.1 Preliminares: normas de estilo 
 Eliminar varias instrucciones en una misma línea 
 Tabular adecuadamente el anidamiento que generen algunas 
sentencias: 
◦ Evitar: 
 
 
 Salvo contadores, identificadores mnemotécnicos que describan 
cometido o lo que representan (subprogramas y variables). 
 Palabras reservadas en mayúsculas 
◦ WHILE, FOR, RECORD,... 
IF precio>MAXIMO THEN writeln(‘Precio abusivo’); 
6 
1.1 Preliminares: normas de estilo 
Identificadores: descriptivos y minúsculas 
◦ Identificadores con varias palabras, unidas por '_', o con el primer 
carácter de la palabra sufija en mayúscula, o ambos 
◦ Ej.: nombre_archivo, nombreArchivo, nombre_Archivo, … 
◦ Constantes en mayúsculas 
◦ Ej.: IVA, PI, NUMERO_E, ... 
◦ Procedimientos: Empezando por letra mayúscula. 
◦ Ej.: BusquedaBinaria, Apilar, PilaVacia, ... 
◦ Tipos: Empezando por “Tipo” o “T” 
◦ Ej.: TipoPila, TPila, ... 
7 
1.1 Preliminares: normas de estilo 
 Módulos y Ficheros: 
◦ Nombres de programas y módulos (unidades) deben coincidir con los 
nombres de los ficheros que los contienen. 
◦ Empezando por mayúsculas y resto minúsculas 
◦ Escribir una cabecera de identificación como la que se muestra a 
continuación: 
{********************************************************************* 
* * 
* Módulo: Nombre * 
* Fichero: ( ) Programa ( ) Espec. TAD ( ) Impl. TAD ( ) Otros * 
* Autor(es): Nombre(s) * 
* Fecha: Fecha de actualización * 
* * 
* Descripción: * 
* Breve descripción del módulo (párrafo corto) * 
* * 
*********************************************************************} 
8 
1.1 Preliminares: normas de estilo 
 Uso extendido de subprogramas para tareas bien 
identificadas 
 Adecuado uso de sentencias de repetición (especialmente 
bucles FOR y WHILE) 
◦ Esquema de búsqueda vs recorrido 
 Evitar variables globales en subprogramas 
 Uso adecuado de funciones 
◦ Devuelven un único valor 
 
9 
1.1 Preliminares: conceptos aprendidos 
 Arrays en Pascal: 
◦ Un tipo de dato array se define en la sección de declaración de tipos 
TYPE 
TYPE 
 TipoCoordenada = ARRAY [1..3] OF real; 
 TipoVector = ARRAY [1..3] OF real; 
 TipoMatriz = ARRAY [1..3, 1..7] OF char; 
 TipoViviendas = ARRAY [1..3, 1..3, ’A’..’E’]OF boolean; 
 
VAR 
 origen: TipoCoordenada; 
 desplazamiento: TipoCoordenada TipoVector; 
 
10 
1.1 Preliminares: conceptos aprendidos 
 Arrays en Pascal (cont.): 
◦ Los arrays son estructuras de acceso directo, ya que permiten 
almacenar y recuperar directamente los datos, especificando su 
posición dentro de la estructura. 
◦ Los arrays son estructuras de datos homogéneas: sus elementos son 
todos del mismo tipo. 
◦ El tamaño de un array se establece de forma fija, en un programa, 
cuando se define una variable de este tipo. 
◦ Cuidado con paso de arrays como parámetros de tipo anónimo a 
subprogramas. 
 
11 
1.1 Preliminares: conceptos aprendidos 
 Registros en Pascal: 
◦ Tipo de datos estructurado que permite almacenar datos 
heterogéneos (de distintos tipos) 
TYPE 
 TNombreReg = RECORD 
 idCampo1 : idTipo1; 
 idCampo2 : idTipo2; 
 ... 
 idCampon : idTipon 
 END; {Fin de TNombreReg} 
12 
1.1 Preliminares: conceptos aprendidos 
Registros en Pascal (cont.): 
◦ Las funciones no pueden devolver un registro. 
◦ Para acceder a un campo se usa el operador punto (.): 
 
 
◦ También se puede acceder a los campos de un registro “abriendo” el 
registro con la sentencia WITH 
◦ Absolutamente no recomendado 
NombreVariableRegistro.NombreCampo 
13 
1.1 Preliminares: conceptos aprendidos 
