TP5&6: Exercices sur les listes chainées

Exercice 1: extraction des informations

Le but de cet exercice est de compléter la fonction read_file_content. Cette fonction va initialiser un tableau avec des informations concernant une liste d’étudiants. Ces informations sont initialement renseignées dans un fichier. La fonction read_file_content parcourt ce fichier et stocke les informations concernant les étudiants dans dans un tableau Student_t students_array[160] dont chaque entrée est du type :

typedef struct student {
	char lastname[30];
	char firstname[20];
	int group;
} Student_t;

Le tableau d’étudiants a été déclaré dans le code source qui vous est fourni:

Student_t students_array [160];

Complétez la fonction read_file_content:

Signature (ou prototype)

void read_file_content(Student_t * array, FILE * file); 

Paramètres

  • array: tableau dans lequel les informations des étudiants doivent être enregistrés.
  • file: fichier (déjà ouvert) contenant les informations sur les étudiants.

Indications

a. La fonction met à jour la valeur de la variable globale number_of_students, qui comptabilise le nombre d’étudiants référencés dans le fichier.

b. Pour lire le fichier, on utilise encore la fonction fscanf, dans une boucle while :

ret_lec = fscanf(fichier, "%s %s %d", array[i].nom,
                 array[i].prenom, &array[i].info);

Cette fonction renvoie EOF quand elle atteint la fin du fichier.

Après lecture du fichier, on visualisera à l’écran (depuis la fonction main) le contenu du tableau students_array.

Exercice 2: Création d’une liste chainée

On va créer une liste chainée à partir des informations contenues dans le tableau students_array. Chaque élément de la liste a le type suivant :

typedef struct link{
      Student_t  student;
      struct link * next;
} Link_t;

Voici la liste des fonctions à compléter :

  • new_link qui crée un nouvel élément de la chaine à partir d’une entrée du tableau (utilisation de malloc),
  • chain qui insère un maillon au début de la liste,

Voici leurs signatures :

Link_t * new_link(Student_t a_student);
Link_t * chain(Link_t * beginning, Link_t * new_link);

Ces fonctions sont à compléter dans le fichier main.c.

Visualiser le contenu de la liste en complétant la fonction display_linked_list qui affiche la liste à l’écran (utilisation de printf):

void display_linked_list(Link_t * beginning);

Exercice 3: Recherche d’un maillon

Dans cet exercice, vous allez coder la fonction search, qui vérifie si un nom se trouve dans la liste et renvoie l’adresse de l’élément correspondant, ou NULL si aucun ne correspond.

Signature

Link_t * search (Link_t * beginning, char * name_to_search); 

Paramètres

  • beginning: le début de la liste chainée
  • name_to_search: le nom pour lequel on cherche un maillon qui correspond

Valeur de retour

Le premier maillon correspondant au nom recherché, ou NULL si le nom recherché n’apparait pas dans la liste.

Indication

Utilisez  strcmp() pour comparer des chaines de caractères; Utilisez la commande man, ou internet, pour avoir de la documentation sur cette fonction.

Exercice 4: Insertion dans la liste

Dans cet exercice, vous allez coder la fonction insert, qui insère un maillon dans la liste supposée triée et renvoie le début de la liste. La liste chainée résultant doit préserver le tri.

Signature

Link_t * insert (Link_t * beginning, Link_t * new_link);

Paramètre

  • befinning: le début de la liste avant insertion. La liste est supposée triée.
  • new_link: le maillon à insérer.

Valeur de retour

Le début de la liste après insertion.

Indication

Continuez à utiliser la fonction strcmp().

Exercice 5: trier la liste

Dans cet exercice, vous allez coder la fonction sort qui trie la liste en la copiant dans une nouvelle liste.

Signature

Link_t * sort (Link_t * beginning);

Paramètre

  • beginning: début de la liste à trier

Valeur de retour

Nouvelle liste résultant du tri.

Indication

Le tri se fera sur le nom et de la façon suivante  :

  • Prendre un à un les maillons de la liste chainee de debut debut pour construire une nouvelle liste chaînee triee en utilisant insert.
  • Renvoyer le debut de la nouvelle liste triée.

Continuez à utiliser la fonction strcmp().

Exercice 6: restitution de la mémoire

Dans ce dernier exercice, vous allez coder la fonction free_list, qui rend la memoire occupée par une liste chainee.

Signature

void free_list (Link_t * first);

Paramètre

  • first: début de la zone mémoire à restituer

Cette fonction ne renvoie rien.