diff options
Diffstat (limited to 'semestre 3/structures des données/tme/tme6-11')
7 files changed, 236 insertions, 0 deletions
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 + |