Structures

Ce fichier ne contient que les implémentations des structures en C et des fonctions de leur interface, autrement dit, les parcours d'arbres et autres ne sont pas ici

Structure générale

(utilisée pour les listes, piles, files)

typedef int contenu;

struct maillon_s {
    contenu valeur;
    struct maillon_s* suivant;
};

typedef struct maillon_s maillon;

Listes chaînées

typedef maillon* liste;

Fonctions

liste creer_liste(void){
    return NULL;
}

bool est_vide_liste(liste l){
    return (l == NULL);
}

void ajouter_tete_liste(contenu elt, liste* l){
    maillon* nouveau_maillon = malloc(sizeof(maillon));
    nouveau_maillon->valeur = elt;
    nouveau_maillon->suivant = *l;
    *l = nouveau_maillon;
}

contenu tete_liste(liste l){
    assert(l != NULL);
    return l->valeur;
}

liste queue_liste(liste l){
    assert(l != NULL);
    return l->suivant;
}

void detruire_liste(liste l){
    if (l != NULL){
        detruire_liste(queue_liste(l));
        free(l);
    }
}

Pas obligatoire mais pratique (pour les tris par exemple)

liste copie(liste l) {
    if (est_vide_liste(l)) {
        return NULL;
    }
    liste nouveau_maillon = malloc(sizeof(maillon));
    assert(nouveau_maillon != NULL)
    nouveau_maillon->valeur = l->valeur;
    nouveau_maillon->suivant = copie(l->suivant);
    return nouveau_maillon;
}


void concat_aux(liste* l1, liste l2){
    if (est_vide(queue(*l1))){
        (*l1)->suivant = l2;
    }
    else{
        concat_aux(&(*l1)->suivant, l2); //Je sais la syntaxe est étrange
    }
}

liste concat(liste l1, liste l2){
    if (est_vide(l1)){
        return copie(l2);
    }
    else if (est_vide(l2)){
        return copie (l1);
    }
    else{
        liste c1 = copie(l1);
        liste c2 = copie(l2);
        concat_aux(&c1, c2);
        return c1;
    }
}

Piles

Structure spécifique

struct pile_s {
    maillon* sommet;
};

typedef struct pile_s* pile;

Fonctions

pile creer_pile(void){
    return NULL;
}

bool est_vide_pile(pile p){
    return p == NULL;
}

void empiler(pile p, contenu elt){
    maillon* nouveau_maillon = malloc(sizeof(maillon));
    nouveau_maillon->valeur = elt;
    nouveau_maillon->suivant = p->sommet;
    p->sommet = nouveau_maillon;
}

contenu depiler(pile p){
    assert(!est_vide_pile(p));
    contenu tete = p->sommet->valeur;
    maillon* temp = p->sommet->suivant;
    free(p->sommet);
    p->sommet = temp;
    return tete;
}

contenu sommet_pile(pile p){
    assert(!est_vide_pile(p));
    return p->sommet->valeur;
}

void detruire_pile(pile p){
    if (!est_vide_pile(p)){
        depiler(p);
        detruire_pile(p);
    }
}

Files

Structure spécifique

struct file_s {
    maillon* premier;
    maillon* dernier;
};

typedef struct file_s* file;

Fonctions

file creer_file(void){
    file file_res = malloc(sizeof(struct file_s));
    file_res->premier = NULL;
    file_res->dernier = NULL;
    return file_res;
}

bool est_vide_file(file f){
    return (f->premier == NULL && f->dernier == NULL);
}

void enfiler(file f, contenu elt){
    maillon* nouveau_maillon = malloc(sizeof(maillon));
    nouveau_maillon->valeur = elt;
    nouveau_maillon->suivant = NULL;
    if (est_vide_file(f)){
        f->premier = nouveau_maillon;
        f->dernier = nouveau_maillon;
    }
    else{
        f->dernier->suivant = nouveau_maillon;
        f->dernier = nouveau_maillon;
    }
}

contenu defiler(file f){
    assert(!est_vide_file(f));
    contenu tete = f->premier->valeur;
    maillon* temp = f->premier->suivant;
    free(f->premier);
    if (temp == NULL){
        f->premier = NULL;
        f->dernier = NULL;
    }
    else{
        f->premier = temp;
    }
    return tete;
}

void detruire_file(file f){
    if (!est_vide_file(f)){
        defiler(f);
        detruire_file(f);
    }
    else{
        free(f);
    }
}

contenu tete_file(file f){
    assert(!est_vide_file(f));
    return f->premier->valeur;
}

Merci Thibaud pour tout ce qui suit

