1 Fundamentos de ComputaciónArreglos
2 Objetivos Aprender la importancia de los arreglos de datos, su declaración y manipulación. Conocer cómo son almacenados en memoria. Aprender la aplicación de la inicialización estática de arreglos. Conocer la estructura de arreglos multidimensionales.
3 Introducción Conocemos los tipos de datos atómicos (int, double, char) Los tipos datos compuestos, por otro lado, están formados por tipos datos atómicos: las cadenas (string) están formados por caracteres (char). Así mismo, se pueden crear otros tipos de datos mas complejos, usando tipos de datos compuestos. Este tipo de agrupación, para crear nuevos tipos de datos, puede seguir hasta que se necesite.
4 Estructura de Datos Se puede considerar un conjunto de datos,Como una sola entidad… Como un solo tipo de dato… De esta forma, se reduce la complejidad de un problema. Un programa esta formado por: Estructuras de control y llamadas a funciones (el algoritmo de nuestro programa). Datos, con sus respectivos tipos, ya sean estos atómicos o complejos, juntos forman una jerarquía (la estructura de datos del programa). PROGRAMA = ALGORITMO + ESTRUCTURA DE DATOS
5 Jamás olvidar que un arreglo tiene un tipo¿Qué es un Arreglo? Basándonos en los tipos de datos atómicos, podemos crear otros más complejos. Un arreglo es una colección, o grupo de datos, donde: Cada dato tiene su posición (primero, segundo, tercero…) Y todos los datos del grupo son del mismo tipo, es decir, o todos son enteros, o todos son reales, etc. La mejor forma de visualizar un arreglo es: Como un grupo de cajas, una detrás de otra NO EXISTEN ARREGLOS “MEZCLADOS” Jamás olvidar que un arreglo tiene un tipo ... Donde cada caja representa un dato del arreglo o un elemento. Podemos concluir que un arreglo tiene: Tamaño: cuantas cajas va a tener, el numero de datos Tipo: cual es el tipo de todos los datos del arreglo Nombre: el único nombre bajo el cual vamos a dirigirnos al mismo.
6 Declaración de ArreglosAl declarar una variable cualquiera siempre indicamos: tipo y nombre. Para declarar un arreglo, se debe indicar Tipo Nombre y Tamaño Un arreglo de 10 elementos enteros, se declara: int ArregloEnteros[10]; Y lo podemos visualizar: Jamás olvidar, el tamaño de un arreglo es una constante 1 2 3 4 5 6 7 8 9 ArregloEnteros Cada elemento del grupo va a estar identificado por un valor numérico, llamado índice. En C el primer elemento de un arreglo tiene el índice 0. Siempre, para indicar el tamaño de un arreglo, se utilizara un valor constante, jamás una variable.
7 Manejo de Arreglos Tenemos ahora 10 enteros bajo un mismo nombre ¿Como accedemos a uno de esos datos? Usamos el nombre del arreglo y el índice que identifica al elemento nombre_arreglo[indice] Si se desea asignar el valor de 2 al primer elemento del arreglo: ArregloEntero[0] = 2; ArregloEntero[4] = 1: ArregloEntero[1] = 9; 1 2 3 4 5 6 7 8 9 ArregloEnteros 2 9 1 Cada elemento es en efecto una variable del tipo declarado para el arreglo Es muy importante no olvidar: El índice de un elemento, no es el valor de dicho elemento El índice puede ser cualquier expresión que retorne un valor entero Para asignar a todos los elementos del arreglo, un mismo valor, lo mas practico es usar un for: for(i = 0; i < 10; i++){ ArregloEntero[i] = 0 }
8 Leer e Imprimir un ArregloAcabamos de ver un ejemplo para acceder a todos los elementos de una arreglo de una forma practica Si tenemos 10 elementos en un arreglo, y queremos pedir que los ingresen por teclado, debemos repetir el ingreso 10 veces: ArregloEnteros[0] = GetInteger(); ArregloEnteros[1] = GetInteger(); ArregloEnteros[2] = GetInteger(); .... for(i = 0; i < 10; i++) { ArregloEnteros[i] = GetInteger(); } Así mismo, para imprimir todos los elementos de un arreglo, deberíamos repetir el proceso de imprimir un, pero diez veces: for(i = 0; i < 10; i++) { printf(“Elemento No. %d:%d\n”,i+1,ArregloEnteros[i]); }
9 Ejercicio Escribir un programa que permita el ingreso de las notas de un curso de 20 alumnos. Una vez ingresados, debe mostrarse el promedio de las mismas. El usuario del programa no tiene porque saber que los índices van desde 0, se le pueden mostrar desde 1 #define MAX_ALUMN 20 main(){ double Notas[MAX_ALUMN]; double total, promedio; int i; total = 0; for(i = 0; i < MAX_ALUMN; i++){ printf("Ingrese Alumno No %d:",i+1); Notas[i]=GetInteger(); } for(i = 0; i < MAX_ALUMN; i++) { total = total + Notas[i]; promedio = (double)total / (double)MAX_ALUMN; printf("Promedio: %.2f",promedio);
10 Representación Interna de DatosEl ejercicio que acabamos de resolver es bastante sencillo. No tuvimos que aplicar refinamiento paso a paso. La clave del refinamiento es el uso de funciones, pero … ¿Cómo uso funciones y arreglos?, es decir, como una función puede recibir un arreglo? Antes de adentrarnos en ese tema debemos revisar como están almacenados internamente los datos
11 Bits bytes y words En el nivel más primitivo están los bits (binary digit), solo almacenan 0 o 1. Los bits son muy pequeños para contener información completa. Para poder almacenar información, se unen varios bits, y se manejan como una unidad. Los bytes son conjuntos de 8 bits, pero siguen siendo muy pequeños, apenas pueden almacenar un carácter. Los bytes se unen para formar las “palabras”(word) Una palabra, usualmente es del tamaño suficiente para almacenar un valor entero.
12 Direcciones de MemoriaPara no perderse, la máquina le da una dirección numérica a cada uno de sus bytes. El primer byte tiene dirección 0, el segundo 1, y así. Al declarar una variable de tipo char, el computador buscará darle una dirección. 1 ... 1001 1002 1003 1004 1005 1006 1089 1090 65 int a char c; No hay como saber la dirección que le dará el computador. Asumamos que es 1004. Si se le asigna un valor a la variable: c = ‘A’; El byte pasará a almacenar dicho valor. Ahora la dirección 1004 tiene el contenido 65. char c Valores mayores a un solo caracter, se deben almacenar en mas bytes. Estos bytes serán consecutivos. Si un entero toma dos bytes, estos tendrán direcciones consecutivas. int a;
13 Operador sizeof Un char ocupa un byte.¿Cuantos bytes ocupa un entero? ¿un real? ¿una cadena? Depende de cada máquina Podemos averiguarlo usando el operador sizeof. sizeof(int) devuelve el número de bytes que necesita un dato de tipo int. CUIDADO: sizeof es un operador, no una función.
14 Reservar Espacio en MemoriaComo ya vimos, cuando se crea una variable, la computadora le asigna un espacio en memoria. Este acto se conoce como “reservar” memoria, o “allocation”(en inglés). Para las variables globales, la memoria se “reserva” cuando el programa comienza y se “libera” cuando este termina. Para las variables locales, la memoria se “reserva” cuando se entra en su ambiente y se “libera” cuando este termina(funciones). Si se declara un arreglo de 10 enteros, la computadora reserva memoria consecutiva para 10 variables, del tamaño de los enteros. Consecutiva, quiere decir que los bytes reservados tienen todos direcciones una a continuación de otra. Ejemplo: char ArregloChar[20]; La computadora reserva 20 bytes double Puntaje[5]; Si cada double requiere 8 bytes, la computadora reserva 40 bytes todos consecutivos.
15 Cuando Acceder a un Elemento ...En memoria, si queremos acceder a un elemento del arreglo Puntaje La dirección base es la dirección del primer elemento del arreglo. El ajuste necesario para llegar a la dirección de un elemento dado se conoce como desfase. ¿Cuál es la dirección del elemento de índice 2? R: 2* = 1016 Si se accede al elemento Puntaje[6], ¿que pasaría? Esta fuera del rango. Pero en memoria tendría, lógicamente, la dirección 6*8+1000= 1048. En la computadora existe un byte con esa dirección, pero no tendrá precisamente lo que esperamos. Contendrá “basura”. 1000 1008 1016 1024 1032 Puntaje[0] Puntaje[1] Puntaje[2] Puntaje[3] Puntaje[4]
16 Paso de Arreglos a FuncionesEscribir un programa que: Lea una lista de enteros hasta que se ingrese 0 Reverse los elementos en la lista Muestre la lista invertida Para resolver un problema con varios requerimientos podemos usar refinamiento paso a paso funciones Aquí se pasa la lista vacía, y debe regresar llena de los datos ingresados por teclado void main() { int list[Nelements]; LeerArreglo(list); ReversarArreglo(list); ImprimirArreglo(list); } La lista ingresada se envía a la función y debe regresar reversada La lista será impresa
17 Generalizando el Número de ElementosEl problema plantea que se debe ingresar una cantidad indefinida de números. Para declarar un arreglo, debemos decidir previamente cuantos elementos este va a tener. La estrategia es asumir un máximo, mucho mayor de lo que se va a necesitar. Quizás no use todos los elementos, pero declara un máximo “por si acaso”. Debemos conocer cuantos elementos vamos usando hasta el momento. Esta información se almacena en una variable separada n El tamaño del arreglo se conoce como el tamaño máximo. El número de elementos usados hasta el momento es el tamaño efectivo.
18 Revisando las FuncionesSi asumimos que al enviar un arreglo a una función, esta lo modifica y lo regresa modificado: La función que lea los datos del arreglo Necesita: El arreglo El máximo numero de elementos La centinela para detener la lectura Devuelve El tamaño efectivo del arreglo Las funciones que reversan e imprimen el arreglo Necesitan El tamaño efectivo Retornan Nada (void) Entonces son procedimientos
19 Los Prototipos A una función que usa un arreglo entonces, siempre se le manda: El arreglo y El tamaño, ya sea el máximo o el efectivo Los prototipos serían: int LeeArreglo(int arreglo[],int max, int centinela); void ReversaArreglo(int arreglo[],int n); void ImprimeArreglo(int arreglo[],int n); Cuando una función recibe un arreglo como parámetro, se indica: El tipo del arreglo, el nombre en la función, seguido de [ ] vacíos, NINGUN VALOR DENTRO DE ELLOS!!!
20 Funcionamiento InternoCuando una variable se envía a una función, lo que realmente se envía es una copia de la variable. Si en la función, se modifica el valor de dicho parámetro, al retornar, no quedará rastro de dichos cambios. El programa que llame a la función, no se enterará de los cambios, pues esta fue llamada por valor. Al pasar un arreglo, sin embargo, no se envía una copia de cada elemento del arreglo. Se envía la dirección de memoria del primer elemento del arreglo. Cualquier cambio que se desee hacer sobre el arreglo, se hace efectivamente sobre el arreglo que fue originalmente enviado a la función. Al regresar al programa que llamo a la función, el arreglo aparece modificado.
21 Note que es un procedimiento.El Programa Principal #define MAX 250 #define CENTINELA 0 static int LeerArreglo(int lista[],int max,int centinela); static void ReversarArreglo(int lista[],int n); static void ImprimirArreglo(int lista[],int n); main(){ int lista[MAX],n; n = LeerArreglo(lista, MAX,CENTINELA); ReversarArreglo(lista,n); ImprimirArreglo(lista,n); } Leer arreglo devuelve el tamaño efectivo del arreglo La misma lista que se manda, va a ser modificada por ReversarArreglo. Note que es un procedimiento.
22 La Estrategia para ReversarPara reversar los elementos almacenados en cualquier arreglo. Ejemplo: 1 2 3 4 5 6 7 8 9 A 15 20 11 El primero se intercambia con el ultimo, el segundo con el penúltimo, etc 1 2 3 4 5 6 7 8 9 A 11 20 4 15 3 5 8 1 9 2 Se puede dividir el arreglo en dos partes Se intercambian los elementos de la primera mitad, con los de la segunda Quiere decir que si el arreglo es de tamaño n, se deben hacer n/2 intercambios Y recuerde, mientras avanza en la primera mitad, retrocede en la segunda
23 La Implementación El objetivo de esta función es leer n elementos hasta que se ingrese una centinela. static int LeerArreglo(int lista[],int max,int centinela){ int i,valor; for(i = 0; i < max;i++){ valor = GetInteger(); if(valor == centinela) break; lista[i] = valor; } return(i); static void ReversarArreglo(int lista[],int n){ int i,tmp; for(i = 0; i
24 Arreglos Para Tabular En lugar de almacenar valores en los elementos de un arreglo, algunas aplicaciones usan los arreglos para almacenar “índices”, que permiten llevar estadísticas, de un dato en particular. Por ejemplo: Se pidió a 40 estudiantes que calificaran la calidad de la comida de la cafetería en una escala del 1 al 10 (1 es terrible y 10 excelente). Escriba un programa en C que pida las 40 respuestas y luego muestre un resumen del resultado.
25 Solución En este tipo de problemas se deben usar dos arreglos:El primero es el que almacena las “respuestas”, los datos a los que se les va a calcular estadísticas(40 respuestas). El segundo es que almacena las estadísticas, en este caso, la frecuencia con la que se dio cada respuesta(10 tipos de respuestas). Los pasos para resolverlos son: Permitir el ingreso de las 40 respuestas. Contabilizar cada respuesta. Cada respuesta incrementa el contador respectivo, el cual sería un elemento del arreglo de frecuencias. Mostrar la tabla con el resumen de respuestas.
26 El Enfoque Adecuado 10 1 5 2 9 7 Respuestas[0] Respuestas[1] Respuestas[2] Respuestas[3] Respuestas[4] Respuestas[5] 4 Respuestas[6] Respuestas[7] Respuestas[8] Respuestas[9] Respuestas[10] Respuestas[11] Respuestas[12] Respuestas[13] Respuestas[14] Respuestas[15] Respuestas[16] Frecuencias[0] Frecuencias[1] Frecuencias[2] Frecuencias[3] Frecuencias[4] Frecuencias[5] Frecuencias[6] Frecuencias[7] Frecuencias[8] Frecuencias[9] 2 1 2 3 1 2 1 2 1 3 2 1 3 3 1 2 3 2 1 2 1 2 1 3 1 2 1 1 1 2 1 1 2 1 2 1 2 Se necesitan dos arreglos: Frecuencias es un conjunto de contadores: Frecuencias[0] es el contador para la respuesta 1 Frecuencias[5] es el contador para la respuesta 4 Por cada elemento de respuestas se aumenta 1 al elemento de frecuencias correspondiente
27 El Programa Principal #define MAX_RESP 40 #define MAX_FREC 10#define CENTINELA 0 static void InicializarArreglo(int arreglo[],int max); static int LeerArreglo(int arreglo[],int max, int sent); static void Contabilizar(int resp[],int n, int freq[]); static void ImprimirArreglo(int arreglo[],int n); main(){ int Respuestas[MAX_RESP], frecuencias[MAX_FREC],n; InicializarArrelo(frecuencias, MAX_FREC); n = LeerArrelo(Respuestas, MAX_RESP, CENTINELA); Contabilizar (Respuestas,n,frecuencias); ImprimirArreglo(frecuencias, MAX_FREC); } Lee hasta 40 respuestas. Cada respuesta solo puede ser un valor entre 1 y 10 Frecuencias es un conjunto de contadores, hay que inicializarlos a 0 antes de usarlos Contabiliza y coloca el resultado en el arreglo frecuencias
28 Valor almacena un valor entre 1 y 10, las posibles respuestasLa Implementación static InicializarArreglo(int arreglo[],int max){ int i; for(i =0; i < max; i++){ arreglo[i] = 0; } static int LeerArreglo(int arreglo, int max, int centi){ for(i = 0; i < max; i++){ while(TRUE){ valor = GetInteger(); if(valor == centi) return(i); if(valor >=1 && valor <=MaxFreq) break; return(max); static void Contabilizar(int resp[],int n, int freq[]){ int i.valor; for(i = 0; i < n;i++){ valor = resp[i]-1; freq[valor] = freq[valor] +1; validar Valor almacena un valor entre 1 y 10, las posibles respuestas Con esto vamos al arreglo de frecuencias y aumentamos el contador respectivo.
29 Inicialización de un ArregloUn arreglo en C también se puede inicializar de las siguientes formas: Crear un arreglo de 3 elementos Inicializando cada elemento: int A[]={11,2,8}; ó int A[3]={11,2,8}; Inicializando todos los elementos con el mismo valor: int A[3]={0};
30 ¿Cómo calcular el tamaño de un arreglo?1000 1008 1016 1024 1032 Arreglo[0] Arreglo[1] Arreglo[2] Arreglo[3] Arreglo[4] Si inicializamos una arreglo sin indicar su ancho, ¿Como podemos saber el ancho, para futuros usos en el programa? Sabemos que sizeof devuelve el número total de bytes que ocupa un tipo de dato o una variable de un tipo dado. sizeof(Arreglo) devolverá el total de bytes que ocupan todos los elementos de un arreglo. sizeof(Arreglo[0]) devuelve el tamaño total de bytes que ocupa un elemento del arreglo. sizeof(Arreglo)/sizeof(Arreglo[0]) devolverá el numero del elementos de Arreglo. sizeof(Arreglo) devuelve 32 sizeof(Arreglo[0]) devuelve el desfase: 8 sizeof(Arreglo)/sizeof(Arreglo[0]) devuelve 4, justo el número de elementos del arreglo.
31 Arreglos MultidimensionalesEn C, los elementos de un arreglo pueden ser de cualquier tipo Esto quiere decir que los elementos de un arreglo pueden ser a su vez, arreglos. Arreglos de arreglos, se conocen como arreglos multidimensionales. El mas común de estos, es el de dos dimensiones, conocido también como Matriz. Un ejemplo de una matriz, es un tablero de tres en raya Este es un arreglo de 3 elementos, donde cada elemento es un arreglo, de tres elementos también. A[0] A[1] A[2] 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] int A[3][3];
32 Paso de Arreglos MultidimensionalesLos arreglos multidimensionales también pueden ser pasados entre funciones Para mostrar un tablero de tres en raya se podría usar un arreglo de caracteres de 3 por 3: char tablero[3][3]; Para mostrar el tablero podríamos usar una función, que seria declarada MostrarTablero(char tablero[3][3]); o MostrarTablero(char tablero[][3]); La cabecera de la implementación luce exactamente igual void MostrarTablero(char tablero[][3]) { int fila, columna; for(fila = 0; fila < 3; fila++) { if(fila != 0) printf(“ \n”); for(columna = 0; columna < 3; columna++) if(columna != 0) printf(“|”; printf(“ %c “, board[fila][columna]); } printf(“\n”); X | O | X | X | O X | | O
33 Inicialización Un arreglo multidimensional también se puede inicializar static double MatrizIdentidad[3][3] = { {1,0,0}, {0,1,0} {0,0,1} }; Así podemos inicializar todos los elementos de una matriz desde el inicio, sin necesidad de usar lazos anidados.
34 Búsqueda en un Arreglo Se refiere al proceso para encontrar un elemento particular en un arreglo. Una de las estrategias mas comunes y simples para buscar un dato en un arreglo es: Revisar uno por uno los elementos del mismo, este método se conoce como búsqueda lineal. Escribir una función que determine si un valor dado se encuentra en un arreglo de elementos enteros, y si es así, indique su posición-
35 Solución Dato a buscar: 58 19 12 1 2 58 100 3 4 45 25 A[0] A[1] A[2]int EncontrarElemento(int valor, int arreglo[ ] ,int n) { for(i=0; i <10; i++) if (valor = = arreglo [ i ] ) return(i); } return(-1);
36 Búsqueda Binaria La búsqueda lineal es conocida por no ser tan eficiente. Si buscamos un dato que justo esta en el ultimo elemento del arreglo, tendremos que revisar todo el arreglo para llegar a el Otro mecanismo de búsqueda es la búsqueda binaria: Para este tipo de búsqueda se asume que el arreglo contiene valores ordenados. Si asumimos que el valor que buscamos esta entre los elementos 0 y n-1, en vez de probar con cada elemento, probamos solo con el de la mitad (0+n-1)/2 Si buscamos la cadena “Manta” desde hasta Cuenca Guayaquil Ibarra Loja Machala Manta Quito 1 2 3 4 5 6 desde mitad desde mitad mitad Si el valor buscado es menor que el elemento de la mitad, ya no buscamos de 0 a n-1, si no de 0 a la mitad. Si el valor buscado es mayor que el elemento de la mitad, ya no buscamos de 0 a n-1, si no de la mitad hasta n-1. Si el valor buscado es igual al elemento de la mitad, terminamos la búsqueda Con estos nuevos “límites”, repetimos la busqueda hasta que el limite inferior sea mayor que el limite superior, en cuyo caso sabremos que el valor buscado no esta en el arreglo. Palabra encontrada en la posición 5
37 Ejercicio En Clase Escribir una función EncontrarCadena que busque una cadena en un arreglo de las mismas int EncontrarCadena(string valor, string conjunto[ ], int n){ int desde, hasta, mid, cmp; desde = 0; hasta = n-1; while(desde <= hasta){ mid = (desde+hasta)/2; cmp = StringCompare(valor,conjunto[mid]); if(cmp == 0) return (mid); if(cmp < 0){ hasta = mid -1; } else{ desde = mid+1; } return (-1); Se calcula la mitad Si ya se encontró el valor, se retorna la posición Se determina que el valor esta en la parte inferior a la mitad(mitad->hasta) Se determina que el valor esta en la parte superior a la mitad(desde->mitad) El valor no está en el arreglo
38 Ordenamiento Se refiere al proceso de arreglar los elementos en una arreglo, para que almacenen los datos en un orden definido. Ejemplo: las compañías telefónicas ordenan sus listas de cuentas por apellido y luego por nombre Un método sencillo es el de la selección. Se llama así porque los valores mas pequeños se van seleccionando. 31 41 59 26 53 A[0] A[1] A[2] A[3] A[4] 26 41 59 31 53 A[0] A[1] A[2] A[3] A[4] 26 31 41 59 53 A[0] A[1] A[2] A[3] A[4] 26 31 41 53 59 A[0] A[1] A[2] A[3] A[4] for(i = 0; i
39 Implementación static void Ordenar(int arreglo[ ],int n){int desde, posmenor,tmp; for(desde = 0; desde