 2003 Prentice Hall, Inc. All rights reserved. 1 Capítulo 4 - Arrays Índice del Capítulo 4.1Introducción 4.2Arrays 4.3Declaración de Arrays 4.4Ejemplos.

Author: Iago Bejarano

0 downloads 0 Views

1  2003 Prentice Hall, Inc. All rights reserved. 1 Capítulo 4 - Arrays Índice del Capítulo 4.1Introducción 4.2Arrays 4.3Declaración de Arrays 4.4Ejemplos de uso de Arrays 4.5Paso de Arrays a Funciones 4.6Ordenación de Arrays 4.7Ejemplo: Cálculo de Media, Mediana y Moda usando Arrays 4.8Búsqueda en Arrays: Búsqueda Lineal y Búsqueda Binaria 4.9Arrays Multidimensionales

2  2003 Prentice Hall, Inc. All rights reserved. 2 4.1Introducción Arrays –Estructuras de datos consistente en elementos de datos relacionados del mismo tipo. –Entidad estática (mismo tamaño durante toda la ejecución del programa) Tipos –Basados en punteros (tipo C) –Arrays como objetos (C++)

3  2003 Prentice Hall, Inc. All rights reserved. 3 4.2Arrays Array –Grupo de localizaciones consecutivas de memoria –Mismo nombre y tipo ( int, char, etc.) Para hacer referencia a un elemento: –Especificamos nombre del array y número de posición (índice) –Formato: nombrearray[ número_posición ] –El primer elemento está en la posición 0 Array c de n elementos: c[ 0 ], c[ 1 ] … c[ n - 1 ] –Elemento n-ésimo en la posición n-1

5  2003 Prentice Hall, Inc. All rights reserved. 5 4.2Arrays c[6] -45 6 0 72 1543 -89 0 62 -3 1 6453 78 Nombre del array (Notad que todos los elementos de este array tienen el mismo nombre, c) c[0] c[1] c[2] c[3] c[11] c[10] c[9] c[8] c[7] c[5] c[4] Número de posición del elemento dentro de array c Imprimo la suma de los 3 primeros elementos del array: cout

6  2003 Prentice Hall, Inc. All rights reserved. 6 4.3Declaración de Arrays Cuando se declaran arrays, hay que especificar: –Nombre –Tipo del array Cualquier tipo de datos –Número de elementos –tipo nombreArray [ tamañoArray ]; int c[ 10 ]; // array de 10 enteros float d[ 3284 ]; // array de 3284 floats Declaración de varios arrays del mismo tipo: –Lista separada por comas, como las variables int b[ 100 ], x[ 27 ];

7  2003 Prentice Hall, Inc. All rights reserved. 7 4.4Ejemplos de Uso de Arrays Inicialización de arrays –Lazo for Dar un valor inicial a cada elemento dentro de un lazo –Lista de inicialización Se especifica cada valor al declarar el array int n[ 5 ] = { 1, 2, 3, 4, 5 }; Si no hay suficientes valores iniciales, los más a la derecha se fijan a 0 Si hay demasiados valores iniciales: error de sintaxis –Para fijar todos los elementos al mismo valor int n[ 5 ] = { 0 }; –Si se omite el tamaño del array, la lista de valores iniciales determina su tamaño int n[] = { 1, 2, 3, 4, 5 }; 5 valores iniciales, por tanto array de 5 elementos

8  2003 Prentice Hall, Inc. All rights reserved. Outline 8 1 // Fig. 4.3: fig04_03.cpp 2 // Declaración de array e Inicialización de elementos usando lazo for. 3 #include 4 5 using std::cout; 6 using std::endl; 7 8 #include 9 10 using std::setw; 11 12 int main() 13 { 14 int n[ 10 ]; // n es un array de 10 enteros 15 16 // inicializo los elementos del array n a 0 17 for ( int i = 0; i < 10; i++ ) 18 n[ i ] = 0; // fijo el elemento en la localización i a 0 19 20 cout

10  2003 Prentice Hall, Inc. All rights reserved. Outline 10 1 // Fig. 4.4: fig04_04.cpp 2 // Inicialización del array en la declaración mediante lista de valores iniciales. 3 #include 4 5 using std::cout; 6 using std::endl; 7 8 #include 9 10 using std::setw; 11 12 int main() 13 { 14 // uso lista de valores iniciales para inicializar array n 15 int n[ 10 ] = { 32, 27, 64, 18, 95, 14, 90, 70, 60, 37 }; 16 17 cout

12  2003 Prentice Hall, Inc. All rights reserved. 12 4.4Ejemplos de uso de Arrays Especificación del tamaño del array mediante una constante –Puede especificarse mediante una ¿variable constante? ( const ) const int size = 20; –Las constantes no pueden modificarse –Las constantes deben inicializarse al declararlas –También llamadas constantes con nombre o variables de sólo lectura