Arbres

Structure spécifique

typedef int etiq; 

struct noeud_s {
    etiq etiquette;
    struct noeud_s* gauche;
    struct noeud_s* droit;
};

typedef struct noeud_s* ab; 

Fonctions

ab vide(void) {
    return NULL;
}

ab noeud(etiq e, ab sag, ab sad) {
    ab a = malloc(sizeof(struct noeud_s));
    assert(a != NULL);
    a->etiquette = e;
    a->gauche = sag;
    a->droit = sad;
    return a;
}

void libere_ab(ab a) {
    if (a != NULL) {
        libere_ab(a->gauche);
        libere_ab(a->droit);
        free(a);
    }
}

bool est_vide_ab(ab a) {
    return a == NULL;
}

etiq etiq_racine(ab a) {
    assert(!est_vide_ab(a));
    return a->etiquette;
}

ab sous_arbre_gauche(ab a) {
    assert(!est_vide_ab(a));
    return a->gauche;
}

ab sous_arbre_droit(ab a) {
    assert(!est_vide_ab(a));
    return a->droit;
}

Graphes

typedef int mat_adjacence[900]; // matrice (30,30) linéarisée
struct graphe_s {
    int nb_sommets; // nombre de sommets du graphe, toujours <= 30
    mat_adjacence mat;
};
typedef struct graphe_s graphe;

typedef int lst_adjacence[30][31];
struct graph_s {
    int nb_sommets;
    lst_adjacence liste;
};
typedef struct graph_s graph;

La liste est implémentée par un tableau contenant les voisins du sommet i où i est le numéro de la ligne.
Deux possibilités : liste[i][0] contient le nombre de voisins du sommet i ou alors liste[i] contient une sentinelle (-1) pour marquer la fin des voisins

Arbres binaires de recherche (ABR)

Structure spécifique

struct noeud_s {
    int etiq;
    struct noeud_s* gauche;
    struct noeud_s* droit;
    struct noeud_s* pere;
};
typedef struct noeud_s* abr;

Fonctions

abr construit(int e, abr g, abr d) {
    abr racine = malloc(sizeof(struct noeud_s));
    assert(racine != NULL);

    racine->etiq = e;
    racine->gauche = g;
    racine->droit = d;
    racine->pere = NULL;

    if (g != NULL) {
        g->pere = racine;
    }
    if (d != NULL) {
        d->pere = racine;
    }

    return racine;
}

void detruit(abr a) {
    if (a != NULL) {
        detruit(a->gauche);
        detruit(a->droit);
        free(a);
    }
}

bool recherche_abr(abr a, int e) {
    if (a == NULL) {
        return false;
    }
    else if (a->etiq == e) {
        return true;
    }
    else if (a->etiq < e) {
        return recherche_abr(a->droit, e);
    }
    else {
        return recherche_abr(a->gauche, e);
    }
}

void insertion_abr(abr* a, int e) {

    // si l'arbre était vide, il devient une feuille d'étiquette e
    if (*a == NULL) {
        *a = construit(e, NULL, NULL);
    }

    // si l'insertion de e doit se faire à droite
    else if ((*a)->etiq < e) {
        // si (*a) n'a pas de sous-arbre droit, on insère ici
        if ((*a)->droit == NULL) {
            (*a)->droit = construit(e, NULL, NULL);
            (*a)->droit->pere = *a;
        }
        // sinon on insère récursivement dans le sous-arbre droit
        else {
            insertion_abr(&(*a)->droit, e);
        }
    }

    // si l'insertion de e doit se faire à gauche
    else if ((*a)->etiq > e) {
        if ((*a)->gauche == NULL) {
            (*a)->gauche = construit(e, NULL, NULL);
            (*a)->gauche->pere = *a;
        }
        else {
            insertion_abr(&(*a)->gauche, e);
        }
    }
}

// suppression par la méthode de la fusion dans un ABR

abr fusion(abr x1, abr x2) {
    if (x1 == NULL) {
        return x2;
    }
    else if (x2 == NULL) {
        return x1;
    }
    else {
        // on suit le schéma
        abr f = fusion(x1->droit, x2->gauche);
        x1->droit = x2;
        x2->pere = x1;
        x2->gauche = f;
        if (f != NULL) {
            f->pere = x2;
        }
        return x1;
    }
}

abr noeud_a_supprimer(abr a, int e) {
    // on est arrivé au bon endroit
    if (a == NULL || a->etiq == e) {
        return a;
    }
    // le nœud à supprimer est à droite
    else if (a->etiq < e) {
        return noeud_a_supprimer(a->droit, e);
    }
    // le nœud à supprimer est à gauche
    else {
        return noeud_a_supprimer(a->gauche, e);
    }
}

