Análisis y Diseño de Algoritmos                                                                                                      

Prof: Ing. Victor Garro

Asistente: Marco Elizondo Vargas

 

Punteros

 

Gestión dinámica de la memoria

 

 

Organización de la memoria

‐ Segmento de código (código del programa).

‐ Memoria estática (variables globales y estáticas).

‐ Pila (stack): Variables automáticas (locales).

‐ Heap (“montón”): Variables dinámicas.

 

 

Reserva y liberación de memoria

 

Cuando se quiere utilizar el heap, primero hay que reservar la memoria que se

desea ocupar:

 

ANSI C: Función malloc

C++: Operador new

 

Al reservar memoria, puede que no quede espacio libre suficiente, por lo que

hemos de comprobar que no se haya producido un fallo de memoria (esto es, ver

si la dirección de memoria devuelta es distinta de NULL).

Tras utilizar la memoria reservada dinámicamente, hay que liberar el espacio

reservado:

 

ANSI C: Función free

C++: Operadore delete

 

Si se nos olvida liberar la memoria, ese espacio de memoria nunca lo podremos

volver a utilizar…

 

Ejemplo: Vector de tamaño dinámico

 

#include <stdio.h>

#include <stdlib.h>

float media (float v[], int n)

{

int i;

float suma = 0;

for (i=0; i<n; i++)

suma += v[i];

return suma/n;

}

int main(int argc, char *argv[])

{

int i;

int n;

float *v;

printf("Número de elementos del vector: ");

scanf("%d",&n);

// Creación del vector

v = malloc(n*sizeof(float));

// Manejo del vector

for (i=0; i<n; i++)

v[i] = i;

printf("Media = %f\n", media(v,n));

// Liberación de memoria

free(v);

return 0;

}

 

 

Ejemplo: TDA Vector Dinámico

 

Tipo de los elementos del vector dinámico

 

typedef int Dato;

 

Estructura de datos del vector

 

typedef struct Vector {

Dato *datos; // Vector de datos

int usado; // Elementos usados del vector

int capacidad; // Capacidad del vector

};

typedef struct Vector *Vector;

 

Creación del vector (constructor)

 

Vector crearVector (void)

{

Vector v =(Vector) malloc ( sizeof(struct Vector) );

v->usado = 0;

v->capacidad = 2;

v->datos = malloc ( (v->capacidad)*sizeof(Dato) );

return vector;

}

 

Destrucción del vector (destructor)

 

void destruirVector (Vector *v)

{

free ( (*v)->datos );

free ( *v );

*v = NULL;

}

 

Constructor y destructor nos permiten manejar vectores sin

tener que conocer su estructura de datos interna (ni siquiera

tendremos que utilizar malloc y free).

Acceso al contenido del vector

 

Funciones que permiten ocultar los detalles de implementación del TDA

Número de elementos del vector:

int elementosVector (Vector v)

{

return v->usado;

}

 

Acceso a los elementos concretos del vector:

Obtención del valor almacenado en una posición del vector:

 

Dato obtenerDato (Vector v, int pos)

{

if ((pos>=0) && (pos<elementosVector(v)))

return v->datos[pos];

else

return NULL;

}

 

Modificación del valor almacenado en una posición del vector:

 

void guardarDato (Vector v, int pos, Dato dato)

{

if ((pos>=0) && (pos<elementosVector(v))) {

v->datos[pos] = dato;

}

}

 

 

Inserción de datos

 

void agregarDato (Vector v, Dato dato)

{

int i;

Dato *datos;

if (v->usado == v->capacidad) {

// Redimensionar el vector

v->capacidad *= 2;

datos = malloc ( (v->capacidad)*sizeof(Dato) );

for (i=0; i < v->usado; i++)

datos[i] = v->datos[i];

free(v->datos);

v->datos = datos;

}

v->datos[v->usado] = dato;

v->usado ++;

}

 

Eliminación de datos

void eliminarDato (Vector v, int pos)

{

int i;

if ((pos>=0) && (pos<elementosVector(v))) {

for (i=pos; i<elementosVector(v)-1; i++)

v->datos[i] = v->datos[i+1];

v->usado --;

}

}

 

¡OJO! En la implementación mostrada no contemplamos la

posibilidad de que la función malloc devuelva NULL

(algo que siempre deberemos hacer al programar).

 

Ejemplo de uso del TDA Vector Dinámico

 

#include <stdio.h>

#include “vector.h”

/* Rutina auxiliar */

void mostrarVector (Vector v)

{

int i;

printf( "Vector de tamaño %d:\n",

elementosVector(v) );

for (i=0; i<elementosVector(v); i++)

printf("- %d\n", obtenerDato(v,i));

}

/* Programa principal */

int main ()

{

Vector v = crearVector();

mostrarVector (v);

agregarDato (v,1);

agregarDato (v,2);

agregarDato (v,3);

mostrarVector (v);

eliminarDato (v,1);

mostrarVector (v);

guardarDato (v, 0, obtenerDato(v,0)+2);

mostrarVector (v);

destruirVector(&v);

return 0;

}