Liste des cours Se connecter

Informations

Auteur(s) Sébastien Strebelle
Date limite Pas de date limite
Limite de soumission Pas de limite

Etiquettes

Se connecter

Se connecter

Liste doublement chaînée

Une liste doublement chaînée est implémentée comme suit. Cette structure de données permet d'enregistrer un ensemble d'éléments, en liant pour chacun une clé à une valeur. On va faire l'hypothèse dans cette question qu'il n'y a qu'un seul exemplaire de chaque clé dans la liste.

typedef struct node {
    int key;
    double value;
    struct node* next;
    struct node* prev;
} node_t;

typedef struct list {
    node_t* head;
    node_t* tail;
} list_t;

list_t* create_list() {
    list_t* list = (list_t*) malloc(sizeof(list_t));
    if (list == NULL) {
        return NULL;
    }

    list->head = NULL;
    list->tail = NULL

    return list;
}

int insert(list_t* list, int key, double value) {
    node_t* node = (node_t*) malloc(sizeof(node_t));
    if (node == NULL) {
        return -1;
    }

    node->key = key;
    node->value = value;
    node->next = NULL;

    if (list->tail == NULL) {
        list->head = node;
        node->prev = NULL;
    } else {
        list->tail->next = node;
        node->prev = list->tail;
    }

    list->tail = node
    return 0;
}

void free_list(list_t* list) {
    node_t* current = list->tail;

    if (current == NULL) {
        free(list);
        return;
    }

    while (current->prev != NULL) {
        current = current->prev;
        free(current->next);
    }

    free(current);
    free(list);
}

Vous devez implémenter la fonction delete dont les spécifications vous sont fournies.

Question 1: Fonction delete

Insérez ici le corps de la fonction delete dont les spécifications vous sont données ci-dessous :

/*
 * pre:
 * - list n'est pas null
 * - Pour chaque paire a, b d'éléments dans la liste, a.key != b.key
 * post:
 * - S'il y a un élément avec la clé `key` dans la liste, celui-ci est retiré
 * - retourne la clé `key` de l'élément retiré
 * - retourne 0 si aucun élément n'a été trouvé pour cette clé
 */
int delete(list_t* list, int key) {
Question 2: Fonctions supplémentaires

Insérez ici les fonctions supplémentaires éventuelles dont vous avez besoin.

Question 3: Fonction de test

Insérez votre code de test optionnel ci-dessous. Vous pouvez utiliser printf dans cette fonction pour débugger votre programme.

Plusieurs fonctions vous sont fournies pour afficher le contenu de la liste.

void print_list(list_t* list) {
    node_t* current = list->head;
    while (current != NULL) {
        printf("Key=%d, Value=%f\n", current->key, current->value);
        current = current->next;
    }
}

void print_elem(list_t* list, int key) {
    node_t* current = list->head;
    while (current != NULL) {
        if (current->key == key) {
            printf("Key=%d, Value=%f\n", current->key, current->value);
            return;
        }
        current = current->next;
    }
    printf("No element found for Key=%d\n", key);
}

void test_func(void) {