void suppression_abr_fusion(abr* a, int e) {
    // on récupère le nœud à supprimer
    abr a_supprimer = noeud_a_supprimer(*a, e);
    if (a_supprimer != NULL) {
        abr pere_du_noeud_supprime = a_supprimer->pere;

        // on fusionne ses fils, et on les raccroche dans l'arbre
        abr f = fusion(a_supprimer->gauche, a_supprimer->droit);
        if (f != NULL) {
            f->pere = pere_du_noeud_supprime;
        }

        // si on a supprimé la racine, la fusion des fils devient notre nouvelle racine
        if (pere_du_noeud_supprime == NULL) {
            *a = f;
        }
        else {
            // sinon on rattache la fusion des fils au père du bon côté
            if (pere_du_noeud_supprime->etiq < e) {
                pere_du_noeud_supprime->droit = f;
            }
            else {
                pere_du_noeud_supprime->gauche = f;
            }
        }

        // on libère le nœud
        free(a_supprimer);
    }
}

Arbres bicolores

Structure spécifique

enum couleur_e {rouge, noir};
typedef enum couleur_e couleur;

struct arn_s {
    int etiq;
    couleur coul;
    struct arn_s* gauche;
    struct arn_s* droit;
};
typedef struct arn_s* arn;

Fonctions

arn construit_arn(int e, couleur c, arn g, arn d) {
    arn racine = malloc(sizeof(struct arn_s));
    assert(racine != NULL);
    racine->etiq = e;
    racine->coul = c;
    racine->gauche = g;
    racine->droit = d;
    return racine;
}

void detruit_arn(arn a) {
    if (a != NULL) {
        detruit_arn(a->gauche);
        detruit_arn(a->droit);
        free(a);
    }
}

// les rotations

arn rotation_droite(arn x) {
    arn y = x->gauche;
    x->gauche = y->droit;
    y->droit = x;
    return y;
}

arn rotation_gauche(arn y) {
    arn x = y->droit;
    y->droit = x->gauche;
    x->gauche = y;
    return x;
}

// insertion

arn corrige_rouge(arn a) {
    arn y = a;
    // je traite les 4 cas problématiques dans le même ordre
    // que celui du schéma présenté dans le TP
    if (a != NULL && a->coul == noir) {
        if (a->gauche != NULL && a->gauche->coul == rouge) {
            if (a->gauche->gauche != NULL && a->gauche->gauche->coul == rouge) {
                y = rotation_droite(a);
            }
            else if (a->gauche->droit != NULL && a->gauche->droit->coul == rouge) {
                y = rotation_gauche(a->gauche);
                a->gauche = y;
                y = rotation_droite(a);
            }
        }
        else if (a->droit != NULL && a->droit->coul == rouge) {
            if (a->droit->gauche != NULL && a->droit->gauche->coul == rouge) {
                y = rotation_droite(a->droit);
                a->droit = y;
                y = rotation_gauche(a);
            }
            else if (a->droit->droit != NULL && a->droit->droit->coul == rouge) {
                y = rotation_gauche(a);
            }
        }
    }
    // une fois les rotations faites il suffit de mettre les bonnes couleurs
    if (y != a) {
        y->coul = rouge;
        y->gauche->coul = noir;
        y->droit->coul = noir;
    }
    return y;
}

void insere_en_corrigeant_rouge(arn* a, int e) {
    // insère une feuille rouge
    if (*a == NULL) {
        *a = construit_arn(e, rouge, NULL, NULL);
    }
    // on insère à droite et on corrige les couleurs
    else if ((*a)->etiq < e) {
        insere_en_corrigeant_rouge(&(*a)->droit, e);
        *a = corrige_rouge(*a);
    }
    // idem à gauche
    else if ((*a)->etiq > e) {
        insere_en_corrigeant_rouge(&(*a)->gauche, e);
        *a = corrige_rouge(*a);
    }  
}

