Estructuras de datos en C y manejo de memoria I

junio 30, 2008

Nota: Este texto supone que se sabe que es una estructura de datos recursivas (nodos de listas, colas, pilas, árboles, etc.) y como se la programa en C e intenta darle una vuelta de rosca a ese conocimiento.

El lenguaje C es uno de los lenguajes de más bajo nivel (relativo) que existe. En este lenguaje la memoria se estructura de manera plana, que es en definitiva lo que es la memoria, un espacio plano de almacenamiento temporal.

Así entonces un nodo de estructura dinámica como el siguiente:

struct empleado{
int idEmpleado;
char* nombre;
char codigoPostal[6];
int idDepto;
struct empleado* sgte;
}

No es una estructura dimensional, sino un manojo de bytes ordenados:

(
Suponiendo arquitectura intel x86 32bits
int = >4 bytes
Dirección de memoria => 4bytes
char x 6 => 6 bytes
)

id nombre Codigo depto siguiente
[][][][] [][][][] [][][][][][] [][][][] [][][][]

Los cuales son interpretados cada uno como entero, puntero a caracter, entero, entero, entero.
En otras palabras, puede ser claramente un vector de bytes, donde a cada subconjunto de bytes se los interpreta como un tipo de datos nativo según la información de la definición de la estructura.

Bien, ahora supongamos que tenemos esta otra estructura bastante distinta:

struct empresa{
char* idEmpresa;
char* razonSocial;
long int cuit;
char* direccion;
char codigoPostal[6];
struct empresa* sgte;
};

Cuando hacemos funciones de acceso a cola (por ejemplo) siempre tenemos la maldita sensación de estar haciendo las mismas cosas miles de veces, puesto que si bien no es lo mismo un empleado y una empresa,
¡¡Las colas son todas iguales!!
¡¡El mecanismo si es el mismo, agrego al final, saco del principio!!

¿Cómo hacer para separar el “¿Qué?” del “¿Cómo?”?

Con el conocimiento que tenemos ahora de la memoria y la estructuración en memoria de las estructuras, existe al menos una forma de hacerlo.

¿Qué tienen en común todos los nodos de una estructura de datos dinámica / recursiva?
Rta.: El puntero al siguiente nodo.

¿Qué tienen en común todos los punteros en una misma arquitectura hardware / sistema operativo?
Rta.: El puntero es un tipo de datos, no importa lo que apunte, siempre pesa lo mismo.

Si planteamos la siguiente estructura:

Struct Nodo {
Struct Nodo* sgte;
};

Tenemos una estructura que el primer valor es un puntero un siguiente nodo, no tenemos variable “contenedor”, y no la necesitamos, puesto que ahora no nos importa el contenido de información, sino el puntero siguiente.

Un programa hecho en C, interpreta los datos según el tipo del mismo en el instante de ejecución dado.

Si yo modificase las estructuras anteriores y pusiese el elemento siguiente primero en la lista, quedaría esto:

struct empleado{
struct empleado* sgte;
int idEmpleado;
char* nombre;
char codigoPostal[6];
int idDepto;
}

struct empresa{
struct empresa* sgte;
char* idEmpresa;
char* razonSocial;
long int cuit;
char* direccion;
char codigoPostal[6];
};

Ahora, la última pregunta a hacernos es:
¿Qué tienen en común nuestras tres estructuras?
Rta.: Las tres empiezan con un puntero conceptualmente igual, el puntero al siguiente elemento.

Como se dan todas estas relaciones, entonces, gracias a la existencia del “casteo”, que hace que el programa interprete un dato como otro, sin afectarlo en el proceso, entonces, podemos definir todas las funciones para manejo de Colas para la estructura mas chica.

#define null NULL
#include
#include

typedef struct Nodo {
struct Nodo* sgte;
}Nodo;

typedef struct Cola {
Nodo* head;
Nodo* tail;
}Cola;

typedef struct Empleado{
struct Empleado* sgte;
int idEmpleado;
char* nombre;
char codigoPostal[6];
int idDepto;
} Empleado;

void inicializarCola (Cola* unaCola) {
unaCola->head = null;
unaCola->tail = null;
}

void agregarNodo (Cola* unaCola, Nodo* unNodo){
unNodo->sgte = null;

if ( unaCola->tail != null) {
unaCola->tail->sgte = unNodo;
}
unaCola->tail = unNodo;

if (unaCola->head == null) {
unaCola->head = unNodo;
}

}

Nodo* obtenerNodo (Cola* unaCola) {
Nodo* retorno;
retorno = unaCola->head;
if ( unaCola->head != null ) {
unaCola->head = unaCola->head->sgte;
}
return retorno;
}

int main (void) {

Cola unaCola;
Empleado* unEmpleado;
int i;
inicializarCola(&unaCola);

for (i = 0; i codigoPostal), ”, 6);
unEmpleado->idDepto = i;
unEmpleado->idEmpleado = i * 2;
unEmpleado->nombre = null;
agregarNodo(&unaCola, (Nodo*)unEmpleado);

}

while ((unEmpleado = (Empleado*) obtenerNodo(&unaCola)) != null) {
printf (” Id Empleado: %d \tId Depto: %d \n”, unEmpleado->idEmpleado, unEmpleado->idDepto);
}

return 0;
}

/*
Nota: Ejemplo probado con GCC y MinGW. No incluye el manejo de cadenas y la creación de empleados por una función dedicada por cuestiones de tiempo.
*/

Y con esto, tenemos el algoritmo de inserción y obtención de colas para cualquier nodo que tenga como primer dato de estructura el puntero al siguiente valor.

Como se puede ver a simple vista, esto de poder usar la misma función para distintos tipos de datos en los parámetros tiene cierto potencial.
Esta posibilidad de, por medio de casteo a estructuras menores de igual forma es una forma de emular el llamado Polimorfismo paramétrico (que no es el polimorfismo de objetos, sino, el de funcional)

About these ads

One Response to “Estructuras de datos en C y manejo de memoria I”


  1. [...] Artituculo original Categories: programacion Tags: c, estructuras de datos, lenguaje c, manejo de memoria Comments (0) Trackbacks (0) Leave a comment Trackback [...]


Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

%d personas les gusta esto: