Votre IP: 38.107.179.241 
  		 
Google
 
Accueil e-mail Linux
Linux		 Perl
Perl		 C
Langage C		 Dico
Dictionnaire		 Biblio liens
Bibliothèque de liens		 Index articles
Index articles		  

Date création : 09-12-2007 19:04:24
Date de la dernière modification : 28-12-2007 22:14:29
C  Vous êtes dans : Langage C Tutoriels / Algorithmes

Les ensembles



Requis table de matières

Les types de données
Les structures
L'utilisation de typedef
Les pointeurs
Les fonctions utilisateur
Les listes simplement chaînées

Un peu de théorie

Description table de matières

Les ensembles sont des collections non ordonnées d'éléments dans lesquelles chaque élément n'apparaît qu'une seule fois.
Les ensembles sont présentés entre les accolades. Si un ensemble A contient les éléments a, b et c il sera écrit A = {a,b,c}
Comme les ensembles sont des collections non ordonnées, nous pourrons écrire aussi A = {c,a,b}

Si un élément appartient au A (est dans A) nous écrivons
Si un élément n'appartient pas au A (n'est pas dans A) nous écrivons

Dans notre exemple les notations suivantes sont valables :

Pour utiliser les ensembles nous devons connaître quelques définitions, les opérations et les propirétés des ensembles.

Définitions

Ensemble vide table de matières

Un ensemble qui n'a aucun élément s'appelle l'ensemble vide.

Notation :

A = ∅

L'Univers table de matières

Un ensemble qui contient tous les éléments possibles s'appelle l'univers.

Notation :

Egalité des ensembles table de matières

Deux ou plusieurs ensembles sont égaux, s'ils contiennent exactement les mêmes éléments.
Supposons l'existence de 3 ensembles : A =  {a,b,c}, B = {b,a,c} et  C  = {1,2,3}
Alors A est égal à B mais il est différent de C

Notation :
 
A = B et A ≠ C

Sous-ensemble table de matières

Un ensemble A est un sous-ensemble de B si B contient tous les éléments de A.
Supposons l'existence de 3 ensembles : A =  {a,c}, B = {b,a,c} et  C  = {a,b}
Alors A est un sous-ensemble de B mais pas de C

Notation :

A ⊂ B et A ⊄ C

Opérations de base

Union table de matières

L'union de deux ensembles A1 et A2 est un ensemble qui contient tous les éléments de A1 et de A2.

Exemple :

A1={1,2,3}
A2 ={3,4,5}
L'union de A1 et A2 est l'ensemble Au={1,2,3,4,5}
Notation :

Intersection table de matières

L'intersection de deux ensembles A1 et A2 est un ensemble qui contient les éléments communs de A1 et de A2.

Exemple :

A1={1,2,3}
A2 ={3,4,5}
L'intersection de A1 et A2 est l'ensemble Ai={3}
Notation :

Différence table de matières

La différence de deux ensembles A1 et A2 est un ensemble qui contient tous les éléments de A1 qui ne se trouvent pas dans A2.

Exemple :

A1={1,2,3}
A2 ={3,4,5}
La différence de A1 et A2 est l'ensemble Ad={1,2}
Notation :

Propriétés des ensembles

Loi de l'ensemble vide table de matières


L'intersection d'un ensembe A avec l'ensemble vide est l'ensemble vide.



L'union d'un ensemble A avec l'ensemble vide est l'ensemble A

Idempotence table de matières

L'intersection et l'union d'un ensemble A avec lui-même est l'ensemble A

Commutativité table de matières

L'intersection d'un ensemble A1 avec un ensemble A2 est égale avec l'intersection de l'ensemble A2 avec l'ensemble A1


L'union d'un ensemble A1 avec un ensemble A1 est égale avec l'union de l'ensemble A2 avec l'ensemble A1

Associativité table de matières

L'intersection de plusieurs ensembles A1,A2,...An peut être faite dans n'importe quelle ordre


