La gestion efficace de données structurées nécessite souvent l'utilisation de structures de données dynamiques. Ce document détaille la conception et l'implémentation d'une liste doublement chaînée en langage C pour stocker, manipuler et rechercher des informations relatives à des étudiants. Les enregistrements contiennent un identifiant, une note et un nom.

Les opérations fondamentales implémentées incluent l'insertion en tête de liste, le parcours séquentiel pour l'affichage, la recherche de notes correspondant à des nombres parfaits (un nombre parfait est un entier positif qui est égal à la somme de ses diviseurs propres), et la recherche d'un étudiant par son nom avec retour de son index dans la liste.

Définition des Structures de Données

Pour améliorer la clarté et la robustesse par rapport aux approches utilisant des unions dans les nœuds de tête, cette implémentation sépare les métadonnées de la liste (pointeur de tête et compteur) des données des nœuds individuels.

#ifndef DLIST_H
#define DLIST_H

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

typedef struct {
    int id;
    int score;
    char name[50];
} Student;

typedef struct Node {
    Student info;
    struct Node *prev;
    struct Node *next;
} Node;

typedef struct {
    Node *head;
    int count;
} DList;

DList* create_dlist();
void insert_head(DList *list, Student student);
void input_students(DList *list);
void display_students(const DList *list);
int is_perfect(int n);
void find_perfect_scores(const DList *list);
void search_by_name(const DList *list);
void free_dlist(DList *list);

#endif

Implémentation des Opérations sur la Liste

Le fichier source contient la logique d'allocation mémoire, les algorithmes d'insertion en tête simplifiés, ainsi que les fonctinos de recherche. L'algorithme de vérification des nombres parfaits a été optimisé pour réduire la complexité temporelle de O(N) à O(sqrt(N)).

#include "dlist.h"

DList* create_dlist() {
    DList *list = (DList*)malloc(sizeof(DList));
    if (!list) return NULL;
    list->head = NULL;
    list->count = 0;
    return list;
}

void insert_head(DList *list, Student student) {
    Node *new_node = (Node*)malloc(sizeof(Node));
    if (!new_node) return;
    
    new_node->info = student;
    new_node->prev = NULL;
    new_node->next = list->head;

    if (list->head) {
        list->head->prev = new_node;
    }
    list->head = new_node;
    list->count++;
}

void input_students(DList *list) {
    int n;
    printf("Nombre d'etudiants a saisir: ");
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        Student s;
        printf("Etudiant %d (ID Score Nom): ", i + 1);
        scanf("%d %d %s", &s.id, &s.score, s.name);
        insert_head(list, s);
    }
}

void display_students(const DList *list) {
    Node *curr = list->head;
    while (curr) {
        printf("ID: %d | Score: %d | Nom: %s\n", 
               curr->info.id, curr->info.score, curr->info.name);
        curr = curr->next;
    }
}

int is_perfect(int n) {
    if (n <= 1) return 0;
    int sum = 1;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            sum += i;
            if (i != n / i) {
                sum += n / i;
            }
        }
    }
    return sum == n;
}

void find_perfect_scores(const DList *list) {
    Node *curr = list->head;
    int found = 0;
    
    while (curr) {
        if (is_perfect(curr->info.score)) {
            printf("Nombre parfait trouve! ID: %d, Score: %d, Nom: %s\n",
                   curr->info.id, curr->info.score, curr->info.name);
            found = 1;
        }
        curr = curr->next;
    }
    
    if (!found) {
        printf("Aucun score ne correspond a un nombre parfait.\n");
    }
}

void search_by_name(const DList *list) {
    char target[50];
    printf("Nom de l'etudiant a rechercher: ");
    scanf("%s", target);

    Node *curr = list->head;
    int index = 1;
    
    while (curr) {
        if (strcmp(curr->info.name, target) == 0) {
            printf("Etudiant trouve a la position (index) %d.\n", index);
            return;
        }
        curr = curr->next;
        index++;
    }
    printf("Aucun etudiant trouve avec ce nom.\n");
}

void free_dlist(DList *list) {
    Node *curr = list->head;
    while (curr) {
        Node *temp = curr;
        curr = curr->next;
        free(temp);
    }
    free(list);
}

Point d'Entrée du Programme

Le programme principal orchestre l'initialiastion de la structure, l'apel séquentiel des fonctions de traitement et la libération finale de la mémoire pour éviter les fuites.

#include "dlist.h"

int main() {
    DList *student_list = create_dlist();
    if (!student_list) {
        fprintf(stderr, "Echec de l'allocation de la liste.\n");
        return 1;
    }

    input_students(student_list);

    printf("\n--- Affichage complet de la liste ---\n");
    display_students(student_list);

    printf("\n--- Recherche des nombres parfaits dans les scores ---\n");
    find_perfect_scores(student_list);

    printf("\n--- Recherche specifique par nom ---\n");
    search_by_name(student_list);

    free_dlist(student_list);
    return 0;
}