UC3M

Grado en Ing. Telemática/Sist. Audiovisuales/Sist. de Comunicaciones

Arquitectura de Sistemas

Septiembre 2015 - Enero 2016

Fugas de memoria en C

Actividades previas

Tabla de contenidos

1. Fugas de memoria en C
Lecturas
Plan de trabajo
Evaluación
Autoevaluación automática
2. Árbol de cadenas de texto
Plan de trabajo

1. Fugas de memoria en C

Plan de trabajo

  1. Resuelve los cuatro problemas que se plantean en el segundo documento. Asegúrate de que asistes a la sesión magistral con ellos bien entendidos.

Evaluación

En la siguiente clase se utilizarán estos conceptos para resolver un problema de gestión de memoria, por lo que necesitarás las soluciones para responder correctamente a las preguntas.

Autoevaluación automática

Comprueba con estas preguntas si has entendido este documento

Indique los errores que encuentra en cada trozo de código.

  1. 1
2
3
4
5
6
7
8
9
10
11
12
    		 
    int count_element(int id, struct list *inicio)
{
  int cont=0;
  struct list *aux= (struct list *) malloc (sizeof(struct list));
  aux=inicio;
  while (aux!=NULL)
  {
   cont++;
   aux=aux->next;
  }
  return cont;
}

    • No hay errores.

    • Línea 5: hay una fuga de memoria de 1 elemento de tamaño sizeof(struct list).

    • Línea 8: uso de memoria sin inicializar.

    • Línea 9: hay una fuga de memoria. Se pierde toda la lista.

  2. 1
2
3
4
5
6
7
8
9
10
11
12
    		 
    int count_element(int id, struct list **inicio)
{
  int cont=0;
  struct list *aux;
  aux=*inicio;
  while (*inicio!=NULL)
  {
   cont++;
   *inicio=(*inicio)->next;
  }
  return cont;
}

    • No hay errores.

    • Línea 5: hay una fuga de memoria de 1 elemento de tamaño sizeof(struct list).

    • Línea 8: uso de memoria sin inicializar.

    • Línea 9: hay una fuga de memoria. Se pierde toda la lista.

  3. 1
2
3
4
5
6
7
8
9
10
11
12
    		 
    int count_element(int id, struct list *inicio)
{
  int cont;
  struct list *aux;
  aux=inicio;
  while (aux!=NULL)
  {
   cont++;
   aux=aux->next;
  }
  return cont;
}

    • No hay errores.

    • Línea 5: hay una fuga de memoria de 1 elemento de tamaño sizeof(struct list).

    • Línea 8: uso de memoria sin inicializar.

    • Línea 9: hay una fuga de memoria. Se pierde toda la lista.

  4. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    		 
    struct list *del_element(int id, struct list *inicio)
{
  struct list *aux,*ant;
  aux=inicio;
  ant=inicio;
  while ((aux!=NULL)&&(aux->id!=id))
  {
   ant=aux;
   aux=aux->next;
  }
  if (aux == NULL)
    return inicio;
  if (aux == ant)
  {
    free(aux);
    inicio=inicio->next;
  }
  else
  {
    ant->next=aux->next;
    free(aux);
  }
  return inicio;
}

    • No hay errores

    • Línea 16: acceso a memoria con un puntero corrupto.

    • Línea 20: fuga de memoria.

    • Línea 13: memoria sin inicializar.

  5. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    		 
    struct list *del_element(int id, struct list *inicio)
{
  struct list *aux,*ant;
  aux=inicio;

