UC3M

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

Arquitectura de Sistemas

Septiembre 2015 - Enero 2016

Estructuras de datos dinámicas

Actividades en clase

Tabla de contenidos

1. Lista encadenada de enteros
Recursos
Plan de trabajo
Autoevaluación automática

1. Lista encadenada de enteros

Recursos

Un programa en C necesita almacenar un número indeterminado de enteros. El tamaño de los datos no se sabe hasta que el programa está ejecutando. Para hacer un uso más óptimo de memoria se opta por representarlos mediante una lista encadenada. Cada elemento de esa lista es una estructura que contiene el número a almacenar y un puntero al siguiente elemento. Los elementos de la lista están, por tanto, encadenados. La siguiente figura muestra un ejemplo de esta estructura:

La lista se manipula en el programa únicamente mediante un puntero a su primer elemento. Escribe las siguientes porciones de código (necesitarás ayuda con alguna de ellas, con lo que esperamos que hagas uso del foro de la asignatura):

  1. Define la estructura de datos necesaria. ¿Cómo representas una lista vacía?

  2. Función que no recibe parámetros y devuelve una lista vacía (no debería tener más de una línea de código).

  3. Función que, dado un entero, devuelve una lista con un único elemento con ese entero.

  4. Función que, dada una lista y un entero, añade el entero a la lista (el lugar donde se añade el entero es irrelevante).

  5. Función que devuelve el número los elementos de una lista.

  6. Función que, dada una lista y un entero, borra todas las apariciones de ese entero (si hay alguna) en la lista.

  7. Función que, dadas dos listas, devuelve una lista que es la concatenación de ambas.

  8. Función que borra totalmente el contenido de una lista.

Sugerencia

Escribe estas estructuras y funciones en un fichero con su propia función main e incluye en ella llamadas para verificar que tu estructura de datos funciona correctamente.

Plan de trabajo

  1. Decide primero qué representación vas a tener de la lista y cómo vas a almacenar los elementos. Piensa si la estructura que propones es la adecuada para ser manipulada por las funciones que se piden.

  2. Para cada función, primero piensa en su prototipo, esto es, el tipo de resultado y los tipos y número de parámetros necesarios. Una vez que tengas esto claro, diseña el cuerpo de la función.

  3. Una vez hayas terminado la implementación de las funciones, mueve la función main a un fichero aparte. Crea un fichero con extensión “*.h” en el que incluyas las definiciones y prototipos necesarios para que, al incluirlo en el fichero del “main”, se compile sin advertencias.

Autoevaluación automática

Ahora, trabajaremos con la lista de alumnos de un curso (de tamaño variable) donde se guardará, para cada alumno, un nombre (de tamaño variable), sus notas (otra lista de tamaño variable) y su identificador de alumno (un entero).

  1. Elija la definición de datos adecuada para guardar las notas de cada alumno.

    • struct score
{
    int score;
    struct score next;
};

    • struct score
{
    int score;
};


    • struct score
{
    int score;
    struct score *next;
};

  2. Elija la definición de datos adecuada para la lista de alumnos.

    • struct lista
{
    int id;
    char *name;
    struct score scores_student;
    struct lista next;
};

    • struct lista
{
    int id;
    char *name;
    struct score *scores_student;
    struct lista *next;
};

    • #define SIZE 30
struct lista
{
    int id;
    char name[SIZE];
    struct score *scores_student;
    struct lista *next;
};

    • #define SIZE 30
struct lista
{
    int id;
    char name[SIZE];
    struct score scores_student;
    struct lista next;
};

  3. Se desea inicializar en el programa principal la lista como vacía. Elija la correcta declaración.

    • struct lista *clase= (struct lista *) malloc (sizeof(struct lista));
*clase=NULL;

    • struct lista *clase= (struct lista *) malloc (sizeof(struct lista));
