PDF de programación - Estructuras de Datos y Algoritmos

Estructuras de Datos y Algoritmos

Facultad de Informática

Universidad Politécnica de Valencia

Curso 2004/2005

Tema 1:

Introducción a la programación con C++

FI– UPV: Curso 2004/2005

EDA-Tema1

TEMA 1. Introducción a la programación con C++

Objetivos

Aprender algunos conceptos del lenguaje C++ con el fin de poder utilizarlo a lo largo
de la asignatura. Es decir, no necesitamos saber todos los detalles y conceptos de este
lenguaje.

Conocimientos previos
Se asume que ya se sabe programar en lenguaje C.

Contenidos
1 Conceptos básicos de C++.
2 Clases en C++.
3 Algunas librerías estándar.

Bibliografía
• C++ estándar , de Enrique Hernández Orallo et al.

FI– UPV: Curso 2004/2005

Página 1.1

EDA-Tema1

El movimiento se demuestra andando. . .

Problema: Calcular la moda de una colección de valores enteros; es decir, su valor más
frecuente. Los valores enteros pertenecerán al intervalo [0, 29 999].

1 #include <iostream>
2 using namespace std;
3 #define tam 30000
4 int main() {
5

int v[tam],i,num,max,imax;
for (i=0; i < tam; i++) v[i] = 0; // primero inicializar el vector
while (cin >> num) {

// leer los numeros por entrada estandar

6

7

8

9

10

11

12

13

14

15

16
17 }

cout << "Proceso " << num << endl;
v[num]++;

}
max = v[0]; imax = 0;
for (i=1; i < tam; i++)

if (v[i] > max) {

max = v[i]; imax = i;

}

cout << "La moda es " << imax << endl;

FI– UPV: Curso 2004/2005

Página 1.2

EDA-Tema1

El lenguaje C++

Diseñado por Bjarne Stroustrup en los Laboratorios AT&T a principios de los años 80. Es
una extensión de C (salvo detalles, C es un subconjunto de C++).

Objetivos del diseño de C++:
• Comprobación de tipos más fuerte que en C.
• Soporte para la programación modular: Espacios de nombres.
• Soporte para la programación orientada a objetos: Clases.
• Soporte para la programación genérica (plantillas). No todos los lenguajes orientados a

objetos la soportan (por ej. Java no dispone de plantillas).

Al igual que C, se trata de un lenguaje donde la eficiencia en tiempo de ejecución se
considera importante.

Por tanto, hay dos clases de extensiones respecto de C:
• Extensiones no orientadas a objetos: Espacios de nombre, sobrecarga de funciones y
de operadores, plantillas, nuevos tipos de datos, funciones inline, nuevos comentarios,
nuevas librerías, etc.

• Extensiones relacionadas con la programación orientada a objetos: Clases.

FI– UPV: Curso 2004/2005

Página 1.3

EDA-Tema1

C++ no tiene soporte (estándar) para:
• Concurrencia.
• Persistencia de datos.
• Recolección automática de memoria (como ocurre, por ejemplo, en Java).

C++ soporta programación orientada a objetos, pero no es imprescindible (se puede
utilizar C++ sin objetos).

Compatibilidad con librerias C y herramientas UNIX (make) para reutilización de código.

Se ha convertido en un estándar de programación: iso/iec 98-14882. Esto proporciona
estabilidad al
lenguaje. Este estándar incluye una biblioteca estándar muy amplia que
incluye, entre otras cosas, la Standard Template Library: STL consistente en contenedores
(vectores,
listas, diccionarios, etc.), algoritmos e iteradores genéricos que se pueden
instanciar a diversos tipos de datos.

FI– UPV: Curso 2004/2005

Página 1.4

EDA-Tema1

Comentarios.

/* ...
...
... */

Conceptos básicos de C++

comentario que pueden abarcar múltiples líneas

// ...

comentario hasta el final de la línea

Los comentarios no se pueden anidar.

FI– UPV: Curso 2004/2005

Página 1.5

EDA-Tema1

Conceptos básicos de C++

Tipos de datos

Tipos fundamentales

Vienen definidos por el propio lenguaje, en C++ se dividen en:

Integrales o discretos (integral types)
• Tipos máquina: bool, char, short, int, long.
• Tipos enumerados: enum.

Reales (coma flotante): float, double, long double.

void.
• se usa en funciones y punteros.
• no se pueden declarar variables de ese tipo.
• no consume memoria y no hay ningun operador aplicable a él (excepto sizeof)

FI– UPV: Curso 2004/2005

Página 1.6

EDA-Tema1

Tipo bool

Conceptos básicos de C++

Tipos de datos

Puede tener dos valores: true y false

El tamaño no está establecido en el estándar, suele ser un byte.

Los valores numéricos se convierten implícitamente a tipos booleanos.

Valores distintos de cero se convierten a true y el cero a false.

Los punteros también se convierten implícitamente.

Puntero a NULL o cero se convierte a false y el resto se considera true.

Literales: los valores true y false

FI– UPV: Curso 2004/2005

Página 1.7

EDA-Tema1

Tipos enteros

Conceptos básicos de C++

Tipos de datos

Podemos tener distintos tamaños mínimos: short, int, long.
• 2 ≤ sizeof(short)
• 4 ≤ sizeof(long)
• sizeof(short) ≤ sizeof(int) ≤ sizeof(long)

Literales: Podemos utilizar distintas bases numéricas:

Decimal: No empieza por 0 (el literal 0 da igual la base).
Octal: Empiezan por 0. Ejemplo: 010 es como poner 8
Hexadecimal: Empiezan por 0x o por 0X.
Para los valores de 10 a 15 se utilizan las letras ABCDEF o también abcdef.

El sufijo fuerza el tipo del literal:

