Cours du 24 au 28 novembre

5 files changed, 173 insertions, 4 deletions

diff --git a/semestre 3/structures des données/tme/tme6-11/00014_burma.res b/semestre 3/structures des données/tme/tme6-11/00014_burma.res
new file mode 100644
index 0000000..38e25d0
--- /dev/null
+++ b/semestre 3/structures des données/tme/tme6-11/00014_burma.res
@@ -0,0 +1,42 @@
+NbNoeuds: 12
+NbLiaisons: 15
+NbCommodites: 8
+Gamma: 3
+
+v 12 16.530000 97.380000
+v 11 25.230000 97.240000
+v 10 20.090000 94.550000
+v 9 17.200000 96.290000
+v 8 16.300000 97.380000
+v 7 21.520000 95.590000
+v 6 14.050000 98.120000
+v 5 16.470000 94.440000
+v 4 22.000000 96.050000
+v 3 22.390000 93.370000
+v 2 20.090000 92.540000
+v 1 16.470000 96.100000
+
+l 8 12
+l 11 12
+l 6 11
+l 3 11
+l 1 10
+l 3 10
+l 9 10
+l 8 9
+l 3 7
+l 1 6
+l 5 6
+l 2 5
+l 3 4
+l 2 3
+l 1 2
+
+k 5 11
+k 2 6
+k 11 8
+k 11 1
+k 8 3
+k 7 6
+k 4 6
+k 1 3
diff --git a/semestre 3/structures des données/tme/tme6-11/Hachage.c b/semestre 3/structures des données/tme/tme6-11/Hachage.c
new file mode 100644
index 0000000..11046cf
--- /dev/null
+++ b/semestre 3/structures des données/tme/tme6-11/Hachage.c
@@ -0,0 +1,88 @@
+#include "Hachage.h"
+#include "Reseau.h"
+#include <math.h>
+#include <stdlib.h>
+
+int cle(double x, double y){
+    return y + (x+y)*(x+y+1)/2;
+}
+
+int hachage(int M, double k){
+    float A = (sqrt(5)-1)/2;
+    return floor(M*(k*A-floor(k*A)));
+}
+
+TableHachage* initHachage(int M){
+    TableHachage* hash = malloc(sizeof(TableHachage));
+    hash->len = M;
+    hash->values = malloc(M*sizeof(CellNoeud));
+    for (int i = 0; i < M; i++) hash->values[i] = NULL;
+    return hash;
+}
+
+/*void freeHachage(TableHachage* hash){
+    for (int i = 0; i < hash->len; i++) freeCellHash(hash->values[i]);
+    free(hash->values);
+    free(hash);
+}*/
+
+void insertHachage(TableHachage* H, CellNoeud* cell){
+    int key = hachage(H->len, cle(cell->nd->x, cell->nd->y));
+    cell->suiv = H->values[key];
+    H->values[key] = cell;
+}
+
+Noeud* rechercheCreeNoeudHachage(Reseau* R, TableHachage* H, double x, double y){
+    int key = cle(x, y);
+    CellNoeud* val = H->values[hachage(H->len, key)];
+    // je suppose que les clés sont uniques
+    while (val && (val->nd->x != x || val->nd->y != y)) val = val->suiv;
+    if (val) return val->nd;
+    // on a besoin de créer le nœud
+    Noeud* node = rechercheCreeNoeudListe(R, x, y);
+    CellNoeud* cell = malloc(sizeof(CellNoeud));
+    cell->nd = node;
+    insertHachage(H, cell);
+    return node;
+}
+
+Reseau* reconstitueReseauHachage(Chaines *C, int M){
+    TableHachage* hash = initHachage(M);
+    Reseau* R = (Reseau*) malloc(sizeof(Reseau));
+    CellChaine* chain = C->chaines;
+    while (chain){
+        CellPoint* points = chain->points;
+        CellNoeud* before;
+        CellNoeud* beforeTwice;
+        CellCommodite* com = malloc(sizeof(CellCommodite));
+        com->extrA = NULL;
+        while (points){
+            Noeud* node = rechercheCreeNoeudHachage(R, hash, points->x, points->y);
+            if (!com->extrA) com->extrA = node;
+            // 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;
+            if (!points->suiv) com->extrB = node;
+            points = points->suiv;
+        }
+        if (beforeTwice && before){
+            before->nd->voisins = beforeTwice; // set before voisins
+        }
+        com->suiv = R->commodites;
+        R->commodites = com;
+        chain = chain->suiv;
+    }
+    return R;
+}
diff --git a/semestre 3/structures des données/tme/tme6-11/Hachage.h b/semestre 3/structures des données/tme/tme6-11/Hachage.h
new file mode 100644
index 0000000..2faca4c
--- /dev/null
+++ b/semestre 3/structures des données/tme/tme6-11/Hachage.h
@@ -0,0 +1,20 @@
+#ifndef HACHAGE_H
+#define HACHAGE_H
+
+#include "Reseau.h"
+
+typedef struct{
+    int len;
+    CellNoeud** values;
+} TableHachage;
+
+int cle(double x, double y);
+int hachage(int M, double k);
+
+Noeud* rechercheCreeNoeudHachage(Reseau* R, TableHachage* H, double x, double y);
+TableHachage* initHachage(int M);
+void freeHachage(TableHachage* hash);
+
+Reseau* reconstitueReseauHachage(Chaines *C, int M);
+
+#endif // !HACHAGE_H
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
index cbdaa88..151bcfe 100644
--- a/semestre 3/structures des données/tme/tme6-11/Reseau.c
+++ b/semestre 3/structures des données/tme/tme6-11/Reseau.c
@@ -27,8 +27,11 @@ Reseau* reconstitueReseauListe(Chaines *C){
         CellPoint* points = chain->points;
         CellNoeud* before;
         CellNoeud* beforeTwice;
+        CellCommodite* com = malloc(sizeof(CellCommodite));
+        com->extrA = NULL;
         while (points){
             Noeud* node = rechercheCreeNoeudListe(R, points->x, points->y);
+            if (!com->extrA) com->extrA = node;
             // represents voisins of node
             CellNoeud* cellNode = (CellNoeud*) malloc(sizeof(CellNoeud));
             cellNode->nd = node;
@@ -42,12 +45,28 @@ Reseau* reconstitueReseauListe(Chaines *C){
             }
             beforeTwice = before;
             before = cellNode;
+            if (!points->suiv) com->extrB = node;
             points = points->suiv;
         }
         if (beforeTwice && before){
             before->nd->voisins = beforeTwice; // set before voisins
         }
+        com->suiv = R->commodites;
+        R->commodites = com;
         chain = chain->suiv;
     }
     return R;
 }
+
+int nbLiaisons(Reseau *R){
+    return 0;
+}
+
+int nbCommodites(Reseau *R){
+    int i;
+    CellCommodite* com = R->commodites;
+    for (i = 0; com; i++) com = com->suiv;
+    return i;
+}
+
+void afficheReseauSVG(Reseau *R, char* nomInstance);
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
index dc618a1..dbb2d77 100644
--- a/semestre 3/structures des données/tme/tme6-11/Reseau.h
+++ b/semestre 3/structures des données/tme/tme6-11/Reseau.h
@@ -5,9 +5,9 @@
 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 */
+typedef struct cellNoeud {
+    Noeud *nd;                  /* Pointeur vers le noeud stock\'e */
+    struct cellNoeud *suiv;     /* Cellule suivante dans la liste */
 } CellNoeud;
 
 /* Noeud du reseau */
@@ -19,7 +19,7 @@ struct noeud{
 
 /* Liste chainee de commodites */
 typedef struct cellCommodite {
-    Noeud *extrA, *extrB;       /* Noeuds aux extremites de la commodite */
+    Noeud *extrA, *extrB;           /* Noeuds aux extremites de la commodite */
     struct cellCommodite *suiv;     /* Cellule suivante dans la liste */
 } CellCommodite;