clase=NULL;

    • struct lista *clase= (struct lista *) malloc (sizeof(struct lista));

    • struct lista clase=NULL;

    • struct lista *clase=NULL;

  4. Se desea implementar una función que, dado un identificador y un nombre de alumno, devuelva una lista con un único elemento con la lista de notas vacía. La función debe copiar el nombre del alumno. Elija el código correcto para dicha función.

    • struct lista *new_student(int id, char *name)
{
    struct lista *aux= (struct lista *) malloc (sizeof(struct lista));
    if (aux == NULL)
    { 
        return NULL;
    }
    aux->id=id;
    aux->name=name;
    aux->scores_student=NULL;
    aux->next=NULL;
    return aux;
}

    • struct lista *new_student(int id, char *name)
{
    struct lista *aux= (struct lista *) malloc (sizeof(struct lista));
    if (aux == NULL)
    {
        return NULL;
    }
    aux->id=id;
    aux->name=(char *) malloc (sizeof(char)*(strlen(name)+1));
    if (aux->name == NULL)
    {
        free(aux);
        return NULL;
    }
    strcpy(aux->name,name);
    aux->scores_student=NULL;
    return aux;
}

    • struct lista *new_student(int id, char *name)
{
    struct lista *aux= (struct lista *) malloc (sizeof(struct lista *));
    if (aux == NULL)
    { 
        return NULL;
    }
    aux->id=id;
    aux->name=(char *) malloc (sizeof(char *)*(strlen(name)));
    if (aux->name == NULL)
    {
        free(aux);
       return NULL;
    }
    strcpy(aux->name,name);
    aux->scores_student=NULL;
    aux->next=NULL;
    return aux;
}

    • struct lista *new_student(int id, char *name)
{
    struct lista *aux= (struct lista *) malloc (sizeof(struct lista));
    if (aux == NULL)
    {
        return NULL;
    }
    aux->id=id;
    aux->name=(char *) malloc (sizeof(char)*(strlen(name)+1));
    if (aux->name == NULL)
    {
        free(aux);
        return NULL;
    }
    strcpy(aux->name,name);
    aux->scores_student=NULL;
    aux->next=NULL;
    return aux;
}

    • struct lista *new_student(int id, char *name)
{
    struct lista *aux= (struct lista *) malloc (sizeof(struct lista));
    if (aux == NULL) 
    {
        return NULL;
    }
    aux->id=id;
    aux->name=(char *) malloc (sizeof(char)*(strlen(name)+1));
    if (aux->name == NULL)
    {
        free(aux);
        return NULL;
    }
    strcpy(aux->name,name);
    return aux;
}

  5. Se desea llamar a la función anterior desde el programa principal. Elija el código correcto.

    • #define SIZE 30
struct lista *nuevo;
char nombre[SIZE]="pepe";
int id=5;
nuevo=new_student(id,nombre);

    • #define SIZE 30
struct lista nuevo;
char nombre[SIZE]="pepe";
int id=5;
nuevo=new_student(id,nombre);

    • #define SIZE 30
struct lista *nuevo;
char *nombre="pepe";
int id=5;
nuevo=new_student(id,nombre);

    • #define SIZE 30
struct lista *nuevo;
char nombre[SIZE]="pepe";
int id=5;
nuevo=new_student(id,&nombre);

    • #define SIZE 30
struct lista *nuevo;
char *nombre="pepe";
int id=5;
nuevo=new_student(id,&nombre);

  6. Se desea implementar una función que, dada una lista, un identificador y un nombre de alumno, modifique la lista añadiendo el nuevo alumno al final de la lista y devuelva la nueva longitud de la misma. Elija el prototipo correcto de dicha función.

    • int add_new_student(struct lista *list,int id, char *name);

    • int add_new_student(struct lista **list,int id, char *name);

    • struct lista *add_new_student(int id, char *name);

    • void add_new_student(struct lista *list,int id, char *name);

    • El lenguaje C no permite implementar una función de esas características.

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