u o U para que sea de tipo unsigned.
l o L para que sea de tipo long.

Ejemplo: 0xAAuL es un valor 10 × 16 + 10 = 170 unsigned long.

FI– UPV: Curso 2004/2005

Página 1.8

EDA-Tema1

Tipos reales

Conceptos básicos de C++

Tipos de datos

Diferentes representaciones: float, double, long double.

Tamaño dependiendo de la arquitectura, ejemplo:



float
double
long double

32 bits
64 bits
96 bits

Literales: Consiste en una parte entera, un punto decimal, una parte fraccionaria y, opcional-
mente, un carácter e o E, un exponente entero con signo opcional. Se puede añadir un sufijo
para indicar el tipo (sin sufijo se considera double, con f o con F se considera float y
con l o con L es long double). Ejemplos:

0,5
0.5F
float
0,25 double
0.25
-1.0e5L → −100 000

long double

→
→

FI– UPV: Curso 2004/2005

Página 1.9

EDA-Tema1

Conceptos básicos de C++

Tipos de datos

Caracteres

Tipo char, tamaño: 1 byte.

Las variables y literales de tipo char se pueden sumar, restar, etc. ya que son de tipo
aritmético.

Literales: Se delimita por dos apóstrofes ’’. El caracter de escape \ sirve para codificar
algunos caracteres como ’\n’, etc.

Cadenas: Secuencia (vector) de caracteres acabados en el caracter nulo ’\0’

Literales: Las cadenas se delimitan con comillas "", ejemplo: "Hola\nmundo\n"

FI– UPV: Curso 2004/2005

Página 1.10

EDA-Tema1

Tipos enumerados

Conceptos básicos de C++

Tipos de datos

Sirven para definir un tipo que sólo puede tomar valores dentro de un conjunto finito.

La sintaxis es:

enum nombre {Valor1, Valor2, Valor3, ...};

Ejemplos:

enum palo {Oros, Bastos, Espadas, Copas};
enum respuesta {SI, NO};

FI– UPV: Curso 2004/2005

Página 1.11

EDA-Tema1

Tipos derivados

Conceptos básicos de C++

Tipos de datos

Se obtienen de los tipos fundamentales usando los siguientes símbolos de declaración:

Punteros
Referencias

*
&
[] Vectores (arrays)
()

Funciones

FI– UPV: Curso 2004/2005

Página 1.12

EDA-Tema1

Conceptos básicos de C++

Tipos de datos

Punteros
Para un tipo dado T, el tipo puntero a ese tipo es T*. Ejemplos:

int *p; // puntero a entero
int* q,r; // q es puntero a entero pero r es de tipo int
char **c; // puntero a un puntero a caracter

El puntero NULL Se trata de un puntero 0. Cualquier indirección de este puntero se convierte
en un error de ejecución. El identificador NULL no es reservado y hay que incluirlo desde
alguna de estas cabeceras:

<cstddef> // definiciones estándar de C
<cstdlib> // librería estándar de C

Puesto que el 0 tiene conversión estándar a puntero, podemos usar simplemente el 0 en vez
de NULL.

FI– UPV: Curso 2004/2005

Página 1.13

EDA-Tema1

Conceptos básicos de C++

Tipos de datos

Vectores
Una variable indexable que contiene muchos objetos de um mismo tipo que se almacenan
consecutivamente en memoria. Para un vector de n elementos, los índices válidos son los
enteros del 0 al n-1.

Controlar el acceso dentro del vector es responsabilidad del programador.

Los vectores se pueden inicializar poniendo elementos entre llaves y separados por comas.
Ejemplo:

int m[2][3] = { {1,2,3}, {4,5,6} };
char cad1[5] = {’H’,’o’,’l’,’a’,’\0’}; // OJO, HAY QUE PONER ’\0’
char cad2[5]= "Hola"; // es equivalente a lo anterior
char cad2[]= "Hola"; // es equivalente a lo anterior

FI– UPV: Curso 2004/2005

Página 1.14

EDA-Tema1

Conceptos básicos de C++

Tipos de datos

Relación entre vectores y punteros

Cuando definimos un vector, por ejemplo:

int v[10];

se define a como un vector de 10 enteros y se reserva espacio necesario para esos diez
enteros.
El operador [] se convierte a operaciones sobre punteros, así es equivalente:

v[4];
*(v+4); // equivalente a lo anterior

// quinto elemento de v

En general a[b] es equivalente a *((a)+(b))
El tipo de v es int[]. Hay una conversión desde T[] a T*, por tanto si escribimos:

int v[10];
int *p = v;

resulta que p y v son punteros al mismo tipo, pero v es un puntero constante no ocupando
memoria.

FI– UPV: Curso 2004/2005

Página 1.15

EDA-Tema1

p = v; // es válido
v = p; // INVALIDO
p += 4; // válido
v++;

// INVALIDO

En el caso de vectores multidimensionales hay que saber cómo se organizan en memoria.
Ejemplo:

int m[2][10]; // 2 líneas de 10 enteros
cout << *(m+1*10+2); // m[1][2]

Para pedir memoria dinámica se utilizan los operadores new y delete que son más
potentes y cómodos que las funciones malloc() y free() de C. Ejemplo:

1 int main() {
2

int *a = new int; // poco habitual reservar un int
int j = 20;
int *v = new int[j]; // reservamos un vector de 20 enteros
// observa que el argumento j no es constante...
v[0] = 5;
delete a;
delete[] v; // OJO! Es un error frecuente poner delete v

3

4

5

6

7

8
9 }

FI– UPV: Curso 2004/2005

Página 1.16

EDA-Tema1

Conceptos básicos de C++

Tipos de datos

Referencias
Una referencia es como un nombre alternativo o alias. La notación T& significa referencia a
t