Concepts des structures linéaires

Dans une structure linéaire, un ensemble fini non vide d'éléments de données présente les caractéristiques suivantes :

• Il existe un élément unique désigné comme le "premier".
• Il existe un élément unique désigné comme le "dernier".
• Chaque élément, à l'exception du premier, possède exactement un prédécesseur.
• Chaque élément, à l'exception du dernier, possède exactement un successeur.

Cette structure logique reflète une relation un-à-un entre les nœuds. Les types courants incluent les listes linéaires, les piles, les files, les chaînes de caractères et les tableaux.

Définition de la liste linéaire

Une liste linéaire est une séquence finie de n éléments de données. Tous les éléments dans une même liste doivent partager des propriétés communes. Le nombre d'éléments n définit la longueur de la liste ; une liste vide a une longueur nulle.

Représentation séquenitelle et implémentation

La représentation séquentielle utilise un bloc contigu d'emplacements mémoire pour stocker séquentiellement les éléments de la liste. Cette structure de stockage, appelée tableau séquentiel, place les éléments logiquement adjacents dans des emplacements physiquement adjacents.

Avantages et inconvénients

Avantages :

• La proximité logique correspond à une proximité physique.
• L'accès aléatoire à n'importe quel élément est possible (adressage direct).
• L'utilisation de l'espace mémoire est compacte.

Inconvénients :

• Les opérations d'insertion et de suppression nécessitent le déplacement de nombreux éléments.
• L'allocation d'espace doit anticiper la taille maximale, ce qui peut conduire à une sous-utilisation.

Opérations de base sur une liste linéaire

Les opérations fondamentales incluent la modification, l'insertion, la suppression, la recherche et le tri.

Modification : Une seule étape suffit, par exemple affecter une valeur à un index : liste[i] = nouvelleValeur;.

Insertion : Pour insérer un élément avant la position i :

1. Déplacer les éléments de la position i à la fin d'un pas vers la droite.
2. Affecter la valeur au nouvel élément à la position i.
3. Incrémenter la longueur de la liste.

La complexité temporelle de l'insertion est O(n), et la complexité spatiale est O(1) car aucun espace auxiliaire n'est utilisé.

Suppression : Pour supprimer l'élément à la position i :

1. Déplacer les éléments de la position i+1 à la fin d'un pas vers la gauche.
2. Décrémenter la longueur de la liste.

De manière similaire, la suppression a une complexité temporelle O(n) et spatiale O(1).

Représentation chaînée et implémentation

Une liste chaînée stocke les éléments dans des emplacements mémoire arbitraires en utilisant des pointeurs pour établir les relations logiques. Chaque nœud contient la donnée et un pointeur vers le nœud successeur. L'accès aléatoire n'est pas possible ; il faut parcourir la liste depuis la tête.

Questions fondamentales

Distinction entre concepts de liste chaînée

Pointeur de tête : Pointe vers le premier nœud de la liste.

Nœud d'en-tête : Un nœud ajouté avant le premier élément pour simplifier les opérations, permettnat un traitement uniforme des listes vides et non vides.

Premier nœud élément : Le nœud qui contient le premier élément de données de la liste.

Réponses aux questions

1. Dans un tableau séquentiel, l'insertion ou la suppression d'un élément déplace en moyenne la moitié des éléments. Le déplacement exact dépend de la longueur de la liste et de la position de l'élément.
2. Dans une liste chaînée simple, sauf pour le premier nœud, l'emplacement d'un nœud est déterminé par la valeur du champ lien de son prédécesseur direct.
3. Le nœud d'en-tête dans une liste chaînée permet de ne pas traiter spécialement l'insertion ou la suppression du premier élément.

Quand utiliser un tableau séquentiel plutôt qu'une liste chaînée ?

Préférer un tableau séquentiel lorsque des accès fréquents et aléatoires aux éléments sont nécessaires.

Exercices pratiques

Inversion d'un tableau séquentiel en place

L'algorithme inverse les éléments du tableau en échangeant les éléments depuis les extrémités vers le centre.

#include <stdio.h>
#include <stdlib.h>

int main() {
    int valeur, compteur, tempo, taille = 0;
    int *tableau;
    FILE *fichier = fopen("donnees.txt", "r");
    if (fichier == NULL) {
        perror("Erreur d'ouverture du fichier");
        return 1;
    }
    while (fscanf(fichier, "%d", &valeur) == 1) {
        taille++;
    }
    rewind(fichier);
    tableau = (int *)malloc(taille * sizeof(int));
    for (compteur = 0; compteur < taille; compteur++) {
        fscanf(fichier, "%d", &tableau[compteur]);
    }
    fclose(fichier);

    printf("Tableau original : ");
    for (compteur = 0; compteur < taille; compteur++) {
        printf("%d ", tableau[compteur]);
    }
    printf("\n");

    for (compteur = 0; compteur < taille / 2; compteur++) {
        tempo = tableau[compteur];
        tableau[compteur] = tableau[taille - 1 - compteur];
        tableau[taille - 1 - compteur] = tempo;
    }

    printf("Tableau inversé : ");
    for (compteur = 0; compteur < taille; compteur++) {
        printf("%d ", tableau[compteur]);
    }
    free(tableau);
    return 0;
}

