TP Tableaux et pointeurs

Ce TP propose une série d'exercices pratiques sur les tableaux, pointeurs, chaînes de caractères, structures et listes chaînées en langage C. Il permet d'acquérir des compétences en manipulation de données, allocation dynamique, gestion de chaînes et structures complexes. Pour réaliser ce TP, il est nécessaire de disposer d'un environnement de programmation C avec un compilateur compatible et des connaissances de base en programmation C.

Objectifs

• Manipuler des tableaux et effectuer des opérations comme suppression, inversion et fusion.
• Utiliser l'allocation dynamique pour créer et libérer des tableaux et matrices.
• Travailler avec des chaînes de caractères et manipuler des mots et lettres.
• Gérer des structures et collections dynamiques d'objets.
• Implémenter et manipuler des listes chaînées simples.

Prérequis et installation

• Connaissances en langage C : tableaux, pointeurs, fonctions, structures.
• Environnement de développement C avec compilateur (gcc, clang, etc.).
• Éditeur de texte pour écrire le code source.
• Compréhension de la gestion dynamique de la mémoire (malloc, free).

Manipulation de tableaux

Dans cette première étape, vous allez écrire plusieurs fonctions pour manipuler des tableaux d'entiers.

Exercice 1 : Suppression des zéros et compression

Écrire une fonction void collapse_array(int array[], int d) qui supprime toutes les occurrences de zéro dans le tableau array de dimension d. Les éléments non nuls doivent être compressés vers le début du tableau, et les cases restantes à la fin doivent être remplies avec des zéros.

Exemple : collapse_array([10,0,30,0], 4) doit donner [10,30,0,0].

Cette étape permet de comprendre la manipulation directe des tableaux et la gestion des indices.

Exercice 2 : Inversion du tableau

Écrire une fonction void reverse_array(int array[], int d) qui inverse les éléments du tableau array de dimension d sans utiliser de tableau intermédiaire.

Exemple : reverse_array([10,20,30,40], 4) doit donner [40,30,20,10].

Cette fonction développe la maîtrise des échanges d'éléments en place.

Exercice 3 : Fusion de deux tableaux triés

Écrire une fonction void merge_array(int arrayA[], int d1, int arrayB[], int d2, int array_res[]) qui fusionne deux tableaux triés arrayA et arrayB de dimensions respectives d1 et d2. Le tableau résultat array_res doit contenir tous les éléments triés par ordre croissant.

Cette étape permet de pratiquer l'algorithme de fusion, base des tris efficaces.

Exercice 4 : Insertion dans un tableau trié

Écrire une fonction void insert_array(int array[], int d, int val) qui insère la valeur val dans un tableau trié array de dimension d. La dernière case du tableau n’est pas définie et doit être utilisée pour l’insertion. Le tableau doit rester trié après insertion.

Cette fonction illustre l'insertion ordonnée dans un tableau.

Allocation dynamique

Cette étape aborde la gestion dynamique de la mémoire pour tableaux et matrices.

Exercice 5 : Affichage de tableaux et matrices

• Écrire void print_array(float *array, int d) pour afficher un tableau de réels de dimension d.
• Écrire void print_matrix(float **matrix, int l, int c) pour afficher une matrice de réels de dimensions l × c.

Ces fonctions facilitent la visualisation des données dynamiques.

Exercice 6 : Allocation et libération de tableaux

• Écrire int *allocate_array(int d, int n) qui alloue dynamiquement un tableau d'entiers de dimension d et initialise tous ses éléments à n.
• Écrire void free_array(int *array) pour libérer la mémoire allouée à un tableau.

Exercice 7 : Allocation et libération de matrices

• Écrire int **allocate_matrix(int l, int c, int n) qui alloue dynamiquement une matrice de dimensions l × c et initialise tous ses éléments à n.
• Écrire void free_matrix(int **matrix, int l) qui libère la mémoire d'une matrice de l lignes.

Manipulation de chaînes de caractères

Cette étape traite la manipulation de mots et lettres dans des tableaux de chaînes.

Exercice 8 : Échange de mots

