UC3M

Telematic/Audiovisual Syst./Communication Syst. Engineering

Systems Architecture

September 2015 - January 2016

Dynamic Data Structures

In-class activities

Table of Contents

1. Integer linked list
Resources
Work Plan
Automatic self-assessment

1.  Integer linked list

Resources

A C program needs to store integers. The size of this data is not known until execution time. To optimize memory usage, a linked list data structure was chosen. Each element of that list is a structure that contains a number and a pointer to the following element. The following figure shows an example of this structure.

The list is managed in the program simply by the pointer to its first element. Write the following code portions (you will need help with some of them, so we expect you to use the course forum):

  1. Define the required data structure. How is the empty list represented?

  2. Function receives no parameters and returns an empty list (it should not have more than one line of code).

  3. Function that, given an integer, returns a list with a single element with this integer.

  4. Function that, given a list and an integer, adds the integer to the list (the place in the list where the integer is inserted is irrelevant).

  5. Function that returns the number of elements in a list.

  6. Function that, given a list and an integer, removes all appearances of this element on the list (if any).

  7. Function that, given two lists, returns the concatenation of both lists.

  8. Function that deletes completely the content of the list.

Suggestion

Write these structures and functions in a file with its own main function and include in it calls to verify that your data structure works correctly.

Work Plan

  1. Decide first how are you going to represent the list and how are you going to store the elements. Think if the proposed structure is the appropriate one to be manipulated by the required functions.

  2. For each function, first think about its prototype, that is, the result type and type and number of required parameters. Once this is clear, write the body of the function.

  3. Once all functions have been implemented, move the main function to a separate file. Create a file with extension “*.h” containing the definitions and prototypes needed to be included in the file with the “main” and compile without any warnings.

Automatic self-assessment

Now, we will work with a list of students (of variable size) where, for each student, we will store her/his name (variable size), her/his scored (in another list of variable size) and her/his student id (an integer).

  1. Choose the correct data definition for the scores of the students

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

    • struct score
{
    int score;
};


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

  2. Choose the correct data definition

    • 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. We would like to initialize the students list in the main program as an empty list. Choose the correct data declaration.

    • 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. We would like to implement a function that, given an id and the name of a student, returns a list with one element. The score list of this element will be empty. The function must copy the name of the student. Choose the correct code.

    • 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. We would like to invoke the previous function. Choose the correct code.

    • #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. We would like to implement a function that, given a list, an id and the name of a student, modifies the list, adding the new student at its end. The function must returns the new length of the list. Choose the correct prototype.

    • 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);

    • The C language does not allow such prototype declaration.

How long did this activity take you? mins.
© Carlos III University of Madrid | Creative Commons License