Inversion d'une liste chaînée en place

Deux méthodes sont présentées. La première construit la liste en inversant l'ordre d'insertion, et la seconde utilise un algorithme de parcours et de mise à jour des pointeurs.

Méthode 1 : Inversion par construction

#include <stdio.h>
#include <stdlib.h>

typedef struct Noeud {
    int donnee;
    struct Noeud *suivant;
} Noeud;

Noeud *ajouterTete(Noeud *tete, int valeur) {
    Noeud *nouveau = (Noeud *)malloc(sizeof(Noeud));
    nouveau->donnee = valeur;
    nouveau->suivant = tete;
    return nouveau;
}

void afficherListe(Noeud *tete) {
    while (tete != NULL) {
        printf("%d ", tete->donnee);
        tete = tete->suivant;
    }
    printf("\n");
}

int main() {
    int nombre;
    Noeud *tete = NULL;
    FILE *fichier = fopen("liste.txt", "r");
    if (fichier == NULL) {
        perror("Erreur d'ouverture du fichier");
        return 1;
    }
    printf("Liste originale : ");
    while (fscanf(fichier, "%d", &nombre) == 1) {
        printf("%d ", nombre);
        tete = ajouterTete(tete, nombre);
    }
    fclose(fichier);
    printf("\nListe inversée : ");
    afficherListe(tete);
    return 0;
}

Méthode 2 : Inversion par manipulation des pointeurs

Noeud *inverserListe(Noeud *tete) {
    Noeud *precedent = NULL;
    Noeud *courant = tete;
    Noeud *suivant = NULL;
    while (courant != NULL) {
        suivant = courant->suivant;
        courant->suivant = precedent;
        precedent = courant;
        courant = suivant;
    }
    return precedent;
}

Fusion de deux listes chaînées triées par ordre croissant

L'algorithme fusionne deux listes triées en une seule liste triée. La première liste est construite normalement, et la seconde est insérée dans la première en respectant l'ordre.

#include <stdio.h>
#include <stdlib.h>

typedef struct NoeudPoly {
    int coeff;
    int degre;
    struct NoeudPoly *suivant;
} NoeudPoly;

NoeudPoly *ajouterFin(NoeudPoly *tete, int c, int d) {
    NoeudPoly *nouveau = (NoeudPoly *)malloc(sizeof(NoeudPoly));
    nouveau->coeff = c;
    nouveau->degre = d;
    nouveau->suivant = NULL;
    if (tete == NULL) return nouveau;
    NoeudPoly *courant = tete;
    while (courant->suivant != NULL) courant = courant->suivant;
    courant->suivant = nouveau;
    return tete;
}

NoeudPoly *insererTrie(NoeudPoly *tete, int c, int d) {
    NoeudPoly *nouveau = (NoeudPoly *)malloc(sizeof(NoeudPoly));
    nouveau->coeff = c;
    nouveau->degre = d;
    nouveau->suivant = NULL;
    if (tete == NULL || d < tete->degre) {
        nouveau->suivant = tete;
        return nouveau;
    }
    NoeudPoly *courant = tete;
    while (courant->suivant != NULL && courant->suivant->degre <= d) {
        courant = courant->suivant;
    }
    if (courant->degre == d) {
        courant->coeff += c;
    } else {
        nouveau->suivant = courant->suivant;
        courant->suivant = nouveau;
    }
    return tete;
}

void afficherPoly(NoeudPoly *tete) {
    printf("Polynôme fusionné :\n");
    while (tete != NULL) {
        printf("%d,%d\n", tete->coeff, tete->degre);
        tete = tete->suivant;
    }
}

int main() {
    FILE *fichier1, *fichier2;
    int coeff, degre;
    NoeudPoly *polynome = NULL;
    fichier1 = fopen("poly1.txt", "r");
    if (fichier1 == NULL) {
        perror("Erreur");
        return 1;
    }
    while (fscanf(fichier1, "%d,%d", &coeff, &degre) == 2) {
        polynome = ajouterFin(polynome, coeff, degre);
    }
    fclose(fichier1);

    fichier2 = fopen("poly2.txt", "r");
    if (fichier2 == NULL) {
        perror("Erreur");
        return 1;
    }
    while (fscanf(fichier2, "%d,%d", &coeff, &degre) == 2) {
        polynome = insererTrie(polynome, coeff, degre);
    }
    fclose(fichier2);

    afficherPoly(polynome);
    return 0;
}

Points clés à retenir

L'utilisation de fscanf renvoie le nombre d'éléments lus avec succès, ce qui permet de vérifier la lecture complète. Lors de la fusion, l'insertion doit comparer le degré avec les nœuds suivants pour maintenir l'ordre trié, et gérer le cas où un nouveau nœud devient la tête de la liste.