DEVOIR sur les LISTES CHAINEES!!!(aidez-moi!)

Question

Bonjour,
je voudrais bien qu'on puisse m'aider ,c très important!!!!!!!!!!!!!!!!!
Mon prof d'informatique nous a donné un devoir à faire à la maison et ça fait deux jours que j travaille là dessus............
Bn voici l'énoncé, SVP AIDEZ MOI A L RESOUDRE!!!!!!!!

on dispose de deux ensembles d'entiers représentés par des listes chaînéés L1 et L2.
a- Ecrire une fonction INTERSECTION qui permet de donner l'intersection de ces deux ensembles.
b- Ecrire une fonction UNION qui permet de donner la réunion de ces deux ensembles.

SebManfred · Answer

Salut,
permier truc : je ne vais pas te donner la solution, mais je peux te donner des pistes ou des conseils.
ensuite, bien comprendre l'énoncé : il s'agit, pour la question a, de donner une liste qui ne comprend que les éléments qui sont à la fois dans ta liste L1 et dans ta liste L2, et pour la question b, donner une liste qui contient tous les éléments contenus dans L1, tous les éléments contenus dans L2, mais en faisant en sorte que les éléments qui sont à la fois dans L1 ET L2 n'apparaissent qu'une seule fois

pour ma part, je sais que quand j'ai du mal avec les listes chainées, je me fais des petits dessins avec les pointeurs de tête, les différents éléments avec les pointeurs vers les précédents et suivants, le pointeur courant, etc..., et puis j'exécute sur le dessin en pas à pas mes fonction de navigation dans ma (ou mes) listes.

sinon, ou en es-tu de tes fonctions? as-tu déjà écrit quelque chose?

SebManfred · Answer

tout d'abord, qu'est-ce que tu attend de ta fonction?
qu'est-ce que tu veux pouvoir y passer comme arguments et qu'est-ce que tu attends qu'elle te retourne?
comment as-tu prototypé ta structure list?
là, tu as une fonction à laquelle tu passes deux variables dont je ne connais pas le type, tu mets à jour ces variables avec d'autres variables apparament locales à ta fonction et qui ne sont ni déclarées ni initialisées. donc, c'est normal que ton compilateur te jette.

essaie de voir ça du point de vue utilisation de ta fonction dans ton main : ton main va avoir à faire appel à ta fonction, il aura deux listes et voudra en avoir une troisième issue des deux premières.
donc, il faut qu'en paramètre, tu passes à ta fonction "quelque chose" qui puisse lui permettre d'utiliser tes listes, et qu'en retour, ta fonction te retourne "quelque chose" qui puisse te permettre de travailler sur la liste créée.
ensuite, et seulement ensuite, on passera à l'implémentation de ta fonction

ce que je te demande pour l'instant, c'est 
- un prototype pour ta structure
- un main vide
- la déclaration de tes fonctions et leurs carcasses vides

lami20j · Answer

Salut,

pour les liste simplement chaînée
pour les ensemble je suis en train d'écrire un tutoriel, voici le code
j'ai mis en gras les fonctions pour l'intersection et l'union

ensemble.h

 /*****************\
 *  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

/**********************\
 * 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);

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

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

int main()
{
    char *nom;
    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("Entre un nom : ");
    scanf("%s",nom);
    insert_ens(ens,nom);
    printf("Entre un nom : ");
    scanf("%s",nom);
    insert_ens(ens,nom);
    printf("Entre un nom : ");
    scanf("%s",nom);
    insert_ens(ens,nom);
    printf("***** ens1 *****\n");
    affiche(ens);
    
    printf("Entre un nom : ");
    scanf("%s",nom);
    insert_ens(ens2,nom);
    printf("Entre un nom : ");
    scanf("%s",nom);
    insert_ens(ens2,nom);
    printf("Entre un nom : ");
    scanf("%s",nom);
    insert_ens(ens2,nom);
    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("%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("%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("%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");

    return 0;
}

lami20j · Answer

Si tu as besoin je pourrai t'expliquer, mais pas maintenant, je suis au boulot ;-)

SebManfred · Answer

déjà, ne met pas de caractères du genre "-" dans tes noms de variables, types ou structures, le compilateur n'accepte pas.
si tu y tiens vraiment, remplace-les par "_", ça passera beaucoup mieux.
ensuite, quel est le prototype de ta fonction?
je voudrai voir un truc du genre 

typedef struct nom_struct {
// données
};

type1 intersection(type2 ListeL1, type3 ListeL2);
type4 intersection(type5 ListeL1, type6 ListeL2);

int main(void)
{
return 0;
}

type1 intersection(ListeL1, ListeL2)
{
type1 retour;
// initialisation du retour en fonction de son type, à toi de le faire
return retour;
}

type4 intersection(ListeL1, ListeL2)
{
type4 retour;
// initialisation du retour en fonction de son type, à toi de le faire
return retour;
}


à toi de voir quels types donner à type1, type2, type3, type4, type5 et type6 pour pouvoir passer tes différents paramètres en pouvant les utiliser, et pour pouvoir également utiliser ton retour comme tu le souhaite...
l'écriture de tes fonctions viendra plus tard, tu ne peux pas écrire tes fonctions tant que tu ne sais pas ce qu'elles doivent faire, ni ce qu'elle prennent et rendent
on remplira le main plus tard, mais déjà, si tu écris tout correctement, ça devrait compiler

lami20j · Answer

Salut,

l'intersection est une liste Li
donc tu dois avoir plutôtstruct cell 
{
  int info; 
  struct cell*suiv; 
}; 
typedef struct cell *listeL; 

int intersection(listeL Li, listeL L1, listeL L2);

lami20j · Answer

Quand on écrit une fonction il faut d'abord penser de ce qu'on veux passer en parametre et aussi de la valeur qu'on veut renvoyer.

Si la fonction prends en paramètre les 2 listes et renvoi l'intersection alors on peut écrire


struct cell 
{
  int info; 
  struct cell*suiv; 
}; 
typedef struct cell *listeL; 

listeL intersection(listeL L1, listeL L2);

si on veut envoyer un entier 0 pour réussite et -1 pour echéc alors on peut écrire

struct cell 
{
  int info; 
  struct cell*suiv; 
}; 
typedef struct cell *listeL; 

int intersection(listeL Li, listeL L1, listeL L2);


en revanche int struct cell intersection(struct cellule listeL1,struct cellule listeL2); 
on ne peux pas écrire puisque dans ce cas le type et int et le nom de la fonction sera separé par des espaces et ce n'est pas permis
il faut choisir :
- si je veux renvoyer une valeur int alors je mets comme type de la fonction int
- si je veux renvoyer une liste alors je mets le type comme liste
mais ta structure n'est qu'un élément de la liste
si tu veux utilser les listes chaînée tu dois utiliser au moins un pointeur qui pointe vers le 1er élément de la liste, sinon tu ne pourras pas parcourir la liste
Pourqouoi ne regardes-tu le tuto que je t'ai donnée, il y a aussi des images pour mieux comprendre ;-)

DEVOIR sur les LISTES CHAINEES!!!(aidez-moi!)

7 réponses

Votre réponse

Discussions similaires

Newsletters