  while ((aux!=NULL)&&(aux->id!=id))
  {
   ant=aux;
   aux=aux->next;
  }
  if (aux == NULL)
    return inicio;
  if (aux == ant)
  {
    inicio=inicio->next;
    free(aux);
  }
  else
  {
    ant->next=aux->next;
    free(aux);
  }
  return inicio;
}

    • No hay errores.

    • Línea 15: acceso a memoria con un puntero corrupto.

    • Línea 20: fuga de memoria.

    • Línea 13: memoria sin inicializar.

  6. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    		 
    struct list *del_element(int id, struct list *inicio)
{
  struct list *aux,*ant;
  aux=inicio;
  ant=inicio;
  while ((aux!=NULL)&&(aux->id!=id))
  {
   ant=aux;
   aux=aux->next;
  }
  if (aux == NULL)
    return inicio;
  if (aux == ant)
  {
    inicio=inicio->next;
    free(aux);
  }
  else
  {
    ant->next=aux->next;
  }
  return inicio;
}

    • No hay errores.

    • Línea 15: acceso a memoria con un puntero corrupto.

    • Línea 20: fuga de memoria.

    • Línea 13: memoria sin inicializar.

  7. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    		 
    struct  vector *create_vector(int number)
{
if (number == 0)
  return NULL;
struct vector *nuevo= (struct vector *) malloc(sizeof(struct vector)*number);
if (nuevo == NULL)
  return NULL;
int i=0;
while (i<=number)
{
  nuevo[i]=i;
  i++;
}
return nuevo;
}

    • No hay errores.

    • Línea 9: memoria sin inicializar.

    • Línea 11: sobre-escritura de memoria dinámica.

  8. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    		 
    struct  vector *create_vector(int number)
{
if (number == 0)
  return NULL;
struct vector *nuevo= (struct vector *) malloc(sizeof(struct vector)*number);
if (nuevo == NULL)
  return NULL;
int i;
while (i<number)
{
  nuevo[i]=i;
  i++;
}
return nuevo;
}

    • No hay errores.

    • Línea 9: memoria sin inicializar.

    • Línea 11: sobre-escritura de memoria dinámica.

¿Cuánto tiempo has dedicado a esta actividad? mins.

2. Árbol de cadenas de texto

Plan de trabajo

En un programa en C necesita almacenar un número indeterminado de palabras. La estructura de datos seleccionada es un árbol binario en el que cada nodo almacena una palabra. Además, el árbol tiene la propiedad de que la palabra almacenada en cada nodo sigue lexicograficamente a las del sub-arbol izquierdo, y precede a las del sub-arbol derecho. La siguiente figura muestra un ejemplo de esta estructura de datos.

La aplicación necesita manipular varios conjuntos de palabras independientes.

  1. Define las estructuras de datos necesarias para manipular estos árboles.

  2. Define los prototipos de las siguientes funciones:

    • Función que crea un nuevo conjunto vacío.

    • Función que busca una palabra en un conjunto y la devuelve (la palabra devuelta se puede modificar).

    • Función que añade una palabra en un árbol. Si ya existe, no hace nada.

    • Función que destruye un árbol entero.

    • Función que borra una palabra de un árbol.

  3. Escribe el método main que contenga un bucle y mediante la función getline lea de teclado una cadena y la inserta en dos árboles. El programa se detiene cuando getline devuelve el valor NULL.

  4. Dividir el trabajo en equipos y que cada uno haga uno de los métodos de búsqueda, inserción o borrado de todos los elementos. La función strcmp recibe como parámetros dos enteros y devuelve un número menor, igual o mayor que cero si la primera palabra precede, es idéntica o antecede a la segunda respectivamente.

  5. Implementar la función de borrado de una cadena.

  6. Responder a las siguientes preguntas:

    1. Si comparamos esta estructura de datos con una lista encadenada de palabras, ¿qué estructura ofrece una inserción de nuevas palabras más eficiente?

    2. ¿Cómo comparan estas dos estructuras con respecto a la búsqueda?

    3. Dos árboles contienen exactamente las mismas palabras. ¿Quiere decir esto que tienen idéntica estructura?

    4. Si en la aplicación C que utiliza estas funciones, el 99% de las operaciones que se ejecutan son de búsqueda de palabras, ¿qué mejora propondrías a la estructura de datos para ganar eficiencia?

¿Cuánto tiempo has dedicado a esta actividad? mins.
© Universidad Carlos III de Madrid | Licencia Creative Commons