TP3 - Les listes chaînées

Durée : 3h

Inès de Courchelle, Elisabeth Ranisavljevic

Objectifs :

  • Étudier des structures de données liées
  • Connaître les particularités des chaînes
  • Appréhender des notions de gestion de données

Attention :

À chaque étape de programmation, vous devez vérifier si le programme :

  • Compile sans warning
  • Obtient les résultats attendus
  • Avant de coder, il faut écrire un algo avec un papier et un stylo !

    logo

Exercice 1 : La préparation

  1. Créer les fichiers suivants :
  • liste.h
  • liste.c
  • main.c
  1. Créer le squelette du programme

liste.h

#ifndef LISTES_H
#define LISTES_H

/* Le prototype/signature de toutes mes fonctions/procédures */

#endif

liste.c

#include "liste.h"
/* corps des différentes fonctions/procédures */

main.c

#include <stdio.h>
#include "liste.h"

int main(){
    printf("C'est la liste !");
    return 0;
}

Exercice 2 : Les basiques

  1. Déclarer une structure liste chaînée contenant un maillon d’entier
  2. Coder les fonctionnalités suivantes :
/* Auteur : xxxxxx */
/* Date : xxxxx */
/* Entrees :  une donnee*/
/* Sorties : un maillon */
/* Résumé :  creer un maillon avec la donnee associée */
maillon* creerMaillon(int donnee);

/* Auteur : xxxxxx */
/* Date : xxxxx */
/* Entrees :  une tete de liste, une donnee */
/* Sorties : une tete de liste */
/* Résumé :  ajouter un maillon en tête de liste */
teteListe ajouterTete(teteListe maListe, int donnee);

/* Auteur : xxxxxx */
/* Date : xxxxx */
/* Entrees :  une tete de liste */
/* Sorties :  */
/* Résumé :  Affiche une liste chaînée */
void afficher(teteListe maListe);

Exercice 3 : Les avancées

  1. Coder les fonctions d’ajout suivantes :
/* Auteur : xxxxxx */
/* Date : xxxxx */
/* Entrees :  une tete de liste et  une donnee*/
/* Sorties :  une tete de liste */
/* Résumé :  ajoute une donnée à la fin une liste chaînée */
teteListe ajouterFin(teteListe maListe, int donnee);

/* Auteur : xxxxxx */
/* Date : xxxxx */
/* Entrees :  une tete de liste, une donnee et une position */
/* Sorties :  une tete de liste */
/* Résumé :  ajoute une donnée à une position donnée dans une liste chaînée */
teteListe ajouterPos(teteListe maListe,int valeur,int pos);
  1. Coder les fonctions de suppression suivantes :
/* Auteur : xxxxxx */
/* Date : xxxxx */
/* Entrees :  une tete de liste */
/* Sorties :  une tete de liste */
/* Résumé :  supprime la donnée en tête de liste */
teteListe supprimerDebut(teteListe maListe);

/* Auteur : xxxxxx */
/* Date : xxxxx */
/* Entrees :  une tete de liste */
/* Sorties :  une tete de liste */
/* Résumé :  supprime une donnée à la fin d'une liste chaînée */
teteListe supprimerFin(teteListe maListe);

/* Auteur : xxxxxx */
/* Date : xxxxx */
/* Entrees :  une tete de liste et une position */
/* Sorties :  une tete de liste */
/* Résumé :  supprime une donnée à une position donnée dans une liste chaînée */
teteListe supprimerPos(teteListe maListe,int pos);

/* Auteur : xxxxxx */
/* Date : xxxxx */
/* Entrees :  une tete de liste */
/* Sorties :  une tete de liste */
/* Résumé :  supprime le contenu de la liste chaînée */
teteListe viderListe(teteListe maListe);
  1. N’oublier pas de tester l’ensemble des fonctionnalités dans le main petit à petit

Exercice 4 : Les masters

  1. Écrire la procédure/fonction permettant de supprimer le premier nœud dont la valeur est égale à une valeur donnée
/* Auteur :   */
/* Date :  */
/* Résumé :  fonction permettant de supprimer un maillon dont
            la valeur est passée en paramètre  */
/* Entrée(s) :  une tete de liste et la valeur*/
/* Sortie(s) :  la nouvelle liste */
teteListe supprVal(teteListe maListe, TYPE val);
  1. Écrire la procédure/fonction permettant de supprimer tous les nœuds dont la valeur est égale à une valeur donnée.
/* Auteur :   */
/* Date :  */
/* Résumé :  fonction permettant de supprimer tous les maillons dont
             la valeur est passée en paramètre  */
/* Entrée(s) :  une tete de liste et la valeur*/
/* Sortie(s) :  la nouvelle liste */
teteListe supprValDoublons(teteListe maListe, TYPE val);
  1. Écrire la procédure/fonction permettant de rattacher la liste à elle-même. Par exemple, {10, 15, 20} devient {10, 15, 20, 10, 15, 20}.
/* Auteur :   */
/* Date :  */
/* Résumé :  fonction permettant de  rattacher la liste à elle-même.  */
/* Entrée(s) :  une tete de liste et la tete liste */
/* Sortie(s) :  la nouvelle liste */
teteListe rattacherFin (teteListe maListe, teteListe maListe2);
  1. Écrire la procédure/fonction permettant d’inverser la liste. Par exemple, {1, 4, 3, 8} devient {8, 3, 4, 1}.
/* Auteur :   */
/* Date : */
/* Résumé :  fonction permettant d'inverser le contenu d'une liste dans une autre  */
/* Entrée(s) :  une tete de liste et la tete liste */
/* Sortie(s) :  la nouvelle liste */
teteListe inverser (teteListe maListe, teteListe maListe2);
  1. Écrire la procédure/fonction permettant de chercher la position d’un élement dans une liste chaînée. Par exemple, {42, 24, 2, 3, 24, 8}, 24 est à la position 1. Par contre, si on cherche 68 (qui n’est pas dans la liste) la fonction renverra -1.
/* Auteur :    */
/* Date :  */
/* Résumé :  fonction permettant de chercher la position d'un élement dans une liste chaînée  */
/* Entrée(s) :  une tete de liste, la donnée et l'accumulateur pour la position */
/* Sortie(s) :  la nouvelle liste */
int chercherElt(teteListe maListe,int donnee,int acc);
  1. Écrire la procédure/fonction permettant de supprimer les doublons. Par exemple, {42, 24, 2, 2, 3, 24, 8} devient {42,24,2,3,8}.
/* Auteur :  */
/* Date :  */
/* Résumé :  fonction permettant de supprimer les doublons  */
/* Entrée(s) :  une tete de liste, la tete liste */
/* Sortie(s) :  la nouvelle liste */
teteListe sansDoublons (teteListe maListe, teteListe maListe2);