Tema 32 – Lenguaje c: manipulación de estructuras de datos dinámicas y estáticas.

Veremos las posibilidades que nos brinda el lenguaje C para implementar estructuras estáticas y dinámicas.

Estos puntos le otorgan potencia y flexibilidad que lo hacen especialmente indicado para la implementación de estructuras de este tipo, que son imprescindibles para el desarrollo de sistemas operativos, programas de gráficos, compiladores…

2. ESTRUCTURAS ESTÁTICAS

C cuenta con un número limitado de tipos de datos elementales.

Una estructura es estática si los elementos que constituyen dicha estructura son fijos durante la ejecución del programa

2.1 Arrays

Tipo de dato compuesto por un conjunto de elementos del mismo tipo a los que podemos acceder empleando para ello uno o más índices. Pueden tener una o más dimensiones.

2.1.1 Arrays unidimensionales

Es unidimensional si accedemos a sus elementos con un solo índice.

Podemos definir un array unidimensional indicando el tipo, nombre del array y número de elementos.

Ejemplo: int números [3];

Para acceder a los elementos de un array empleamos un índice entero de manera que el primer elemento del array tiene índice o.

Números [0];

Números [1];…

Para recorrer un array normalmente se usa un bucle for, de manera que utilizamos el contador del bucle para acceder a los elementos.

Para introducir valores en un array unidimensional:

#include <stdio.h>

#include <stdlib.h>

Void main () {

Int num[10],i;

For (i=0; i<10; i++)

Num[i]=rand ();

}

2.1.2 Arrays multidimensionales

Podemos definir un array multidimensional indicando el tipo, nombre del array y número de elementos de cada dimensión.

Tipo nombre [dim1][dim2]…[dimn]

Ejemplo: int notas [20][3]

Para acceder a los elementos de un array, empleamos tantos índices enteros como dimensiones tenga. En el caso del array definido antes, accedemos a los elementos de la siguiente forma:

Notas [0][0];

Notas [0] [1];

….

Para acceder a los elementos de un array multidimensional, usaremos bucles anidados.

Ejemplo:

#include <stdio.h>

#include <stdlib.h>

Void main() {

Int notas [10] [3], i,j;

For (i=0; i<10; i++)

For (j=0; j<3; j++)

Notas [i][j]=rand ();

}

2.1.2.1 Inicialización de arrays

Tenemos la posibilidad de inicializar un array durante su declaración, indicando los valores de sus elementos individuales.

Ejemplo: int cuadrados [5][2] = {{1,1},

{2,4},

{3,9},

{4,16},

{5,25}};

2.2 Cadenas

Las cadenas son un tipo particular de arrays en los que sus elementos son de tipo carácter (char), y se definen como cualquier otro array.

Ejemplo: char nombre [20];

Tenemos 2 maneras de inicializar las cadenas:

2.2.1 Lectura de cadenas por teclado

Para la lectura de cadenas empleamos la función “scanf” o la función “gets”

Ejemplo:

Char nombre [20], apellidos [20];

Scanf(“%s”, nombre);

Gets(apellidos);

2.2.2 Escritura de cadenas por pantalla

Tenemos 2 opciones (printf y puts)

Ejemplo:

Char nombre [20]=”Pepe”;

Char apellidos [20]=”García”;

Printf(“%s”, nombre);

Puts(apellidos);

2.2.3 Funciones de cadena

El lenguaje C cuenta con un conjunto de funciones específicas para cadenas que se encuentran definidas en el archivo de cabecera “string.h”. Vamos a exponerlas:

2.2.3.1 Función strcpy

Copia una cadena de origen en otra cadena, de modo que pasamos ambas cadenas en la llamada a la función:

Char *strcpy (char *CadDestino, const char *CadOrigen);

2.2.3.2 Función strcat

Añade el contenido de una cadena origen a una cadena destino, efectúa una concatenación.

Char *strcat (char *CadDestino, const char *CadOrigen);

2.2.3.3 Función strcmp

