diff options
Diffstat (limited to 'semestre 2/informatique/tme/semaine9')
4 files changed, 176 insertions, 0 deletions
diff --git a/semestre 2/informatique/tme/semaine9/Makefile b/semestre 2/informatique/tme/semaine9/Makefile new file mode 100644 index 0000000..e961ede --- /dev/null +++ b/semestre 2/informatique/tme/semaine9/Makefile @@ -0,0 +1,4 @@ +build-run: + gcc -o app multi_ensembles.c multi_ensembles.h test_multi_ensembles.c + ./app + rm app diff --git a/semestre 2/informatique/tme/semaine9/multi_ensembles.c b/semestre 2/informatique/tme/semaine9/multi_ensembles.c new file mode 100644 index 0000000..64a8a34 --- /dev/null +++ b/semestre 2/informatique/tme/semaine9/multi_ensembles.c @@ -0,0 +1,132 @@ +#include <stdio.h> +#include <stdlib.h> +#include "multi_ensembles.h" + + +/* Retourne un pointeur sur le premier element de valeur val, retourne NULL si aucun élément n'a la valeur val */ +element_t * Recherche_val(element_t *ensemble, int val) { + while (ensemble){ + if (ensemble->valeur == val) return ensemble; + ensemble = ensemble->suivant; + } + return NULL; +} + +/* Ajoute l'element val en tete de l'ensemble s'il n'apparait pas dans l'ensemble, augmente sa frequence de 1 sinon */ +element_t * Ajout_tete_ensemble(element_t *ensemble, int val, int freq) { + element_t *f = Recherche_val(ensemble, val); + if (f) { + f->frequence += freq; + return ensemble; + } + element_t *el = malloc(sizeof(element_t)); + el->suivant = ensemble; + el->frequence = freq; + el->valeur = val; + return el; +} + + +/* Affche tous les elements d'un ensemble avec leur frequence */ +void Affiche_ensemble(element_t *ensemble) { + element_t *ptr = ensemble; + + while (ptr != NULL) { + printf("val : %d, frequence : %d\n",ptr->valeur,ptr->frequence); + ptr=ptr->suivant; + } +} + +/* Saisie des n elements d'un ensemble */ +element_t * Creation_ensemble(int n) { + element_t *ensemble=NULL; + + int i = 0; + int val; + + for (i=0; i < n; i++) { + printf("Saisie d'un entier: "); + scanf("%d",&val); + ensemble=Ajout_tete_ensemble(ensemble,val,1); + } + return ensemble; +} + +element_t *Supprime_total_element_ensemble(element_t *ensemble, int val){ + element_t *head = ensemble; + element_t *before = NULL; + while (ensemble){ + element_t *toDelete = NULL; + if (ensemble->valeur == val){ + if (before) before->suivant = ensemble->suivant; + else head = ensemble->suivant; + toDelete = ensemble; + } else before = ensemble; + ensemble = ensemble->suivant; + if (toDelete) free(toDelete); + } + return head; +} + +element_t *Supprime_element_ensemble(element_t *ensemble, int val){ + element_t *head = ensemble; + element_t *before = NULL; + while (ensemble){ + element_t *toDelete = NULL; + if (ensemble->valeur == val){ + ensemble->frequence--; + if (ensemble->frequence < 1){ + if (before) before->suivant = ensemble->suivant; + else head = ensemble->suivant; + toDelete = ensemble; + } + } else before = ensemble; + ensemble = ensemble->suivant; + if (toDelete) free(toDelete); + } + return head; +} + +element_t *Ajout_ensemble_trie(element_t *ensemble, int val, int freq){ + if (!ensemble || ensemble->valeur > val) { + element_t *el = malloc(sizeof(element_t)); + el->suivant = ensemble; + el->frequence = freq; + el->valeur = val; + return el; + } + element_t *head = ensemble; + while (ensemble && ensemble->valeur <= val){ + if (ensemble->valeur == val) ensemble->frequence += freq; + else if (!ensemble->suivant || ensemble->suivant->valeur > val){ + element_t *new = malloc(sizeof(element_t)); + new->valeur = val; + new->frequence = freq; + new->suivant = ensemble->suivant; + ensemble->suivant = new; + ensemble = new; // empêche de passer deux fois sur la même valeur + } + ensemble = ensemble->suivant; + } + return head; +} + +int Inclus(element_t *sub, element_t *ens){ + while (ens && sub && ens->valeur <= sub->valeur){ + if (sub->valeur == ens->valeur){ + if (sub->frequence > ens->frequence) return 0; + else sub = sub->suivant; + } + ens = ens->suivant; + } + return sub == NULL; +} + +int Intersection_vide(element_t *e1, element_t *e2){ + while (e1 && e2){ + if (e1->valeur == e2->valeur) return 0; + if (e1->valeur < e2->valeur) e1 = e1->suivant; + else e2 = e2->suivant; + } + return 1; +} diff --git a/semestre 2/informatique/tme/semaine9/multi_ensembles.h b/semestre 2/informatique/tme/semaine9/multi_ensembles.h new file mode 100644 index 0000000..63c13aa --- /dev/null +++ b/semestre 2/informatique/tme/semaine9/multi_ensembles.h @@ -0,0 +1,16 @@ +typedef struct _element_t element_t; +struct _element_t{ + int valeur; + int frequence; + element_t *suivant; +}; + +element_t *Recherche_val(element_t *ensemble, int val); +element_t *Ajout_tete_ensemble(element_t *ensemble, int val, int freq); +element_t *Ajout_ensemble_trie(element_t *ensemble, int val, int freq); +element_t *Supprime_total_element_ensemble(element_t *ensemble, int val); +element_t *Supprime_element_ensemble(element_t *ensemble, int val); +void Affiche_ensemble(element_t *ensemble); +element_t * Creation_ensemble(int n); +int Inclus(element_t* sub, element_t *ens); +int Intersection_vide(element_t *e1, element_t *e2); diff --git a/semestre 2/informatique/tme/semaine9/test_multi_ensembles.c b/semestre 2/informatique/tme/semaine9/test_multi_ensembles.c new file mode 100644 index 0000000..d141210 --- /dev/null +++ b/semestre 2/informatique/tme/semaine9/test_multi_ensembles.c @@ -0,0 +1,24 @@ +#include <stdio.h> +#include "multi_ensembles.h" + +element_t *CreationMultiEnsemble(int deb, int n, int freq){ + element_t *liste=NULL; + int i; + + for (i=deb+n-1; i >=deb; i--) { + liste=Ajout_tete_ensemble(liste,i,freq); + } + return liste; +} + +int main() { + element_t *ensemble1= CreationMultiEnsemble(1,20,1); + element_t *ensemble2= CreationMultiEnsemble(5,10,2); + Affiche_ensemble(ensemble1); + printf("====\n"); + Affiche_ensemble(ensemble2); + printf("====\n"); + printf("%d\n",Intersection_vide(ensemble1, ensemble2)); + printf("%d\n",Intersection_vide(ensemble2, ensemble1)); + return 0; +} |