Asignación Dinámica de Memoria

(Listas enlazadas en Turbo C)

 

Contenido:

 

Definición.

 

¿Cómo definir una lista enlazada en lenguaje C?

 

Función que manejan la asignación dinámica de memoria.

 

Ejercicios.

 

Definición:

 

            Las listas constituyen una estructura flexible en particular, porque pueden crecer y acortarse según lo requiera; los elementos son accesibles y pueden insertar y suprimir en cualquier posición de la lista.

         Las listas enlazadas a diferencia de los vectores (arrays o arreglos), su tamaño se define en tiempo de ejecución.

 

         A continuación les presento un cuadro con las diferencias más destacadas entre listas enlazadas y vectores:

 

Vectores

Listas enlazadas

·        En un tipo de almacenamiento estático.

 

·        El tamaño se determina en tiempo de compilación.

 

·        El almacenamiento es contiguo.

·        Es un tipo de almacenamiento dinámico.

 

·        El tamaño se determina en tiempo de ejecución.

 

 

Una lista enlazada gráficamente se representa de la siguiente manera:

 

 

 

 


     

 

 

 

 

Cada cuadro que está dividido en dos se lo denomina nodo. Los datos en un nodo se guarda de la siguiente manera:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


NOTA: una lista enlazada está compuesta por nodos, y estos nodos a su vez de dos áreas:

·        Área de datos: En esta área se guarda los datos que se desee almacenar, esta área puede tener más de un campo.

·        Un área donde guarda la dirección al siguiente elemento, por lo general es un puntero de estructura.

 

¿Cómo definir una lista enlazada en el lenguaje C?

 

Para definir una lista enlazada en lenguaje C se utiliza la palabra clave struct. Esta palabra clave tiene otras utilidades, quiero decir, que aparte de crear listas enlazadas, también se crea lo que se llama tipos de datos definidos por el usuario. (Supuestamente ya el manejo de estructura lo doy por sabido).

 

Para crear un nodo generalmente se utiliza el siguiente código:

 

Struct nodo_lista {

  int n                     // guarda un número entero.

  struct nodo_lista *sig;  //  Guarda la dirección del siguiente nodo

  };

 

A partir de aquí vamos a crear una lista enlazada para números entero. Ya tenemos la estructura que vamos a usar.

 

Si vemos el razonamiento de esta estructura, vemos que tiene dos campos, una campo donde guarda los datos y otro donde guarda la dirección del siguiente elemento.

Como ves, “*sig” es un puntero a estructura, una lista enlazada se maneja con punteros (ya doy por sabido el manejo de punteros).

 

FUNCIONES QUE MANEJAN LA ASIGNACIÓN DINÁMICA DE MEMORIA.

 

En Turbo C, existen dos funciones que manejan las listas enlazadas, se denominan malloc() y free(). Estas dos funciones se encuentran en el archivo de cabecera STDLIB.H que se lo llama mediante un #include<stdlib.h> al comienzo de un programa.

Malloc(): Esta función lo que hace es asignar memoria, es decir, piede memoria cuando la necesita. Esta función devuelve un puntero que contiene la dirección de la nueva porción de memoria asignada.

 

Por ejemplo malloc en una lista enlazada se utiliza de la siguiente manera:

 

         Supongamos que pido memoria al sistema, y la dirección de esa porción de memoria la guardo en un puntero llamado ‘p’, el uso sería de la siguiente manera:

 

struct nodo_lista *p;

 