Efectúa una comparación de cadenas, de manera que el resultado nos indica si ambas cadenas son iguales o no.

Char *strcmp (char *cadena1, const char *cadena2);

2.3 Estructuras

Nos permite definir variables compuestas de una serie de elementos de diferente tipo, a diferencia de los arrays.

2.3.1 Definición

Para definir una estructura empleamos la palabra reservada “struct”

Struct nombre_estructura

{

Tipo1 var1;

Tipo2 var2;

…

Tipon varn;

};

Con esto no hemos declarado ninguna variable. Para definir una variable en el tipo, especificamos la estructura que tendrá dicha variable.

· Para declarar una variable:

Struct ficha agenda; à ejemplo

· Para declarar una variable junto con la estructura:

Struct ficha {

Char nombre[10];

Char apellidos[20];

Int edad;

} agenda;

————————————–à de este modo declaramos la estructura y la variable llamada agenda.

· Para definir un tipo nuevo mediante “typedef”.

Struct ficha {

Char nombre[10];

Char apellidos[20];

Int edad;

}

Typedef struct ficha FICHA

Ficha agenda;

2.3.2 Acceso a los campos

Para acceder a los elementos de la estructura, especificamos el nombre de la variable seguida de un punto (.) y el nombre del campo.

Por ejemplo:

Agenda.nombre

Agenda.apellidos

2.4 Arrays de estructura

Podemos combinar estos dos tipos de datos, de manera que definamos arrays cuyos elementos son, a su vez, estructuras.

Podemos definir una agenda de N elementos, de manera que cada elemento contenga datos de una persona.

Struct estruc_ficha

{

Char nombre[10];

Char apellidos[20];

Int edad;

Typedef estruct_ficha FICHA

Ficha agenda[20];

2.5 Unión

La sintaxis es similar a la de una estructura, pero en este caso, el compilador reserva memoria sólo para el elemento de mayor tamaño, de manera que todos los elementos hacen referencia a una misma posición de memoria.

Ejemplo:

Unión ejemplo {

Int I;

Long l;

} x;

El acceso a los datos se hace de igual forma que en una estructura.

3. ESTRUCTURAS DINÁMICAS

A diferencia de las estructuras estáticas, las dinámicas pueden crecer durante la ejecución del programa, de modo que emplearemos más memoria cuando sea necesario y menos cuando deje de serlo.

3.1 Punteros

Es una variable que contiene una dirección de memoria. Podemos consultar el contenido de un puntero, asignarle una dirección de memoria, e incluso incrementar o decrementar la dirección que contiene dicho puntero.

3.1.1 Declaración de punteros

Usamos el operador *

Ejemplo: int *p;

3.1.2 Asignación de direcciones

Usamos el operador & para averiguar la dirección de una variable.

Ejemplo:

Int *p,i=0;

P=&i;

3.1.3 Incremento y decremento

Usamos los operadores de incremento o decremento para acceder a las direcciones anterior y siguiente:

Ejemplo:

Int *p,i[2]={0,1};

P=&i;

P++;

3.1.4 Asignación de punteros

Podemos asignarle la dirección de un puntero a otro puntero.

Ejemplo:

Int *p, *q,i=0;

P= &i;

Q=p;

3.2 Punteros versus arrays

Los arrays son punteros y podemos asignar a un puntero la dirección de un elemento de dicho array, y acceder al resto de elementos incrementando o decrementando dicho puntero.

Ejemplo:

Int a[N], *p;

/* Usando arrays */

For (i=0;i<N;i++)

a[i]=o;

/* Usando punteros */

p=&a[0];

For (i=0;i<N;i++)

*(p+i)=0;

3.3 Asignación dinámica

Cuando definimos un puntero, el compilador no reserva memoria para dicha variable, así que, si queremos acceder a su contenido, provocaremos un error. Por tanto, para acceder al contenido de un puntero, tendremos que asignarle memoria. Utilizamos la función malloc:

Void *malloc (unsigned int tamaño);

Int *p;

P=(int*)malloc(sizeof(int));

3.4 Liberación

Una vez utilizada una zona de memoria, si no la necesitamos, debemos liberarla. Para ello, usamos la función free:

Void free(void *p);

Ejemplo:

#include <stdio.h>

Void main() {

Int *p;

P=(int *)malloc (sizeof(int));

If (p!= NULL)

{

*p= rand();

Printf(%d,*p);

Free(p);

}

3.5 Listas

Es una estructura dinámica formada por un conjunto de elementos, denominados nodos, que deben ser recorridos secuencial y que, al ser una estructura dinámica, el número de elementos que la integran puede variar durante la ejecución del programa.

3.5.1 Declaración

Para declarar una lista debemos definir la estructura de los nodos y declarar un puntero a dicha estructura.

Ejemplo:

Typedef struct nodo

{

Int num;

Struct nodo *ps

}

NODO

NODO *lista;

3.5.2 Insertar

Debemos actualizar los punteros, de manera que el elemento anterior apunte al nuevo nodo y el elemento insertado apunte al siguiente nodo.

3.5.3 Borrar

Debemos localizar el nodo a borrar y el que le precede (nodo anterior), de manera que enlazaremos el anterior con el siguiente y, por último, liberamos el nodo a borrar.

3.5.4 Recorrer

Las listas deben ser recorridas de modo secuencial, empezando por el primer nodo.

Ejemplo:

Void recorre(NODO *pl)

{

While(pl != NULL)

{

Printf(“%d”,pl->num);

Pl=pl->ps;

}

3.6 Tipos de listas

Las listas pueden ser clasificadas según los enlaces entre nodos, de manera que disponemos de las siguientes cuatro combinaciones:

3.6.1 Lista simple

Cada nodo está enlazado con el nodo siguiente:

3.6.2 Lista doblemente enlazada

Los nodos están doblemente enlazados. Se vinculan con el nodo anterior y con el nodo siguiente.

3.6.3 Lista simple circular

3.6.4 Lista circular doblemente enlazada

Lista doblemente enlazada donde mantenemos enlazados el primer nodo y el último.

3.7 Árbol binario

Estructura compuesta por nodos que apuntan a dos o más nodos, de modo que todo nodo tiene un nodo padre y, a su vez, puede tener nodos hijos. El primer nodo no tiene padre y es el ascendente de los nodos restantes, así que podemos acceder a cualquier nodo del árbol partiendo de su nodo raíz.

Un árbol binario es un tipo particular de árbol en el que los nodos tienen como máximo dos nodos hijos.

3.7.1 Declaración

Debemos definir la estructura de los nodos.

Ejemplo:

Typedef struct nodo

{

Int num;

Struct nodo *pi;

Struct nodo *pd;

} NODO;

3.7.2 Insertar

Para insertar un nodo en un árbol, debemos recorrerlo hasta localizar el lugar que les corresponde. Colocaremos en la rama izquierda, los nodos anteriores y, en la rama derecha, los nodos posteriores.

Si tenemos un nodo cuyo contenido es el valor numérico 2, y pretendemos insertar un nodo hijo cuyo valor es 1 debemos insertarlo en el subárbol de la izquierda.

3.7.3 Recorrido de árboles binarios

El recorrido de árboles se puede efectuar de 3 maneras, dependiendo del orden.

3.7.3.1 Preorden

Primero el nodo padre, luego el subárbol izq y por último el subárbol dch.

3.7.3.2 Inorden

Primero el subárbol izq, luego el padre, y por último el subárbol dch.

3.7.3.3 Postorden

Primero subárbol izq, luego el subárbol dch, y por último el nodo padre.

3.8 Pilas

La entrada y salida de los datos se lleva a cabo por uno de los extremos.

Es una estructura LIFO (Last in first out). El último elemento en entrar es el primero en salir.

Una lista se puede implementar utilizando arrays, o lista enlazada. Debemos definir todos los nodos y funciones que permitan introducir un nuevo elemento y extraer un elemento de la pila.