From 20fc727d4f954eb2109b71a7686c3107fdfa4bbf Mon Sep 17 00:00:00 2001 From: Anhgelus Morhtuuzh Date: Fri, 21 Nov 2025 18:37:48 +0100 Subject: Cours du 3 au 21 novembre ce qui fait 3 semaines en philo et une semaine en info --- .../structures des donn\303\251es/td/td2/exo3" | Bin 16160 -> 16184 bytes .../structures des donn\303\251es/td/td2/exo3.c" | 4 +- .../structures des donn\303\251es/td/td3/exo4.c" | 5 +- .../structures des donn\303\251es/td/td7/exo1.c" | 90 +++++++++++++++++++++ .../structures des donn\303\251es/td/td7/exo2.c" | 39 +++++++++ 5 files changed, 134 insertions(+), 4 deletions(-) create mode 100644 "semestre 3/structures des donn\303\251es/td/td7/exo1.c" create mode 100644 "semestre 3/structures des donn\303\251es/td/td7/exo2.c" (limited to 'semestre 3/structures des données/td') diff --git "a/semestre 3/structures des donn\303\251es/td/td2/exo3" "b/semestre 3/structures des donn\303\251es/td/td2/exo3" index b3ee123..d2f0aed 100755 Binary files "a/semestre 3/structures des donn\303\251es/td/td2/exo3" and "b/semestre 3/structures des donn\303\251es/td/td2/exo3" differ diff --git "a/semestre 3/structures des donn\303\251es/td/td2/exo3.c" "b/semestre 3/structures des donn\303\251es/td/td2/exo3.c" index 55b9242..d94c8dc 100644 --- "a/semestre 3/structures des donn\303\251es/td/td2/exo3.c" +++ "b/semestre 3/structures des donn\303\251es/td/td2/exo3.c" @@ -1,5 +1,4 @@ #include -#include #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\303\251es/td/td3/exo4.c" "b/semestre 3/structures des donn\303\251es/td/td3/exo4.c" index 02134c8..09d6d4a 100644 --- "a/semestre 3/structures des donn\303\251es/td/td3/exo4.c" +++ "b/semestre 3/structures des donn\303\251es/td/td3/exo4.c" @@ -1,12 +1,13 @@ +#include 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\303\251es/td/td7/exo1.c" "b/semestre 3/structures des donn\303\251es/td/td7/exo1.c" new file mode 100644 index 0000000..ba5d6a4 --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/td/td7/exo1.c" @@ -0,0 +1,90 @@ +#include +#include + +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\303\251es/td/td7/exo2.c" "b/semestre 3/structures des donn\303\251es/td/td7/exo2.c" new file mode 100644 index 0000000..3e67451 --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/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; +} -- cgit v1.2.3