|
|
||
| PRIMERO DE INGENIEROS INDUSTRIALES | ||
| UNIVERSIDAD POLITÉCNICA DE CARTAGENA |
FUNDAMENTOS DE INFORMÁTICA. PROGRAMACIÓN EN C. |
|
|
Pedro María Alcover Garau |
PRIMERO DE INGENIEROS TÉCNICOS INDUSTRIALES |
|
|
0.
Presentación. |
ASIGNACIÓN DINÁMICA DE MEMORIA
Cuando hemos hablado de los vectores, hemos remarcado la idea de que la dimensión indicada en su declaración debe ser un literal: long numeros[100]; Con esa sentencia creamos un vector de 100 enteros largos: acabamos de reservar 400 bytes para codificar valores de este tipo de dato. En muchas ocasiones nos podría interesar que la declaración de este vector se hiciera mediante una variable, y poder así reservar el espacio de memoria que realmente necesitáramos. Por ejemplo, al crear unas matrices en un programa de operatoria de matrices, vendría bien poder codificar algo del siguiente estilo: long f, c; printf(“Número de filas de su matriz A ... ”); scanf(“%ld”,&f); printf(“Número de columnas de su matriz A ... ”); scanf(“%ld”,&c); long A[f][c]; Y así, quedaría creada la matriz de acuerdo con la dimensión deseada. Pero este código es erróneo. Esta forma de crear matrices no puede llevarse a cabo bajo ningún concepto, porque la reserva de memoria de una matriz o de un vector se realiza en tiempo de compilación: el compilador, antes de ejecución alguna, debe saber cuánta memoria se debe reservar y para qué dominio de valores. Eso es un serio problema. Si deseamos hacer un programa que necesite manejar información con arrays o matrices, siempre habrá que dimensionar esos espacios de memoria de manera que consideren el caso más desfavorable: para la ocasión en que se necesite un mayor tamaño. Y luego recorrer ese array o esa matriz acotando el uso a la zona que nos interesa. Un ejemplo simple: si queremos crear una matriz cuadrada, y su dimensión puede estar en un valor entre 2 y 100, el programador deberá hacer lo siguiente: long matriz[100][100]; short int dimension; short int i, j; printf(“Indique la dimensión de la matriz ... ”); scanf(“%hd”,&dimension); // Introducción de valores... for( i = 0 ; i < dimension ; i++) for(j = 0 ; j < dimension j++) { printf(“matriz[%hd][%hd] = ”, i, j); scanf(“%ld”,&matriz[i][j]); } Y así, si el usuario introduce el valor 3, entonces emplearemos 36 bytes para el manejo de nuestra matriz de 9 enteros largos. Pero la memoria reservada será de cuarenta mil bytes. C dispone de un modo para lograr que la reserva de memoria quede optimizada, haciendo esa reserva en tiempo de ejecución, cuando el programa se ejecuta y ya sabe con exactitud la memoria que necesita: mediante la asignación dinámica de memoria. Con ello se logra ajustar la cantidad de memoria que utiliza el programa al tamaño que realmente es necesario para cada ejecución concreta Disponemos de algunas funciones que nos permiten reservar y liberar esa memoria de una forma dinámica, es decir, en tiempo de ejecución.
Función malloc Esta función malloc queda definida en la biblioteca stdlib.h. También la encontramos en la biblioteca alloc.h. Recomendamos hacer uso siempre de la definición recogida en stdlib. Su prototipo es el siguiente: void *malloc(size_t size); Donde el tipo de dato size_t lo consideraremos ahora nosotros simplemente como un tipo de dato long. La función reserva tantos bytes consecutivos como indique el valor de la variable size y devuelve la dirección del primero de esos bytes. Esa dirección debe ser recogida por una variable puntero: si no se recoge, tendremos la memoria reservada pero no podremos acceder a ellas porque no sabremos dónde ha quedado hecha esa reserva. Como se ve, la dirección de devuelve con el tipo de dato void*. La función malloc así lo hace porque está definida para hacer reserva de bytes, al margen de para qué se reservan esos bytes. Pero no tendría sentido trabajar con direcciones de tipo de dato void. Por eso, en la asignación al puntero que debe recoger la dirección del array, se debe indicar, mediante el operador forzar tipo, el tipo e la dirección. Veamos un ejemplo: long dim; float *vector; printf(“Dimensión de su vector ...”); scanf(“%ld”,&dim); vector = (float*)malloc(4 * dim); En el ejemplo, hemos reservado tantos bytes como hace falta para reservar memoria para un array de float de la dimensión indicada por el usuario. Como cada variable float ocupa cuatro bytes hemos multiplicado la dimensión por cuatro. Como se ve, en la asignación, a la dirección de memoria que devuelve la función malloc, le hemos indicado que deberá comportarse como dirección de float. De ese tipo es además el puntero que la recoge. A partir de este momento, desde el puntero vector y con operatoria de punteros podemos manejarnos por el array creado en tiempo de ejecución. También se puede recorrer el array con índices, como si de un vector normal se tratase: la variable vector[i] es la misma que la variable *(vector + i). Es responsabilidad del programador reservar un número de bytes que sea múltiplo del tamaño del tipo de dato para el que hacemos la reserva. Si, por ejemplo, en una reserva para variables float, el número de bytes no es múltiplo de 4, el compilador no interrumpirá su trabajo, y generará el ejecutable; pero existe el peligro, en un momento dado, de incurrir en una violación de memoria. De forma habitual al invocar a la función malloc se hace utilizando el operador sizeof. La sentencia anterior en la que reservábamos espacio para nuestro vector de tipo float quedaría mejor de la siguiente forma: vector = (float*)malloc(sizeolf(float) * dim); Y una última observación sobre la reserva de la memoria. La función malloc busca un espacio de memoria (en la memoria heap o montón: pero no es ese tema que ahora vaya a ocuparnos) de la longitud que se le indica en el argumento. Gracias a esta asignación de memoria se podrá trabajar con una serie de valores, y realizar cálculos necesarios para nuestra aplicación. Pero… ¿y si no hay en la memoria un espacio suficiente de bytes consecutivos, libres y disponibles para satisfacer la demanda? En ese caso, no podríamos realizar ninguna de las tareas que el programa tiene determinadas, simplemente porque no tendríamos memoria. Cuando la función malloc lo logra satisfacer la demanda, devuelve el puntero nulo. Es importante, siempre que se crea un espacio de memoria con esta función, y antes de comenzar a hacer uso de ese espacio, verificar que sí se ha logrado hacer buena reserva. En caso contrario, habitualmente lo que habrá que hacer es abortar la ejecución del programa, porque sin memoria, no hay datos ni capacidad de operar con ellos. Esta verificación se realiza de la siguiente manera: vector = (float*)malloc(dimension * sizeof(float)); if(vector == NULL) { printf("\nNo hay memoria disponible."); printf("\nEl programa va a terminar."); printf("\nPulse cualquier tecla ... "); exit(1); } Y así, nunca trabajaremos con un puntero cuya dirección es nula. Si no hiciéramos esa verificación, en cuanto se echase mano del puntero vector para recorrer nuestra memoria inexistente, el programa abortaría inmediatamente. Es mejor tomar nosotros la iniciativa, mediante la función exit, y decidir nosotros el modo de terminación del programa en lugar de que lo decida un error fatal de ejecución. Existen otras funciones muy similares de reserva de memoria dinámica. Por ejemplo, la función calloc, que tiene el siguiente prototipo: void *calloc(size_t nitems, size_t size); Que recibe como parámetros el número de elementos que se van a reservar y el número de bytes que ocupa cada elemento. La sentencia anterior vector = (float*)malloc(dimension * sizeof(float)); ahora, con la función calloc, quedaría: vector = (float*)calloc(dimension, sizeof(float)); Como se ve, en sustancia, ambas funciones tienen un comportamiento muy similar. También en este caso, obviamente, será conveniente hacer siempre la verificación de que la memoria ha sido felizmente reservada. Lo mejor es acudir a las ayudas de los compiladores para hacer buen uso de las especificaciones de cada función. Una última función de asignación dinámica de la memoria es la función realloc. Su prototipo es el siguiente: void *realloc(void *block, size_t size); Esta función sirve para reasignar una zona de memoria sobre un puntero. El primer parámetro es el del puntero sobre el que se va a hacer el realojo; el segundo parámetro recoge el nuevo tamaño que tendrá la zona de memoria reservada. Si el puntero block ya tiene memoria asignada, mediante una función malloc o calloc, o reasignada por otra llamada anterior realloc, entonces la función varía el tamaño de la posición de memoria al nuevo tamaño que indica la variable size. Si el tamaño es menor que el que había, simplemente deja liberada para nuevos usos la memoria de más que antes disponíamos y de la que hemos decidido prescindir. Si el nuevo tamaño es mayor, entonces procura prolongar ese espacio reservado con los bytes siguientes; si eso no es posible, entonces busca en la memoria un espacio libre del tamaño indicado por size, y copia los valores asignados en el tramo de memoria anterior en la nueva dirección. La función devuelve la dirección donde queda ubicada toda la memoria reservada. Es importante recoger esa dirección de memoria que devuelve la función realloc, porque en su ejecución, la función puede cambiar la ubicación del vector. La llamada podría ser así: vector = (float*)realloc(vector, new_dim * sizeof(float)); Si el puntero block tiene el valor nulo, entonces realloc funciona de la misma forma que la función malloc. Si el valor de la variable size es cero, entonces la función realloc libera el puntero block, que queda nulo. En ese caso, el comportamiento de la función realloc es semejante al de la función free que vemos a continuación.
Función free Esta función viene también definida en la biblioteca stdlib.h. Su cometido es liberar la memoria que ha sido reservada mediante la función malloc, o calloc, o realloc. Su sintaxis es la siguiente: void free(void *block); Donde block es un puntero que tiene asignada la dirección de memoria de cualquier bloque de memoria que haya sido reservada previamente mediante una función de memoria dinámica, como por ejemplo la función malloc ya presentada y vista en el epígrafe anterior. La memoria que reserva el compilador ante una declaración de un vector se ubica en la zona de variables de la memoria. La memoria que se reserva mediante la función malloc queda ubicada en otro espacio de memoria distinto, que se llama habitualmente heap. En ningún caso se puede liberar, mediante la función free, memoria que haya sido creada estática, es decir, vectores declarados como tales en el programa y que reservan la memoria en tiempo de ejecución. Es esa memoria del heap la que libera la función free. Si se aplica esa función sobre memoria estática se produce un error en tiempo de compilación.
Ejemplo: la Criba de Erastóthenes Vamos a ver un ejemplo. Supongamos que deseamos hacer un programa que almacene en un vector todos los números primos menores que un millón. Para esa búsqueda utilizaremos el algoritmo de la criba de Erastósthenes. Es un algoritmo que permite encontrar todos los Números Primos menores o iguales a un entero dado. Se comienza generando una tabla con todos los números desde 1 hasta el límite superior (en nuestro caso hemos quedado que un millón). Tomamos el número 1 como primo por definición. A continuación se pasa al siguiente número, que es el 2, que ya desde ese momento se considerará primo, y se procede a marcar en la tabla como enteros compuestos (es decir, no primos) a todos los números posteriores a 2 y múltiplos de 2. A continuación pasamos al siguiente número que no esté marcado como compuesto, que resulta ser el 3, que queda considerado ahora como primo, y procedemos a marcar como compuestos en nuestra tabla todos los números posteriores a él y múltiplos suyos. Ya hemos marcado como compuestos todos los múltiplos de 3. Ahora buscamos el siguiente número no marcado como compuesto. El 4 es múltiplo de 2 y ya ha quedado marcado como compuesto, así que nos lo saltamos y llegamos al 5 que no es múltiplo ni de 2 ni de 3. El 5 queda considerado primo y ahora procedemos a marcar como compuestos todos los múltiplos de 5. El proceso se va repitiendo hasta llegar al último número menor que el límite superior marcado. Todos los números que no hayan sido marcados como compuestos serán primos. En realidad no es necesario realizar la criba hasta llegar al último número menor que el límite superior fijado: basta llegar hasta la raíz cuadrada de ese límite. La razón es que si un número no tiene un divisor menor que su raíz cuadrada, entonces tampoco lo puede tener mayor que su raíz cuadrada y, por tanto, si al llegar a ese limite no se ha encontrado un divisor, entonces ese número es primo con total certeza. Una vez tenemos claro el algoritmo que nos permitirá llegar a crear la tabla de los primos, el siguiente paso será implementar el programa que nos haga este proceso. Vamos a definir para ellos dos funciones más la función principal: #include <stdio.h> #include <math.h> #include <stdlib.h> #define MAX 1000000
long Criba(char*, long); void TablaPrimos(char*, long*, long);
void main(void) { char *num; long *primos; long pr, i;
num = (char*)malloc((MAX + 1) * sizeof(char)); if(num == NULL) { printf("\nNo hay memoria disponible."); printf("\nEl programa va a terminar."); printf("\nPulse cualquier tecla ... "); exit(1); } pr = Criba(num, MAX + 1); // Ya está hecha la criba. Tenemos pr primos. // Creamos ahora el vector que contendrá a los primos. // Reservamos memoria para este vector: primos = (long*)malloc((pr + 1) * sizeof(long)); if(primos == NULL) { printf("\nNo hay memoria disponible."); printf("\nEl programa va a terminar."); printf("\nPulse cualquier tecla ... "); exit(1); } TablaPrimos(num, primos, MAX + 1); free(num);
// Mostramos los primos por pantalla ... printf("Primos menores que %ld... \n\n",MAX); for(i = 0 ; *(primos + i) != 0 ; i++) printf("%10ld", *(primos + i)); free(primos); }
long Criba(char* num, long rango) { long i, j; // En principio marcamos todos los elementos como PRIMOS for(i = 0 ; i < rango; i++) num[i] = 'p'; for(i = 2 ; i < sqrt(rango) ; i++) if(num[i] == 'p') for(j = 2 * i ; j < rango ; j += i) num[j] = 'c'; for( i = 1 , j = 0 ; i < rango ; i++) if(num[i] == 'p') j++; return j; }
void TablaPrimos(char* num, long* primos, long rango) { long i, j; for(i = 1 , j = 0 ; i < rango ; i++) if(num[i] == 'p') { *(primos + j) = i; j++; } *(primos + j) = 0; } Vamos viendo este programa, resuelto mediante funciones. Primero reservamos, en la función main, un espacio de memoria suficiente para albergar tantas variables char (de un bytes cada una) como indica MAX + 1. MAX es la macro que recoge el límite superior sobre el que se van a buscar todos los primos inferiores. A esa memoria, que manejaremos desde un puntero tipo char* que hemos llamado num, le asignamos a todas sus posiciones el valor ‘p’, que vamos a entender que significa “primo”. Y es sobre ese vector sobre quien se hace la criba de Erastóthenes, definida en la función Criba, que devuelve el número de primos que hay en ese rango entre 1 y MAX (la función principal recoge ese valor en la variable pr) y que deja modificada la memoria recogida por el puntero num: una vez ejecutada la función Criba, cada posición valdrá ‘c’ ó ‘p’ según que su índice en el vector sea compuesto o primo: num[i] valdrá ‘p’ si i es primo, y valdrá ‘c’ si i en compuesto. Como ya sabemos cuantos primos hay en nuestro intervalo, ahora creamos un espacio de memoria para almacenar enteros largos: tantos como indica la variable pr (en realidad reservamos uno más que pr, por el motivo que se explica enseguida). Y llamando a la función TablaPrimos se le asigna a cada posición de esa memoria cada uno de los pr primos del intervalo. El último valor (ese espacio en memoria de más que acabamos de reservar) de nuestro vector de primos lo ponemos a cero: así el recorrido de nuestro vector no se rige por un índice, sino por un valor que hace de fin de lista: se podrá recorrer el vector de enteros primos mientras que no se llegue a un valor cero. Así se ha recorrido al final de función principal, cuando se muestra la lista de primos por pantalla. Si en el programa se quiere aumentar el rango de primos bastará modificar la definición de la directiva define. Al final del programa, y antes de terminar su ejecución liberamos la memoria de la tabla de primos. Antes, ya habíamos liberado la memoria recogida por el puntero num. Y eso es algo interesante a destacar de la memoria dinámica: se crea cuando se necesita, y se libera cuando ya no se necesita. Y en ese aspecto, esta memoria tiene un régimen de vida y de ámbito diferente al de las variables creadas por declaración. La variable puede dejar de existir antes de finalizar el bloque en el que ha sido creada; y puede comenzar a existir pasado un tiempo al inicio de la ejecución de su bloque.
Matrices en memoria dinámica Para crear matrices, podemos trabajar de dos maneras diferentes. La primera es crear una estructura similar a la indicada en el cuadro 12.1. Presentamos un código que genera una matriz de tipo float. El programa solicita al usuario las dimensiones de la matriz (el número de filas y el número de columnas). A continuación la aplicación reserva un array de tantos punteros como filas tenga la matriz; y sobre cada uno de esos punteros hace una reserva de tantos elementos float como columnas se deseen en la matriz. Luego, para ver cómo se puede hacer uso de esa matriz creada mediante memoria dinámica, solicitamos al usuario que dé valor a cada elemento de la matriz y, finalmente, mostramos por pantalla todos los elementos de la matriz. Por último, se realiza la liberación de la memoria. Para ello primero habrá que liberar la memoria asignada a cada uno de los vectores creados en memoria dinámica sobre el puntero p, y posteriormente liberar al puntero p del array de punteros. El código es el siguiente: #include <stdlib.h> #include <stdio.h>
void main(void) { float **p; short f, c; short i, j; // Introducir las dimensiones ... printf("Indique filas del vector ... "); scanf("%hd",&f); printf("Indique columnas del vector ... "); scanf("%hd",&c); // Creación de las filas ... p = (float**)malloc(f * sizeof(float*)); if(p == NULL) { printf("Memoria insuficiente.\n"); printf("La ejección se interrumpirá.\n"); printf("Pulse una tecla para terminar ... "); getch(); exit(0); } // Creación de las columnas ... for( i = 0 ; i < f ; i++) { *(p + i) = (float*)malloc(c * sizeof(float)); if(*(p + i) == NULL) { printf("Memoria insuficiente.\n"); printf("La ejección se interrumpirá.\n"); printf("Pulse una tecla para terminar..."); getch(); exit(0); } } // Asignación de valores ... for(i = 0 ; i < f ; i++) for(j = 0 ; j < c ; j++) { printf("matriz[%2hd][%2hd] = ", i, j); scanf("%f",*(p + i) + j); } // Mostrar la matriz por pantalla ... for(i = 0 ; i < f ; i++) { printf("\n"); for(j = 0 ; j < c ; j++) printf("%6.2f\t",*(*(p + i) + j)); } // Liberar la memoria ... for(i = 0 ; i < f ; i++) free(*(p + i)); free(p); } Desde luego, hemos trabajado con operatoria de punteros. Ya se explicó que hablar de *(*(p + i) + j) es lo mismo que hablar de p[i][j]. Y que hablar de (*(p + i) + j) es hablar de &p[i][j]. Y así se podría haber codificado. Veamos algunas de las líneas del código anterior, recogidas con operatoria de índices: // Asignación de valores ... for(i = 0 ; i < f ; i++) for(j = 0 ; j < c ; j++) { printf("matriz[%2hd][%2hd] = ", i, j); scanf("%f",&p[i][j]); } // Mostrar la matriz por pantalla ... for(i = 0 ; i < f ; i++) { printf("\n"); for(j = 0 ; j < c ; j++) printf("%6.2f\t",p[i][j]); } Una última observación a este código presentado: el puntero p es (debe ser así) puntero a puntero. Y, efectivamente, él apunta a un array de punteros que, a su vez, apuntan a un array de elementos float.
Decíamos que había dos formas de crear una matriz
por asignación dinámica de memoria. La segunda es crear un solo array, de
longitud igual al producto de filas por columnas. Y si la matriz tiene
El código de esta nueva forma de manejar matrices podría ser: #include <stdlib.h> #include <stdio.h> void main(void) { float *p; short f, c; short i, j; // Introducir las dimensiones ... printf("Indique filas del vector ... "); scanf("%hd",&f); printf("Indique columnas del vector ... "); scanf("%hd",&c); // Creación de la matriz ... p = (float*)malloc(f * c * sizeof(float*)); if(p == NULL) { printf("Memoria insuficiente.\n"); printf("La ejección se interrumpirá.\n"); printf("Pulse una tecla para terminar ... "); getch(); exit(0); } // Asignación de valores ... for(i = 0 ; i < f ; i++) for(j = 0 ; j < c ; j++) { printf("matriz[%2hd][%2hd] = ", i, j); scanf("%f",p + (i * c + j)); } // Mostrar la matriz por pantalla ... for(i = 0 ; i < f ; i++) { printf("\n"); for(j = 0 ; j < c ; j++) printf("%6.2f\t",*(p + (i * c + j))); } // Mostrar los datos como vector lineal ... printf("\n\n"); for(i = 0 ; i < f * c ; i++) printf("%6.2f\t",*(p + i)); // Liberar la memoria ... free(p); } Ahora el puntero es un simple puntero a float. Y jugamos con los valores de los índices para avanzar más o menos en el array. Cuando hablamos de *(p + (i * c + j)), donde p es el puntero, i es el contador de filas, j el contador de columnas, y c la variable que indica cuántas columnas hay, estamos recorriendo el array de la siguiente manera: si queremos ir, por ejemplo, a la fila 2 (i = 2) y a la columna 5 (j = 5), y suponiendo que la matriz tiene, por ejemplo, 8 columnas (c = 8) entonces, ese elemento del vector (2, 5) está ubicado en la posición 2 * 8 + 5. es decir, en la posición 21. Con el valor i = 0 tenemos los elementos de la primera fila, situados en el vector desde su posición 0 hasta el su posición c – 1. Con el valor i = 1 tenemos los elementos de la segunda fila, situados en el vector desde su posición c hasta su posición 2 * c – 1. Y en general, la fila i se sitúa en el vector desde la posición i * c hasta la posición (i + 1) * c – 1. De nuevo, podremos trabajar con operatoria de índices: hablar de *(p + (i * c + j)) es lo mismo que hablar del elemento del vector p[i * c + j]. |
|
Otras publicaciones o páginas sobre el lenguaje C: |
|
| Comentarios o preguntas a: pedro.alcover@upct.es |
filas y 
columnas, considerar los