Cours du 3 au 21 novembre

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

5 files changed, 134 insertions, 4 deletions

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;
+}