14 files changed, 467 insertions, 5 deletions
diff --git a/semestre 3/structures des données/8- Parcours de graphe.md b/semestre 3/structures des données/8- Parcours de graphe.md
new file mode 100644
index 0000000..4bfab39
--- /dev/null
+++ b/semestre 3/structures des données/8- Parcours de graphe.md
@@ -0,0 +1,97 @@
+---
+tags:
+  - sorbonne
+  - informatique
+  - structure-des-données
+semestre: 3
+---
+On cherche à apprendre à parcourir tous les chemins possibles
+|> permet de savoir si un sommet $r$ est accessible depuis un sommet $s$
+Pires cas :
+- $r$ n'est pas accessible
+- trouver $r$ en dernier
+## Sous-parcours
+On appelle la racine du parcours est l'endroit où on commence
+
+Un algorithme de « sous-parcours » est un algorithme de parcours commençant à la racine du parcours (noté $r$)
+|> formellement, il retourne $L=(s_1,\ldots,s_k)$ telle que :
+- $s_1 = r$
+- $s1,\ldots,s_k$ est l'ensemble des sommets accessibles à partir de $r$
+- pour tout $i\in\{2,\ldots,k\}$, il existe $j\in\{1,\ldots,i-1\}$ telle que $(s_j,s_i)$ est un arc (ou une arête) du graphe (on parlera de bordure)
+
+**Vocabulaire**
+- **Sommet visité** = un sommet qui a été ajouté au sous-parcours
+- **Sommet non-visité** = un sommet qui n’a pas (encore) été ajouté au sous-parcours
+- **Sommet ouvert** = un sommet visité dans un cadre dont tous les descendants (ou sommets accessibles) n’ont pas encore été visités
+- **Sommet fermé** = un sommet visité dont tous les descendants (ou sommets accessibles) ont été visités
+- **Bordure d’une liste de sommet** = étant donné une liste L de sommets visités, la bordure B(L) est l’ensemble des sommets non-visités qui sont successeurs (ou voisins) d’au moins un sommet dans la liste ; formellement, dans le graphe $G = (S, A)$, on a :
+ $$ B(L) = \{s\in S\backslash L| \exists t \in L, (t,s)\in A\}~\text{en orienté} $$
+ $$ B(L) = \{s\in S\backslash L| \exists t \in L, \{t,s\}\in A\}~\text{en non-orienté} $$
+
+```
+L = Liste(r)
+Tant que B(L) n'est pas vide :
+	Choisir un sommet s dans B(L)
+	Ajouter s à la fin de la liste L
+Fin Tant que
+```
+À la fin de ce parcours
+|> tous les sommets visités sont fermés
+|> un sommet non-visité est inaccessible depuis $r$
+
+Cette algo est en $O(n^2)$ car $B(L)$ est en $O(n)$
+|> pas ouf
+-> pour éviter d'être aussi lent, on peut facilement mettre à jour B(L) à chaque itération
+|> transforme l'algo en $O(n)$
+## Parcours
+Un algorithme de « parcours » doit parcourir tous les nœuds
+|> besoin de relancer l'algo de sous-parcours quand il s'arrête
+|> les racines de tous les sous-parcours sont des points de régénération
+
+```
+L=Liste(r)
+Tant qu’il existe un sommet non-visité :
+	Si B(L) est non vide:
+		Choisir un sommet s dans B(L)
+	Sinon:
+		Choisir un sommet s non visité  <--- il n'existe pas de bon choix
+	Fin Si
+	Ajouter s à la fin de la liste L
+Fin Tant que
+```
+## Stratégie de parcours
+Quand on choisit un sommet, on a plusieurs possibilités :
+- aléatoire
+- profondeur -> va le plus loin possible dans le chemin courant
+- largeur -> évite d'aller le plus loin possible
+- le plus proche (au sens d'une distance)
+- etc
+
+Elles permettent toutes de trouver les sommets accessibles depuis $r$
+|> mais les trois dernières donnent des informations sur le graphe !
+### Parcours en profondeur
+Parcours en profondeur (ou DFS, *deep first search*) est le fait de choisir systématiquement d'explorer un successeur (ou un voisin) du dernier sommet visité ouvert
+
+```
+L=Liste(r)
+Tant que B(L) n'est pas vide :
+	Choisir un sommet s dans B(L) qui est successeur (ou voisin) du dernier sommet ouvert de L
+	L = union de L et {s}
+Fin Tant que
+```
+
+Dans ce type de parcours, la bordure est... une pile !
+|> version récursive n'a pas besoin de pile explicite
+|> version itérative a besoin d'expliciter la pile (et donc de construire une struct pour)
+
+**voir le code sur les diapos**
+
+Complexité temporelle, chaque ligne de code est exécuté :
+- une fois
+- au maximum une fois par sommet ($n$)
+- au maximum une fois par arcs ou arêtes ($m$ ou $2m$)
+-> $O(n+m)$
+
+Occupation mémoire est similaire pour itérative et récursive pour des $n$ pas trop grand
+|> par contre, comme récursive n'est pas terminal, elle prendra plus de place pour des $n$ très grands
+### Parcours en largeur
diff --git a/semestre 3/structures des données/td/td2/exo3 b/semestre 3/structures des données/td/td2/exo3
index b3ee123..d2f0aed 100755
--- a/semestre 3/structures des données/td/td2/exo3
+++ b/semestre 3/structures des données/td/td2/exo3
diff --git a/semestre 3/structures des données/td/td2/exo3.c b/semestre 3/structures des données/td/td2/exo3.c
index 55b9242..d94c8dc 100644
--- a/semestre 3/structures des données/td/td2/exo3.c
+++ b/semestre 3/structures des données/td/td2/exo3.c
@@ -1,5 +1,4 @@
 #include <stdio.h>
-#include <stdlib.h>
 #include "LDC.h"
 
 int strToInt(char** s){
@@ -49,8 +48,9 @@ int algo(char* expr){
     return res;
 }
 
-void main(){
+int main(){
     char* s = "(((4+2)-5)*4)";
     int res = algo(s);
     printf("%s = %d\n", s, res);
+    return 0;
 }
diff --git a/semestre 3/structures des données/td/td3/exo4.c b/semestre 3/structures des données/td/td3/exo4.c
index 02134c8..09d6d4a 100644
--- a/semestre 3/structures des données/td/td3/exo4.c
+++ b/semestre 3/structures des données/td/td3/exo4.c
@@ -1,12 +1,13 @@
+#include <stdlib.h>
 typedef struct cell{
     int val;
     int key;
-    cell* next;
+    struct cell* next;
 } Cell;
 
 typedef struct hashMap{
     int size;
-    cell** map;
+    struct cell** map;
 } HashMap;
 
 void mapInsert(HashMap* map, int val){
diff --git a/semestre 3/structures des données/td/td7/exo1.c b/semestre 3/structures des données/td/td7/exo1.c
new file mode 100644
index 0000000..ba5d6a4
--- /dev/null
+++ b/semestre 3/structures des données/td/td7/exo1.c
@@ -0,0 +1,90 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+typedef struct Road{
+    int u, v;
+    double dist;
+} Road;
+
+typedef struct RoadCell{
+    Road* road;
+    struct RoadCell* next;
+} RoadCell;
+
+typedef struct City{
+    int id;
+    int x, y;
+    RoadCell* roads; 
+} City;
+
+City** init_cities(int n){
+    City** cities = (City**) malloc(sizeof(City)*n);
+    for (int i = 0; i < n; i++){
+        cities[i] = (City*) malloc(sizeof(City));
+        cities[i]->id = i;
+        cities[i]->x = 0;
+        cities[i]->y = 0;
+        cities[i]->roads = NULL; 
+    }
+    return cities;
+}
+
+void update_city(City* city, int x, int y){
+    city->x = x;
+    city->y = x;
+}
+
+void add_route(City* c1, City* c2, double dist){
+    Road* road = (Road*) malloc(sizeof(Road));
+    road->u = c1->id;
+    road->v = c2->id;
+    road->dist = dist;
+
+    RoadCell* road_1 = (RoadCell*) malloc(sizeof(RoadCell));
+    road_1->road = road;
+    road_1->next = c1->roads;
+    c1->roads = road_1;
+
+    RoadCell* road_2 = (RoadCell*) malloc(sizeof(RoadCell));
+    road_2->road = road;
+    road_2->next = c2->roads;
+    c2->roads = road_2;
+}
+
+void print(City** cities, int n){
+    printf("Cities len: %d\n", n);
+    for (int i = 0; i < n; i++){
+        printf("city %d: {x: %d, y: %d}, roads [", i, cities[i]->x, cities[i]->y);
+        RoadCell* roads = cities[i]->roads;
+        while (roads){
+            Road* road = roads->road;
+            printf("{from: %d, to: %d, dist: %f},", road->u, road->v, road->dist);
+            roads = roads->next;
+        }
+        printf("]\n");
+    }
+}
+
+void free_cities(City** cities, int n){
+    for (int i = 0; i < n; i++) {
+        City* city = cities[i];
+        while (city->roads){
+            //TODO: free(city->roads->road)
+            RoadCell* old = city->roads;
+            city->roads = city->roads->next;
+            free(old);
+        }
+        free(city);
+    }
+    free(cities);
+}
+
+int main(){
+    City** cities = init_cities(4);
+    add_route(cities[0], cities[1], 3);
+    add_route(cities[1], cities[2], 4);
+    add_route(cities[0], cities[2], 8);
+    add_route(cities[3], cities[1], 4.5);
+    print(cities, 4);
+    return 0;
+}
diff --git a/semestre 3/structures des données/td/td7/exo2.c b/semestre 3/structures des données/td/td7/exo2.c
new file mode 100644
index 0000000..3e67451
--- /dev/null
+++ b/semestre 3/structures des données/td/td7/exo2.c
@@ -0,0 +1,39 @@
+// complexite = O(2n) = O(n)
+void degre_matrice(int** M, int n, int u, int* deg_e, int* deg_s){
+    for (int i = 0; i < n; i++) if (M[u][i]) (*deg_e)++;
+    for (int i = 0; i < n; i++) if (M[i][u]) (*deg_s)++;
+}
+
+typedef struct Cell{
+    int to;
+    struct Cell* next;
+} Cell;
+
+typedef struct List{
+    int val;
+    Cell* linked;
+} List;
+
+// complexite = O(degre max de n)
+int degre_entrant_LA(List** l, int n, int u){
+    int acc = 0;
+    Cell* c = l[u]->linked;
+    while (c){
+        acc++;
+        c = c->next;
+    }
+    return acc;
+}
+
+// complexite = O(n+(degre max de n))
+int degre_sortant_LA(List** l, int n, int u){
+    int acc = 0;
+    for (int i = 0; i < n; i++){
+        Cell* c = l[i]->linked;
+        while (c){
+            if (c->to == u) acc++;
+            c = c->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 178b7a8..6a3741b 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
@@ -1,6 +1,5 @@
 #include "entreeSortieLC.h"
 #include <stdio.h>
-#include <stdlib.h>
 #include <string.h>
 
 Biblio* charger_n_entrees(char* nomfic, int n){
diff --git a/semestre 3/structures des données/tme/tme6-11/00014_burma.cha b/semestre 3/structures des données/tme/tme6-11/00014_burma.cha
new file mode 100644
index 0000000..74c69a2
--- /dev/null
+++ b/semestre 3/structures des données/tme/tme6-11/00014_burma.cha
@@ -0,0 +1,10 @@
+NbChain: 8
+Gamma: 3
+0 3 25.23 97.24 14.05 98.12 16.47 94.44 
+1 3 14.05 98.12 16.47 96.1 20.09 92.54 
+2 3 16.3 97.38 16.53 97.38 25.23 97.24 
+3 4 16.47 96.1 20.09 94.55 22.39 93.37 25.23 97.24 
+4 4 22.39 93.37 20.09 94.55 17.2 96.29 16.3 97.38 
+5 5 14.05 98.12 16.47 94.44 20.09 92.54 22.39 93.37 21.52 95.59 
+6 5 14.05 98.12 16.47 94.44 20.09 92.54 22.39 93.37 22 96.05 
+7 3 22.39 93.37 20.09 92.54 16.47 96.1 
diff --git a/semestre 3/structures des données/tme/tme6-11/Chaine.c b/semestre 3/structures des données/tme/tme6-11/Chaine.c
new file mode 100644
index 0000000..d25f38e
--- /dev/null
+++ b/semestre 3/structures des données/tme/tme6-11/Chaine.c
@@ -0,0 +1,54 @@
+#include "Chaine.h"
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+Chaines* lectureChaines(FILE* f){
+    char s[256];
+    char* err = fgets(s, 256, f);
+    if (!err) return NULL;
+    int nbChain;
+    sscanf(s, "NbChain: %d", &nbChain);
+
+    err = fgets(s, 256, f);
+    if (!err) return NULL;
+    int gamma;
+    sscanf(s, "Gamma: %d", &gamma);
+
+    Chaines* chains = (Chaines*) malloc(sizeof(Chaines));
+    chains->nbChaines = nbChain;
+    chains->gamma = gamma;
+    
+    for (int i = 0; i < nbChain; i++){
+        err = fgets(s, 256, f);
+        if (!err) {
+            free(chains); // avoiding a memory leak
+            return NULL;
+        }
+        CellChaine* chain = (CellChaine*) malloc(sizeof(CellChaine));
+        chain->points = NULL;
+        chain->suiv = chains->chaines; 
+        chains->chaines = chain; 
+        int nbPoints;
+        sscanf(s, "%d %d %s", &chain->numero, &nbPoints, s);
+        for (int j = 0; j < nbPoints; j++){
+            CellPoint* point = (CellPoint*) malloc(sizeof(CellPoint));
+            point->suiv = chain->points;
+            chain->points = point;
+            if (j < nbPoints-1) sscanf(s, "%lf %lf %s", &point->x, &point->y, s);
+            else sscanf(s, "%lf %lf", &point->x, &point->y);
+        }
+    }
+    return chains;
+}
+
+void ecrireChaines(Chaines* c, FILE* f){
+    fprintf(f, "NbChain: %d\n", c->nbChaines); 
+    fprintf(f, "Gamma: %d\n", c->gamma);
+    CellChaine** chains = (CellChaine**) malloc(sizeof(CellChaine)*c->nbChaines);
+    CellChaine* chain = c->chaines;
+    for (int i = 0; i < c->nbChaines; i++){
+        chains[i - c->nbChaines - 1] = chain;
+        chain = chain->suiv;
+    }
+}
diff --git a/semestre 3/structures des données/tme/tme6-11/Chaine.h b/semestre 3/structures des données/tme/tme6-11/Chaine.h
new file mode 100644
index 0000000..3539be7
--- /dev/null
+++ b/semestre 3/structures des données/tme/tme6-11/Chaine.h
@@ -0,0 +1,31 @@
+#ifndef __CHAINE_H__
+#define __CHAINE_H__	
+#include<stdio.h>
+
+/* Liste chainee de points */
+typedef struct cellPoint{
+  double x,y;                   /* Coordonnees du point */
+  struct cellPoint *suiv;       /* Cellule suivante dans la liste */
+} CellPoint;
+
+/* Celllule d une liste (chainee) de chaines */
+typedef struct cellChaine{
+  int numero;                   /* Numero de la chaine */
+  CellPoint *points;            /* Liste des points de la chaine */
+  struct cellChaine *suiv;      /* Cellule suivante dans la liste */
+} CellChaine;
+
+/* L'ensemble des chaines */
+typedef struct {
+  int gamma;                    /* Nombre maximal de fibres par cable */
+  int nbChaines;                /* Nombre de chaines */
+  CellChaine *chaines;          /* La liste chainee des chaines */
+} Chaines;
+
+Chaines* lectureChaines(FILE *f);
+void ecrireChaines(Chaines *C, FILE *f);
+void afficheChainesSVG(Chaines *C, char* nomInstance);
+double longueurTotale(Chaines *C);
+int comptePointsTotal(Chaines *C);
+
+#endif	
diff --git a/semestre 3/structures des données/tme/tme6-11/Makefile b/semestre 3/structures des données/tme/tme6-11/Makefile
new file mode 100644
index 0000000..b79e199
--- /dev/null
+++ b/semestre 3/structures des données/tme/tme6-11/Makefile
@@ -0,0 +1,11 @@
+build: Chaine.o Reseau.o ReconstitueReseau.o
+	gcc -o main Chaine.o Reseau.o ReconstitueReseau.o 
+
+ReconstitueReseau.o:
+	gcc -c ReconstitueReseau.c
+
+Chaine.o:
+	gcc -c Chaine.h Chaine.c
+
+Reseau.o:
+	gcc -c Reseau.h Reseau.c
diff --git a/semestre 3/structures des données/tme/tme6-11/ReconstitueReseau.c b/semestre 3/structures des données/tme/tme6-11/ReconstitueReseau.c
new file mode 100644
index 0000000..449f534
--- /dev/null
+++ b/semestre 3/structures des données/tme/tme6-11/ReconstitueReseau.c
@@ -0,0 +1,36 @@
+#include "Chaine.h"
+#include "Reseau.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+int main(int argc, char** argv){
+    if (argc != 3){
+        printf("nombre d'argument invalide, besoin de 3\n");
+        return 1;
+    }
+    char* file = argv[1];
+    int id = atoi(argv[2]);
+    if (id > 2 || id < 0){
+        printf("le deuxième argument doit être entre 0 et 2 inclus\n");
+        return 1;
+    }
+    FILE* f = fopen(file, "r");
+    if (!f){
+        printf("impossible d'ouvrir le fichier '%s'\n", file);
+        return 2;
+    }
+    Chaines* C = lectureChaines(f);
+    if (!C){
+        printf("erreur lors du parsing\n");
+        return 3;
+    }
+    switch (id) {
+    case 0:
+        Reseau* res = reconstitueReseauListe(C);
+        break;
+    default:
+        printf("opération pas implémentée\n");
+        return 4;
+    }
+    return 0;
+}
diff --git a/semestre 3/structures des données/tme/tme6-11/Reseau.c b/semestre 3/structures des données/tme/tme6-11/Reseau.c
new file mode 100644
index 0000000..cbdaa88
--- /dev/null
+++ b/semestre 3/structures des données/tme/tme6-11/Reseau.c
@@ -0,0 +1,53 @@
+#include "Chaine.h"
+#include <stdlib.h>
+#include "Reseau.h"
+
+CellNoeud* initNode(Reseau* R, double x, double y){
+    CellNoeud* node = (CellNoeud*) malloc(sizeof(CellNoeud));
+    node->nd = (Noeud*) malloc(sizeof(Noeud));
+    node->nd->num = ++R->nbNoeuds;
+    node->nd->x = x;
+    node->nd->y = y;
+    node->suiv = R->noeuds;
+    R->noeuds = node;
+    return node;
+}
+
+Noeud* rechercheCreeNoeudListe(Reseau *R, double x, double y){
+    CellNoeud* node = R->noeuds;
+    while (node && (node->nd->x != x || node->nd->y != y)) node = node->suiv;
+    if (node) return node->nd;
+    return initNode(R, x, y)->nd;
+}
+
+Reseau* reconstitueReseauListe(Chaines *C){
+    Reseau* R = (Reseau*) malloc(sizeof(Reseau));
+    CellChaine* chain = C->chaines;
+    while (chain){
+        CellPoint* points = chain->points;
+        CellNoeud* before;
+        CellNoeud* beforeTwice;
+        while (points){
+            Noeud* node = rechercheCreeNoeudListe(R, points->x, points->y);
+            // represents voisins of node
+            CellNoeud* cellNode = (CellNoeud*) malloc(sizeof(CellNoeud));
+            cellNode->nd = node;
+            cellNode->suiv = NULL;
+            if (beforeTwice){
+                CellNoeud* cell = (CellNoeud*) malloc(sizeof(CellNoeud));
+                cell->nd = node;
+                cell->suiv = NULL;
+                beforeTwice->suiv = cell; // link beforeTwice to current
+                before->nd->voisins = beforeTwice; // set before voisins
+            }
+            beforeTwice = before;
+            before = cellNode;
+            points = points->suiv;
+        }
+        if (beforeTwice && before){
+            before->nd->voisins = beforeTwice; // set before voisins
+        }
+        chain = chain->suiv;
+    }
+    return R;
+}
diff --git a/semestre 3/structures des données/tme/tme6-11/Reseau.h b/semestre 3/structures des données/tme/tme6-11/Reseau.h
new file mode 100644
index 0000000..dc618a1
--- /dev/null
+++ b/semestre 3/structures des données/tme/tme6-11/Reseau.h
@@ -0,0 +1,41 @@
+#ifndef __RESEAU_H__
+#define __RESEAU_H__
+#include "Chaine.h"
+
+typedef struct noeud Noeud;
+
+/* Liste chainee de noeuds (pour la liste des noeuds du reseau ET les listes des voisins de chaque noeud) */
+typedef struct cellnoeud {
+    Noeud *nd;               /* Pointeur vers le noeud stock\'e */
+    struct cellnoeud *suiv;         /* Cellule suivante dans la liste */
+} CellNoeud;
+
+/* Noeud du reseau */
+struct noeud{
+   int num;                        /* Numero du noeud */
+   double x, y;                    /* Coordonnees du noeud*/
+   CellNoeud *voisins;             /* Liste des voisins du noeud */
+};
+
+/* Liste chainee de commodites */
+typedef struct cellCommodite {
+    Noeud *extrA, *extrB;       /* Noeuds aux extremites de la commodite */
+    struct cellCommodite *suiv;     /* Cellule suivante dans la liste */
+} CellCommodite;
+
+/* Un reseau */
+typedef struct {
+    int nbNoeuds;                   /* Nombre de noeuds du reseau */
+    int gamma;                      /* Nombre maximal de fibres par cable */
+    CellNoeud *noeuds;              /* Liste des noeuds du reseau */
+    CellCommodite *commodites;      /* Liste des commodites a relier */
+} Reseau;
+
+Noeud* rechercheCreeNoeudListe(Reseau *R, double x, double y);
+Reseau* reconstitueReseauListe(Chaines *C);
+void ecrireReseau(Reseau *R, FILE *f);
+int nbLiaisons(Reseau *R);
+int nbCommodites(Reseau *R);
+void afficheReseauSVG(Reseau *R, char* nomInstance);
+#endif
+