Transcript
Cristian Blanco www.cristianblanco.es Vectores y matrices ; Pagina :1 de 11
TEMA 3(b).-Estructuras de datos VECTORES , MATRICES y ESTRUCTURAS Los vectores son datos del mismo tipo agrupados bajo un mismo nombre y accesibles o referenciados de forma individual mediante un índice, que es un número entero que va de cero en adelante El mayor valor que puede tomar el índice se denomina dimensión del vector La definición de vectores en C se realiza del sgte. modo: Tipo de dato nombre[dimensión]; Así si queremos definir un vector de 100 enteros pondremos: int v[100]; donde los elementos se almacenan en v[0]…v[99]; La dimensión suele ponerse antes del main() con las declaraciones: #define dim 100 ó también const int dim=100; si queremos tamaño 100. De este modo los programas son fácilmente parametrizables pues cambiando el valor de dim trabajamos con nueva dimensión a lo largo de todo el programa. Así se definen los vectores estáticos que reservan memoria en tiempo de compilación Los datos son reservados en posiciones de memoria contiguas, al igual que las cadenas. De hecho estas últimas son un caso particular de vectores. No existen funciones de librería estándar para manejar los vectores en bloque, salvo bsearch y qsort, que se verán si son necesarias. La lectura de datos se realiza uno a uno en bucles tipo for….. Al igual que en caracteres el nombre de un vector es un puntero a la dirección de memoria donde empieza dicho vector, es decir, es lo mismo v que &v[0]. De todos modos es mejor manejar los vectores con sus índices que con sus punteros a memoria, siempre que esto pueda hacerse.. Debido a la relación entre nombres de vectores y punteros la declaración de parámetros en funciones cuando éstos son vectores puede realizarse de dos formas: a) void funcion(int v[]……) b) void funcion(int *v…….) Los vectores son siempre parámetros por referencia, cosa que el compilador realiza para mayor eficiencia en el paso de parámetros. Lo que se pasa es la dirección del primer elemento, es cuestión del programador no salirse de la dimensión, para no provocar un “machacamiento” de la memoria, al igual que ocurre en caracteres. Es preferible la primera forma a), pues se indica con los corchetes que se pasa un vector.
Cristian Blanco www.cristianblanco.es Vectores y matrices ; Pagina :2 de 11
Es muy útil cuando realizamos programas con vectores numéricos el utilizar la función random() para llenarlos de valores y evitarnos así la penosa tarea de introducir un conjunto grande de datos, sobre todo cuando queremos manejar grandes vectores. Ejemplo: // esta secuencia de programa genera un vector de 500 enteros, con números entre 1 y 100 for(t=0;t<500;t++) v[t]=random(100)+1; Los vectores pueden ser inicializados de forma explícita enumerando sus datos, esto es : int x[5]={1,2,3,4,5}; Si en la lista de valores existen menos datos de los que marca la dimensión el resto son inicializados a cero.
MATRICES Una matriz puede considerarse como el apilamiento o agrupamiento de vectores, por tanto cada elemento individual debe ser referenciado con dos índices uno de fila y otro de columna. Puede representarse gráficamente como una tabla donde el índice que varía en vertical es el de fila y el horizontal el de columna.
Fila 1 Fila 2 Fila 3
Columna 1 Dato Dato Dato
Columna 2 dato dato dato
Columna 3 dato dato dato
El esquema anterior representa una matriz de 3 filas por 3 columnas. El estándar ANSI C permite generalizar matrices de hasta 12 índices Es decir sería valido definir una matriz de 3x5x2 Como se definen en C las matrices: tipo nombre[dimension1][dimension2] Ejemplo: float x[20][30]; define una matriz de 20 filas por 30 columnas. Los elementos van desde el x[0][0]….. x[19][29]; Para la lectura ó asignación de matrices se utilizan con frecuencia bucles encajados ó anidados esto es: int x[20][30]; for(i=0;i<20;i++) for(k=0;k<30;k++) x[i][k]=100; Esta secuencia inicializa la matriz x de 20x30 con todos sus elementos a valor 100; Si se leyeran por teclado esto seria del siguiente modo:
Cristian Blanco www.cristianblanco.es Vectores y matrices ; Pagina :3 de 11
int x[20][30]; for(i=0;i<20;i++) for(k=0;k<30;k++) { printf(“dame datos para el elemento %d / %d”,i,k); scanf(“%d”,&x[i][k]); } El printf es muy recomendable ponerlo para guiar al usuario por donde vamos Lo dicho con anterioridad para variables individuales sobre locales, globales ó estáticas es aplicable igualmente para vectores y matrices. Las matrices son pasadas igualmente por referencia a las funciones cuando son parámetros. Para indicar que se pasan matrices a una función tanto en el prototipo (antes del main), como en la cabecera de su cuerpo se pone función (int a[][5]….) , la segunda dimensión es obligada, por motivos de localización en memoria de los elementos, téngase en cuenta que el acceso a los elementos se realiza mediante la formula direccion_base+num de elementos por fila(segundo índice)*tamaño de cada elemento(según tipo)+columna, siendo necesario pues especificar la segunda dimensión para saber el número de elementos por fila. Un caso particular de matrices son los vectores de caracteres, es decir, por ejemplo char v[20][50], sería un vector de 20 elementos y cada elemento una cadena de 50 caracteres. Una matriz puede también ser inicializada de forma explícita como un vector, pero hay que usar doble llave para separar las filas. Ejemplo: int x[2][2]={{1,2}, {5,7}}, esto produce la siguiente asignación Primera fila x[0][0]=1 x[0][1]=2 Segunda fila x[1][0]=5 x[1][1]=7 Al igual que en vectores, si no existen suficientes valores los restantes de la matriz son puestos a cero.
Cristian Blanco www.cristianblanco.es Vectores y matrices ; Pagina :4 de 11
Estructuras. Una estructura es un tipo agregado de datos de los tipos básicos o de otros datos estructurados que ya conocemos, agrupados bajo un mismo nombre. Una estructura en C la creamos del siguiente modo: struct nombre_estructura { tipo_dato1 nombre1; tipo_dato2 nombre2; tipo_dato3 nombre3; }; Con esto definimos los componentes de la estructura pero no se ha declarado ninguna variable, esto es, sólo con lo anterior el compilador no reserva memoria alguna para estructuras de este tipo, para ello necesitamos hacer además esto: struct nombre_estrcutura variable; // con esto definimos variable como del tipo nombre_estructura. Ejemplo: struct ficha { char desc[30]; long exist; int recargo; }; struct ficha almacen; // con esto definimos una variable almacen que es una estructura. Es decir la primera declaración no crea variables, crea el tipo y sus componentes y la segunda crea las variables en memoria, podríamos hacer también esto: struct ficha almac1,almac2; // creamos dos variables de estructura llamadas almac1 y almac2; ¿Cómo acceder a los miembros de una estructura? Una vez definida la estructura, para operar con un miembro individual de la misma se hace mediante el operador. (punto) En el ejemplo anterior para imprimir el dato recargo haríamos lo siguiente: Printf("%d",almacen.recargo); es decir se accede a una estructura poniendo el nombre de la variable de tipo estructura, punto y el nombre del elemento
Cristian Blanco www.cristianblanco.es Vectores y matrices ; Pagina :5 de 11
Otra forma muy cómoda de definir estructuras es utilizar typedef, esta declaración usada en estructuras crea un "alias " de la estructura de forma que el nombre definido con typedef es un nuevo tipo de datos: Ejemplo: typedef struct { char desc[30]; long exist; int recargo; } tipo_ficha; /* hemos definido un alias de struct ficha llamado tipo_ficha que ahora es como si fuese un tipo int, long,float etc. y este nombre puede ser usado para definir estructuras de este tipo.*/ tipo_ficha var1,var2; //hemos definido dos variables tipo estructura llamadas var1 y var2 ..... .... Tipos que pueden ser definidos dentro de una estructura:
Tipos fundamentales (int,long,char,float etc..) Tipo vector o matriz (incluidas cadenas de caracteres) Punteros. Estructuras. También uniones y funciones, pero el uso de ellas no serán materia de este curso.
Como estructuras dentro de otras, por ejemplo: struct fecha { int dia,mes,anyo; }; struct ficha { char nombre[25]; char apellido[30]; struct fecha fecha_nac; } ( aquí el elemento fecha_nac se crea con referencia a la estructura fecha que debe ser declarado antes) struct ficha persona; // aqui se declara la variable en memoria que será persona si queremos acceder al dato anyo de su fecha de nacimiento pondremos persona.fecha_nac.anyo, es decir la componente fecha_nac y dentro de ella especificamos el año.
Cristian Blanco www.cristianblanco.es Vectores y matrices ; Pagina :6 de 11
Vectores de estructuras. Podemos y nos será muy útil para el caso de aplicar algoritmos de búsqueda y ordenación el crear vectores de estructuras, esto se hace de forma muy sencilla , viendo el siguiente ejemplo: typedef struct { char nombre[20]; char apellido[30]; int edad; }tipo_persona; tipo_persona alumnos[100]; se ha declarado un vector de 100 celdas donde cada una es una estructura, sería legal hacer referencia por tanto a: alumnos[k].edad // seria el dato edad del alumno en posición k+1 del vector. Operaciones con estructuras. Básicamente podemos indicar con una variable de tipo estructura las siguientes operaciones: Inicializarla en el momento de definirla: struct ficha empleado={"Santos Lopez","Francisco",25}; Obviamente pueden ser asignadas desde teclado con scanf y gets o mediante una función random si no queremos teclear datos. Acceder a sus miembros mediante el operador punto(.) poniendo nombre de estructura y nombre del dato componente. Asignar una estructura a otra con el operador de igualdad, esto debe hacerse teniendo cuidado de que ambas sea de la misma configuración de datos o podríamos tener problemas de machacar la memoria. Es decir: // si per1 y per2 son estructuras de tipo tipo_persona se puede hacer per1=per2; // y copiará todos los datos de per2 encima de per1; Paso de estructuras a funciones Si trabajamos con funciones donde los parámetros son estructuras éstas pueden pasarse por valor o referencia, y si queremos pasar por referencia una estructura a una función, por ser parámetro por referencia debemos hacer como siempre la indicación de que se pasa un puntero, por ejemplo:
Cristian Blanco www.cristianblanco.es Vectores y matrices ; Pagina :7 de 11
#include #include #include struct ficha { char nombre[15]; int edad; int codigo; };
void funcion(struct ficha *pficha); main() { struct ficha midato;
int t; printf("dame el nombre:"); flushall(); scanf("%s",midato.nombre); printf("dame la edad:"); scanf("%d",&midato.edad); printf("dame el codigo:"); scanf("%d",&midato.codigo); funcion(&midato); printf("valor modificado: %d",midato.edad); } void funcion(ficha *pficha) { pficha->edad=pficha->edad+1; }
Fijarse que pficha es un puntero a ficha, y cuando luego usamos dentro de la función un dato de pficha lo indicamos poniendo pficha->edad
Cristian Blanco www.cristianblanco.es Vectores y matrices ; Pagina :8 de 11
Creación de tablas dinámicas Es muy común que cuando necesitamos usar un vector o matriz no sepamos las dimensiones, en el momento del diseño del programa, para ello en C tenemos unas funciones que nos permiten reservar memoria para tipos de datos, en particular vectores y matrices, pero en tiempo de ejecución es decir el programa obtiene el tamaño desde el exterior (bien por los usuarios o desde un fichero) y a continuación reserva memoria para los vectores y matrices necesarios. Las dos funciones que vamos a ver son malloc y calloc y ambas están en el fichero de cabecera el cual habrá que referenciar para utilizar dichas funciones, ambas funciones son ANSI C. Función malloc La función malloc reserva memoria dinámicamente del montículo (heap) de memoria disponible por el compilador, tiene un parámetro que es el numero de bytes que se desean reservar y devuelve un puntero al bloque de memoria reservada y para el tipo de datos que se especifique (char, int, float etc. etc) Si no puede reservar la memoria referida por falta de la misma devuelve un puntero NULL. Su uso es el siguiente: int *pa=NULL; // puntero a un entero pa=(int *)malloc(1000*sizeof(int)); // reserva 4000 bytes de memoria , para enteros que comienzan en pa /* fijarse que utilizo el operador sizeof(tipo) que me da la longitud en bytes de un entero cosa que puede variar segun la arquitectura de la máquina*/ pa[2]=25;//asigno la celda 3 con un 25 ........ ....... // podria manejarse desde pa[0]....pa[999] sin problemas pues ha sido reservados // 1000 elementos
El siguiente programa ilustra completamente el uso de malloc /*************** Array dinámico de una dimensión ***************/ /* arrdim01.c */ #include #include main() { int *pa = NULL; unsigned int nbytes = 0, nElementos=0, i = 0; printf("Número de elementos del array: "); scanf("%u", &nElementos); fflush(stdin);
Cristian Blanco www.cristianblanco.es Vectores y matrices ; Pagina :9 de 11
nbytes = nElementos * sizeof(int); if ((pa = (int *)malloc(nbytes)) = = NULL ) { printf("Insuficiente espacio de memoria\n"); exit(-1); } printf("Se han asignado %u bytes de memoria\n", nbytes); // pa es el vector listo para usarse /* Inicializar el array */ for ( i = 0; i < nElementos; i++ ) pa[i] = random(500)+1; /* imprimir el vector generado */ for ( i = 0; i < nElementos; i++ ) printf("%d--",pa[i]);
/* Operaciones */ free(pa); }
Fijarse que al final del programa se usa otra función free (puntero a bloque de memoria reservada) , esta función es la inversa de malloc y libera la memoria reservada para que pueda ser usada por el resto del programa más adelante. El parámetro es el puntero de memoria que se reservó para la tabla. Si la memoria no se libera, al salir al sistema operativo se libera automáticamente por supuesto. Función calloc Esta función se comporta de igual modo que malloc solo que sus parámetros son el número de elementos de la tabla y el tamaño de cada uno con lo que la forma valida de usarla sería: pa=(int*)calloc(1000,sizeof(int)); Es decir reservar memoria para 1000 datos de tamaño un entero, la función devuelve igual que antes un puntero al bloque de memoria asignado o si no un puntero a NULL.
Cristian Blanco www.cristianblanco.es Vectores y matrices ; Pagina :10 de 11
Matrices dinámicas Lo dicho para vectores, puede hacerse también para matrices pero es algo más costoso de escribir. Se trata de hacer un vector de punteros que apunten al comienzo de cada fila, que será también un puntero, aquí pues aparece el concepto de puntero a puntero. El siguiente programa ilustra el uso de matrices dinámicas creadas con malloc: Graficamente seria esto:
ppa
/************** Array dinámico de dos dimensiones **************/ /* arrdim02.c */ #include #include void main() { // se define ppa como puntero a puntero a entero int **ppa = NULL; unsigned int nFilas = 0, nCols = 0; unsigned int f = 0, c = 0;
printf("Número de filas del array: scanf("%u", &nFilas); fflush(stdin);
");
printf("Número de columnas del array: "); scanf("%u", &nCols); fflush(stdin); /* Asignar memoria para el array de punteros */ if ((ppa = (int **)malloc(nFilas * sizeof(int *))) == NULL) { printf("Insuficiente espacio de memoria\n"); exit(-1); }
Cristian Blanco www.cristianblanco.es Vectores y matrices ; Pagina :11 de 11
/* Asignar memoria para cada una de las filas */ for (f = 0; f < nFilas; f++) { if ((ppa[f] = (int *)malloc(nCols * sizeof(int))) == NULL) { printf("Insuficiente espacio de memoria\n"); exit(-1); } } /* Inicializar el array a cero */ for ( f = 0; f < nFilas; f++ ) for ( c = 0; c < nCols; c++ ) ppa[f][c] = 0; /* Operaciones */ for ( f = 0; f < nFilas; f++ ) { for ( c = 0; c < nCols; c++ ) printf("%d ", ppa[f][c]); printf("\n"); } /* Liberar la memoria asignada a cada una de las filas */ for ( f = 0; f < nFilas; f++ ) free(ppa[f]); /* Liberar la memoria asignada al array de punteros */ free(ppa); } Se deben usar vectores y/o matrices dinámicas sólo cuando sea necesario. En aquellos programas donde sepamos el tamaño de las estructuras de datos es más cómodo trabajar con dimensiones fijas marcada por #define o const. Si el tamaño no se sabe o no se da como dato estimado en el problema, entonces sí que habrá que reservar el espacio sobre la marcha.