void insertion_arn(arn* a, int e) {
    // on insère puis on remet la racine en noir
    insere_en_corrigeant_rouge(a, e);
    (*a)->coul = noir;

Tas

Structure spécifique

typedef int contenu_file_prio;
struct file_prio_s {
    int* priorites; // tableau des priorité
    contenu_file_prio* elements; // tableau des éléments
    int nb_elements; // nombre d'éléments dans la file de priorité
    int capacite_maximale; // taille de la zone allouée pour 'priorites' et 'elements'
};
typedef struct file_prio_s file_de_priorite;

Fonctions

const int CAPACITE_MAX_INITIALE = 2;

void echange(int* t, int i, int j) {
    int tmp = t[i];
    t[i] = t[j];
    t[j] = tmp;
}

// fonction pour la réallocation de zones plus grandes / plus petites
void realloue(file_de_priorite* fp, int nouvelle_capacite) {
    // allocation des nouvelles zones
    fp->capacite_maximale = nouvelle_capacite;
    int* nouvelle_zone_priorites = malloc(fp->capacite_maximale * sizeof(int));
    contenu_file_prio* nouvelle_zone_elements = malloc(fp->capacite_maximale * sizeof(contenu_file_prio));
    // recopie du contenu actuel de la file de priorité
    for (int i = 0; i < fp->nb_elements; i += 1) {
        nouvelle_zone_priorites[i] = fp->priorites[i];
        nouvelle_zone_elements[i] = fp->elements[i];
    }
    // libération des anciennes zones
    free(fp->elements);
    free(fp->priorites);
    fp->elements = nouvelle_zone_elements;
    fp->priorites = nouvelle_zone_priorites;
}

void percolation_vers_le_haut(file_de_priorite* fp, int indice_mal_place) {
    int pere = (indice_mal_place - 1) / 2;
    if (indice_mal_place != 0 && fp->priorites[indice_mal_place] < fp->priorites[pere]) {
        echange(fp->priorites, indice_mal_place, pere);
        echange(fp->elements, indice_mal_place, pere);
        percolation_vers_le_haut(fp, pere);
    }
}

void percolation_vers_le_bas(file_de_priorite* fp, int indice_mal_place) {
    int fils_gauche = 2*indice_mal_place + 1;
    int fils_droit = 2*indice_mal_place + 2;
    int indice_avec_lequel_echanger = indice_mal_place;
    if (fils_gauche < fp->nb_elements && fp->priorites[indice_mal_place] > fp->priorites[fils_gauche]) {
        indice_avec_lequel_echanger = fils_gauche;
    }
    if (fils_droit < fp->nb_elements && fp->priorites[indice_avec_lequel_echanger] > fp->priorites[fils_droit]) {
        indice_avec_lequel_echanger = fils_droit;
    }
    if (indice_avec_lequel_echanger != indice_mal_place) {
        echange(fp->priorites, indice_avec_lequel_echanger, indice_mal_place);
        echange(fp->elements, indice_avec_lequel_echanger, indice_mal_place);
        percolation_vers_le_bas(fp, indice_avec_lequel_echanger);
    }
}

file_de_priorite* fp_creer(void) {
    file_de_priorite* fp = malloc(sizeof(file_de_priorite));
    fp->capacite_maximale = CAPACITE_MAX_INITIALE;
    fp->nb_elements = 0;
    fp->priorites = malloc(fp->capacite_maximale * sizeof(int));
    fp->elements = malloc(fp->capacite_maximale * sizeof(contenu_file_prio));
    return fp;
}

bool fp_est_vide(file_de_priorite* fp) {
    return fp->nb_elements == 0;
}

void fp_enfiler(file_de_priorite* fp, contenu_file_prio element, int priorite) {
    // si on doit enfiler un élément et que la zone allouée est pleine,
    // on réalloue une zone deux fois plus grande
    if (fp->nb_elements == fp->capacite_maximale) {
        realloue(fp, 2 * fp->capacite_maximale);
    }
    // on insère tout en bas à droite puis percolation vers le haut
    fp->elements[fp->nb_elements] = element;
    fp->priorites[fp->nb_elements] = priorite;
    fp->nb_elements += 1;
    percolation_vers_le_haut(fp, fp->nb_elements-1);
}

contenu_file_prio fp_defiler(file_de_priorite* fp) {
    assert(fp->nb_elements != 0);
    // l'élément de priorité minimale se trouve à la racine
    contenu_file_prio a_renvoyer = fp->elements[0];
    // on échange la racine avec l'élément tout en bas à droite puis percolation vers le bas
    fp->nb_elements -= 1;
    if (fp->nb_elements != 0) {
        echange(fp->elements, 0, fp->nb_elements);
        echange(fp->priorites, 0, fp->nb_elements);
        percolation_vers_le_bas(fp, 0);
    }
    // si on défile un élément et que moins d'un quart de la zone est utilisée,
    // on réalloue une zone deux fois plus petite
    if (fp->nb_elements < fp->capacite_maximale / 4) {
        realloue(fp, fp->capacite_maximale / 2);
    }
    return a_renvoyer;
}

void fp_detruire(file_de_priorite* fp) {
    free(fp->elements);
    free(fp->priorites);
    free(fp);
}

Tas

Structure spécifique

struct tas_s {
    int* elements; // tableau représentant le tas
    int nb_elements; // nombre actuel de nœuds dans le tas
    int capacite_maximale; // nombre maximal de nœuds que peut contenir le tas
    bool est_tas_min; // true s'il s'agit d'un tas-min, false s'il s'agit d'un tas-max
};
typedef struct tas_s tas;

Fonctions

int fils_gauche(int i, int taille_tas) {
    assert(0 <= i && i < taille_tas);
    if (2*i + 1 >= taille_tas) {
        return -1;
    }
    return 2*i + 1;
}

int fils_droit(int i, int taille_tas) {
    assert(0 <= i && i < taille_tas);
    if (2*i + 2 >= taille_tas) {
        return -1;
    }
    return 2*i + 2;
}

int pere(int i, int taille_tas) {
    assert(0 <= i && i < taille_tas);
    if (i == 0) {
        return -1;
    }
    return (i - 1) / 2;
}

tas* tas_vide(int capacite, bool type_de_tas) {
    tas* t = malloc(sizeof(tas));
    assert(t != NULL);
    t->elements = malloc(capacite * sizeof(int));
    assert(t->elements != NULL);
    t->nb_elements = 0;
    t->capacite_maximale = capacite;
    t->est_tas_min = type_de_tas;
    return t;
}

void tas_detruit(tas* t) {
    free(t->elements);
    free(t);
}

void tas_initialise(tas* t, int n, int tableau[n]) {
    assert(t->nb_elements == 0 && n <= t->capacite_maximale);
    for (int i = 0; i < n; i += 1) {
        t->elements[i] = tableau[i];
    }
    t->nb_elements = n;
}

void percolation_vers_le_haut_tas(int* t, int taille_t, int indice_noeud_mal_place, bool tas_min) {
    int p = pere(indice_noeud_mal_place, taille_t);
    if (p != -1 && ((tas_min && t[indice_noeud_mal_place] < t[p])
                    ||
                    (!tas_min && t[indice_noeud_mal_place] > t[p]))) {
        echange(t, indice_noeud_mal_place, p);
        percolation_vers_le_haut_tas(t, taille_t, p, tas_min);
    }
}

void percolation_vers_le_bas_tas(int* t, int taille_t, int indice_noeud_mal_place, bool tas_min) {
    int fg = fils_gauche(indice_noeud_mal_place, taille_t);
    int fd = fils_droit(indice_noeud_mal_place, taille_t);
    int indice_avec_lequel_echanger = indice_noeud_mal_place;
    // on regarde si l'échange doit se faire avec le fils gauche du nœud mal placé
    if (fg != -1 && ((tas_min && t[indice_noeud_mal_place] > t[fg])
                     ||
                     (!tas_min && t[indice_noeud_mal_place] < t[fg]))) {
        indice_avec_lequel_echanger = fg;
    }
    // ou bien avec son fils droit
    if (fd != -1 && ((tas_min && t[indice_avec_lequel_echanger] > t[fd])
                     ||
                     (!tas_min && t[indice_avec_lequel_echanger] < t[fd]))) {
        indice_avec_lequel_echanger = fd;
    }
    // si un échange est nécessaire, on le fait et on continue la percolation vers le bas depuis ce nœud
    if (indice_noeud_mal_place != indice_avec_lequel_echanger) {
        echange(t, indice_noeud_mal_place, indice_avec_lequel_echanger);
        percolation_vers_le_bas_tas(t, taille_t, indice_avec_lequel_echanger, tas_min);
    }
}

int tas_lecture_minimum_ou_maximum(tas t) {
    assert (t.nb_elements > 0);
    return t.elements[0];
}

void tas_insertion(tas* t, int etiquette_a_inserer) {
    assert(t->nb_elements < t->capacite_maximale);
    t->elements[t->nb_elements] = etiquette_a_inserer;
    t->nb_elements += 1;
    percolation_vers_le_haut_tas(t->elements, t->nb_elements, t->nb_elements - 1, t->est_tas_min);
}

int tas_extraction_racine(tas* t) {
    assert(t->nb_elements > 0);
    t->nb_elements -= 1;
    if (t->nb_elements != 0) {
        echange(t->elements, 0, t->nb_elements);
        percolation_vers_le_bas_tas(t->elements, t->nb_elements, 0, t->est_tas_min);
    }
    return t->elements[t->nb_elements];
}