L'union de plusieurs ensembles A1,A2,...An peut être faite dans n'importe quelle ordre

La distributivité par rapport à l'union table de matières

L'intersection d'un ensemble A1 peut être distribuée avec l'union des deux ensembles A2 et A3

La distributivité par rapport à l'intersection table de matières

L'union d'un ensemble A1 peut être distribuée avec l'intersection des deux ensembles A2 et A3

Absorbtion table de matières

L'intersection d'un ensemble A1 avec l'union de l'ensemble A1 avec un ensemble A2, égal l'ensemble A1


L'union d'un ensemble A1 avec l'intersection de l'ensemble A1 avec un ensemble A2, égal l'ensemble A1

Les lois de DeMorgan table de matières

La différence de l'ensemble A1 avec la l'intersection de deux ensembles A2 et A3, est égale avec l'union entre la différence entre A1 et A2 et la différence entre A1 et A3


La différence de l'ensemble A1 avec la l'union de deux ensembles A2 et A3, est égale avec l'intersection entre la différence entre A1 et A2 et la différence entre A1 et A3

II. L'implémentation des ensembles table de matières

Pour l'implémentation des ensembles nous avons utilisé les listes simplement chaînées.
Toutes les fonctions que nous avons utilisées dans l'implémentation des listes simplement chaînées, peuvent être utilisées.
La compréhension des listes simplement chaînées est donc nécessaire pour comprendre la suite de ce tutoriel.
Ce n'est pas obligatoire d'utiliser les listes pour comprendre le mécanisme des ensembles, vous pouvez utiliser par exemple les tableaux.
Toutefois, comme il s'agit de plusieurs opérations d'insertion/suppression, j'ai choisi les listes simplement chaînées (qui n'est pas toujours la meilleure solution).
Nous gardons toujours dans l'esprit que ce tutoriel à pour le but la compréhension des ensembles et pas l'implémentation en fonction de vos besoins.

III. La construction du prototype d'un élément de l'ensemble table de matières

Pour l'implémentation des ensembles nous utiliserons les listes simplement chaînées. C'est la raison pour laquelle nous utiliserons la même définition d'éléments.
Ensuite nous encapsulerons cette définition à l'aide de typedef.

Pour définir un élément de la liste, le type struct sera utilisé.
L'élément de la liste contiendra un champ donnee et un pointeur suivant.
Le pointeur suivant doit être du même type que l'élément, sinon il ne pourra pas pointer vers l'élément.
Le pointeur "suivant" permettra l'accès vers le prochain élément.

typedef struct ListeElement{
        char *nom;
        struct ListeElement *suivant;
}Element;

Pour avoir le contrôle de la liste, il est préférable de sauvegarder certains éléments :
le premier élément, le dernier élément, le nombre d'éléments.