p=(struct nodo_lista *)malloc(sizeof(struct nodo_lista);

 

Como verás utilice una palabra reservada llamada “sizeof”, para que tengas una idea, esto quiere decir tamaño de. Sizeof devuelve un tamaño en bytes, en este caso está devolviendo el tamaño de bytes de la estructura.

En este cado, ‘p’ tiene la dirección del nuevo nodo. La función malloc se utiliza generalmente en la función insertar (más adelante desarrollaré el código de esta función), porque cada vez que quiero agregar un dato, tengo que pedir memoria.

 

La función free() es lo contrario de malloc(), esta función devuelve memoria al sistema. Es necesario cuando se termina de usar la porción de memoria, hay que devolversela al sistema. Esta función se utiliza generalmente para borrar datos de una lista.

 

Podría no devolver la memoria al sistema cuando la termino de usar, pero pensá que cuando elimino un dato, esa porción de memoria queda inaccesible, por lo que sería un desperdicio tener una porción de memoria que no se pueda utilizar.

 

Basta ya de palabras y comencemos a armar un pequeño programa donde vamos a guardar una lista de números entero donde no sepamos cuantos número va a contener esta lista. Aquí se incluye el desarrollo de las funciones insertar, eliminar, mostrar y busacar en una lista enlazada.

 

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

 

struct nodo_lista {

  int    n;

  struct nodo_lista *sig;

 };

 

struct nodo_lista *primero=NULL;

 

void insertar(int num) {

 struct nodo_lista *p, *q;

 p=(struct nodo_lista *)malloc(sizeof(struct nodo_lista));

 p->n=num;

 p->sig=NULL;

 if(primero == NULL)

    primero=p;

 else {

    q=primero;

    while(q->sig != NULL)

         q=q->sig;

    q->sig=p;

    }

}

 

void mostrar() {

 struct nodo_lista *p;

 p=primro;

 while((p != NULL) && (primero != NULL))

    {

     printf(“%d”, p->n);

     p=p->sig;

    }

}

 

struct nodo_lista *buscar(int num) {

 struct nodo_lista *p, *q;

 p=primero;

 while((p != NULL) && (primero != NULL))

    {

     if(num == p->n)

         q=p->sig;

     else printf(“Número no encontrado”);

     p=p->sig;

}

 if(p->sig == NULL) && (p->n == num)

    q=p->sig;

 return q;

}

 

void eliminar(int pos) {

 struct nodo_lista *p, *q;

 int c;

 if(pos == 1)

    {

     q=primero;

     primero=primero->sig;

     free(primero);

    }

else {

     c=1;

     q=NULL;

     p=primero;

     while((q->sig != NULL) && (c < pos))

         {

          q=p;

          p=p->sig;

          c++;

         }

 if(c == pos)

    {

     q->sig = p->sig;

     free(p);

    }

}

 

 

void main() {

 int n;

 

 scanf(“%d”, &n);

 while(n != 0)

    {

     insrtar(n);

     scanf(“%d”, &n);

    }

 

 clrscr();

 mostrar();

 scanf(“%d”, &n);

 eliminar(n);

 clrscr();

 mostrar();

}

 

 

Como verás, al principio del programa, declaré la estructura para la lista y puse un puntero llamado ‘primero’ en nulo (NULL). En lenguaje C la palabre NULL en este caso indica el fin de la lista. Puse primero en NULL, porque se supone que al principio la lista no existe. El último nodo de la lista, el campo siguiente vale NULL.

La palabra NULL en lenguaje C tiene varias utilidades, pero no voy a entrar en detalles.

En la función insertar usé dos punteros ‘p’ y ‘q’, el puntero ‘p’ lo que hace es guardar la dirección del nuevo nodo, mientras que ‘q’ me permite recorrer la lista. En algún momento puse ‘q->sig=p”, en esta linea me permite enlazar el nuevo nodo a la lista.

 

 

 

EJERCICIOS:

 

Confeccionar un programa que permita generar una lista de empleados con los siguientes datos:

 

-         Identificación de empleado (entero de 1 a n)

-         Apellido y nombre(string[30])

-         Saldo por mes.

 

Este programa debe estar escrito por las siguiente funciones:

 

a)      Una función insertar, para ingresar los empleados.

b)      Una función buscar, que busque por identificación de empleado, e imprima por pantalla el Apellido y nombre y el sueldo que gana.

 

Le recomiendo que lo arme directamente en la computadora. Aunque si le sirve para guiarse se puede utilizar un diagrama de flujo y luego codificarlo. Suerte.

 

Yo creo que con esto ya les doy una base de lo que es asignación dinámica de memoria. Cualquier pregunta que tengan, en esta página hay una sección de preguntas y respuestas, podés dejar tu pregunta allí.

 

 

 

 

 

 

 

 

 

 

 

Autor: Leonardo Diego Zulli

Estudiante de Tecnico en programación.

[email protected]

 

 

Bibliografía:

Para poder expresar una definición lo más posible clara he consultado un libro:

ESTRUCTURA DE DATOS Y ALGORITMOS de ALFRED V. AHO, JHON E. HOPCROFT y JEFFREY D. ULLMAN

 

El Resto del Apunte, he aportado el conocimiento que logré conseguir hasta ahora sobre el tema.

Programa de ejemplo comprimido en un zip, trabajado en Turbo C.