diff options
Diffstat (limited to 'semestre 3/structures des données/tme')
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; |