Pour réaliser cela, une autre structure sera utilisée (ce n'est pas obligatoire, des variables peuvent être utilisées).
Voici sa composition:

typedef struct ListeRepere{
        int taille;
        Element *debut;
        Element *fin;
}Liste;

Le pointeur debut contiendra l'adresse du premier élément de la liste.
Le pointeur fin contiendra l'adresse du dernier élément de la liste.
La variable taille contient le nombre d'éléments.

Quelque soit la position dans la liste, les pointeurs debut et fin pointent toujours respectivement vers le 1er et le dernier élément.
Le champ taille contiendra le nombre d'éléments de la liste quelque soit l'opération effectuée sur la liste.

Une fois que la structure d'élément de la liste est définie, nous utiliserons une encapsulation pour ne pas faire une confusion de traitement avec les listes simplement chaînées.
Pour réaliser cela le typedef sera utilisé

typedef Liste Ensemble;

IV. Opérations sur les ensembles table de matières


A. Initialisation table de matières


Prototype de la fonction :

void init_ens(Ensemble *ens);

Cette opération doit être faite avant toute autre opération sur l'ensemble.
Elle initialise le pointeur debut et le pointeur fin avec le pointeur NULL, et la taille avec la valeur 0.

La fonction

void init_ens(Ensemble *ens){
    ens->taille = 0;
    ens->debut = NULL;
    ens->fin = NULL;
}

B. Insertion d'éléments dans un ensemble table de matières

Pour l'insertion d'un élément dans l'ensemble, j'utilise 3 fonctions :

1. insertion dans la liste
  • le prototype
int insertion (Liste *liste,char *nom);

La fonction insertion, exécute une insertion d'éléments dans la liste chaînée de la  façon suivante :
  • déclaration d'élément(s) à insérer
  • allocation de la mémoire pour le nouvel élément
  • remplir le contenu du champ de données
  • mettre à jour les pointeurs vers le 1er et le dernier élément si nécessaire.
Si la liste n'est pas vide l'insertion se fera toujours à la fin.
  • la fonction

int insertion (Liste *liste,char *nom){
   Element *nouveau_element;
   Element *courant;

   if((nouveau_element = (Element *) malloc (sizeof(Element)))
           == NULL)
      return -1;
   if((nouveau_element->nom = (char *) malloc (50 * sizeof(char)))
           == NULL)
      return -1;
   strcpy(nouveau_element->nom,nom);
   if(liste->taille == 0){
      liste->fin = nouveau_element;
      nouveau_element->suivant = liste->debut;
      liste->debut = nouveau_element;
   } else { /* l'insertion se fera toujours à la fin */
      courant = liste->fin;
      nouveau_element->suivant =  courant->suivant;
      courant->suivant = nouveau_element;
      liste->fin = nouveau_element;
   }
   liste->taille++;
   return 0;
}

2. existence d'élément dans l'ensemble
  • le prototype

int existe (Ensemble *ens, char *nom);


Cette fonction permet de tester si le nouvel élément à insérer existe dans l'ensemble. Si c'est le cas, alors l'élément ne sera pas inséré.
Elle prend comme arguments l'ensemble et le nouveau champ de donnée à insérer.
L'ensemble est parcouru de début à la fin et pour chaque élément de l'ensemble le champ de donnée est comparé à la nouvelle donnée.
  • La fonction

int existe (Ensemble *ens, char *nom){
    Element *element;

    for(element=ens->debut;element != NULL;element=element->suivant)
        if(strcmp(element->nom,nom) == 0)
            return 1;
    return 0;
}

3. insertion dans l'ensemble
  • le prototype

int insert_ens(Ensemble *ens, char *nom);

Cette fonction appelle les fonctions existe et insertion. Le nouveau élément est comparé à chaque élément de l'ensemble et il est inséré s'il n'existe pas.
  • la fonction
nt insert_ens(Ensemble *ens, char *nom){
    if(existe(ens,nom))
        return -1;
    return insertion(ens,nom);
}


C. Suppression d'éléments d'un ensemble table de matières

L'ensemble étant une liste simplement chaînée, pour supprimer un élément, nous pourrons utiliser les fonctions de suppressions utilisées dans les listes simplement chaînée
Il suffit juste de changer le prototype des fonctions en utilisant le type Ensemble au lieu de Liste.

D. L'Union de 2 ensembles table de matières

  • le prototype
Cette fonction prend en argument 3 éléments : l'ensemble union, et les 2 ensembles sur lequells nous effectueons l'opération d'union.
En premier temps, la fonction insère dans l'ensemble union les éléments du 1er ensemble.
Ensuite chaque élément du 2ème ensemble est comparé à chaque élément de l'ensemble union et il l'insère si l'élément n'existe déjà dans l'ensemble union.

int ens_union (Ensemble *ens_u, Ensemble *ens1, Ensemble *ens2);

  • la fonction

int ens_union (Ensemble *ens_u, Ensemble *ens1, Ensemble *ens2){
    Element *element;
   
    for(element=ens1->debut;element != NULL;element = element->suivant)
        insertion(ens_u,element->nom);
   
    for(element=ens2->debut;element != NULL;element = element->suivant)
        if(! existe(ens_u,element->nom))
            insertion(ens_u,element->nom);
       
    return 0;
}


E. L'intersection de 2 ensembles table de matières

  • le prototype
Cette fonction prend en argument 3 éléments : l'ensemble intersection, et les 2 ensembles sur lesquels on effectue l'opération d'intersection.
Chaque élément du 1er ensemble est comparé aux éléments du 2ème ensemble.
Dès qu'une correspondance est trouvée, l'élément sera inséré dans l'ensemble intersection.

int ens_intersect (Ensemble *ens_i, Ensemble *ens1, Ensemble *ens2);
  • la fonction

int ens_intersect (Ensemble *ens_i, Ensemble *ens1, Ensemble *ens2){
    Element *element;

    for(element=ens1->debut;element != NULL;element = element->suivant)
        if(existe(ens2,element->nom))
            insertion(ens_i,element->nom);
    return 0;
}


F. La différence de 2 ensembles table de matières

  • le prototype
Cette fonction prend en argument 3 éléments : l'ensemble différence, et les 2 ensembles sur lesquels nous effectueons l'opération différence.
Chaque élément du 1er ensemble est comparé aux éléments du 2ème ensemble.
Dès qu'une non correspondance est trouvée, l'élément sera inséré dans l'ensemble différence.

int ens_diff (Ensemble *ens_d, Ensemble *ens1, Ensemble *ens2);


int ens_diff (Ensemble *ens_d, Ensemble *ens1, Ensemble *ens2){
    Element *element;

    for(element=ens1->debut;element != NULL;element=element->suivant)
        if(! existe(ens2,element->nom))
            insertion(ens_d,element->nom);
    return 0;
}


G. Vérification si un ensemble est un sous-ensemble d'un autre ensemble table de matières

  • le prototype
Cette fonction prend en argument les 2 ensembles.
Nous vérifions d'abord si la taille de 1er ensemble est plus grande que la taille du 2ème ensemble. Si c'est le cas alors le 1er ensemble ne peut pas être un sous-ensemble du 2ème ensemble.
Si le 1er ensemble a une taille plus petite que le 2ème, on compare chaque élément du 1er ensemble aux éléments du 2ème ensemble.

Nous aurons 2 possibilités :

- si une non-correspondance est trouvée alors le 1er ensemble n'est pas un sous-ensemble du 2ème ensemble
- si tous les éléments correspondent alors le 1er ensemble est un sous-ensemble du 2ème ensemble

int ens_sous_ens (Ensemble *ens1, Ensemble *ens2);

  • la fonction
int ens_sous_ens (Ensemble *ens1, Ensemble *ens2){
    Element *element;

    if(ens1->taille > ens2->taille)
        return 0;

    for(element=ens1->debut;element != NULL;element=element->suivant){
        if(! existe(ens2,element->nom))
            return 0;
    }
    return 1;
}


I. L'égalité de 2 ensembles table de matières

  • le prototype
Cette fonction prend en argument les 2 ensembles.
Nous vérifions d'abord si la taille des 2 ensembles est différente. Si c'est le cas alors le 1er ensemble ne peut pas être égal avec le 2ème ensemble.
Si la taille est égale alors si le 1er ensemble est un sous-ensemble du 2ème ensemble, nous pourrons dire que les 2 ensembles sont égaux.

int ens_egal_ens (Ensemble *ens1, Ensemble *ens2);
  • la fonction

int ens_egal_ens (Ensemble *ens1, Ensemble *ens2){
    if(ens1->taille != ens2->taille)
        return 0;
    return ens_sous_ens(ens1,ens2);
}

Exemple complet


ensemble.h table de matières


 /*****************\
 *  ensemble.h   *
\*****************/

typedef struct ListeElement{
        char *nom;
        struct ListeElement *suivant;
}Element;

typedef struct ListeRepere{
        int taille;
        Element *debut;
        Element *fin;
}Liste;


/* insertion dans liste */
int insertion (Liste *liste,char *nom);
/* suppression dans liste */
int suppression (Liste *liste);

/* traitement des ensembles */
typedef Liste Ensemble;

void init_ens(Ensemble *ens);
int insert_ens(Ensemble *ens, char *nom);
int suppr_ens(Ensemble *ens);

int ens_union (Ensemble *ens_u, Ensemble *ens1, Ensemble *ens2);
int ens_intersect (Ensemble *ens_i, Ensemble *ens1, Ensemble *ens2);
int ens_diff (Ensemble *ens_d, Ensemble *ens1, Ensemble *ens2);

int ens_sous_ens (Ensemble *ens1, Ensemble *ens2);
int ens_egal_ens (Ensemble *ens1, Ensemble *ens2);

void affiche(Ensemble *ens);
void detruire(Ensemble *ens);
int existe (Ensemble *ens, char *nom);

Ensemble * alloc_ens(Ensemble *ens);

ensemble_function.h table de matières


/**********************\
 * ensemble_function.h *
\**********************/

/* insertion dans liste */
int insertion (Liste *liste,char *nom){
   Element *nouveau_element;
   Element *courant;

   if((nouveau_element = (Element *) malloc (sizeof(Element)))
           == NULL)
      return -1;
   if((nouveau_element->nom = (char *) malloc (50 * sizeof(char)))
           == NULL)
      return -1;
   strcpy(nouveau_element->nom,nom);
   if(liste->taille == 0){
      liste->fin = nouveau_element;
      nouveau_element->suivant = liste->debut;
      liste->debut = nouveau_element;
   } else { /* l'insertion se fera toujours à la fin */
      courant = liste->fin;
      nouveau_element->suivant =  courant->suivant;
      courant->suivant = nouveau_element;
      liste->fin = nouveau_element;
   }
   liste->taille++;
   return 0;
}

/* suppression dans liste */
int suppression (Liste *liste){
    Element *supp_element;

    supp_element = liste->debut;
    liste->debut = liste->debut->suivant;
    if(liste->taille == 1)
        liste->fin = NULL;
    free(supp_element->nom);
    free(supp_element);
    liste->taille--;
    return 0;
}

/* traitement des ensembles */
void init_ens(Ensemble *ens){
    ens->taille = 0;
    ens->debut = NULL;
    ens->fin = NULL;
}

/* insertion élément dans un ensemble */
int insert_ens(Ensemble *ens, char *nom){
    if(existe(ens,nom))
        return -1;
    return insertion(ens,nom);
}
/* opérations avec ensemlbes */
int ens_union (Ensemble *ens_u, Ensemble *ens1, Ensemble *ens2){
    Element *element;
  
    for(element=ens1->debut;element != NULL;element = element->suivant)
        insertion(ens_u,element->nom);
  
    for(element=ens2->debut;element != NULL;element = element->suivant)
        if(! existe(ens_u,element->nom))
            insertion(ens_u,element->nom);
      
    return 0;
}

int ens_intersect (Ensemble *ens_i, Ensemble *ens1, Ensemble *ens2){
    Element *element;

    for(element=ens1->debut;element != NULL;element = element->suivant)
        if(existe(ens2,element->nom))
            insertion(ens_i,element->nom);
    return 0;
}

int ens_diff (Ensemble *ens_d, Ensemble *ens1, Ensemble *ens2){
    Element *element;

    for(element=ens1->debut;element != NULL;element=element->suivant)
        if(! existe(ens2,element->nom))
            insertion(ens_d,element->nom);
    return 0;
}

int ens_sous_ens (Ensemble *ens1, Ensemble *ens2){
    Element *element;

    if(ens1->taille > ens2->taille)
        return 0;

    for(element=ens1->debut;element != NULL;element=element->suivant){
        if(! existe(ens2,element->nom))
            return 0;
    }
    return 1;
}
  
int ens_egal_ens (Ensemble *ens1, Ensemble *ens2){
    if(ens1->taille != ens2->taille)
        return 0;
    return ens_sous_ens(ens1,ens2);
}

void affiche(Ensemble *ens){
    Element *element;
    for(element=ens->debut;element != NULL;element=element->suivant)
        printf("%s ",element->nom);
    printf("\n");
}

int existe (Ensemble *ens, char *nom){
    Element *element;

    for(element=ens->debut;element != NULL;element=element->suivant)
        if(strcmp(element->nom,nom) == 0)
            return 1;
    return 0;
}

void detruire(Ensemble *ens){
    while(ens->taille > 0)
        suppression(ens);
}

Ensemble * alloc_ens(Ensemble *ens){
    if((ens = (Ensemble *) malloc (sizeof(Ensemble)))
            == NULL)
        return NULL;
    return ens;
}


ensemble.c table de matières


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ensemble.h"
#include "ensemble_function.h"

int main()
{
    char *nom;
    int i,nb;

    Ensemble *ens;
    Ensemble *ens2;
    Ensemble *ens_u;
    Ensemble *ens_i;
    Ensemble *ens_d;

    ens = alloc_ens(ens);
    init_ens(ens);
    ens2 = alloc_ens(ens2);
    init_ens(ens2);
    ens_u = alloc_ens(ens_u);
    init_ens(ens_u);
    ens_i = alloc_ens(ens_i);
    init_ens(ens_i);
    ens_d = alloc_ens(ens_d);
    init_ens(ens_d);

    if((nom = (char *) malloc (50 * sizeof(char)))
            == NULL)
        return -1;

    printf("****************************************************\n");
    printf("*         OPERATIONS AVEC LES ENSEMBLES            *\n");
    printf("****************************************************\n");

    printf("Entrez la taille du 1er ensemble : ");
    scanf("%d",&nb);

    for (i=0;i<nb;++i){
        printf("Entre un nom : ");
        scanf("%s",nom);
        insert_ens(ens,nom);
    }
    printf("***** ens1 *****\n");
    affiche(ens);
   
    printf("Entrez la taille du 2ème ensemble : ");
    scanf("%d",&nb);

    for (i=0;i<nb;++i){
        printf("Entre un nom : ");
        scanf("%s",nom);
        insert_ens(ens2,nom);
    }
    printf("***** ens2 *****\n");
    affiche(ens2);

    //ens_union(ens_u,ens,ens2);
    ens_union(ens_u,ens,ens2);
    printf("***** l'UNION *****\n");
    printf("taille %d\n",ens_u->taille);
    affiche(ens_u);

    //ens_intersect(ens_i,ens,ens2);
    ens_intersect(ens_i,ens,ens2);
    printf("*****l'INTERSECTION*****\n");
    printf("taille %d\n",ens_i->taille);
    affiche(ens_i);

    //ens_diff(ens_d,ens,ens2);
    ens_diff(ens_d,ens,ens2);
    printf("*****la DIFFERENCE*****\n");
    printf("taille %d\n",ens_d->taille);
    affiche(ens_d);

    // sous-ensemble
    if(ens_sous_ens(ens,ens2))
        printf("ens est sous-ensemble de ens2!\n");
    else
        printf("ens n'est pas un sous-ensemble de ens2!\n");

    // égalité
    if(ens_egal_ens(ens,ens2))
        printf("ens est égal ens2!\n");
    else
        printf("ens n'est pas égal avec ens2!\n");

    return 0;
}

Voir aussi table de matières
Création : octobre 2007  © Tous droits réservés 2007 linux-perl-c
Valid HTML 4.01 TransitionalValid CSS