1 files changed, 272 insertions, 0 deletions
diff --git a/semestre 2/informatique/tme/semaine10/multi_ensembles.c b/semestre 2/informatique/tme/semaine10/multi_ensembles.c
new file mode 100644
index 0000000..d2a023e
--- /dev/null
+++ b/semestre 2/informatique/tme/semaine10/multi_ensembles.c
@@ -0,0 +1,272 @@
+#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 Inclus_rec(element_t *sub, element_t *ens){
+	if (!sub) return 1;
+	if (!ens) return 0;
+	if (sub->valeur == ens->valeur){
+		if (sub->frequence > ens->frequence) return 0;
+		sub = sub->suivant;
+	}
+	return Inclus_rec(sub, ens->suivant);
+}
+
+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;
+}
+
+
+int taille(element_t *ensemble){
+	if (ensemble == NULL) return 0;
+	return ensemble->frequence + taille(ensemble->suivant);
+}
+
+element_t *Supprime_frequence_inf_seuil(element_t *ensemble, int s){
+	while (ensemble && ensemble->frequence < s) ensemble = ensemble->suivant;
+	if (!ensemble) return ensemble;
+	element_t * head = ensemble;
+	element_t * prec = head;
+	ensemble = ensemble->suivant;
+	while (ensemble){
+		if (ensemble->frequence < s){
+			prec->suivant = ensemble->suivant;
+			free(ensemble);
+			ensemble = prec;
+		}
+		prec = ensemble;
+		ensemble = ensemble->suivant;
+	}
+	return head;
+}
+
+element_t *Union(element_t *e1, element_t *e2){
+	element_t* ens = NULL;
+	while (e1 && e2){
+		if (e1->valeur < e2->valeur) {
+			ens = Ajout_tete_ensemble(ens, e1->valeur, e1->frequence);
+			e1 = e1->suivant;
+		} else if (e1->valeur > e2->valeur) {
+			ens = Ajout_tete_ensemble(ens, e2->valeur, e2->frequence);
+			e2 = e2->suivant;
+		} else {
+			ens = Ajout_tete_ensemble(ens, e1->valeur, e1->frequence + e2->frequence);
+			e1 = e1->suivant;
+			e2 = e2->suivant;
+		}
+	}
+	if (e1){
+		while (e1){
+			ens = Ajout_tete_ensemble(ens, e1->valeur, e1->frequence);
+			e1 = e1->suivant;	
+		}
+	} else if (e2) {
+		while (e2){
+			ens = Ajout_tete_ensemble(ens, e2->valeur, e2->frequence);
+			e2 = e2->suivant;	
+		}
+	}
+	return ens;
+}
+
+
+element_t *Ajout_suivant(element_t *ens, int val, int freq){
+	element_t * e = malloc(sizeof(element_t));
+	e->valeur = val;
+	e->frequence = freq;
+	e->suivant = NULL;
+	ens->suivant = e;
+	return e;
+}
+
+element_t *Union_triee(element_t *e1, element_t *e2){
+	element_t* ens = malloc(sizeof(element_t));
+	ens->suivant = NULL;
+	ens->frequence = 0;
+	ens->valeur = 0;
+	element_t * queue = ens;
+	while (e1 && e2){
+		int freq = 0;
+		int val = 0;
+		if (e1->valeur == e2->valeur){
+			freq = e1->frequence + e2->frequence;
+			val = e1->valeur;
+			e1 = e1->suivant;
+			e2 = e2->suivant;
+		} else {
+			element_t **min = e1->valeur < e2->valeur ? &e1 : &e2;
+			freq = (*min)->frequence;
+			val = (*min)->valeur;
+			*min = (*min)->suivant;
+		}
+		if (ens->frequence == 0){
+			ens->frequence = freq;
+			ens->valeur = val;
+		} else queue = Ajout_suivant(queue, val, freq);
+	}
+	if (!e1 && !e2) return ens;
+	element_t *e = e1 ? e1 : e2;
+	for (int i = 0; e; e = e->suivant)
+		queue = Ajout_suivant(queue, e->valeur, e->frequence);
+	return ens;
+}
+
+element_t *Union_triee_rec(element_t *e1, element_t *e2){
+	if (!e1 && e2) return NULL;
+	element_t* ens = malloc(sizeof(element_t));
+	ens->suivant = NULL;
+	ens->valeur = 0;
+	ens->frequence = 0;
+	if (!e1 || !e2) {
+		element_t *e = e1 ? e1 : e2;
+		element_t *queue = ens;
+		for (int i = 0; e; e = e->suivant){
+			if (ens->frequence == 0){
+				ens->valeur = e->valeur;
+				ens->frequence = e->frequence;
+			} else queue = Ajout_suivant(queue, e->valeur, e->frequence);	
+		}
+		return ens;
+	}
+	int freq = 0;
+	int val = 0;
+	if (e1->valeur == e2->valeur){
+		freq = e1->frequence + e2->frequence;
+		val = e1->valeur;
+		e1 = e1->suivant;
+		e2 = e2->suivant;
+	} else {
+		element_t **min = e1->valeur < e2->valeur ? &e1 : &e2;
+		freq = (*min)->frequence;
+		val = (*min)->valeur;
+		*min = (*min)->suivant;
+	}
+	ens = Ajout_tete_ensemble(ens, val, freq);
+	ens->suivant = Union_triee_rec(e1, e2);
+	return ens;
+}