13  2003 Prentice Hall, Inc. All rights reserved. Outline 13 1 // Fig. 4.5: fig04_05.cpp 2 // Especificación tamaño array con constante. Inicialización con cálculos. 3 #include 4 5 using std::cout; 6 using std::endl; 7 8 #include 9 10 using std::setw; 11 12 int main() 13 { 14 // constante que especifica el tamaño del array 15 const int arraySize = 10; 16 17 int s[ arraySize ]; // el array s tiene 10 elementos 18 19 for ( int i = 0; i < arraySize; i++ ) // fijo los valores 20 s[ i ] = 2 + 2 * i; 21 22 cout

15  2003 Prentice Hall, Inc. All rights reserved. Outline 15 1 // Fig. 4.6: fig04_06.cpp 2 // Uso de una variable constante correctamente inicializada. 3 #include 4 5 using std::cout; 6 using std::endl; 7 8 int main() 9 { 10 const int x = 7; // variable constante inicializada 11 12 cout

16  2003 Prentice Hall, Inc. All rights reserved. Outline 16 1 // Fig. 4.7: fig04_07.cpp 2 // Un objeto constante debe inicializarse. 3 4 int main() 5 { 6 const int x; // Error: x debe inicializarse 7 8 x = 7; // Error: no se puede modificar una variable constante 9 10 return 0; 11 12 } d:\cpphtp4_examples\ch04\Fig04_07.cpp(6) : error C2734: 'x' : const object must be initialized if not extern d:\cpphtp4_examples\ch04\Fig04_07.cpp(8) : error C2166: l-value specifies const object const no inicializada causa un error de sintaxis. Intentar modificar la const es otro error.

17  2003 Prentice Hall, Inc. All rights reserved. Outline 17 1 // Fig. 4.8: fig04_08.cpp 2 // Cálculo de la suma de las componentes de un array. 3 #include 4 5 using std::cout; 6 using std::endl; 7 8 int main() 9 { 10 const int arraySize = 10; 11 12 int a[ arraySize ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 13 14 int total = 0; 15 16 // suma contenidos del array a 17 for ( int i = 0; i < arraySize; i++ ) 18 total += a[ i ]; 19 20 cout

18  2003 Prentice Hall, Inc. All rights reserved. Outline 18 1 // Fig. 4.9: fig04_09.cpp 2 // Gráfico de los valores de los elementos de un array con histogramas. 3 #include 4 5 using std::cout; 6 using std::endl; 7 8 #include 9 10 using std::setw; 11 12 int main() 13 { 14 const int arraySize = 10; 15 int n[ arraySize ] = { 19, 3, 15, 7, 11, 9, 13, 5, 17, 1 }; 16 17 cout

20  2003 Prentice Hall, Inc. All rights reserved. Outline 20 1 // Fig. 4.10: fig04_10.cpp 2 // Tirar un dado 6000 veces y totalizar resultados en un array. 3 #include 4 5 using std::cout; 6 using std::endl; 7 8 #include 9 10 using std::setw; 11 12 #include 13 #include 14 15 int main() 16 { 17 const int arraySize = 7; 18 int frecuencia[ arraySize ] = { 0 }; 19 20 srand( time( 0 ) ); // semilla del generador de números aleatorios 21 22 // tiro el dado 6000 veces 23 for ( int tirada = 1; tirada

22  2003 Prentice Hall, Inc. All rights reserved. Outline 22 1 // Fig. 4.11: fig04_11.cpp 2 // Uso de arrays para totalizar resultados de encuestas. 3 #include 4 5 using std::cout; 6 using std::endl; 7 8 #include 9 10 using std::setw; 11 12 int main() 13 { 14 // define los tamaños de los arrays 15 const int tamRespuestas = 40; // tamaño del array respuestas 16 const int tamFrecuencia = 11; // tamaño del array frecuencia 17 18 // sitúa respuestas de la encuesta en array respuestas 19 int respuestas[ tamRespuestas ] = { 1, 2, 6, 4, 8, 5, 9, 7, 8, 20 10, 1, 6, 3, 8, 6, 10, 3, 8, 2, 7, 6, 5, 7, 6, 8, 6, 7, 21 5, 6, 6, 5, 6, 7, 5, 6, 4, 8, 6, 8, 10 }; 22 23 // inicializa contadores de frecuencia a 0 24 int frecuencia[ tamFrecuencia ] = { 0 }; 25 Encuesta: calidad comida cafetería alumnos (1=horrible, 10=excelente). Nº encuestados: 40 alumnos

