Cours du 22 au 26 septembre

6 files changed, 244 insertions, 0 deletions

diff --git a/semestre 3/structures des données/td/td2/LDC.h b/semestre 3/structures des données/td/td2/LDC.h
new file mode 100644
index 0000000..78524d3
--- /dev/null
+++ b/semestre 3/structures des données/td/td2/LDC.h
@@ -0,0 +1,39 @@
+#ifndef LDC_H
+#define LDC_H
+
+typedef struct cell {
+    struct cell* after;
+    struct cell* before;
+    int val;
+} Cell;
+
+typedef struct {
+    Cell* first;
+    Cell* last;
+} ChainedList;
+
+Cell* creerElement(int val);
+
+ChainedList* initialiserListe(ChainedList* list);
+
+ChainedList* creerListe();
+
+int listeVide(ChainedList* list);
+
+void insererEnTete(ChainedList* list, int val);
+
+void insererEnFin(ChainedList* list, int val);
+
+void afficher(ChainedList* list);
+
+ChainedList* rechercher(ChainedList* list, int val);
+
+void supprimerElement(ChainedList* list, Cell* el);
+
+void supprimerTete(ChainedList* list);
+
+void supprimerFin(ChainedList* list);
+
+void desalloueListe(ChainedList* list);
+
+#endif // !LDC_H
diff --git a/semestre 3/structures des données/td/td2/Makefile b/semestre 3/structures des données/td/td2/Makefile
new file mode 100644
index 0000000..592f4f2
--- /dev/null
+++ b/semestre 3/structures des données/td/td2/Makefile
@@ -0,0 +1,8 @@
+all: exo3.o exo1.o
+	gcc -o exo3 exo3.o exo1.o
+
+exo1.o: LDC.h exo1.c
+	gcc -c LDC.h exo1.c
+
+exo3.o: exo3.c
+	gcc -c exo3.c
diff --git a/semestre 3/structures des données/td/td2/exo1.c b/semestre 3/structures des données/td/td2/exo1.c
new file mode 100644
index 0000000..752828a
--- /dev/null
+++ b/semestre 3/structures des données/td/td2/exo1.c
@@ -0,0 +1,117 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include "LDC.h"
+
+Cell* creerElement(int val){
+    Cell* cell = (Cell*) malloc(sizeof(Cell));
+    cell->val = val;
+    cell->after = NULL;
+    cell->before = NULL;
+    return cell;
+}
+
+ChainedList* initialiserListe(ChainedList* list){
+    list->first = NULL;
+    list->last = NULL;
+    return list;
+}
+
+ChainedList* creerListe(){
+    ChainedList* list = (ChainedList*) malloc(sizeof(ChainedList));
+    return initialiserListe(list);
+}
+
+int listeVide(ChainedList* list){
+    /* we assume in this case that first is equal to last */
+    return !list->first;
+}
+
+void insererEnTete(ChainedList* list, int val){
+    Cell* cell = creerElement(val);
+    cell->after = list->first;
+    if (listeVide(list)){
+        list->last = cell;
+    } else {
+        list->first->before = cell;
+    }
+    list->first = cell;
+}
+
+void insererEnFin(ChainedList* list, int val){
+    Cell* cell = creerElement(val);
+    cell->before = list->last;
+    if (listeVide(list)){
+        list->first = cell;
+    } else {
+        list->last->after = cell;
+    }
+    list->last = cell;
+}
+
+void afficher(ChainedList* list){
+    Cell* cell = list->last;
+    printf("[ ");
+    while (cell){
+        printf("%d ", cell->val);
+        cell = cell->before;
+    }
+    printf("]\n");
+}
+
+ChainedList* rechercher(ChainedList* list, int val){
+    Cell* cell = list->last;
+    while (cell){
+        if (cell->val == val){
+            return list;
+        }
+        cell = cell->before;
+    }
+    return NULL;
+}
+
+void supprimerElement(ChainedList* list, Cell* el){
+    if (listeVide(list)){
+        return;
+    }
+    if (el == list->last){
+        list->last = list->last->before;
+        if (!list->last){
+            list->first = NULL;
+        }
+        return;
+    }
+    if (el == list->first){
+        list->first = list->first->after;
+        if (!list->first){
+            list->last = NULL;
+        }
+        return;
+    }
+    Cell* cell = list->last;
+    while (cell && cell != el){
+        cell = cell->before;
+    }
+    if (cell != el){
+        return;
+    }
+    cell->before->after = cell->after;
+    free(cell);
+}
+
+void supprimerTete(ChainedList* list){
+    supprimerElement(list, list->first);
+}
+
+void supprimerFin(ChainedList* list){
+    supprimerElement(list, list->last);
+}
+
+void desalloueListe(ChainedList* list){
+    Cell* cell = list->last;
+    while (cell){
+        Cell* before = cell->before;
+        free(cell);
+        cell = before; 
+    }
+    free(list);
+}
diff --git a/semestre 3/structures des données/td/td2/exo2.c b/semestre 3/structures des données/td/td2/exo2.c
new file mode 100644
index 0000000..166616c
--- /dev/null
+++ b/semestre 3/structures des données/td/td2/exo2.c
@@ -0,0 +1,24 @@
+#include "LDC.h"
+
+/* N is the number of guichet */
+#define N 15
+
+ChainedList** creerBureauPoste(){
+    ChainedList** postes = (ChainedList**) malloc(N*sizeof(ChainedList));
+    return postes;
+}
+
+void afficherPoste(ChainedList** guichets){
+    for (int i = 0; i < N; i++){
+        afficher(guichets[i]);
+    }
+}
+
+ChainedList* ajouterAuGuichet(ChainedList* guichet, int id){
+    return insererEnFin(guichet, creerElement(id));
+}
+
+ChainedList* appelerAuGuichet(ChainedList* guichet){
+    return supprimerTete(guichet);
+}
+
diff --git a/semestre 3/structures des données/td/td2/exo3 b/semestre 3/structures des données/td/td2/exo3
new file mode 100755
index 0000000..b3ee123
--- /dev/null
+++ 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
new file mode 100644
index 0000000..55b9242
--- /dev/null
+++ b/semestre 3/structures des données/td/td2/exo3.c
@@ -0,0 +1,56 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include "LDC.h"
+
+int strToInt(char** s){
+    int n = -1;
+    while (*s && **s != '\0' && **s - '0' < 10 && **s - '0' >= 0){
+        if (n == -1) n = 0;
+        n *= 10;
+        n += **s - '0';
+        (*s)++;
+    }
+    // avoid skipping the char is it was not converted
+    if (n >= 0) (*s)--;
+    return n;
+}
+
+int algo(char* expr){
+    char* c = expr;
+    ChainedList* stack = creerListe();
+    while (c && *c != '\0'){
+        if (*c == ')'){
+            int o2 = stack->last->val;
+            supprimerFin(stack);
+            char op = (char) stack->last->val;
+            supprimerFin(stack);
+            int o1 = stack->last->val;
+            supprimerFin(stack);
+
+            int res = 0;
+            if (op == '+'){
+                res += o1 + o2;
+            } else if (op == '-'){
+                res += o1 - o2;
+            } else if (op == '*'){
+                res += o1 * o2;
+            } else if (op == '/'){
+                res += o1 / o2;
+            }
+            insererEnFin(stack, res);
+        } else if (*c != '(' && *c != ')'){
+            int n = strToInt(&c);
+            insererEnFin(stack, n >= 0 ? n : (int) *c);
+        }
+        c++;
+    }
+    int res = stack->first->val;
+    desalloueListe(stack);
+    return res;
+}
+
+void main(){
+    char* s = "(((4+2)-5)*4)";
+    int res = algo(s);
+    printf("%s = %d\n", s, res);
+}