Écrire une fonction void exchange_word(char *array[], int i, int j) qui échange les mots situés aux positions i et j dans un tableau de mots.

Exercice 9 : Échange de lettres

Écrire une fonction void exchange_letter(char *tab[], int i, int j) qui échange la première lettre des mots aux positions i et j.

Exercice 10 : Recherche de caractère

Écrire une fonction char *search(char *m, char c) qui cherche la première occurrence du caractère c dans le mot m. La fonction retourne un pointeur vers cette occurrence ou NULL si le caractère n’existe pas.

Exercice 11 : Analyse de chaînes

On utilise la fonction suivante pour lire une chaîne de caractères (espaces inclus) :

void MyGets(char *chaine)
{
  char c;
  while((c=getchar())!='\n')
    *(chaine++) = c;
  *chaine = '\0';
}

• Écrire int est_lettre(char c) qui retourne 1 si c est une lettre (majuscule ou minuscule), 0 sinon.
• Écrire int compte_alphabet(char *chaine) qui compte le nombre de lettres dans la chaîne.
• Écrire int compte_mot(char *chaine) qui compte le nombre de mots (groupes de caractères séparés par un ou plusieurs espaces).
• Écrire un programme qui saisit une chaîne, puis affiche le nombre de caractères alphabétiques et le nombre de mots.

Structures

Cette étape permet de manipuler des structures et collections dynamiques.

Exercice 12 : Gestion d’une collection de livres

Soit la structure :

struct book {
  char title[30];
  int code;
  float price;
};

• Écrire struct book *create_collection(int n) qui alloue dynamiquement une collection de n livres. Les champs int sont initialisés à 0, les chaînes à une chaîne vide.
• Tester cette fonction dans un programme principal.
• Écrire void print_collection(struct book *collection, int n) pour afficher la collection.
• Écrire void exchange_book(struct book *collection, int i, int j) qui échange les livres aux positions i et j.

Listes chaînées

Cette dernière étape aborde la création et manipulation de listes chaînées simples.

Exercice 13 : Liste chaînée d’entiers

Soit la structure :

typedef struct list {
  int n;
  struct list *suivant;
} int_list;

• Écrire int_list *create_list(void) qui crée une liste vide (retourne NULL).
• Écrire int empty_list(int_list *l) qui teste si une liste est vide.
• Écrire void print_list(int_list *l) qui affiche les éléments d'une liste.
• Écrire int_list *insert_elem(int_list *l, int val) qui insère un entier en tête de liste.
• Écrire int_list *delete_elem(int_list *l) qui supprime l’élément en tête et retourne la liste restante (la liste doit contenir au moins un élément).
• Écrire void free(int_list *l) qui libère la mémoire occupée par la liste.
• Écrire int_list *delete_val(int_list *l, int val) qui supprime la première occurrence de val dans la liste.

Résultats attendus

• Les fonctions de manipulation de tableaux doivent produire des tableaux modifiés conformes aux exemples donnés.
• Les allocations dynamiques doivent créer des structures initialisées correctement et libérées sans fuite mémoire.
• Les fonctions sur chaînes doivent correctement identifier lettres, mots et positions de caractères.
• Les structures doivent être créées, affichées et manipulées sans erreurs.
• Les listes chaînées doivent permettre insertion, suppression, affichage et libération correctes.

Pièges courants

• Ne pas oublier de remplir les cases vides avec zéro après suppression dans collapse_array.
• Dans reverse_array, éviter d'utiliser un tableau temporaire.
• Lors de la fusion dans merge_array, bien gérer les indices pour ne pas dépasser les limites.
• Pour l’insertion dans un tableau trié, vérifier que la dernière case est libre avant insertion.
• En allocation dynamique, toujours vérifier que malloc ne retourne pas NULL.
• Libérer correctement toute la mémoire allouée, notamment pour les matrices et les listes chaînées.
• Pour les chaînes, bien gérer le caractère de fin '\0' et éviter les dépassements de tampon.
• Dans les listes chaînées, vérifier que la liste n’est pas vide avant suppression d’éléments.
• Ne pas confondre pointeurs et valeurs lors des échanges dans les tableaux de chaînes ou structures.