Post on 28-Jan-2016
Computación II
UNIDAD V
Arreglos y Cadenas
Presentación de la unidad
• Objetivos– Comprende el concepto de arreglos– Comprender el uso de arreglos para almacenar,
ordenar y buscar.– Saber declarar arreglos, inicializarlos y como referirse
a los elementos individuales del arreglo.– Ser capaces de pasar arreglos a funciones.– Ser capaces de declarar y manipular arreglos de
varios subíndices.– Ser capaces de utilizar funciones de procesamiento
de cadenas.– Conocer las funciones de conversión de cadenas.
• Contenidos:– Arreglos.– Declaración de arreglos.– Como pasar arreglos a funciones.– Ordenación de datos.– Búsqueda en arreglos.– Arreglos con múltiples subíndices.– Cadenas– Lectura de cadenas.– Conversión.– Funciones de Biblioteca
Presentación de la unidad
• Un arreglo es un grupo de posiciones en memoria relacionadas entre si, por el hecho de que todas tienen el mismo nombre y son del mismo tipo.
• El tipo de elementos de un arreglo puede ser cualquier tipo de dato, incluyendo estructuras definidas por el usuario.
• Cualquier elemento de un array puede ser referenciado dándole el nombre del arreglo y la posición de dicho elemento entre corchetes.
• El número de posición se conoce como subíndice. Un subíndice debe ser un entero o una expresión entera.
• El primer elemento de cualquier arreglo es 0.
Arreglos
Declaración de Arreglos
• Los arreglos ocupan el espacio de memoria especificado en la declaración.
• Se especifica el tipo de elemento y el numero de elementos requerido por cada arreglo.
• Sintaxis:tipo_de_dato nombreArreglo [nroElementos]
• Los elementos de un arreglo pueden ser inicializados en la declaración.int x[5] = {3,5,7,9,11};int n[20] = {0};int y[] ={1,2,3,4};
• Si en una declaración con una lista inicializadora se omite el tamaño del arreglo, el numero de elementos del arreglo será el numero de elementos incluidos en la lista.
Cómo pasar arreglos a funciones
• C++ pasa de forma automática los arreglos a las funciones utilizando la simulación de llamadas por referencia.
• Para evitar la modificación de los valores del arreglo en la función se usa const.
• Ejemplos:float suma(const float arr[5]);float calcula(float arr[], int n); // n = tamañofloat media(float *arr, int n);
Las llamadas serían:cout<< suma(arr);cout<<calcula(arr, 5);cout<<media(arr, 5);
Ordenación de datos
• Ordenación tipo Burbuja– (ordenación por hundimiento) los valores mas
pequeños “flotan” hacia la parte superior del arreglo.
– Fácil de programar, lento en ejecución.– Técnica que consiste en llevar a cabo varias
pasadas a través del arreglo. En cada pasada se comparan pares sucesivos de elementos.
int ordenar_burbuja(int* array, int nroElementos){int i, j;int aux_elem;for (i = 0; i < nroElementos - 1; i++){
for (j = 1; j < nroElementos; j++){if (array[j] < array[j-1]){
aux_elem = array[j];array[j] = array[j-1];array[j-1] = aux_elem;
}}
}
}
Búsqueda en arreglos
• El proceso de encontrar en un arreglo un elemento en particular se llama búsqueda.
• Búsqueda lineal:– Técnica mas simple. Compara cada uno de los
elementos del arreglo con el valor buscado.– Útil para arreglos pequeños y arreglos no ordenados.
• Búsqueda binaria:– Técnica de alta velocidad. Después de cada una de
las comparaciones elimina la mitad de los elementos del arreglo bajo búsqueda.
Búsqueda lineal
int busquedaLineal(int arrayA[], int clave, int tam){int i = 0;for(; i<tam; i++)
if(arrayA[i] == clave)return i;
return -1;}
Búsqueda binariaint busquedaBinaria(int v[], int clave, int linf, int lsup){ int mitad, pos=-1, enc=0; while (linf<=lsup && !enc) { mitad=(linf+lsup)/2; if (v[mitad]==clave) enc=1; else if (x<v[mitad]) lsup=mitad-1; else linf=mitad+1; } if (enc) pos=mitad; return(pos);}
Arreglos con múltiples subíndices
• Loa arreglos pueden tener múltiples subíndices, conocidos como tablas o matrices.
• La información es arreglada en filas y columnas; para identificar un elemento debemos especificar los dos subíndices.
• Por convención, el primer subíndice identifica la fila o renglón y el segundo la columna.
• Sintaxis:tipo_de_elemento nArray [nroFilas][nroColumnas]int arrayA[2][3];
• Los arreglos de múltiples subíndices pueden tener mas de dos subíndices.tipo_de_elemento nArray <cota1><cota2><cota3>
• Un array multidimencional es en realidad un array de array.
Arreglos con múltiples subíndices
• Ejemplo:a [2][3]
0 1 2
0 a[0][0] a[0][1] a[0][2]
1 a[1][0] a[1][1] a[1][2]
columnafila
• Inicialización:
int a[2][3] = {{1,2,3}, {4,5,6}};
Cadenas
• Serie de caracteres tratados como una sola unidad.• En C/C++ una cadena es un arreglo de caracteres que
termina con el carácter nulo ‘/0’.• Se tiene acceso a la cadena mediante el puntero al primer
elemento de la cadena.• Una cadena puede ser asignada en una declaración, ya
sea como un arreglo de caracteres o como una variable de tipo char*
char color[] = “azul”;char color[] = {‘a’, ‘z’,’u’,’l’,’/n’}char *color;
• Constantes de carácter: valor int representado como un carácter entre comillas simples. El valor de una constante de carácter es el valor entero del carácter en el conjunto de caracteres de la maquina.
• Funciones de biblioteca:– getline(): permite leer una cadena completa
incluyendo cualquier espacio en blanco.cin.getline(<variable>, <max_long+2>);<variable>: identificador de la cadena a leer.<max_long+2>: máximo de caracteres que se leeran mas dos caracteres para permitir el carácter nulo ‘/0’ y el ‘/n’.
– get(): introduce un carácter del flujo designado, y devuelve dicho carácter como valor de la llamada.cin.get();
– putback(): coloca un carácter previo obtenido por un get() del flujo de entrada de regreso a dicho flujo.cin.putback();
Cadenas
• Funciones de biblioteca:– ignore(): pasa por alto un numero designado
de caracteres.
Puede tener tres comportamientos: 1. Sin argumentos, descarta el siguiente carácter de la
entrada
2. Con un argumento, un número, descarta ese número de caracteres
3. Con dos argumentos, un número y una letra, descarta o bien ese número de caracteres o bien hasta que se encuentre el carácter dado (descartándola también), lo que ocurra antes.
Cadenas
• Funciones de biblioteca:– put(): se utiliza para escribir el flujo de salida
cout carácter a carácter.
cout.put(‘A’);
Las llamadas a put pueden ser anidadas:
cout.put(65).put(‘/n’);
y contienen una constante de carácter o un ASCII
Cadenas
int main(){int c;
cout<<"Antes de ingresar una oracion por teclado, cin.eof" <<cin.eof()<<endl; while ((c = cin.get())!=EOF) cout.put(c); cout<<"\nluego de ingresar una oracion, cin.eof()" <<cin.eof()<<endl; system("PAUSE"); return 0;}
Cadenas
• EOF: por lo regular es -1, a fin de distinguirlo de los caracteres ASCII.
(<ctrl> + z) seguido por <return>• cin.eof() es 0 (falso); cuando el usuario escribe una línea
de texto seguida por un fin de archivo cin.eof() es 1 (verdadero.)
• Funciones de manipulación de cadenas (string.h)– char *strcpy(char *s1, const char *s2);
• Copia la cadena s2 al arreglo s1. Retorna la cadena s1.
– char *strcat(char *s1, const char *s2); • Agrega la cadena s2 al arreglo s1 y retorna s1.
– int strcmp(const char *s1, const char *s2); • Compara la cadena s1 con la cadena s2; si son iguales
devuelve 0, si es mayor devuelve 1, sino -1
– char strchr(const char *s, int c);• Localiza la primera instancia del carácter c en la cadena s. Si
encuentra c, regresa un puntero a c, sino un puntero a NULL
Cadenas
• Funciones de manipulación de cadenas (string.h)– char *strtok (char *s1, const char *s2);
• La secuencia de llamadas de strtok, divide la cadena s1 en tokens – partes lógicas- separados por caracteres contenidos en s2.
– size_t strlen(const char *s);• Determina la longitud de la cadena s, sin el
carácter ‘/n’.
Cadenas
• Conversión de cadenas a números– int atoi(const char *s1);
• Convierte la cadena s1 a int.
– double atof(const char *s1);• Convierte la cadena s1 a double.
– long atol(const char *s1);• Convierte la cadena s1 a long.
Cadenas