Descarga la aplicación para disfrutar aún más
Lea materiales sin conexión, sin usar Internet. Además de muchas otras características!
Apuntes completos de EDI _Estructura de Datos y de la Información_ en C__
Materiales Generales
Esta es una vista previa del archivo. Inicie sesión para ver el archivo original
EDI todo/ejercs T-1.pdf
1
Estructuras de Datos y de la Información
Ingeniería Técnica en Informática de Gestión. Curso 2007/2008
Ejercicios del Tema 1
Análisis de algoritmos iterativos
1. Determina la complejidad temporal en el caso peor y en el caso mejor de los siguientes algorit-
mos de ordenación.
(a) Ordenación por inserción
void ordenaIns ( int v[], int num ) {
int i, j, x;
for ( i = 1; i < num; i++ ) {
x = v[i];
j = i-1;
while ( (j >= 0 ) && (v[j] > x) ){
v[j+1] = v[j];
j = j-1;
}
v[j+1] = x;
}
}
(b) Ordenación por selección
void ordenaSel ( int v[], int num ) {
int i, j, menor, aux;
for ( i = 0; i < num; i++ ) {
menor = i;
for ( j = i+1; j < num; j++ )
if ( v[j] < v[menor] )
menor = j;
if ( i != menor ) {
aux = v[i];
v[i] = v[menor];
v[menor] = aux;
}
}
}
(c) Método de la burbuja
void ordenaBur ( int v[], int num ) {
int i, j, aux;
bool modificado;
i = 0;
modificado = true;
while ( (i < num-1) && modificado ) {
modificado = false;
for ( j = num-1; j > i; j-- )
if ( v[j] < v[j-1] ) {
aux = v[j];
v[j] = v[j-1];
v[j-1] = aux;
modificado = true;
}
i++;
}
}
2
2. Determina la complejidad temporal en el caso peor del siguiente algoritmo.
int buscaBin( int v[], int num, int x ) {
int izq, der, centro;
izq = -1;
der = num;
while ( der != izq+1 ) {
centro = (izq+der) / 2;
if ( v[centro] <= x )
izq = centro;
else
der = centro;
}
return izq;
}
3. El siguiente algoritmo de búsqueda decide si un entero dado aparece o no dentro de un vector de
enteros dado:
bool busca( int v[], int num, int x ) {
// Pre.: v es un array de al menos num elementos
int j;
bool encontrado;
j = 0;
encontrado = false;
while ( (j < num) && ! encontrado ) {
encontrado = ( v[j] == x );
j++;
}
return encontrado;
// Post.: devuelve true si x aparece en v entre las posiciones 0 .. num-1
// y false en caso contrario
}
Analiza la complejidad en promedio del algoritmo, bajo las hipótesis siguientes: (a) la probabilidad de
que x aparezca en v es un valor constante p, 0 < p < 1; y (b) la probabilidad de que x aparezca en
la posición i de v (y no en posiciones anteriores) es la misma para cada índice i, 0 ≤ i < num.
4. Las dos implementaciones siguientes calculan la potencia nm:
int potencia1(int n, int m)
{
int p;
p=1;
while (m>0)
{
p=p*n; m--;
}
return p;
}
int potencia2(int n, int m)
{
int p;
p=1;
while (m>0)
{
if (m%2!=0) p=p*n;
m=m/2;
n=n*n;
}
return p;
}
Describir su funcionamiento y determinar su complejidad en el peor caso, ¿cuál es mejor?.
3
5. (Febrero 2003) Describir brevemente lo que hace el siguiente fragmento de código y determinar
su complejidad asintótica en función de n:
for (i=1; i<=n; i++){
for (j=1; j<=n-i; j++) cout << " ";
for (j=1; j<=i; j++) cout << j;
for (j=i-1; j>=1; j--) cout << j;
cout << "\n";
}
6. Los algoritmos de ordenación de arrays han sido objeto de estudio meticuloso en el área de la in-
formática, así como la complejidad asociada a los mismos. Los que hemos estudiado nosotros
hasta el momento son generales en el sentido de que, en principio, sirven para ordenar cualquier
array de enteros (es muy fácil modificarlos para ordenar arrays de cualquier tipo ordenado).
Sin embargo, para algunos problemas concretos es posible sacar partido de las particularidades
del problema. Por ejemplo, si sabemos que el array a ordenar v[1..n] contiene enteros en un rango
acotado (y relativamente pequeño), n0 ≤ v[i] ≤ n1 para todo i ∈ {1, . . . , n}, podemos utilizar el
siguiente algoritmo:
construir la tabla de frecuencias t asociada a v. Esta tabla no es más que un array t[n0..n1] tal
que t[i] contiene el número de apariciones del elemento i en el array inicial v
a partir de la tabla de frecuencias, obtener la ordenación del vector v. La idea es: colocar al
principio de v t[n0] elementos n0, a continuación colocar t[n0 +1] elementos n1 y así sucesi-
vamente.
Por ejemplo, consideremos v = [1, 3, 2, 4, 5, 3, 4, 2, 3, 1, 4, 5]
Todos los elementos están en el rango [1.,5]. La tabla de frecuencias asociada es:
1 2 3 4 5
t 2 2 3 3 2
Ahora, colocamos en v en este orden 2 unos, 2 doses, 3 treses, 3 cuatros y 2 cincos, y obtenemos
el array ordenado:
v = [1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5]
Implementar este algoritmo en C++ para vectores de enteros en el rango 0.,999. ¿Cuál es la com-
plejidad del algoritmo en el peor caso? ¿Y en el mejor? Ampliar la funcionalidad de modo que el
rango de los elementos se determine en tiempo de ejecución y el algoritmo opere de acuerdo con
este dato. ¿Cuál es la complejidad de este nuevo algoritmo?
7. (Junio 2003) Hoy es día de excursión para todo el cole y los niños están muy contentos. Como
son muchísimos niños, para evitar despistes y no perder a ninguno, la señorita encargada los ha
colocado por orden alfabético. Sin embargo, en un despiste de la “seño”, algunos niños han
hecho de las suyas y han intercambiado su posición con la de uno de los compañeros de al lado
(el de la izquierda o el de la derecha). Los niños más revoltosos han repetido este proceso varias
veces, mientras que hay otros que no se han movido ni una sola vez, como Remedios que es muy
buena. La señorita se enfada mucho cuando descubre el desaguisado: “He malgastado n*log(n) (uni-
dades de tiempo, siendo n el número de niños) en ordenaros... ¡Os pondré un negativo a todos!”. Pero Remedios,
que tiene un expediente inmaculado, protesta: “Seño, yo no me he movido ninguna vez. Jaimito es el que
más veces se ha movido. Yo lo he visto... y se ha movido 4 veces”.
Casualmente un alumno de EDI que ve lo que ha ocurrido y tranquiliza a la señorita diciéndole
que la entropía generada por los niños no es excesiva y que de hecho puede diseñar un algoritmo
de complejidad lineal para recomponer la ordenación. Asumiendo que los niños están representa-
dos en un vector diseña e implementa un algoritmo que reconstruya la ordenación en tiempo
lineal. Por simplicidad, puedes suponer que cada niño está representado por un entero con res-
pecto al que se ordena. Razona que el algoritmo construido es de complejidad lineal.
4
Órdenes de Complejidad
8. Demostrar:
a) f(n) ∈ O(g(n)) ⇔ O(f(n)) ⊆ O(g(n))
b) O(f(n)) = O(g(n)) ⇔ f(n) ∈ O(g(n)) y g(n) ∈ O(f(n))
d) O(c · f(n)) = O(f(n)), siendo c > 0.
9. Demostrar la regla de la suma para el orden exacto:
Θ(f(n) + g(n)) = Θ(max(f(n), g(n)))
10. Demostrar las siguientes inclusiones estrictas:
O(1) ⊂ O(log(n)) ⊂ O(n) ⊂ O(n ¢ log(n)) ⊂ O(n2) ⊂ O(n3) ⊂ . . . ⊂ O(nk) ⊂ O(2n) ⊂ O(n!)
11. Demostrar la propiedad de la dualidad:
f(n) ∈ O(g(n)) ⇔ g(n) ∈ Ω(f(n))
12. Demostrar o refutar las siguientes propiedades:
a) f(n) ∈ O(n2) y g(n) ∈ O(n) ⇒ f(n)/g(n) ∈ O(n)
b) f(n) ∈ Θ (n2) y g(n) ∈ Θ (n) ⇒ f(n)/g(n) ∈ Θ (n)
13. Demostrar o refutar las siguientes afirmaciones:
a) 2n + n99 ∈ O(n99)
b) 2n + n99 ∈ Ω(n99)
c) 2n + n99 ∈ Θ(n99)
d) 2n + n99 ∈ O(2n)
e) 2n + n99 ∈ Ω(2n)
f) 2n + n99 ∈ Θ(2n)
14. Buscar ejemplos de funciones f(n) y g(n) tales que f(n) ∈ O(g(n)) pero f(n) ∉ Ω(g(n))
EDI todo/ejercs T-2.pdf
1
Estructuras de Datos y de la Información
Ingeniería Técnica en Informática de Gestión. Curso 2007/2008
Ejercicios del Tema 2
Diseño de algoritmos recursivos
1. Dado un vector de enteros de longitud N, diseñar un algoritmo de complejidad O(N·logN) que
encuentre el par de enteros más cercanos. ¿Se puede hacer con complejidad O(N)?
2. Dado un vector de enteros de longitud N, diseñar un algoritmo de complejidad O(N·logN) que
encuentre el par de enteros más lejanos. ¿Se puede hacer con complejidad O(N)?
3. Diseñar un algoritmo recursivo que realice
el cambio de base de un número binario dado en su
correspondiente decimal.
4. Diseñar un algoritmo recursivo que, dado un array de caracteres, cuente el número de vocales que
aparecen en él.
5. Escribir una función recursiva que devuelva el producto de los elementos de un array mayores o
iguales que un determinado número b
6. Implementa una función recursiva simple cuadrado que calcule el cuadrado de un número natural
n, basándote en el siguiente análisis de casos:
Caso directo: Si n = 0, entonces n2 = 0
Caso recursivo: Si n > 0, entonces n2 = (n–1)2 + 2*(n–1) + 1
7. Implementa una función recursiva log que calcule la parte entera de logb n, siendo los datos b y n
enteros tales que b ≥ 2 ∧ n ≥ 1. El algoritmo obtenido deberá usar solamente las operaciones de
suma y división entera.
8. Implementa una función recursiva bin tal que, dado un número natural n, bin(n) sea otro número
natural cuya representación decimal tenga los mismos dígitos que la representación binaria de n.
Es decir, debe tenerse: bin(0) = 0; bin(1) = 1; bin(2) = 10; bin(3) = 11; bin(4) = 100; etc.
9. Implementa una función recursiva doble que satisfaga la siguiente especificación:
int sumaVec( int v[], int a, int b ) {
// Pre: 0 <= a <= num && -1 <= b <= num-1 && a <= b+1
// siendo num el número de elementos de v
// Post: devuelve la suma de las componentes de v entre a y b
}
Básate en el siguiente análisis de casos:
Caso directo: a ≥ b
v[a..b] tiene a lo sumo un elemento. El cálculo de s es simple.
Caso recursivo: a < b
v[a..b] tiene al menos dos elementos. Hacemos llamadas recursivas para sumar v[a..m] y
v[m+1..b], siendo m = (a+b) / 2.
2
10. Implementa un procedimiento recursivo simple dosFib que satisfaga la siguiente especificación
pre/post:
void dosFib( int n, int& r, int& s ) {
// Pre: n >= 0
// Post: r = fib(n) && s = fib(n+1)
}
En la postcondición, fib(n) y fib(n+1) representan los números que ocupan los lugares n y n+1
en la sucesión de Fibonacci, para la cual suponemos la definición recursiva habitual.
11. Implementa una función recursiva que calcule el número combinatorio ⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
m
n
a partir de los datos
m, n: Integer tales que n ≥ 0 ∧ m ≥ 0. Usa la recurrencia siguiente:
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛ −
+⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
−
−
=⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
m
n
m
n
m
n 1
1
1
siendo 0 < m < n
12. Una palabra se llama palíndroma si la sucesión de sus letras no varía al invertir el orden. Especifica
e implementa una función recursiva final que decida si una palabra dada, representada como vec-
tor de caracteres, es o no palíndroma.
13. El problema de las torres de Hanoi consiste en trasladar una torre de n discos de diferentes tama-
ños desde la varilla ini a la varilla fin, con ayuda de la varilla aux. Inicialmente los n discos están
apilados de mayor a menor, con el más grande en la base. En ningún momento se permite que un
disco repose sobre otro menor que él. Los movimientos permitidos consisten en desplazar el dis-
co situado en la cima de una de las varillas a la cima de otra, respetando la condición anterior.
Construye un procedimiento recursivo hanoi tal que la llamada hanoi(n, ini, fin, aux) produzca el
efecto de escribir una serie de movimientos que represente una solución del problema de Hanoi.
Supón disponible un procedimiento movimiento(i, j), cuyo efecto es escribir "Movimiento de la va-
rilla i a la varilla j ".
Análisis de algoritmos recursivos
14. En cada uno de los casos que siguen, plantea una ley de recurrencia para la función T(n) que mide
el tiempo de ejecución del algoritmo en el caso peor, y usa el método de desplegado para resolver
la recurrencia.
(a) Función log (ejercicio 2).
(b) Función bin (ejercicio 3).
(c) Función sumaVec (ejercicio 4).
(d) Procedimiento dosFib (ejercicio 5).
(e) La función del ejercicio 6.
(f) Función palindroma (ejercicio 7).
(g) Procedimiento hanoi (ejercicio 8).
15. Aplica las reglas de análisis para dos tipos comunes de recurrencia a los algoritmos recursivos del
ejercicio anterior. En cada caso, deberás determinar si el tamaño de los datos del problema decre-
ce por sustracción o por división, así como los parámetros relevantes para el análisis.
3
16. En cada caso, calcula a partir de las recurrencias el orden de magnitud de T(n). Hazlo aplicando
las reglas de análisis para dos tipos comunes de recurrencia.
(a) T(1) = c1; T(n) = 4 ⋅ T(n/2) + n, si n > 1
(b) T(1) = c1; T(n) = 4 ⋅ T(n/2) + n2, si n > 1
(c) T(1) = c1; T(n) = 4 ⋅ T(n/2) + n3, si n > 1
17. Usa el método de desplegado para estimar el orden de magnitud de T(n), suponiendo que T obe-
dezca la siguiente recurrencia:
T(1) = 1; T(n) = 2 ⋅ T(n/2) + n ⋅ log n, si n > 1
¿Pueden aplicarse en este caso las reglas de análisis para dos tipos comunes de recurrencia?
¿Por qué?
Eliminación de la recursión final
18. Aplica la transformación de recursivo final a iterativo sobre la función palindroma del ejercicio 7.
19. La primera versión (la que aparece a la izquierda) de la búsqueda binaria es la misma que aparecía
en el ejercicio 6 de la hoja 1 de ejercicios, mientras que la segunda (la que aparece a la derecha),
vista en teoría, es el resultado de transformar a iterativo la versión recursiva de este algoritmo.
¿En qué se diferencian estos dos algoritmos iterativos?
Escribe un algoritmo recursivo final con la misma idea de la primera versión iterativa.
int buscaBin( TElem v[], int num, TElem x )
{
int izq, der, centro;
izq = -1;
der = num;
while ( der != izq+1 ) {
centro = (izq+der) / 2;
if ( v[centro] <= x )
izq = centro;
else
der = centro;
}
return izq;
}
int buscaBin( TElem v[], int num, TElem x )
{
int a, b, p, m;
a = 0;
b = num-1;
while ( a <= b ) {
m = (a+b) / 2;
if ( v[m] <= x )
a = m+1;
else
b = m-1;
}
p = a - 1;
return p;
}
4
Técnicas de generalización
20. Se trata de obtener un algoritmo recursivo de complejidad lineal que dado un polinomio de coefi-
cientes enteros, representado como un vector, y el valor de la incógnita, calcule el valor del
polinomio. En el vector, de tipo int v[ ], se almacenan los coeficientes del polinomio ordenados
por exponentes: en la posición 0 el coeficiente de x0, en la posición 1 el coeficiente de x, y así su-
cesivamente.
Idea: Implementa primero una función recursiva evaluaGen de complejidad cuadrática donde las
potencias de x se obtengan de forma iterativa. A continuación, plantea otra generalización eva-
luaEfi que permita obtener el algoritmo de complejidad lineal, y escribe su implementación
transformando el código de evaluaGen. Puede conseguirse recursión final.
21. Comprueba que el procedimiento combiGen especificado como sigue es una generalización de la
función combi del ejercicio 6, y que combiGen admite un algoritmo recursivo simple, más eficiente
que la recursión doble de combi, implementándola.
void combiGen ( int a, int b, int v[], int num ) {
// Pre: 0 <= b <= a && b < num
// Post: para cada i entre 0 y b se tiene v[i] = ⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
i
a
}
22. Especifica e implementa un algoritmo recursivo que dado un vector de enteros calcule el número
de posiciones de dicho vector que cumplan la condición de que la suma de las componentes a su
izquierda coincida con la suma de las componentes a su derecha. Utilizando el método de des-
pliegue de recurrencias, analiza la complejidad temporal en el caso peor del algoritmo obtenido.
23. Especifica e implementa un algoritmo recursivo que dado un vector de enteros lo reorganice de
forma que los valores pares ocupen la parte izquierda del vector y los valores impares la parte de-
recha. Utilizando el método de despliegue de recurrencias, analiza la complejidad temporal en el
caso peor del algoritmo obtenido.
24. Especifica e implementa un algoritmo recursivo que
dado un vector de enteros determine si el
vector tiene forma de montaña. Un vector tiene forma de montaña si contiene una secuencia estric-
tamente creciente seguida de una secuencia estrictamente decreciente −una de las dos secuencias
puede ser vacía–. Utilizando el método de despliegue de recurrencias, analiza la complejidad tem-
poral en el caso peor del algoritmo obtenido.
25. Especifica e implementa un algoritmo recursivo que dado un vector v de enteros, que viene dado
en orden estrictamente creciente, determine si el vector contiene alguna posición i que cumpla
v[i]=i. Utilizando el método de despliegue de recurrencias, analiza la complejidad temporal en el
caso peor del algoritmo obtenido.
26. Especifica e implementa un algoritmo recursivo que dados dos vectores u, v de enteros, ordena-
dos en orden estrictamente creciente, obtenga el número de elementos que aparecen en los dos
vectores. Utilizando el método de despliegue de recurrencias, analiza la complejidad temporal en
el caso peor del algoritmo obtenido.
5
27. Especifica e implementa un algoritmo recursivo que dado un vector v de enteros determine si
contiene un punto de inflexión. Un punto de inflexión es una posición del vector tal que todas las
componentes que aparecen a su izquierda son negativas, y todas las que aparecen a su derecha
son positivas o 0. Si el vector contiene punto de inflexión la función devolverá su posición, y si
no lo contiene devolverá –1. Utilizando el método de despliegue de recurrencias, analiza la com-
plejidad temporal en el caso peor del algoritmo obtenido.
28. Especifica e implementa un algoritmo recursivo que dado un vector v de enteros determine si el
vector tiene la forma 1n 0n 0n 1n, es decir: un cierto número n de unos, seguidos del doble (2n) de
ceros, seguidos a su vez de otros n unos. Por ejemplo, un vector de tamaño 8 con las componen-
tes [1,1,0,0,0,0,1,1] cumpliría lo anterior. Utilizando el método de despliegue de recurrencias,
analiza la complejidad temporal en el caso peor del algoritmo obtenido.
29. Especifica e implementa un algoritmo recursivo que dado un vector v de enteros determine si el
vector representa una escalera con peldaños de ancho estrictamente creciente, donde:
— Un peldaño queda constituido por una secuencia de apariciones consecutivas del mismo ele-
mento. Por ejemplo, el vector [1, 6, 6, 6, 2, 2, 5] tiene 4 peldaños.
— El ancho de un peldaño es el número de apariciones consecutivas del elemento que constituye
el peldaño. Por ejemplo, los anchos de los 4 peldaños del vector anterior son 1, 3, 2 y 1 (por
orden de aparición).
— Un vector forma una escalera con peldaños de ancho estrictamente creciente si cada peldaño
es más ancho que el anterior, como, por ejemplo, el vector [3, 3, 1, 1, 1, 1, 5, 5, 5, 5, 5, 5].
Utilizando el método de despliegue de recurrencias, analiza la complejidad temporal en el caso
peor del algoritmo obtenido.
30. Especifica e implementa un algoritmo recursivo que dado un vector u de enteros obtenga la lon-
gitud de la meseta más larga. Una meseta es un conjunto de posiciones consecutivas del vector que
contienen el mismo valor. Utilizando el método de despliegue de recurrencias, analiza la comple-
jidad temporal en el caso peor del algoritmo obtenido.
EDI todo/ejercs T-3.pdf
Estructuras de Datos y de la Información
Ingeniería Técnica en Informática de Gestión. Curso 2007/2008
Ejercicios del Tema 3
Las implementaciones de los TAD se realizarán como clases de C++. En cada caso, se formulará el in-
variante de la representación y las especificaciones pre/post de los procedimientos y funciones que
realicen las operaciones del TAD. En el caso de los TADs genéricos, la implementación se realizará
mediante clases parametrizadas (templates o plantillas).
1. Desarrolla un TAD TComplejo que ofrezca el tipo TComplejo junto con las operaciones adecuadas
para construir números complejos y calcular con ellos.
2. Desarrolla un TAD TMonomio para representar los monomios como coeficiente y grado, con las
operaciones de creación, consultar el grado y consultar el coeficiente.
A continuación, utilizando el TAD TMonomio desarrolla un TAD TPolinomio que ofrezca el tipo de
los polinomios, con operaciones para crear el polinomio nulo, añadir un nuevo monomio a un
polinomio, consultar el coeficiente de un determinado grado, consultar el grado del polinomio,
sumar polinomios y evaluar un polinomio para un valor dado de la indeterminada.
P ara el TAD TPolinomio construye dos implementaciones:
— representando los polinomios mediante un vector de monomios ordenados por el grado; y
— representando los polinomios mediante una lista enlazada de monomios ordenados por el gra-
do.
3. ñade a la clase TPilaDinamica<TElem> dos nuevas operaciones: A
— fondo: devuelve el elemento del fondo de una pila no vacía.
— inversa: devuelve una nueva pila con los elementos de la pila original apilados en orden inverso.
4. Las pilas formadas por números naturales del intervalo [0..N–1] (para cierto N ≥ 2 fijado de an-
temano) se pueden representar por medio de números, entendiendo que un número natural P
cuya representación en base N tenga “1” como dígito de mayor peso representa la pila formada
por los restantes dígitos de la representación de P en base N (excepto el de mayor peso), siendo
la cima el dígito de menor peso. Por ejemplo, si N = 10, el número 1073 representa la pila que
contiene los números 0, 7, 3, con 0 en la base y 3 en la cima. Implementa el TAD TPilaNat con
esta representación. Comprueba que esta representación permite implementar todas las operacio-
nes de las pilas con coste O(1).
5. Desarrolla un TAD genérico TDosPilas<TElem> que representa una pareja de pilas que pueden
anejarse independientemente del modo usual. m
— Desarrolla una implementación estática de este TAD, representando la pareja de pilas con
ayuda de un único vector de almacenamiento. Organiza la implementación de modo que las
dos pilas crezcan en sentidos opuestos, cada una desde uno de los dos extremos del vector.
— Desarrolla una segunda implementación utilizando la clase TPilaDinamica<TElem>.
6. Especifica e implementa un TAD genérico TLista<TElem> que represente a las listas de elemen-
tos con las siguientes operaciones:
— Nuevo: crea una lista vacía.
— Cons: añade un elemento al principio de la lista.
— ponDr: añade un elemento al final de la lista.
— primero: devuelve el primer elemento de la lista.
— resto: elimina el primer elemento de la lista.
— ultimo: devuelve el último elemento de la lista.
— inicio: elimina el último elemento de la lista.
— concatena: añade al final de una lista los elementos de otra.
1
2
— esVacio: determina si la lista está vacía.
— numElem: devuelve el número de elemento de la lista
— elemEn: devuelve el elemento que está en una cierta posición de la lista, identificada por su
número de orden.
La lista se debe implementar como una lista enlazada.
7. xplica razonadamente qué mostrará este programa por pantalla. E
typedef TPilaDinamica< TPilaDinamica<int> > TPilas;
typedef TPilaDinamica< TPilaDinamica<int>* > TPuntPilas;
TPilas pilas ( int max ) {
TPilas res;
TPilaDinamica<int> pila;
for ( int i = 0; i < max; i++ ) {
pila = TPilaDinamica<int>();
for ( int j = 0; j < i; j++ )
pila.apila(j);
res.apila(pila);
}
return res;
}
int suma ( TPilas pilaDePilas ) {
TPilaDinamica< int > pila;
int res;
res = 0;
while ( ! pilaDePilas.esVacio() ) {
pila = pilaDePilas.cima();
pilaDePilas.desapila();
while ( ! pila.esVacio() ) {
res += pila.cima();
pila.desapila();
}
}
return res;
}
TPuntPilas pilas2 ( int max ) {
TPuntPilas res;
TPilaDinamica<int>* pila;
for ( int i = 0; i < max; i++ ) {
pila = new TPilaDinamica<int>();
for ( int j = 0; j < i; j++ )
pila->apila(j);
res.apila(pila);
}
return res;
}
int suma2 ( TPuntPilas pilaDePilas )
{
TPilaDinamica< int >* pila;
int res;
res = 0;
while ( ! pilaDePilas.esVacio() ) {
pila = pilaDePilas.cima();
pilaDePilas.desapila();
while ( ! pila->esVacio() ) {
res += pila->cima();
pila->desapila();
}
}
return res;
}
int main(int argc, char* argv[])
{
TPilas pilaDePilas;
TPuntPilas pilaDePilas2;
pilaDePilas = pilas( 4 );
cout << suma( pilaDePilas ) + suma( pilaDePilas ) << endl;
pilaDePilas2 = pilas2( 4 );
cout << suma2( pilaDePilas2 ) + suma2( pilaDePilas2 ) << endl;
}
Estructuras de Datos y de la InformaciónIngeniería Técnica en Informática de Gestión. Curso 2007/2008Ejercicios del Tema 3
EDI todo/ejercs T-4.pdf
1
Estructuras de Datos y de la Información
Ingeniería Técnica en Informática de Gestión. Curso 2007/2008
Ejercicios del Tema 4
1. Transforma a iterativo los siguiente algoritmos recursivos:
(a) Función log del ejercicio 2 de la hoja 2.
(b) Procedimiento dosFib del ejercicio 5 de la hoja 2.
(c) Función del ejercicio 17 de la hoja 2.
Aplica en cada caso la técnica de transformación que conlleve un menor consumo de espacio en
el algoritmo iterativo.
2. Una frase se llama palíndroma si la sucesión de caracteres obtenida al recorrerla de izquierda a de-
recha (ignorando los blancos) es la misma que si el recorrido se hace de derecha a izquierda. Esto
sucede, por ejemplo, con la socorrida frase “dábale arroz a la zorra el abad”. Construye una fun-
ción iterativa ejecutable en tiempo lineal, que decida si una frase dada en forma de cola de caracteres
es o no palíndroma. El algoritmo utilizará una pila de caracteres, declarada localmente.
3. El agente 0069 ha inventado un nuevo método de codificación de mensajes secretos. El mensaje
original X se codifica en dos etapas:
— Primero, X se transforma en X’ reemplazando cada sucesión de caracteres consecutivos que
no sean vocales por su imagen especular.
— A continuación, X’ se transforma en la sucesión de caracteres X’’ obtenida al ir tomando suce-
sivamente: el primer carácter de X’; luego el último; luego el segundo; luego el penúltimo; etc.
Ejemplo: para X = “Bond, James Bond”, resultan:
X’ = “BoJ ,dnameB sodn” y X’’ = “BnodJo s, dBneam”
Construye los algoritmos de codificación y descodificación de mensajes y analiza su complejidad,
utilizando pilas y colas. Supón que el mensaje inicial viene dado como una cola de caracteres.
4. Añade las siguientes operaciones a la clase TListaDinamica<TElem>:
— ==: comparación sobre igualdad entre listas
— <=: comparación de orden entre listas
— ordenada: determina si una lista está ordenada
— insertaOrd: inserta un elemento delante del primero que es mayor que él.
5. Resuelve los problemas que siguen aplicando el esquema de recorrido de secuencias. En cada ca-
so, el contenido de la secuencia debe quedar inalterado.
(a) Contar el número de apariciones de ‘a’ en una secuencia de caracteres dada.
(b) Dada una secuencia de enteros, contar cuántas posiciones hay en ella tales que el entero que
aparece en esa posición es igual a la suma de todos los precedentes.
6. Resuelve los problemas que siguen aplicando el esquema de búsqueda secuencial.
(a) Buscar la primera aparición de ‘b’ en una secuencia de caracteres dada.
(b) Dada una secuencia de enteros, buscar la primera posición ocupada por un número que sea
menor que todos los anteriores.
7. Algunos problemas de procesamiento de secuencias requieren modificar y/o combinar los es-
quemas de recorrido y búsqueda secuencial. Resuelve los casos siguientes:
(a) Dada una secuencia de caracteres, copiarla en otra eliminando los blancos múltiples.
(b) Contar el número de caracteres anteriores y posteriores a la primera aparición de ‘a’ en una
secuencia de caracteres dada.
(c) Contar el número de parejas de vocales consecutivas que aparecen en una secuencia de ca-
racteres dada.
2
8. Una expresión aritmética construida con los operadores binarios ‘+’, ‘–’, ‘*’, ‘/’ y operandos (re-
presentados cada uno por un solo carácter) se dice que está en forma postfija si es o bien un solo
operando o dos expresiones en forma postfija una tras otra, seguidas inmediatamente de un ope-
rador. Lo que sigue es un ejemplo de una expresión escrita en la notación infija habitual, junto
con su forma postfija:
Forma infija: (A/(B–C))*(D+E)) Forma postfija: ABC–/DE+*
Diseña un algoritmo iterativo que calcule el valor de una expresión dada en forma postfija por el
siguiente método: se inicializa una pila vacía de números y se van recorriendo de izquierda a dere-
cha los caracteres de la expresión. Cada vez que se pasa por un operando, se apila su valor. Cada
vez que se pasa por un operador, se desapilan los dos números más altos de la pila, se componen
con el operador, y se apila el resultado. Al acabar el proceso, la pila contiene un solo número, que
es el valor de la expresión. Representa la expresión dada como secuencia de caracteres, y supón
disponible una función valor que asocie a cada operando su valor numérico.
9. Dado un número natural N ≥ 2, se llaman números afortunados a los que resultan de ejecutar el si-
guiente proceso: se comienza generando una cola que contiene los números desde 1 hasta N, en
este orden; se elimina de la cola un número de cada 2 (es decir, los números 1, 3, 5, etc.); de la
nueva cola, se elimina ahora un número de cada 3; etc. El proceso termina cuando se va a elimi-
nar un número de cada m y el tamaño de la cola es menor que m. Los números que queden en la
cola en este momento son los afortunados. Diseña un procedimiento que reciba N como pará-
metro y produzca una secuencia formada por los números afortunados resultantes.
(Indicación: para eliminar de una cola de n números un número de cada m, hay que reiterar n veces
el siguiente proceso: extraer el primer número de la cola, y añadirlo al final de la misma, salvo si le
tocaba ser eliminado.)
10. Añade las siguientes operaciones a la clase TSecuenciaDinamica<TElem>:
— busca: operación que busca una secuencia s’ dentro de otra secuencia s. La búsqueda se realiza
en s, a partir de la posición actual del punto de interés, y los elementos a buscar son aquellos
que aparecen a la derecha del punto de interés de s’. Esta operación modifica el punto de inte-
rés de s, colocándolo delante de la primera aparición de la subsecuencia buscada, o al final del
todo si la subsecuencia no se ha encontrado. La operación no está definida si el punto de inte-
rés de s’ está a la derecha del todo –no hay nada que buscar–.
Por ejemplo, si trabajásemos con secuencias de caracteres:
— borraSec: operación que borra todas las apariciones de una secuencia s’ dentro de otra secuencia
s. La búsqueda de los elementos a eliminar se realiza de la misma forma que en la operación
busca, es decir, se busca en s a partir de la posición del punto de interés, y la subsecuencia a
eliminar es la compuesta por los elementos de s’ a la derecha del punto de interés. Igualmente,
la operación no está definida si el punto de interés de s’ se encuentra al final.
11. Implementa el TAD secuencia utilizando como tipo representante una par de listas, según las in-
dicaciones vistas en clase. Para mejorar la eficiencia de algunas operaciones, añade a la
implementación de las listas una operación de concatenación por la izquierda.
s : Una casa al borde del mar, un gran mar, en la playa
s’ : La mar
s : Una casa al borde del mar, un gran mar, en la playa
s’ : La mar
Entrada:
Salida:
EDI todo/ejercs T-5.pdf
1
Estructuras de Datos y de la Información
Ingeniería Técnica en Informática de Sistemas. Curso 2007/2008
Ejercicios del tema 5
Arboles
1. Añade las siguientes operaciones a la clase TArbinDinamico<TElem>, analizando su complejidad.
– talla: Arbin[Elem] → Nat
Calcula la talla de un árbol binario, definida
como el número de nodos de la rama más
larga.
– numNodos: Arbin[Elem] → Nat
Calcula el número de nodos de un árbol binario.
– numHojas: Arbin[Elem] → Nat
Calcula el número de hojas de un árbol binario.
– espejo: Arbin[Elem] → Arbin[Elem]
Construye la imagen especular de un árbol binario.
– frontera: Arbin[Elem] → Sec[Elem]
Obtiene la secuencia formada por los elementos almacenados en las hojas de un árbol
binario, tomados de izquierda a derecha.
– ==: (Arbin[Elem], Arbin[Elem]) → Bool
Determina si dos árboles binarios son iguales.
2. Un árbol de codificación es un árbol binario a que almacena en cada una de sus hojas un carácter di-
ferente. La información almacenada en los nodos internos se considera irrelevante. Si un cierto
carácter c se encuentra almacenado en la hoja de posición α, se considera que α es el código asig-
nado a c por el árbol de codificación a. Más en general, el código de cualquier cadena de
caracteres dada se puede construir concatenando los códigos de los caracteres que la forman, res-
petando su orden de aparición.
(a) Dibuja el árbol de codificación correspondiente al código siguiente:
Carácter Código
‘A’ 1.1
‘T’ 1.2
‘G’ 2.1.1
‘R’ 2.1.2
‘E’ 2.2
(b) Construye el resultado de codificar la cadena de caracteres “RETA” utilizando el código
representado por el árbol de codificación anterior.
(c) Descifra 1.2.1.1.2.1.2.1.2.1.1 usando el código que estamos utilizando en estos ejemplos,
construyendo la cadena de caracteres correspondiente.
(d) Desarrolla un módulo que implemente la clase TArbCod que representa a los árboles de co-
dificación descritos en el ejercicio anterior, equipada con las siguientes operaciones
– Nuevo: → ArbCod
Genera un árbol de codificación vacío.
2
– Inserta: (ArbCod, Car, Sec[Nat]) – → ArbCod
Dado un árbol de codificación, un carácter y un código, representado como una secuen-
cia de [1,2], añade el carácter al árbol en el lugar indicado por la secuencia. La operación
no está definida si el carácter ya formaba parte del árbol.
– codifica: (ArbCod, Cadena) – → Sec[Nat]
Construye el código de una cadena. La operación no está definida si la cadena contiene
algún carácter que no se encuentra codificado en el árbol.
– decodifica: (ArbCod, Sec[Nat]) – → Cadena
Construye una cadena a partir de su código. La operación no está definida si no es posi-
ble decodificar toda la entrada.
3. Modifica las implementaciones desarrolladas en clase para los árboles de búsqueda, de manera
que las operaciones busca, inserta y borra sean iterativas en lugar de recursivas.
4. Añade las siguientes operaciones a la clase TArbus<TClave, TValor>, analizando su complejidad.
– consultaK: (Arbus[Clave,Valor], Nat) → Clave
Obtiene la k-ésima clave de un árbol de búsqueda, considerando que en un árbol con n
elementos k=0 corresponde a la menor clave y k=n–1 a la mayor.
– recorreRango: (Arbus[Clave,Valor], Clave, Clave) → Sec[Valor]
Dadas dos claves a y b devuelve una secuencia con los valores asociados a las claves que
están en el intervalo [a .. b ].
En los dos siguientes ejercicios debes suponer que la clase TArbus<TClave,TValor> está equipada con la
operación:
– recorreClaveValor: Arbus[Clave,Valor] → Sec[Pareja[Clave,Valor]]
Obtiene una secuencia, ordenada por clave, con todas las parejas de clave, valor almacenadas en
el árbol de búsqueda.
5. El problema de las concordancias consiste en lo siguiente: Dado un texto, se trata de contar el nú-
mero de veces que aparece en él cada palabra, y producir un listado ordenado alfabéticamente por
palabras, donde cada palabra aparece acompañada del número de veces que ha aparecido en el
texto. Suponemos que el texto a analizar viene dado como secuencia de tipo Sec[string], donde ca-
da elemento de la secuencia es una palabra. Se pide construir un algoritmo que resuelva el
problema con ayuda de un árbol de búsqueda de tipo Arbus[string, int], y analizar su complejidad.
El listado pedido se dará como secuencia de parejas, de tipo Sec[Pareja[string, int]].
6. Dado un texto organizado por líneas, el problema de las referencias cruzadas pide producir un lista-
do ordenado alfabéticamente por palabras, donde cada palabra del texto vaya acompañada de una
lista de referencias, que contendrá los números de todas las líneas del texto en las que aparece la pa-
labra en cuestión (con posibles repeticiones si la palabra aparece varias veces en una misma línea).
Suponiendo que el texto a analizar venga dado como secuencia de tipo Sec[Sec[string]] –secuencia
de líneas representadas como secuencias de palabras–, construye un algoritmo que resuelve el
problema con ayuda de un árbol de búsqueda de tipo Arbus[string, Sec[int]], y analiza su compleji-
dad. El listado pedido se dará como secuencia de parejas, de tipo Sec[Pareja[string, Sec[int]]].
7. Añade a la clase TArbinDinamico<TElem> una operación que determine si un árbol binario es un
montículo. Analiza su complejidad.
8. Añade a la clase TArbinDinamico<TElem> una operación maxNivel que obtenga el máximo número
de nodos de un nivel del árbol, esto es, el número de nodos del “nivel más ancho”. Analiza su
complejidad.
3
9. Se trata de modificar la implementación de la clase TArbus<TClave,TValor> para permitir que en
un árbol de búsqueda se puedan almacenar distintos valores con la misma clave, lo cual implica
cambios en el comportamiento de algunas operaciones de los árboles:
— Al insertar un par <clave, valor>, si la clave ya se encontrase en el árbol, en lugar de sustituir
el valor antiguo por el nuevo, se asociará el valor adicional con la clave.
— La operación de consulta, en lugar de devolver el valor asociado con una clave dada, devol-
verá una secuencia con los valores asociados con dicha clave. La secuencia estará ordenada
según el orden en el que se insertaron los valores en el árbol.
— La operación de borrado deberá eliminar todos los valores asociados con la clave dada.
Implementa en C++:
— Los cambios necesarios en la estructura de datos para permitir la implementación eficiente
de las operaciones de este nuevo TAD. En la estructura de datos sólo puedes utilizar tipos
predefinidos de C++; está prohibido el uso de otros TADs.
— Las operaciones de inserción y consulta, indicando razonadamente la complejidad temporal
de las implementaciones obtenidas.
10. En la clase TArbinDinamico<TElem> añade una constructora con el siguiente perfil
template <class TElem>
TArbinDinamico::TArbinDinamico (TElem v[], int num );
donde num es el número de elementos del array v. La constructora debe generar un árbol semi-
completo con los elementos del array. Indica razonadamente la complejidad temporal de la
implementación obtenida.
EDI todo/ejercs T-6.pdf
1
Estructuras de Datos y de la Información
Ingeniería Técnica en Informática de Gestión. Curso 2007/2008
Hoja de ejercicios número 6
Tablas
1. Se trata de enriquecer la clase TTablaAbierta<TClave,TValor> añadiéndole operaciones de recorri-
do que permitan visitar todos los nodos de la tabla sin importar el orden:
— reinicia, sitúa el punto de interés al “principio” de la tabla. La especificación no fija cuál ha
de ser el principio de una tabla.
— esFin, consulta si el punto de interés está al final de la tabla. Si la tabla está vacía esFin ha de
ser cierto.
— actual, devuelve una pareja TPareja<TClave,TValor> con el contenido del nodo situado a
continuación del punto de interés. Es un error consultar por actual cuando esFin es cierto.
— avanza, mueve una posición hacia delante el punto de interés. Es un error ejecutar avanza
cuando esFin es cierto.
Estas operaciones se deben implementar de forma que un bucle como este
tabla.reinicia();
while ( ! tabla.esFin() ) {
cout << tabla.actual();
tabla.avanza();
}
recorra todos los elementos almacenados en la tabla.
Indica qué cambios sería necesario
realizar en la estructura de datos de la clase TTablaAbier-
ta<TClave,TValor> para poder implementar estas operaciones de manera eficiente, sin que por
ello se perjudique la complejidad de las otras operaciones de las tablas. Describe cómo implemen-
tarías las nuevas operaciones, qué cambios sería necesario realizar en las otras operaciones de las
tablas y razona la complejidad temporal que obtendrías.
2. Se trata de desarrollar un TAD TABLA-ORD[C :: ORD, V :: ANY] que represente a las tablas
ordenadas. Este TAD ofrecerá las siguientes operaciones:
— Nuevo: crea una tabla vacía.
— Inserta: añade una clave y un valor a una tabla. Si en la tabla ya se encontrase la clave insertada,
se sustituirá el valor antiguo por el nuevo.
— borra: dada una clave y una tabla, elimina dicha clave, y su valor asociado, de la tabla. Si la clave
no se encuentra en la tabla, se devolverá la tabla sin modificar.
— está: determina si una clave se encuentra en una tabla dada.
— consulta: dada una tabla y una clave, obtiene el valor asociado a dicha clave. Es un error consul-
tar por el valor de una clave que no haya sido insertada previamente.
— minClave: obtiene la menor clave almacena en la tabla. Es un error consultar por la mínima cla-
ve de una tabla vacía.
— esVacío: determina si una tabla está vacía.
— enumera: devuelve una secuencia de pares (clave, valor) con el contenido de la tabla ordenado
por claves.
Desarrolla en C++ una clase TTablaOrd<TClave,TValor> que implemente este TAD de forma
que la complejidad de enumera sea O(n), siendo n el número de datos almacenados en la tabla, y se
perjudique lo menos posible a la complejidad de las otras operaciones. Analiza la complejidad
temporal de las operaciones.
Idea: cada nodo de una lista de colisiones formará parte de dos listas, la propia lista de colisiones
y una lista ordenada doblemente enlazada que contenga todos los nodos de la tabla. De esta for-
ma, cada nodo contendrá tres punteros: el siguiente en la lista de colisiones, además de el
siguiente y el anterior en la lista ordenada.
2
3. Se trata de desarrollar un TAD MCJTO[A :: ORD] que represente a los multiconjuntos. Un mul-
ticonjunto es un conjunto donde puede haber elementos repetidos. Este TAD ofrecerá las
siguientes operaciones:
— Nuevo: crea un multiconjunto vacío.
— Inserta: añade un elemento al multiconjunto.
— borra: elimina un elemento del multiconjunto.
— está: determina si un elemento pertenece al multiconjunto.
— min: devuelve el menor elemento de entre los que contiene el multiconjunto.
— borraMin: elimina una aparición del menor elemento del multiconjunto.
— esVacío: determina si un multiconjunto está vacío.
Desarrolla en C++ una clase TMultiCjto<TElem> que implemente este TAD intentando minimi-
zar la complejidad temporal de las operaciones.
Idea: representa los multiconjuntos como tablas ordenadas utilizando los elementos como claves
y el número de apariciones como valor.
4. Resuelve de nuevo el problema de las concordancias (cfr. ejercicio 5 de la hoja 5), utilizando en lugar
de un árbol de búsqueda una tabla ordenada del tipo que hemos considerado en el ejercicio 2.
Analiza el tiempo de ejecución del algoritmo que obtengas.
5. Diseña un procedimiento que “limpie” una tabla cerrada, de tal manera que las posiciones borra-
das se eliminen y las restantes informaciones se reubiquen en la tabla. Todas las informaciones
correspondientes a claves sinónimas deberán quedar situadas en posiciones consecutivas de la su-
cesión de pruebas, a partir de la posición primaria que corresponda.
6. Modifica la implementación de la operación de inserción en las tablas cerradas vista en clase para
que cuando la tasa de ocupación supere un cierto valor fijado de antemano, se aumente la capaci-
dad del array, se reubiquen los datos adecuadamente y se “limpie” la tabla.
Aplicaciones
Para los siguientes ejercicios has de suponer que todos los TADs vistos en clase están equipados con
la operación numElem que devuelve el número de elementos de la estructura en cuestión.
Los árboles de búsqueda, además de la operación recorre que obtiene una secuencia con los valores
del árbol, estarán equipados también con estas dos operaciones de recorrido:
TSecuenciaDinamica<TClave> recorreClave( ) const;
// Pre : true
// Post : devuelve las claves del árbol ordenadas
TSecuenciaDinamica< TPareja<TClave,TValor> > recorreClaveValor( ) const;
// Pre : true
// Post : devuelve parejas con las claves y los valores del árbol, ordenadas por clave
Debes considerar así mismo que las tablas (abiertas y cerradas) están equipadas con las siguientes
operaciones:
TSecuenciaDinamica< TPareja<TClave, TValor> > enumera( ) const;
// Pre: true
// Post: Devuelve una secuencia de parejas con los elementos de la tabla
TSecuenciaDinamica<TClave> enumeraClave( ) const;
// Pre: true
// Post: Devuelve una secuencia con las claves de la tabla
TSecuenciaDinamica<TValor> enumeraValor( ) const;
// Pre: true
// Post: Devuelve una secuencia con los valores de la tabla
3
7. En este ejercicio se trata de desarrollar un sistema informático que modele el comportamiento de
un consultorio médico. Para ello suponemos disponibles los módulos que implementan a las siguien-
tes clases, todas ellas equipadas con operaciones de igualdad y orden:
— TMedico que sirve para almacenar y gestionar la información sobre un médico del consultorio.
— TPaciente que sirve para almacenar y gestionar la información sobre un paciente.
Nosotros nos encargaremos de la implementación de la clase TConsultorio, cuya misión es gestio-
nar la información sobre los médicos y las citas de los pacientes. Esta clase ofrece las siguientes
operaciones públicas:
— Nuevo: Genera un consultorio vacío sin ninguna información.
— NuevoMédico: Altera un consultorio, dando de alta a un nuevo médico que antes no figuraba en
el consultorio.
— PideConsulta: Altera un consultorio, haciendo que un paciente se ponga a la espera para ser
atendido por un médico, el cual debe estar dado de alta en el consultorio.
— siguientePaciente: Consulta el paciente a quien le toca el turno para ser atendido por un médico;
éste debe estar dado de alta, y debe tener algún paciente que le haya pedido consulta.
— atiendeConsulta: Modifica un consultorio, eliminando el paciente al que le toque el turno para
ser atendido por un médico; éste debe estar dado de alta, y debe tener algún paciente que le
haya pedido consulta.
— tienePacientes: Reconoce si hay o no pacientes a la espera de ser atendidos por un médico, el cual
debe estar dado de alta.
Desarrolla en C++ una implementación de la clase TConsultorio basada en otros TADs conocidos,
optimizando la complejidad temporal de las operaciones.
8. En este ejercicio se trata de desarrollar un sistema informático que modele el comportamiento de
un mercado de trabajo simplificado, donde las personas pueden ser contratadas y despedidas por
empresas. Para ello suponemos disponibles los módulos que implementan a las siguientes clases,
todas ellas equipadas con operaciones de igualdad y orden:
— TPersona que sirve para almacenar y gestionar la información sobre una persona.
— TEmpresa que sirve para almacenar y gestionar la información sobre una empresa.
Nosotros nos encargaremos de la implementación de la clase TMercado, cuya misión es gestionar
la información sobre el mercado de trabajo. Esta clase ofrece las siguientes operaciones públicas:
— Nuevo: Genera un mercado vacío, sin ninguna información.
— Contrata: Altera un mercado, efectuando la contratación de cierta persona como empleado de
cierta empresa.
— despide: Altera un mercado, efectuando el despido de cierta persona que era antes empleado de
cierta empresa.
— empleados: Consulta los empleados de una empresa, devolviendo el resultado como secuencia
ordenada de personas.
— esEmpleado: Averigua si es cierto o no que una persona dada es empleado
de una empresa dada.
— esPluriempleado: Averigua si es cierto o no que una persona es empleado de más de una empre-
sa.
Desarrolla en C++ una implementación de la clase TMercado basada en otros TADs conocidos,
optimizando la complejidad temporal de las operaciones.
4
9. Nos han encargado desarrollar un sistema informático que se ocupe del almacenamiento y la ges-
tión de citas literarias. La clase TCultura será la encargada de gestionar la información de una
colección de citas, ofreciendo a sus clientes las siguientes operaciones públicas:
— Nuevo: inicializa una colección de citas vacía.
— Inserta: añade una cita a una colección de citas. Una cita viene dada como una cadena (string)
y se puede suponer que no se insertarán citas repetidas.
— elimina: dada una secuencia de palabras, que se pueden suponer no repetidas, elimina las ci-
tas que contengan todas esas palabras.
— consulta: dada una secuencia de palabras, que se pueden suponer no repetidas, devuelve una
secuencia sin repetición con las citas que contienen dichas palabras.
— consultaAprox: dada una secuencia de palabras no repetidas y un número n menor o igual
que la longitud de la secuencia, devuelve una secuencia sin repetición con las citas que con-
tienen al menos n palabras de la consulta.
Desarrolla en C++ una implementación de la clase TCultura basada en otros TADs conocidos,
optimizando la complejidad temporal de las operaciones.
Idea: se puede utilizar una tabla donde cada palabra (clave) lleva asociada la lista de citas donde
esa palabra aparece (valor). Para evitar repetir las citas se pueden utilizar punteros.
10. Nos han encargado desarrollar un sistema informático que se ocupe de la gestión de las notas de
los alumnos de la Escuela de Informática de San Petersburgo. Para ello suponemos disponibles
los módulos que implementan a las siguientes clases:
— TAsignatura, que sirve para almacenar y gestionar la información sobre una asignatura: el
nombre de la asignatura, el profesor, el curso en el cual se imparte, …. Suponemos que está
equipado con operaciones de igualdad y orden.
— TAlumno, que sirve para almacenar y gestionar la información sobre un alumno: su nombre,
DNI, domicilio, …. Suponemos también que está equipado con operaciones de igualdad y
orden.
— TNota, que sirve para representar las calificaciones obtenidas por los alumnos en las asigna-
turas: sin calificar, no presentado, suspenso, aprobado, notable y sobresaliente.
Nosotros nos encargaremos de implementar la clase TTablon que ofrece las siguientes operaciones
públicas:
— Nuevo: inicializa un Tablon vacío.
— InsertaAsignatura: añade a un Tablon una asignatura, junto con la lista –o secuencia– de los
alumnos matriculados en ella.
— Califica: añade a un Tablón la información sobre la nota de un alumno en una asignatura de-
terminada.
— listaNotas: devuelve una secuencia ordenada con los alumnos que han aprobado una asigna-
tura, junto con sus notas correspondientes.
— pendientes: devuelve una secuencia con las asignaturas que un determinado alumno no ha
aprobado todavía.
— junio: modifica un Tablon eliminando de él la información relativa a las asignaturas aproba-
das por los alumnos. De esta forma, en el Tablon sólo quedará información sobre las
asignaturas pendientes de los alumnos.
Desarrolla en C++ una implementación de la clase TTablon basada en otros TADs conocidos,
optimizando la complejidad temporal de las operaciones.
5
11. Nos han encargado desarrollar un sistema informático que se ocupe de la gestión de una tienda
que vende libros por Internet. Para ello suponemos disponibles los módulos que implementan a
las siguientes clases, todas ellas equipadas con operaciones de igualdad y orden:
— TCliente, que sirve para almacenar y gestionar la información sobre un cliente: su nombre,
dirección, ….
— TLibro, que sirve para almacenar y gestionar la información sobre un libro: su título, autor,
tema, ISBN, ….
— TPais, que sirve para representar los países a los que pertenecen los clientes. Suponemos
que el TCliente está equipada con la observadora país que devuelve el país donde reside el
cliente.
— TTema, que sirve para representar los temas de los libros. Suponemos que la clase TLibro
está equipada con la observadora tema que devuelve el tema al que pertenece el libro.
Nosotros nos encargaremos de la implementación de la clase TTienda, cuya misión es gestionar la
información sobre los libros disponibles y sobre los pedidos de los clientes. Esta clase ofrece las
siguientes operaciones públicas:
— Nuevo: inicializa una Tienda vacía.
— InsertaLibro: añade a una Tienda un número determinado de ejemplares de un cierto libro. El li-
bro podía estar ya disponible, con lo que esta operación sólo modificará el número de
ejemplares, o puede que se trate de un libro nuevo.
— Pedido: esta operación añade a una Tienda la información de un pedido que ha realizado un
cliente determinado. La información sobre el pedido está dada como una secuencia de libros.
Aunque el envío de los libros no se realiza automáticamente al recibirse el pedido, los libros
solicitados se consideran reservados, por lo que esta operación se deberá encargar de actualizar
adecuadamente el número de ejemplares disponibles. También puede ocurrir que no haya exis-
tencias de alguno de los libros solicitados, en cuyo caso se retendrá la información sobre el
pedido del libro o libros en cuestión, para así poder atenderlo en cuanto lleguen más ejempla-
res. Al insertarse nuevos ejemplares de un libro agotado para el que existen pedidos
pendientes, dichos ejemplares se asignarán respetando el orden en el que se realizaron los pe-
didos.
— envíoLibros: esta operación consulta y modifica una Tienda para obtener la información sobre
los pedidos pendientes de envío que tienen como destino a un país determinado, y darlos por
realizados. Esta operación devuelve una secuencia donde cada elemento contiene los datos de
un cliente y la secuencia de libros que ese cliente ha pedido (y tiene reservados). Nótese que
entre los libros a enviar no se pueden incluir aquellos pedidos que están pendientes debido a la
falta de ejemplares. Nótese asimismo que entre dos envíos sucesivos al mismo país, cada clien-
te puede haber realizado más de un pedido.
— envíoCatálogo: periódicamente, la librería edita catálogos con las novedades editoriales de un
cierto tema. Esta operación sirve para consultar una Tienda y obtener la lista de clientes intere-
sados en el tema en cuestión. Se considera que un cliente está interesado en un cierto tema si
ha comprado más de minLibros libros de dicho tema.
Desarrolla en C++ una implementación de la clase TTienda basada en otros TADs conocidos, op-
timizando la complejidad temporal de las operaciones.
6
12. Nos han encargado desarrollar un sistema informático que se ocupe de la gestión de los pedidos
en la pizzería la Pizza Veloz. Para ello suponemos disponibles los módulos que implementan a las
siguientes clases:
— TZona, que sirve para representar una zona de la ciudad, y que se utiliza para organizar los en-
víos por zonas.
— TDireccion, que sirve para representar una dirección concreta. Suponemos que TDireccion ofrece
una operación zona que devuelve un objeto de tipo TZona con la zona a la que pertenece dicha
dirección.
— TPizza, que sirve para representar un tipo de pizza de entre las que se preparan en la Pizza Ve-
loz.
— THora, que sirve para representar una hora del día.
— TPedido, que sirve para representar la información sobre un pedido y que está equipado con las
operaciones:
— direccion, que devuelve un objeto TDireccion con el destino del envío.
— cargamento, que devuelve una secuencia de objetos TPizza con las pizzas a enviar.
— hora, que devuelve la hora en la que se realizó el pedido.
Nosotros nos encargaremos de la implementación de la clase TPizzeria, cuya misión es
gestionar
la información sobre los pedidos pendientes. En concreto, esta clase estará equipada con las si-
guientes operaciones públicas:
— Nuevo: inicializa una TPizzeria vacía.
— Inserta: añade a una TPizzeria un nuevo pedido (TPedido).
— comanda: esta operación proporciona la información necesaria para que un motorista cargue su
moto y atienda a un cierto número de pedidos. El resultado de esta operación será una se-
cuencia de pares <dirección, secuencia de pizzas> que se obtendrá de la siguiente forma:
— el pedido pendiente más antiguo pasa directamente a formar parte del resultado,
— la comanda se completa con otros pedidos pendientes de la misma zona que el primero, te-
niendo en cuenta que: (1) se han de atender antes a los pedidos más antiguos, (2) no se
debe superar el número de maxPizzas que caben en una moto, y (3) no se pueden fraccionar
pedidos. De esta forma, se van considerando sucesivamente, por orden cronológico, los
pedidos pendientes a la zona en cuestión e insertándolos en el resultado siempre que no se
supere el número de maxPizzas. Este proceso se detiene cuando se ha conseguido exacta-
mente una comanda con maxPizzas o cuando se han considerado todos los pedidos
pendientes de envío a dicha zona. Se puede suponer, por último, que ningún pedido con-
tiene más de maxPizzas.
Desarrolla en C++ una implementación de la clase TPizzeria basada en otros TADs conocidos,
optimizando la complejidad temporal de las operaciones.
13. Nos han encargado desarrollar un sistema informático que se ocupe de la gestión de la reserva de
películas en un pequeño video club. Para ello suponemos disponibles los módulos que implemen-
tan a las siguientes clases, todas ellas equipadas con operaciones de igualdad y orden:
— TPelícula, que sirve para representar una de las películas del video club.
— TCliente, que sirve para representar un socio del video club.
Nosotros nos encargaremos de la clase TReservas, cuya misión es gestionar la información sobre
las películas reservadas. Esta clase ofrecerá las siguientes operaciones públicas:
— nuevo: inicializa un TReservas vacío.
— reserva: establece que un cliente ha reservado una cierta película.
— reservasPendientes: consulta cuántas reservas pendientes hay para una cierta película.
— películasReservadas: consulta qué películas tiene reservadas un cierto cliente.
— primero: consulta quién es el primer cliente que tiene reservada una cierta película.
— alquila: elimina la reserva más antigua de una cierta película.
Desarrolla en C++ una implementación de la clase TReservas basada en otros TADs conocidos,
optimizando la complejidad temporal de las operaciones.
7
14. Nos han encargado desarrollar un sistema informático que se ocupe de las estadísticas sobre las
medallas obtenidas en las Olimpiadas. Para ello suponemos disponibles los módulos que imple-
mentan a las siguientes clases:
— TPais, que sirve para representar un país.
— TDeporte, que sirve para representar un deporte olímpico.
— TPrueba, que sirve para representar una prueba concreta de un cierto deporte y que está equi-
pada con la operación deporte que devuelve un objeto TDeporte con el deporte al que pertenece
dicha prueba.
— TAtleta, que sirve para representar a un atleta de los que participan en las Olimpiadas y que es-
tá equipada con la operación pais que devuelve un objeto TPais con el país al que pertenece el
atleta.
Nosotros nos encargaremos de la clase TMedallero, cuya misión es gestionar la información sobre
el número de medallas obtenido por los países participantes en las Olimpiadas, y de la clase TMe-
dallas que representa el número de medallas obtenido por un país concreto (cuántas de oro,
cuántas de plata y cuántas de bronce). La clase TMedallero estará equipada con las siguientes ope-
raciones públicas:
— Nuevo: inicializa un TMedallero vacío.
— clasificacion: añade a un TMedallero la información sobre la clasificación de una prueba, dada
como un objeto TPrueba y una secuencia de objetos TAtleta ordenada por el puesto obtenido
en dicha prueba.
— medalleroDeporte: para un deporte dado devuelve una secuencia de pares <TPais, TMedallas> con
los países que han obtenido alguna medalla en dicho deporte, ordenada por el número de me-
dallas.
— medallero: devuelve una secuencia de pares <TPais, TMedallas> con los países que han obtenido
alguna medalla, ordenada por el número de medallas.
Para obtener el orden en el medallero, se consideran primero el número de medallas de oro, si
éstas coinciden, se comparan entonces las de plata, y si también coinciden éstas, las de bronce.
Si coinciden el número de medallas de oro, plata y bronce, entonces no importa el orden.
Desarrolla en C++ una implementación de las clases TMedallas y TMedallero basada en otros
TADs conocidos, optimizando la complejidad temporal de las operaciones.
15. Nos han encargado desarrollar un revisor de textos. Nuestro sistema gestionará una colección
con palabras del castellano y posibles formas de escribirlas mal, suponiendo que una palabra mal
escrita se corresponde con una única palabra correcta. El proceso de corrección consistirá en, da-
do un texto, revisarlo palabra por palabra, de forma que si la palabra es correcta entonces se deja
como está, si no es correcta pero sabemos a qué palabra correcta se refiere la sustituimos, y si el
sistema no la conoce se deja tal cual.
La clase TCorrector que implementa el sistema ofrecerá las siguientes operaciones públicas:
— nuevo: inicializa un TCorrector vacío.
— insertaPalabra: añade una nueva palabra correcta.
— insertaError: añade una nueva forma de escribir mal una cierta palabra, es decir, asocia una
nueva palabra incorrecta con una correcta.
— revisa: dado un texto representado por una secuencia de palabras, le aplica el proceso de co-
rrección antes descrito, devolviendo el texto corregido junto con una secuencia que
contenga las palabras que el sistema desconoce –no sabe si son correctas o incorrectas–.
— diccionario: devuelve una secuencia ordenada alfabéticamente que contenga cada palabra co-
rrecta y las formas posibles de escribirla mal.
Desarrolla en C++ una implementación de la clase TCorrector basada en otros TADs conocidos,
optimizando la complejidad temporal de las operaciones. En la implementación está prohibido el
acceso a los tipos representantes de los TADs que se usen.
Para cada operación, indica la complejidad temporal que has obtenido.
8
16. Nos han encargado desarrollar un sistema informático que gestione un foro de mensajes. En el
foro hay dos tipos de mensajes: los que inician una “línea de discusión”, es decir, aquellos mensa-
jes nuevos que no responden a un mensaje anterior; y los que responden a un mensaje previo (ya
sea una respuesta a otra respuesta o una respuesta a un mensaje inicial).
La clase TForo que implementa el sistema ofrecerá las siguientes operaciones públicas:
— una constructora sin parámetros que inicialice un TForo vacío.
— insertaMensaje: añade un mensaje que inicia una línea de discusión.
— insertaRespuesta: inserta un mensaje a como respuesta directa a un mensaje previo b.
— iniciales: obtiene los mensajes almacenados en el foro que han iniciado una línea de discu-
sión.
— respuestas: obtiene las respuestas directas a un mensaje dado.
— mensajes: obtiene todos los mensajes del foro.
Escribe la definición de la clase TMensaje (sólo la interfaz) y desarrolla en C++ una implementa-
ción de la clase TForo basada en otros TADs conocidos, optimizando la complejidad temporal de
las operaciones. Si en la clase TMensaje decides incluir alguna operación no trivial, entonces has de
implementar también dicha operación.
Para cada operación, indica la complejidad temporal que has obtenido.
17. Nos han encargado desarrollar un sistema informático que gestione un sistema de indexación de
documentos mediante palabras clave relacionadas. Cuando se inserta un documento, se le asocia
una palabra clave que luego permitirá recuperarlo (decimos entonces que el documento está in-
dexado por esa palabra clave). La misma palabra clave puede tener varios documentos asociados.
Por otra parte, las palabras clave están relacionadas entre sí por relaciones de dependencia, de
forma que si la palabra clave c1 depende de la palabra clave c2, entonces cada vez que se consulte
por c1 se deberán recuperar también los documentos asociados con c2. La relación de dependen-
cia es transitiva (si c1 depende de c2 y c2 depende de c3 entonces c1 depende de c3 ) y antisimétrica
(si c1 depende de c2 entonces c2 no puede depender de c1).
La clase TGestor que implementa el sistema ofrecerá las siguientes operaciones públicas:
— una constructora sin parámetros que inicialice un TGestor vacío.
— insertaClaves: añade una relación de dependencia entre dos claves dadas. No es necesario que
las claves hayan sido insertadas previamente en el sistema. Se valorará que esta operación
compruebe que no se producen ciclos en la relación de dependencia entre claves.
— insertaDocumento: añade un documento con una palabra clave asociada. No es necesario que
la clave haya sido insertada previamente.
— consulta: dada una cierta palabra clave, recupera sus documentos asociados junto con los do-
cumentos asociados con las claves de las que depende directa o indirectamente, si es que
existen.
Escribe la definición de la clase TDocumento (sólo la interfaz) y, suponiendo que las palabras clave
se representan como datos de tipo string, desarrolla en C++ una implementación de la clase TGes-
tor basada en otros TADs conocidos, optimizando la complejidad temporal de las operaciones. Si
en la clase TDocumento decides incluir alguna operación no trivial, entonces has de implementar
también dicha operación.
Para cada operación, indica la complejidad temporal que has obtenido.
EDI todo/IntroduccionC++.pdf
TEMA 0
INTRODUCCIÓN AL LENGUAJE C++
1. El programa “Hola mundo”
2. Tipos simples
3. Declaración, inicialización y asignación de variables y constantes
4. Operadores
5. Tipos definidos por el programador
6. Estructuras de control
7. Procedimientos y funciones
8. Entrada y salida
Bibliografía: El lenguaje de programación C++. Tercera edición
Bjarne Stroustrup
Addison Wesley, 1998
Introducción al lenguaje C++ 1
0.1 Hola mundo
El programa “Hola mundo” en C++
#include <iostream>
using namespace std;
void main( )
{
cout << "Hola mundo mundial\n";
}
El programa principal es siempre una función de nombre main.
Las operaciones de entrada/salida se importan de módulos de la biblioteca
usando la directiva include. En el ejemplo se ha importado iostream.
— Los módulos de la biblioteca estándar definen sus identificadores en el espa-
cio de nombres std, por lo tanto, si no se quiere cualificar a los identificado-
res es necesario añadir la sentencia
using namespace std;
para así poder escribir cout en lugar de std::cout
Los delimitadores { } marcan, respectivamente, el principio y el final de una
función y sirven así mismo para delimitar bloques de código.
El tipo void representa la ausencia de valor.
En C++ un procedimiento es una función que devuelve un resultado de tipo
void.
Todas las sentencias terminan con el carácter ;
Las cadenas se escriben entre comillas dobles.
Para mostrar un mensaje por la salida estándar (la pantalla), se aplica el opera-
dor de inserción << teniendo como primer operando cout (importado de ios-
tream)y como segundo operando el dato que se pretende mostrar.
Introducción al lenguaje C++ 2
“Hola mundo” (en C++ Builder 5)
— File | New ...
— En el cuadro de diálogo New Items se selecciona Console Wizard
— En el diálogo Console Wizard se aceptan las opciones por defecto
Introducción al lenguaje C++ 3
— Y ya tenemos un programa ejecutable
//---------------------------------------------------------------------
#pragma hdrstop
//---------------------------------------------------------------------
#pragma argsused
int main(int argc, char* argv[])
{
return 0;
}
//---------------------------------------------------------------------
sin más que seleccionar Run | Run o pulsar F9.
— Si el programa no se ha compilado previamente, se compilará al seleccionar
la orden Run.
Para compilar se utiliza la orden Project | Compile unit (ALT+F9) para compi-
lar el archivo actual o Project | Make nombre_proyecto (CTRL+F9) para compilar
todos los archivos de un proyecto.
— Si añadimos a este esqueleto de programa las líneas de nuestro “Hola mun-
do”
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
cout << "Hola mundo\n";
return 0;
}
Si ejecutamos ahora este programa, veremos en Windows una consola de
MS-DOS que se abre y cierra rápidamente. Para que nos dé tiempo a ver el
mensaje, podemos añadir una operación de lectura
int main(int argc, char* argv[])
{
char c;
cout << "Hola mundo\n";
cin >> c;
return 0;
}
Introducción al lenguaje C++ 4
0.2 Tipos simples
Los tipos simples más utilizados
— char
caracteres, los literales se escriben entre comillas simples: ’a’
— int
números enteros en el intervalo −32768 .. 32767
— double
números reales en el intervalo 1.7e−308 .. 1.7e+308
— bool
valores lógicos true | false
— void
el tipo del resultado de las funciones que no devuelven resultado
(i.e., los procedimientos)
Introducción al lenguaje C++ 5
0.3 Declaración, inicialización y asignación de variables
y constantes
Sintaxis
tipo lista_de_variables;
donde lista_de_variables se compone de uno o más identificadores separados
por comas.
En los identificadores se distinguen mayúsculas de minúsculas.
Una declaración puede aparecer en cualquier lugar de un programa, su ámbito
será local si se declara dentro de una función y global si se declara al nivel más
externo.
En general siempre declararemos las variables locales al principio del cuerpo
de las funciones.
= es el operador de asignación
Las variables se pueden inicializar al ser declaradas
Las constantes se declaran como las variables pero precedidas de la palabra re-
servada const
Ejemplo
int global = 0; // variable global inicializada
void main( )
{
int local1, local2 = 2; // variables locales a la función main
const int uno = 1, dos = 2; // declaración de constantes
local1 = uno; // asignación
bool b; // evitaremos estas declaraciones
b = true;
}
Introducción al lenguaje C++ 6
0.4 Operadores
0.4.1 Operadores aritméticos y de manipulación de bits
Actúan sobre constantes y variables numéricas
— +, –, *, / : suma, resta, multiplicación y división
— % : módulo, que sólo está definido para los enteros (int o long)
— &, |, ^, <<, >> : operaciones bit a bit y-lógica, o-lógica, o-exclusiva, despla-
zamiento a la izquierda y desplazamiento a la derecha
Cada uno de estos operadores lleva asociado un operador de asignación de la for-
ma op= tal que
variable op= expresión
es equivalente a
variable = variable op expresión
Ejemplo
void main( )
{
const int tres = 3;
int n = 289898454 % tres;
double f = 1.34e-6, g = 6.7;
double h = f + g * f;
n += tres;
}
Introducción al lenguaje C++ 7
0.4.2 Operadores relacionales y lógicos
Operadores relacionales
— ==, != : igual, diferente
— >, >=, <, <= : mayor, mayor o igual, menor, menor o igual
Operadores lógicos
— && : conjunción
— || : disyunción
— ! : negación
Ejemplo
void main( )
{
double f = 1.34e-6, g = 1.35e-6;
char h, j;
bool b = ! (f == g) && (f*3.6 <= g);
}
Introducción
al lenguaje C++ 8
0.4.3 Operadores de incremento y decremento
Permiten incrementar y decrementar el valor de una variable
— ++ : incrementa en una unidad
— – – : decrementa en una unidad
Tienen dos formas de uso
— pre-incremento/pre-decremento.
La variable se incrementa/decrementa antes de evaluar la expresión
— post-incremento/post-decremento.
La variable se incrementa/decrementa después de evaluar la expresión
Ejemplo
void main( )
{
int x = 1, y, z;
++x; // pre-incremento
x++; // post-incremento
y = ++x;
z = y--;
}
¿Cuál es el valor de las variables después de la última asignación?
Introducción al lenguaje C++ 9
0.5 Tipos definidos por el programador
Para definir un tipo se utiliza la palabra reservada typedef delante
de la declaración de tipo y el nombre del tipo
typedef declaración_tipo nombre_tipo
No existe una palabra reservada para introducir la zona de definiciones de tipo
de un programa.
Tipos enumerados
Los tipos enumerados se declaran con la palabra reservada enum seguida de una
lista de etiquetas encerradas entre llaves { }
Las etiquetas de un tipo enumerado son en realidad constantes con valor ente-
ro, donde la primera etiqueta toma el valor 0, la segunda el 1, ...
Ejemplo
typedef int TDiaMes;
typedef enum {lun, mar, mie, jue, vie, sab, dom} TDiaSemana;
void main( )
{
TDiaMes diaMes = 1;
TDiaSemana diaSemana = lun;
diaMes += 2;
diaSemana += 2;
}
Introducción al lenguaje C++ 10
Registros
Los registros se declaran con la palabra reservada struct seguida de la lista de
declaración de los campos encerrada entre llaves { } y donde los campos se
separan por ;
struct {
nombre_tipo1 nombre_campo1;
...
nombre_tipoN nombre_campoN;
} nombre_tipo
Ejemplo
typedef int TDiaMes;
typedef enum {lun, mar, mie, jue, vie, sap, dom} TDiaSemana;
typedef struct {
TDiaMes diaMes;
TDiaSemana diaSemana;
} TDia;
void main( )
{
TDia dia;
dia.diaMes = 1;
dia.diaSemana = lun;
}
Introducción al lenguaje C++ 11
Arrays
Para cualquier tipo T se puede declarar el tipo T[num] que representa a los vec-
tores de num elementos de tipo T, con índices en el intervalo 0 .. num –1
— num ha de ser una expresión constante
También es posible declarar una variable de tipo array sin necesidad de definir
un nuevo tipo, con la siguiente sintaxis
nombre_tipo identificador[num];
Los arrays se pueden inicializar en la declaración proporcionando una lista de
valores, separados por comas y encerrados entre llaves
— Si la lista de inicialización contiene menos elementos que la dimensión del
array el resto de posiciones se inicializan a 0
Los vectores multidimensionales se declaran como arrays de arrays
Ejemplo
typedef int TMatriz[2][2];
void main( )
{
int lista[5] = {0, 1, 2, 3, 4};
TMatriz matriz = { {1,1}, {2,2} };
matriz[0][0] = lista[0];
cout << matriz[0][0] << matriz[0][1] << matriz[1][0] \
<< matriz[1][1] << "\n";
}
¿qué se mostraría por pantalla?
Introducción al lenguaje C++ 12
0.6 Estructuras de control
Selección condicional
Sintaxis
if ( condición ) sentencia
if ( condición ) sentencia else sentencia
Ejemplos
int x, y;
if (x == y)
x = y++;
int x, y, z;
if (x == y)
{ x = y++;
z = ++x; }
else
z = x + y;
int x, y, z;
if (x == y)
z = 2;
else if (x > y)
{ z = 1;
x++; }
else
{ z = 0;
y++; }
Introducción al lenguaje C++ 13
Selección múltiple
Sintaxis
switch ( expresión )
case expresión-constante : sentencia
...
default : sentencia
— Se compara secuencialmente la expresión con las expresiones-constantes hasta en-
contrar una que coincida. A partir de ahí, se ejecutan todas las sentencias hasta
llegar al final o hasta encontrar una sentencia break
— Si ninguna expresión constante coincide con el valor de expresión, se ejecuta la
sentencia de la cláusula default, si es que la hay
Ejemplo
int x = 1, y;
switch (x)
{ case 1:
y++;
break;
case 2:
x++;
break;
default:
x++; y++;
break;
}
Introducción al lenguaje C++ 14
Composición iterativa
Sentencia while
while ( condición ) sentencia
— Ejemplo:
int x = 10, y = 1;
while (x > y)
{ x--;
y++; }
Sentencia do .. while
do sentencia while ( condición );
— Ejemplo:
int x = 10, y = 1;
do
{ x--;
y++; }
while (x > y);
Introducción al lenguaje C++ 15
Sentencia for
for ( inicializaciónopcional; condiciónopcional; expresiónopcional )
sentencia
— Se ejecuta la inicialización y mientras la condición sea cierta, se ejecuta la sentencia
y a continuación la expresión
— Es posible incluir varias inicializaciones, condiciones y/o expresiones separándolas
por comas
Ejemplos
— Este fragmento de código
int a[10], indice;
for (indice = 0; indice < 10; indice++)
a[indice] = 2*indice;
es equivalente a este otro
int a[10], indice;
indice = 0;
while ( indice < 10 )
{ a[indice] = 2*indice;
indice++; }
— Ejemplo de expresiones compuestas
int a[10], indice, valor;
for (indice = 0, valor = 9; indice < 10; indice++, valor--)
a[indice] = valor;
Introducción al lenguaje C++ 16
0.7 Procedimientos y funciones
Sintaxis
tipo-resultado nombre ( lista-parámetros )
{
lista-de-sentencias
}
El resultado de una función se devuelve con la sentencia
return expresión;
que además termina la ejecución de la función
Un procedimiento es una función cuyo tipo de resultado es void
Ejemplo
int suma ( int x, int y )
{
return x + y;
}
void main( )
{
int x = suma(2, 3);
}
Introducción al lenguaje C++ 17
Paso de parámetros
Por defecto los parámetros se pasan por valor.
Para indicar que un parámetro formal es por referencia, se escribe el carácter
& detrás del nombre del tipo
Los arrays, por razones de eficiencia, se pasan siempre por referencia
Es posible utilizar como parámetro arrays abiertos con la sintaxis
nombre-tipo identificador [ ]
Así se pueden escribir funciones que pueden recibir un array de cualquier lon-
gitud. Para que la función conozca la longitud del array que se pasa como pa-
rámetro real es habitual pasar un segundo argumento con la longitud.
También es posible definir valores por defecto para los argumentos
Los argumentos con valor por defecto deben aparecer siempre al final de la lis-
ta de argumentos
Ejemplo
void acumula ( int vector[], int longitud, int& suma )
{
int indice;
for( indice = 0; indice < longitud; indice++ )
suma += vector[indice];
}
int suma ( int x, int y = 1 )
{
return x + y;
}
void main( )
{
int v[5] = {0, 1, 2, 3, 4};
int s = 0;
acumula( v, suma(4), s);
}
Introducción al lenguaje C++ 18
0.8 Entrada y salida
Una de las posibles formas de realizar entrada/salida en C++ es por medio de
los flujos o canales –streams–
— En el módulo iostream se incluyen las funciones e identificadores estándar pa-
ra el manejo de canales
En iostream se definen tres canales predefinidos
— cin, para entrada de datos
— cout, para salida de datos
— cerror, para salida de errores
Los canales se manejan con los operadores de inserción y extracción
— <<, para enviar datos a un canal
— >>, para obtener datos de un canal
Los operadores importados de iostream saben cómo manejar datos de los tipos
predefinidos
Ejemplo
void pesado ( )
{
const int magico = 123;
int intento;
char c;
cout << “Adivina el número mágico: “;
cin >>Compartir
Materiales relacionados
5 pag.
6 pag.
5 pag.
Preguntas relacionadas
Compartir