diff options
Diffstat (limited to 'semestre 3/structures des données')
4 files changed, 137 insertions, 28 deletions
diff --git a/semestre 3/structures des données/5- File de priorité.md b/semestre 3/structures des données/5- File de priorité.md new file mode 100644 index 0000000..94b67e2 --- /dev/null +++ b/semestre 3/structures des données/5- File de priorité.md @@ -0,0 +1,65 @@ +--- +tags: + - sorbonne + - informatique + - structure-des-données +semestre: 3 +--- +**Rattraper la définition** + +Implémentation naïve en liste chaînée, son extraction est en $O(n)$ pour récupérer la valeur minimum +|> utilisation d'une liste chaînée triée permet d'éviter ça, mais on se retrouve à être en $O(n)$ pour l'insertion +-> on fait sûrement des opérations en trop car à chaque fois on trie tout +=> on peut utiliser un arbre pour que ça soit plus opti + +Voir la définition de arbre $m$-aire en maths discrètes + +On dit qu'un arbre est complet (ou « tassé à gauche ») si tous les niveaux sont remplis, sauf si le dernier est vide ou possède un nœud à gauche +```mermaid +flowchart TB + A --> B + A --> C + B --> B1 + B --> B2 + C --> C1 + C --> C2["$\varnothing$"] +``` + +Un tas (min) est un arbre binaire complet +|> tous les nœuds doivent avoir une valeur plus grande que celle de son père +-> le minimum se trouve en haut +-> le maximum on s'est pas où il est, on sait juste que c'est une feuille +|> la topologie de l'arbre est unique +|> sa hauteur est $\lfloor\log_2(n)\rfloor$ (on va le prouver en TD) + +Propriétés des arbres complets (où $i$ est l'indice du nœud) : +- $i(\text{racine}) = 1$ +- $i(\text{fils gauche}) = 2\times i(\text{père})$ +- $i(\text{fils droit}) = 2\times i(\text{père})+1$ +- $i(\text{père}) = \lfloor i(\text{fils gauche})\rfloor = i(\text{fils droit})$ + +On peut représenter l'arbre complet à l'aide d'un tableau +|> les indices de l'arbre sont aussi les indices du tableau 🎉 +-> on peut stocker le nombre d'élément du tas dans la première case du tableau (car on commence à l'indice 1) + +```c title="Fonction de transformations d'indice" +int indicePere(int i){ + return i/2; +} +int indiceFilsGauche(int i){ + return 2*i; +} +int indiceFilsDroit(int i){ + return 2*i+1; +} +``` +Voir le diapo pour les tests d'existence + +Pour ajouter un élément, on : +1. ajoute l'élément tout en bas +2. tant que l'élément est plus grand que son père, on les échange +-> elle est en $O(\log_2 n)$ (car au pire on remonte à la racine) + +Voir le diapo pour la fonction d'ajout implémenté + +Voir le diapo pour l'extraction
\ No newline at end of file diff --git a/semestre 3/structures des données/td/td4/exo1.c b/semestre 3/structures des données/td/td4/exo1.c new file mode 100644 index 0000000..aa4f7c0 --- /dev/null +++ b/semestre 3/structures des données/td/td4/exo1.c @@ -0,0 +1,49 @@ +#include <stdio.h> + +typedef struct _Cell { + Formation* val; + struct _Cell* next; +} Cell; + +typedef struct _Formation { + char* name; + int hours; + Cell* formations; +} Formation; + +typedef struct{ + int length; + int max; + Formations** formations; +} Catalogue; + +void print_formation(Formation* f){ + if (f->hours != 0) { + printf("Cours %s\n", f->name); + return; + } + printf("%s (%d): ", f->name, f->hours); + Cell* fms = f->formations; + while (fms) { + print_formation(fms->val); + fms = fms->next; + } + printf("\n"); +} + +void print_catalogue(Catalogue* c){ + for (int i = 0; i < c->lenght; i++) { + print_formation(c->formations[i]); + } +} + +int sum_formation_hours(Formation* f, int acc){ + acc += f->hours; + Cell* fms = f->formations; + while (fms){ + acc += sum_formation_hours(fms, acc); + fms = fms->next; + } + return acc; +} + diff --git a/semestre 3/structures des données/tme/tme3-5/exo1/entreeSortieLC.c b/semestre 3/structures des données/tme/tme3-5/exo1/entreeSortieLC.c index 3adb7fb..178b7a8 100644 --- a/semestre 3/structures des données/tme/tme3-5/exo1/entreeSortieLC.c +++ b/semestre 3/structures des données/tme/tme3-5/exo1/entreeSortieLC.c @@ -12,20 +12,11 @@ Biblio* charger_n_entrees(char* nomfic, int n){ char* tmp = fgets(content, 256, f); if (!tmp) return NULL; - char* parsed[3]; - char c[256]; - int k = 0; - int l = 0; - for (int j = 0; j < 256 && content[j] != '\0'; j++){ - if (content[j] == ' '){ - c[k] = '\0'; - parsed[l++] = strdup(c); - k = 0; - } else { - c[k++] = content[j]; - } - } - inserer_en_tete(bib, atoi(parsed[0]), parsed[1], parsed[2]); + int num; + char title[256]; + char author[256]; + if (sscanf(content, "%d %s %s", &num, &title, &author) != 3) return NULL; + inserer_en_tete(bib, num, title, author); } if (fclose(f) != 0) return NULL; return bib; diff --git a/semestre 3/structures des données/tme/tme3-5/exo1/main.c b/semestre 3/structures des données/tme/tme3-5/exo1/main.c index f1e85c0..b38104a 100644 --- a/semestre 3/structures des données/tme/tme3-5/exo1/main.c +++ b/semestre 3/structures des données/tme/tme3-5/exo1/main.c @@ -27,13 +27,13 @@ int main(int argc, char** argv){ int rep; do { menu(); - char s[2]; - char* r = fgets(s, 2, stdin); - if (!r) { + char s[3]; + char* r = fgets(s, 3, stdin); + if (!r){ printf("erreur lors de la lecture :(\n"); return 3; } - s[1] = '\0'; + s[1] = '\0'; // skipping \n char rep = atoi(s); printf("\n"); switch(rep){ @@ -42,17 +42,21 @@ int main(int argc, char** argv){ afficher_biblio(bib); break; case 2: - int num; - char titre[256]; - char auteur[256]; printf("Veuillez ecrire le numero, le titre et l' auteur de l' ouvrage. \n"); - /* On suppose que le titre et l’auteur ne contiennent pas d’espace*/ - if (scanf("%d %s %s", &num, titre, auteur) == 3){ - inserer_en_tete(bib, num, titre, auteur); - printf("Ajout fait.\n"); - } else { - printf("Erreur format\n"); + char input[256]; + char* s = fgets(input, 256, stdin); + if (!s){ + printf("Entrée invalide."); + break; + } + int num; + char title[256]; + char author[256]; + if (sscanf(input, "%d %s %s", &num, &title, &author) != 3){ + printf("Entrée invalide."); + break; } + inserer_en_tete(bib, num, title, author); break; case 3: Biblio* db = rechercher_doublons(bib); @@ -61,6 +65,6 @@ int main(int argc, char** argv){ } printf("\n"); } while (rep != 0); - printf ("Merci, et au revoir.\n"); + printf("Merci, et au revoir.\n"); return 0; } |