Universidad Simón Bolívar
Departamento de Computación
CI2126 Computación II  

Gabriela Ochoa

Asignación Dinámica de Memoria, Introduccion a las Listas Enlazadas

Permite crear variables y arreglos de manera dinámica. Dinámica quiere decir que el espacio de memoria es asignado durante la ejecucion o corrida del programa.

En ocasiones el tamaño de los objetos no se sabe hasta el momento de la corrida. Por ejemplo, la longitud de una cadena de caracteres que introducira el usuario no se sabe hasta el tiempo de corrida. El tamaño de un arreglo puede depender de un parametro cuyo valor se desconoce previo al momento de ejecución. Ciertas estrcturas de datos como listas enlazadas, pilas y colas utilizan memoria dinámica.

Cómo Asignar y Liberar Memoria

La función malloc  se utiliza para asignar memoria (stdlib.h) . Su prototipo es.

void *malloc(size_t nbytes);

Malloc retorna un apuntador a void. Puede asigarnse a un apuntador a cualquier tipo, haciendo el casting adecuado. Si ocurre una falla, malloc retorna el apuntador null. El valor de retorno de malloc, debe chequearse para evitar errores:

char *cpt;
...
if ((cpt = (char *) malloc(25)) == NULL)
{
    printf("Error on malloc\n");

}
El tipo size_t es equivalente a un entero sin signo (unsigned). El numero de bytes de memoria requeridos depende del número y tamaño de los objetos a almacenar.

Char se almacena en un byte, float en 4 bytes. En la mayoria de las máquinas de 32 bits, int se almacenan en 4 bits. La manera mas fácil de determinar el tamaño de una variable es utilizando el operador sizeof , que devuelve el tamaño en bytes de un objeto. Sizeof puede ser llamado con cualquier tipo de datos como argumento.

#include <stdio.h>

typedef struct employee_st {
    char name[40];
    int id;
} Employee;

int main()
{
    int myInt;
    Employee john;

    printf("Size of int is %d\n",sizeof(myInt));   -- 4
        /* The argument of sizeof is an object */     
    printf("Size of int is %d\n",sizeof(int));        4
        /* The argument of sizeof is a data type */

    printf("Size of Employee is %d\n",sizeof(Employee)); 44
        /* The argument of sizeof is an object */
    printf("Size of john is %d\n",sizeof(john));         44 
        /* The argument of sizeof is a data type */

    printf("Size of char is %d\n",sizeof(char));      1
    printf("Size of short is %d\n",sizeof(short));    2
    printf("Size of int is %d\n",sizeof(float));      4
    printf("Size of int is %d\n",sizeof(double));     8
    
}

Cuando se usa memoria dinámica, es necesario que el programador libere la memoria luego de utilizarla, esto se hace usando la función de librería stándard free:

Void free(void *pt);

Free puede recibir como argumento cualquier tipo de apuntador, no es necesario hacer un casting a void.

Ejercicio: Escribir un programa que asigne dinamicamente un arreglo de tipo Empleados. Pedir al ususrion el numero de empleados que debe crearse. Contrate algunos empleados (llene los campos de nombre y numero de id.)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{

    Employee *workers, *wpt;
    int num;

    printf("How many employees do you want\n");
    scanf("%d",&num);

    workers = (Employee *) malloc(num * sizeof(Employee));
    if (workers == NULL)
    {
        printf("Unable to allocated space for employees\n");
        return 1;
        /* A nonzero return is usually used to indicate an error */
    }

    wpt = workers;

    strcpy(wpt->name,"John");
    wpt->id = 12345;

    wpt++;
    strcpy(wpt->name,"Justin");
    wpt->id = 12346;

    wpt = workers;
    printf("Employee %d is %s\n", wpt->id, wpt->name);
    wpt++;
    printf("Employee %d is %s\n", wpt->id, wpt->name);

    free(workers);
    workers = NULL;

    return 0;
}

Listas Enlazadas

 

Una lista enlazada está formada por una colección de elementos (denominados nodos) tales que cada uno de ellos almacena dos valores: (1) un valor de la lista y (2) un apuntador que indica la posición del nodo que contiene el siguiente valor de la lista.

Un arreglo almacena  todos sus elementos agrupados en un bloque de memoria.  Mientras que en una lista enlazada la memoria se va tomando según se necesita. Se van agregando “nodos”. Cuando queremos añadir un nuevo elemento (“nodo” ) reservamos memoria para él y lo añadimos a la lista. La lista va tomando su estructura usando apuntadores que conectan todos sus nodos como los eslabones de una cadena, o las cuentas de un collar. Cuando queremos eliminar el elemento simplemente lo sacamos de la lista y liberamos la memoria usada.

Ejemplo de una Lista de numeros 1, 2, 3

Lista {1, 2, 3}

 

El comienzo de la lista enlazada es almacenado en el apuntador “head” (cabeza) que apunta al primer nodo. El primer nodo contiene un apuntador al segundo nodo. El segundo contiene un apuntador al tercero, … y así sucesivamente. El último nodo en la lista tiene su campo .next asignado a NULL para indicar el fin de la lista.

 

Se puede acceder cualquier nodo en la lista comenzando por la cabeza (head) y siguiendo los subsiguientes apuntadores .next a. Por tanto, las operaciones hacia el inicio de la lista son mas rapidas mientras las operaciones de acceso hacia el final de la lista tomam mas tiempo a medida que estan mas alejadas del inicio. Costo de acceso mayor que el costo constante de acceso a un arreglo. En este sentido, los arreglos son mucho mas eficientes que las listas.

 

Antes de escribir el codigo que construye la lista descrita arriba, necesitamos dos tipos de datos:

 

• Nodo

Tipo de los nodos que conformaran el cuerpo de la lista. Cada nodo contiene un campo de datos, y un apuntador al siguiente nodo de la lista. Tipo: struct node

 

struct node {

int data;

struct node* next;

};

 

• Apuntador a nodo

Tipo apuntador a nodo. Sera el tipo de la cabeza de la lista y de los campos next de cada nodo. En C no se requiere una declaracion de tipos aparte dado que el tipo apuntador es el nodo seguido de un '*'. Tipo: struct node*

 

Ejemplo de función simple que usa operaciones con apuntadores para construir la lista {1, 2, 3}.

 

/*

Build the list {1, 2, 3} in the heap and store

its head pointer in a local stack variable.

Returns the head pointer to the caller.

*/

struct node* BuildOneTwoThree()

{

struct node* head = NULL;

struct node* second = NULL;

struct node* third = NULL;

 

head = malloc(sizeof(struct node)); // asigna 3 nodes

second = malloc(sizeof(struct node));

third = malloc(sizeof(struct node));

head->data = 1; // setup first node

head->next = second; // note: pointer assignment rule

second->data = 2; // setup second node

second->next = third;

third->data = 3; // setup third link

third->next = NULL;

return head;

}

 


Volver a Pagina del Curso