Cours du 3 au 21 novembre

ce qui fait 3 semaines en philo et une semaine en info

8 files changed, 236 insertions, 1 deletions

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
+