23  2003 Prentice Hall, Inc. All rights reserved. Outline 23 26 // para cada i, selecciono el valor de un elemento del array 27 // respuestas y uso ese valor como índice del array 28 // frecuencia para determinar el elemento a incrementar 29 for ( int i = 0; i < tamRespuestas; i++ ) 30 ++frecuencia[ respuestas[i] ]; 31 32 // imprimo resultados 33 cout

24  2003 Prentice Hall, Inc. All rights reserved. 24 4.4Ejemplos de uso de Arrays Uso de arrays para almacenar y manipular cadenas de caracteres o strings (más en capítulo 5) –Arrays de caracteres –Todas las cadenas terminan con null ( '\0' ) –Ejemplos char cadena1[] = "hola"; –Carácter null añadido implícitamente – cadena1 tiene 5 elementos char cadena1[] = { 'h', 'o', 'l', 'a', '\0’ }; –Los índices funcionan igual: cadena1[ 0 ] es 'h' cadena1[ 2 ] es 'l'

25  2003 Prentice Hall, Inc. All rights reserved. 25 4.4Ejemplos de uso de Arrays Entrada de teclado char cadena2[ 10 ]; cin >> cadena2; –Coloca la entrada del usuario en la variable Finaliza cuando encuentra el primer espacio en blanco Añade el carácter null –Si se introduce demasiado texto, los datos se escriben más allá del array Imprimir cadenas de caracteres –cout

26  2003 Prentice Hall, Inc. All rights reserved. Outline 26 1 // Fig. 4_12: fig04_12.cpp 2 // Tratamiento de arrays de caracteres como cadenas. 3 #include 4 5 using std::cout; 6 using std::cin; 7 using std::endl; 8 9 int main() 10 { 11 char cadena1[ 20 ], // reserva 20 caracteres 12 char cadena2[] = "cadena literal"; // reserva 15 caracteres 13 14 // lee cadena del usuario y la mete en array string2 15 cout > cadena1; // lee "hola" [el espacio finaliza la entrada] 17 18 // imprimo cadenas 19 cout

28  2003 Prentice Hall, Inc. All rights reserved. 28 4.4Ejemplos de uso de arrays Arrays locales estáticos y automáticos –Estáticos Si son static, las variables locales guardan sus valores entre llamadas a funciones Visibles sólo en el cuerpo de la función Se pueden declarar arrays estáticos –Inicializados a cero static int array[3]; –Si no son estáticos (automáticos) Se crean (y destruyen) en cada llamada a la función

29  2003 Prentice Hall, Inc. All rights reserved. Outline 29 1 // Fig. 4.13: fig04_13.cpp 2 // Los arrays estáticos se inicializan a cero. 3 #include 4 5 using std::cout; 6 using std::endl; 7 8 void staticArrayInit( void ); // prototipo de función 9 void automaticArrayInit( void ); // prototipo de función 10 11 int main() 12 { 13 cout

30  2003 Prentice Hall, Inc. All rights reserved. Outline 30 26 // función para demostrar un array local estático 27 void staticArrayInit( void ) 28 { 29 // inicializa elementos a 0 la primera vez que se llama a la función 30 static int array1[ 3 ]; 31 32 cout

31  2003 Prentice Hall, Inc. All rights reserved. Outline 31 47 // función para demostrar un array local automático 48 void automaticArrayInit( void ) 49 { 50 // inicializa los elementos cada vez que se llama a la función 51 int array2[ 3 ] = { 1, 2, 3 }; 52 53 cout

32  2003 Prentice Hall, Inc. All rights reserved. Outline 32 Primera llamada a cada función: Valores al entrar en staticArrayInit: array1[0] = 0 array1[1] = 0 array1[2] = 0 Valores al salir de staticArrayInit: array1[0] = 5 array1[1] = 5 array1[2] = 5 Valores al entrar en automaticArrayInit: array2[0] = 1 array2[1] = 2 array2[2] = 3 Valores al salir de automaticArrayInit: array2[0] = 6 array2[1] = 7 array2[2] = 8 Segunda llamada a cada función: Valores al entrar en staticArrayInit: array1[0] = 5 array1[1] = 5 array1[2] = 5 Valores al salir de staticArrayInit: array1[0] = 10 array1[1] = 10 array1[2] = 10 Valores al entrar en automaticArrayInit: array2[0] = 1 array2[1] = 2 array2[2] = 3 Valores al salir de automaticArrayInit: array2[0] = 6 array2[1] = 7 array2[2] = 8

33  2003 Prentice Hall, Inc. All rights reserved. 33 4.5Paso de arrays a funciones Se especifica el nombre sin corchetes –Para pasar el array miArray a miFuncion int miArray[ 24 ]; miFuncion( miArray, 24 ); –Se suele pasar el tamaño del array, pero no es necesario Útil para recorrer todos los elementos

34  2003 Prentice Hall, Inc. All rights reserved. 34 4.5Paso de Arrays a Funciones Los arrays se pasan por referencia –Las funciones pueden modificar los datos del array original –El valor del nombre del array es la dirección del primer elemento  La función sabe dónde está almacenado el array Puede modificar las localizaciones de memoria originales Los elementos individuales del array se pasan por valor –Como el resto de las variables –cuadrado( miArray[3] );

35  2003 Prentice Hall, Inc. All rights reserved. 35 4.5Paso de Arrays a Funciones Funciones que toman arrays –Prototipo de función void modificaArray( int b[], int arraySize ); void modificaArray( int [], int ); –Nombres opcionales en el prototipo Ambas toman un array de enteros y un entero –No es necesario indicar el tamaño del array entre corchetes El compilador lo ignora –Si declaramos un parámetro array como const No puede modificarse (error de compilación) void noModifica( const int [] );

36  2003 Prentice Hall, Inc. All rights reserved. Outline 36 1 // Fig. 4.14: fig04_14.cpp 2 // Paso de arrays y elementos de un array a funciones. 3 #include 4 5 using std::cout; 6 using std::endl; 7 8 #include 9 10 using std::setw; 11 12 void modificaArray( int [], int ); // aspecto extraño 13 void modificaElemento( int ); 14 15 int main() 16 { 17 const int tamArray = 5; // tamaño de array a 18 int a[ tamArray ] = { 0, 1, 2, 3, 4 }; // inicializa a 19 20 cout

38  2003 Prentice Hall, Inc. All rights reserved. Outline 38 52 53 // en función modificaArray, "b" apunta al 54 // array original "a" en memoria 55 void modificaArray( int b[], int tamañoDeArray ) 56 { 57 // multiplica cada elemento del array por 2 58 for ( int k = 0; k < tamañoDeArray; k++ ) 59 b[ k ] *= 2; 60 61 } // fin de la función modificaArray 62 63 // en función modificaElemento, "e" es una copia local del 64 // elemento del array a[ 3 ] pasado desde main 65 void modificaElemento( int e ) 66 { 67 // multiplica parámetro por 2 68 cout

39  2003 Prentice Hall, Inc. All rights reserved. Outline 39 Efectos de pasar el array completo por referencia: Los valores del array original son: 0 1 2 3 4 Los valores del array modificado son: 0 2 4 6 8 Efectos de pasar un elemento del array por valor: El valor de a[3] es 6 El valor en modificaElemento es 12 El valor de a[3] es 6

40  2003 Prentice Hall, Inc. All rights reserved. Outline 40 1 // Fig. 4.15: fig04_15.cpp 2 // Demostración del calificador de tipo const. 3 #include 4 5 using std::cout; 6 using std::endl; 7 8 void intentaModificarArray( const int [] ); // prototipo de función 9 10 int main() 11 { 12 int a[] = { 10, 20, 30 }; 13 14 intentaModificarArray( a ); 15 16 cout

41  2003 Prentice Hall, Inc. All rights reserved. Outline 41 22 // en función intentaModificarArray, "b" no puede usarse 23 // para modificar el array original "a" en main. 24 void intentaModificarArray( const int b[] ) 25 { 26 b[ 0 ] /= 2; // error 27 b[ 1 ] /= 2; // error 28 b[ 2 ] /= 2; // error 29 30 } // fin de la función intentaModificarArray d:\cpphtp4_examples\ch04\Fig04_15.cpp(26) : error C2166: l-value specifies const object d:\cpphtp4_examples\ch04\Fig04_15.cpp(27) : error C2166: l-value specifies const object d:\cpphtp4_examples\ch04\Fig04_15.cpp(28) : error C2166: l-value specifies const object

42  2003 Prentice Hall, Inc. All rights reserved. 42 4.6Ordenación de Arrays Ordenación de datos –Una de las aplicaciones más importantes en computación –Virtualmente cualquier organización debe ordenar algunos datos y, en muchos casos, cantidades masivas de datos Banco: ordena por nº de cuenta Guía de teléfonos: ordena por apellido Ordenación de burbuja –Varias pasadas por el array –Se comparan parejas de elementos consecutivos Si están en orden creciente (o idéntico), no se cambian Si están en orden decreciente, se intercambian –Se repiten estos pasos para cada elemento

43  2003 Prentice Hall, Inc. All rights reserved. 43 4.6Ordenación de Arrays Ejemplo: –Vamos de izquierda a derecha, e intercambiamos elementos si es necesario Una pasada para cada elemento –Original: 3 4 2 7 6 –Paso 1: 3 2 4 6 7 (se intercambian los elementos) –Paso 2: 2 3 4 6 7 –Paso 3: 2 3 4 6 7 (no se necesitan cambios) –Paso 4: 2 3 4 6 7 –Paso 5: 2 3 4 6 7 –Los elementos menores “burbujean” hacia la izquierda (como el 2 en este ejemplo)

44  2003 Prentice Hall, Inc. All rights reserved. 44 4.6Ordenación de Arrays Intercambio de variables int x = 3, y = 4; y = x; x = y; ¿Qué sucede? –¡Tanto x como y son 3! –Se necesita una variable temporal Solución int x = 3, y = 4, temp; temp = x; // temp toma el valor 3 x = y; // x toma el valor 4 y = temp; // y toma el valor 3

45  2003 Prentice Hall, Inc. All rights reserved. Outline 45 1 // Fig. 4.16: fig04_16.cpp 2 // Este programa ordena los valores de un array en orden ascendente. 3 #include 4 5 using std::cout; 6 using std::endl; 7 8 #include 9 10 using std::setw; 11 12 int main() 13 { 14 const int tamArray = 10; // tamaño del array a 15 int a[ tamArray ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 }; 16 int temp; // localización temporal usada para intercambio de elementos del array 17 18 cout

46  2003 Prentice Hall, Inc. All rights reserved. Outline 46 24 // ordenación de burbuja 25 // lazo que controla el número de pasadas 26 for ( int paso = 0; paso < tamArray - 1; paso++ ) 27 28 // lazo que controla el número de comparaciones por paso 29 for ( int j = 0; j < tamArray - 1; j++ ) 30 31 // compara elementos consecutivos y los intercambia si 32 // el primer elemento es mayor que el segundo 33 if ( a[ j ] > a[ j + 1 ] ) { 34 temp = a[ j ]; 35 a[ j ] = a[ j + 1 ]; 36 a[ j + 1 ] = temp; 37 38 } // fin de if 39 Se realiza una pasada por cada elemento del array. Si el elemento de la izquierda (índice j ) es mayor que el elemento a la derecha (índice j + 1 ), entonces los intercambiamos. Recordemos la necesidad de una variable temporal.

48  2003 Prentice Hall, Inc. All rights reserved. 48 4.7Caso de Estudio: Cálculo de Media, Mediana y Moda usando Arrays Análisis de resultados de una encuesta –Media Promedio (suma/número de elementos) –Mediana Valor en posición central de la lista ordenada 1, 2, 3, 4, 5 (3 es la mediana) Si el número de elementos es par, se toma el promedio de los dos del centro –Moda Respuesta (valor) más frecuente 1, 1, 1, 2, 3, 3, 4, 5 (1 es la moda)

49  2003 Prentice Hall, Inc. All rights reserved. Outline 49 1 // Fig. 4.17: fig04_17.cpp 2 // Este programa introduce el tema de análisis de datos. 3 // Calcula la media, mediana y moda de los datos. 4 #include 5 6 using std::cout; 7 using std::endl; 8 using std::fixed; 9 using std::showpoint; 10 11 #include 12 13 using std::setw; 14 using std::setprecision; 15 16 void media( const int [], int ); 17 void mediana( int [], int ); 18 void moda( int [], int [], int ); 19 void ordenaBurbuja( int[], int ); 20 void imprimeArray( const int[], int ); 21 22 int main() 23 { 24 const int tamRespuestas = 99; // tamaño del array de respuestas 25

50  2003 Prentice Hall, Inc. All rights reserved. Outline 50 26 int frecuencia[ 10 ] = { 0 }; // inicializa array frecuencia 27 28 // inicializa array respuestas 29 int respuestas[ tamRespuestas ] = 30 { 6, 7, 8, 9, 8, 7, 8, 9, 8, 9, 31 7, 8, 9, 5, 9, 8, 7, 8, 7, 8, 32 6, 7, 8, 9, 3, 9, 8, 7, 8, 7, 33 7, 8, 9, 8, 9, 8, 9, 7, 8, 9, 34 6, 7, 8, 7, 8, 7, 9, 8, 9, 2, 35 7, 8, 9, 8, 9, 8, 9, 7, 5, 3, 36 5, 6, 7, 2, 5, 3, 9, 4, 6, 4, 37 7, 8, 9, 6, 8, 7, 8, 9, 7, 8, 38 7, 4, 4, 2, 5, 3, 8, 7, 5, 6, 39 4, 5, 6, 1, 6, 5, 7, 8, 7 }; 40 41 // procesa respuestas 42 media( respuestas, tamRespuestas ); 43 mediana( respuestas, tamRespuestas ); 44 moda( frecuencia, respuestas, tamRespuestas ); 45 46 return 0; 47 48 } 49

51  2003 Prentice Hall, Inc. All rights reserved. Outline 51 50 // calculamos el promedio de todos los valores respuesta 51 void media( const int resp[], int tamArray ) 52 { 53 int total = 0; 54 55 cout

53  2003 Prentice Hall, Inc. All rights reserved. Outline 53 96 // determina la respuesta más frecuente 97 void moda( int frec[], int resp[], int tam ) 98 { 99 int mayor = 0; // representa la mayor frecuencia 100 int valorModa = 0; // representa la respuesta más frecuente 101 102 cout

55  2003 Prentice Hall, Inc. All rights reserved. Outline 55 144 145 // función que ordena un array mediante el algoritmo de la burbuja 146 void ordenaBurbuja( int a[], int tam ) 147 { 148 int temp; // variable temporal para intercambiar elementos 149 150 // lazo para controlar el número de pasos 151 for ( int paso = 1; paso < tam; paso++ ) 152 153 // lazo para controlar el número de comparaciones por paso 154 for ( int j = 0; j < tam - 1; j++ ) 155 156 // intercambio elementos desordenados 157 if ( a[ j ] > a[ j + 1 ] ) { 158 temp = a[ j ]; 159 a[ j ] = a[ j + 1 ]; 160 a[ j + 1 ] = temp; 161 162 } // fin de if 163 164 } // fin de la función ordenaBurbuja 165

56  2003 Prentice Hall, Inc. All rights reserved. Outline 56 166 // imprimo el contenido del array (20 valores por fila) 167 void imprimeArray( const int a[], int tam ) 168 { 169 for ( int i = 0; i < tam; i++ ) { 170 171 if ( i % 20 == 0 ) // comienzo nueva línea cada 20 valores 172 cout

57  2003 Prentice Hall, Inc. All rights reserved. Outline 57 ******** Media ******** La media es el valor promedio de los datos La media es igual al total de todos los datos dividido por el número de datos (99). El valor medio para este caso es: 681 / 99 = 6.8788 ******** Mediana ******** El array de respuestas desordenado es 6 7 8 9 8 7 8 9 8 9 7 8 9 5 9 8 7 8 7 8 6 7 8 9 3 9 8 7 8 7 7 8 9 8 9 8 9 7 8 9 6 7 8 7 8 7 9 8 9 2 7 8 9 8 9 8 9 7 5 3 5 6 7 2 5 3 9 4 6 4 7 8 9 6 8 7 8 9 7 8 7 4 4 2 5 3 8 7 5 6 4 5 6 1 6 5 7 8 7 El array ordenado es 1 2 2 2 3 3 3 3 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 La mediana es el elemento 49 del array de 99 elementos ordenados. Para este caso la mediana es 7

58  2003 Prentice Hall, Inc. All rights reserved. Outline 58 ******** Moda ******** Respuesta Frecuencia Histograma 1 1 2 2 5 0 5 0 5 1 1 * 2 3 *** 3 4 **** 4 5 ***** 5 8 ******** 6 9 ********* 7 23 *********************** 8 27 *************************** 9 19 ******************* La moda es el valor más frecuente. Para este caso la moda es 8 y ocurre 27 veces.

59  2003 Prentice Hall, Inc. All rights reserved. 59 4.8Búsqueda en Arrays: Búsqueda Lineal y Búsqueda Binaria Busco un valor clave dentro del array Búsqueda lineal –Compara cada elemento del array con el valor clave Comienza en un extremo y va hacia el otro –Útil para pequeños arrays desordenados Ineficiente Si la clave de búsqueda no existe, examina todos los elementos

60  2003 Prentice Hall, Inc. All rights reserved. 60 4.8 Búsqueda en Arrays: Búsqueda Lineal y Búsqueda Binaria Búsqueda binaria –Sólo se usa con arrays ordenados –Se compara el elemento en la posición central con la clave Si son iguales, se encontró la clave Si clave < centro –Repite la búsqueda en la primera mitad del array Si clave > centro –Repite la búsqueda en la última mitad del array –Algoritmo termina cuando clave=elemento central subarray –Muy rápida Como mucho N pasos, donde 2 N > nº de elementos Un array de 30 elementos implica como mucho 5 pasos 2 5 > 30

61  2003 Prentice Hall, Inc. All rights reserved. Outline 61 1 // Fig. 4.19: fig04_19.cpp 2 // Búsqueda lineal en un array. 3 #include 4 5 using std::cout; 6 using std::cin; 7 using std::endl; 8 9 int busquedaLineal( const int [], int, int ); // prototipo 10 11 int main() 12 { 13 const int tamArray = 100; // tamaño del array a 14 int a[ tamArray ]; // crea array a 15 int claveBusqueda; // valor a buscar en a 16 17 for ( int i = 0; i < tamArray; i++ ) // crea algunos datos 18 a[ i ] = 2 * i; 19 20 cout > claveBusqueda; 22 23 // busca claveBusqueda en array a 24 int elemento = busquedaLineal( a, claveBusqueda, tamArray ); 25 Toma el array, la clave de búsqueda, y el tamaño del array.

63  2003 Prentice Hall, Inc. All rights reserved. Outline 63 1 // Fig. 4.20: fig04_20.cpp 2 // Búsqueda binaria en un array. 3 #include 4 5 using std::cout; 6 using std::cin; 7 using std::endl; 8 9 #include 10 11 using std::setw; 12 13 // prototipos de funciones 14 int busquedaBinaria( const int [], int, int, int, int ); 15 void imprimeCabecera( int ); 16 void imprimeFila( const int [], int, int, int, int ); 17 18 int main() 19 { 20 const int tamArray = 15; // tamaño del array a 21 int a[ tamArray ]; // crea array a 22 int clave; // valor a localizar en a 23 24 for ( int i = 0; i < tamArray; i++ ) // crea algunos datos 25 a[ i ] = 2 * i; 26 27 cout > clave; 29

64  2003 Prentice Hall, Inc. All rights reserved. Outline 64 30 imprimeCabecera( tamArray ); 31 32 // busco la clave en el array a 33 int resultado = 34 busquedaBinaria( a, clave, 0, tamArray - 1, tamArray ); 35 36 // imprimo resultados 37 if ( resultado != -1 ) 38 cout

65  2003 Prentice Hall, Inc. All rights reserved. Outline 65 59 // imprimo subarray usado en esta iteración 60 imprimeFila( b, menor, medio, mayor, tam ); 61 62 // si la clave de búsqueda está en el elemento central, devuelve medio 63 if ( claveBusqueda == b[ medio ] ) // coinciden 64 return medio; 65 66 else 67 68 // si la clave de búsqueda es menor que el elemento del medio, 69 // calculo el nuevo elemento mayor 70 if ( claveBusqueda < b[ medio ] ) 71 mayor = medio - 1; // busco en la mitad inferior del array 72 73 // si la clave de búsqueda es mayor que el elemento del medio, 74 // calculo el nuevo elemento menor 75 else 76 menor = medio + 1; // busco en la mitad superior del array 77 } 78 79 return -1; // clave de búsqueda no encontrada 80 81 } // fin de la función busquedaBinaria Usa la regla de búsqueda binaria: Si clave=medio, coinciden Si es menor, busco en mitad inferior Si es mayor, busco en mitad superior El lazo calcula menor, mayor y medio dinámicamente. Si la búsqueda es en la mitad superior, menor será el elemento después de medio.

67  2003 Prentice Hall, Inc. All rights reserved. Outline 67 102 // imprime una fila de salida mostrando la parte del array 103 // que está siendo procesada 104 void imprimeFila( const int b[], int menor, int medio, 105 int mayor, int tam ) 106 { 107 // lazo que recorre el array 108 for ( int m = 0; m < tam; m++ ) 109 110 // imprime espacios si estamos fuera del rango del subarray actual 111 if ( m mayor ) 112 cout

68  2003 Prentice Hall, Inc. All rights reserved. Outline 68 Introduce un número entre 0 y 28: 6 Índices: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ------------------------------------------------------------ 0 2 4 6 8 10 12 14* 16 18 20 22 24 26 28 0 2 4 6* 8 10 12 6 encontrado en el elemento 3 del array Introduce un número entre 0 y 28: 25 Índices: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ------------------------------------------------------------ 0 2 4 6 8 10 12 14* 16 18 20 22 24 26 28 16 18 20 22* 24 26 28 24 26* 28 24* 25 no encontrado

69  2003 Prentice Hall, Inc. All rights reserved. Outline 69 Introduce un número entre 0 y 28: 8 Índices: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ------------------------------------------------------------ 0 2 4 6 8 10 12 14* 16 18 20 22 24 26 28 0 2 4 6* 8 10 12 8 10* 12 8* 8 encontrado en el elemento 4 del array

70  2003 Prentice Hall, Inc. All rights reserved. 70 4.9Arrays Multi-Dimensionales Múltiples índices –a[ i ][ j ] –Uso común: Representación de tablas con filas y columnas –Especificar un elemento: Especifico fila, y después columna –“Array de arrays” a[0] es un array de 4 elementos a[0][0] es el primer elemento de ese array Fila 0 Fila 1 Fila 2 Columna 0Columna 1Columna 2Columna 3 a[ 0 ][ 0 ] a[ 1 ][ 0 ] a[ 2 ][ 0 ] a[ 0 ][ 1 ] a[ 1 ][ 1 ] a[ 2 ][ 1 ] a[ 0 ][ 2 ] a[ 1 ][ 2 ] a[ 2 ][ 2 ] a[ 0 ][ 3 ] a[ 1 ][ 3 ] a[ 2 ][ 3 ] Índice de Fila Nombre array Índice de Columna

71  2003 Prentice Hall, Inc. All rights reserved. 71 4.9 Arrays Multi-Dimensionales Para inicializarlos –Por defecto a 0 –Inicializadores agrupados mediante filas entre llaves int b[ 2 ][ 2 ] = { { 1, 2 }, { 3, 4 } }; int b[ 2 ][ 2 ] = { { 1 }, { 3, 4 } }; 1 2 3 4 1 0 3 4 Fila 0Fila 1

73  2003 Prentice Hall, Inc. All rights reserved. Outline 73 1 // Fig. 4.22: fig04_22.cpp 2 // Inicialización de arrays multidimensionales. 3 #include 4 5 using std::cout; 6 using std::endl; 7 8 void imprimeArray( int [][ 3 ] ); 9 10 int main() 11 { 12 int array1[ 2 ][ 3 ] = { { 1, 2, 3 }, { 4, 5, 6 } }; 13 int array2[ 2 ][ 3 ] = { 1, 2, 3, 4, 5 }; 14 int array3[ 2 ][ 3 ] = { { 1, 2 }, { 4 } }; 15 16 cout

74  2003 Prentice Hall, Inc. All rights reserved. Outline 74 28 29 // función para imprimer el array con 2 filas y 3 columnas 30 void imprimeArray( int a[][ 3 ] ) 31 { 32 for ( int i = 0; i < 2; i++ ) { // para cada fila 33 34 for ( int j = 0; j < 3; j++ ) // imprime valores de columna 35 cout

75  2003 Prentice Hall, Inc. All rights reserved. 75 4.9 Arrays Multi-Dimensionales Ejemplo: programa para guardar las notas de 4 exámenes realizados por 3 alumnos –Array multi-dimensional (tabla) –Las filas son los alumnos (3) –Las columnas son las notas (4) 95 85 89 80 Exam1 Exam2 Alumno0 Alumno1

76  2003 Prentice Hall, Inc. All rights reserved. Outline 76 1 // Fig. 4.23: fig04_23.cpp 2 // Ejemplo de array de 2 dimensiones. 3 #include 4 5 using std::cout; 6 using std::endl; 7 using std::fixed; 8 using std::left; 9 10 #include 11 12 using std::setw; 13 using std::setprecision; 14 15 const int alumnos = 3; // número de alumnos 16 const int examenes = 4; // número de exámenes 17 18 // prototipos de funciones 19 int minimo( int [][ examenes ], int, int ); 20 int maximo( int [][ examenes ], int, int ); 21 double promedio( int [], int ); 22 void imprimeArray( int [][ examenes ], int, int ); 23

77  2003 Prentice Hall, Inc. All rights reserved. Outline 77 24 int main() 25 { 26 // inicializo notas de alumnos para 3 alumnos (filas) 27 int notasAlumnos[ alumnos ][ examenes ] = 28 { { 77, 68, 86, 73 }, 29 { 96, 87, 89, 78 }, 30 { 70, 90, 86, 81 } }; 31 32 // imprimo array notasAlumnos 33 cout

79  2003 Prentice Hall, Inc. All rights reserved. Outline 79 71 // busca la nota máxima 72 int maximo( int notas[][ examenes ], int alum, int tests ) 73 { 74 int notaMayor = 0; // inicializa a la menor nota posible 75 76 for ( int i = 0; i < alum; i++ ) 77 78 for ( int j = 0; j < tests; j++ ) 79 80 if ( notas[ i ][ j ] > notaMayor ) 81 notaMayor = notas[ i ][ j ]; 82 83 return notaMayor; 84 85 } // fin de la función maximo 86 87 // calculo la nota media de un alumno 88 double promedio( int notas[], int tests ) 89 { 90 int total = 0; 91 92 // suma todas las notas de un alumno 93 for ( int i = 0; i < tests; i++ ) 94 total += notas[ i ]; 95 96 return static_cast ( total ) / tests; // promedio 97 98 } // fin de función maximo

80  2003 Prentice Hall, Inc. All rights reserved. Outline 80 99 100 // Imprime el array 101 void imprimeArray( int notas[][ examenes ], int alum, int tests ) 102 { 103 // Fijo alineación a la izquierda e imprimo cabeceras de columnas 104 cout

81  2003 Prentice Hall, Inc. All rights reserved. Outline 81 El array es: [0] [1] [2] [3] notasAlumnos[0] 77 68 86 73 notasAlumnos[1] 96 87 89 78 notasAlumnos[2] 70 90 86 81 Nota mínima: 68 Nota máxima: 96 La nota media para el alumno 0 es 76.00 La nota media para el alumno 1 es 87.50 La nota media para el alumno 2 es 81.75

 2003 Prentice Hall, Inc. All rights reserved. 1 Capítulo 4 - Arrays Índice del Capítulo 4.1Introducción 4.2Arrays 4.3Declaración de Arrays 4.4Ejemplos.

Recommend Documents