Discussion :

[Tshik3StyLe]

bon la j'ai rencontré un petit probleme et je sais pas ce que je doit faire je suis debutant en C
je veux faire la fusion de 2 llc trié dans une nouvelle llc en inserant element par element par ordre croissant
la structure

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
struct elem{
    int val;
    struct elem *suiv;
};
typedef struct elem *list;

l'insertion

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
list insert_tete (list l,int v){
    list p;
    p=(list)malloc(sizeof(struct elem));
    p->val=v;
    p->suiv=l;
    l=p;
    return (l);
}

la fonction de tri

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
list  triFuzion(list a, list b){
    list p=NULL, q=NULL, l=NULL, t=NULL;
    p=a;
    q=b;
    l=t;
    while ((p->suiv != NULL) && (q->suiv != NULL)){
        if (p->val < q->val){
         l = insert_tete(t,p->val);
         p=p->suiv;
         l=l->suiv;
        }
        else{
        l = insert_tete(t,q->val);
        q=q->suiv;
        l=l->suiv;
        }
    }
 
        while ((p->suiv = NULL) && (q->suiv != NULL)) {
        l = insert_tete(t,q->val);
        q=q->suiv;
        l=l->suiv;
        }
 
        while ((p->suiv != NULL) && (q->suiv = NULL)) {
        l = insert_tete(t,p->val);
        p=p->suiv;
        l=l->suiv;
        }
return (t);
}

quesque je doit amelioré ?

[koala01]

Salut, et bienvenue sur le forum.

Déjà, le conseil que je donne généralement, c'est de séparer clairement l'idée d'élément de la liste de celle de la liste en elle-même.

Ensuite, il serait intéressant de se poser la question de savoir si, une fois les deux listes fusionnées, tu veux pouvoir malgré tout garder les listes originales ou non.

Pour la première remarque, la forme que je conseille généralement ressemble à

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef struct _elem
{
    int val;
    struct _elem* suivant;
} element;
typedef struct _liste
{
    element* premier; /* le premier élément de la liste
                       * utilisé pour le parcours de celle-ci
                       */
    element* dernier; /* le dernier élément de la liste
                       * utilisé principalement pour permettre d'insérer
                       * un élément en fin de liste en temps constant
                       */
    unsigned int taille; /* il peut être sympa de connaitre le
                         * nombre d'éléments dans la liste ;)
                         */
} liste;

Cela permet de respecter un conseil "primordial" qui est de déléguer les responsabilités, tant du point de vue des structures que du point de vue des fonctions.

Tu aurais donc, classiquement, les fonctions suivantes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
element* creerElement(int val)
{
    element* temp=malloc(sizeof(element));
    if(temp!=0)
    {
        temp->val=val;
        /* quand on crée un élément, il ne pointe sur aucun suivant */
        temp->next = NULL;
    }
}
liste* creerListe()
{
    liste* temp=malloc(sizeof(liste));
    if(temp)
    {
        /* au début, la liste est vide */
        temp->premier = NULL;
        temp->dernier = NULL;
        temp->taille = 0;
    }
    return temp;
}
void push_back(liste*  l, element* elem)
{
    if(l->premier)
        l->premier=elem;
    if(l->dernier)
        l->dernier->suivant=elem;
    l->dernier = elem;
    ++l->taille;
}
void insereElement(liste* l, element * avant,element* elem)
{
    elem->suivant=avant->suivant;
    avant->suivant = elem;
    if(avant==l->dernier)
        l->dernier = elem;
    ++l->taille;
} 
void trieListe(liste* l)
{
    /* implémentation "classique" du tri à bulles, par exemple */
}
void suppressElement(liste* l, element* todel)
{
    /* cherchons l'élément qui précède celui à supprimer */
    element* temp=l->premier;
    /* c'est peut être le premier */
    if(temp==todel)
    {
        /*et unique */
        if(todel==l->dernier)
        {
            delete temp;
            l->premier = NULL;
            l->dernier = NULL;
        }
        else
        {
            /* sinon, celui qui suit l'élément à supprimer devient le premier 
             * element de la liste
             */
            l->premier = temp->suivant;
            free(temp);
            --l->taille;
        }
    }
    else
    {
        while(temp->suivant!=todel)
            temp=temp->suivant;
        /* si l'élément à supprimer est le dernier */
        if(todel=l->dernier)
        {
            /* celui qui le précède devient le dernier */
            l->dernier = temp;
        }
        /* quoi qu'il en soit, on rattache l'élément qui précède
         * celui à supprimer à celui qui suit l'élément à supprimer
         */
       temp->suivant=todel->suivant;
       /* on libère la mémoire */
       free(todell);
    }
    /* et on décrémente la taille */
    --l->taille;
}
void detruitListe(liste* l)
{
    element* temp;
    while(l->premier)
    {
        temp=l->premier->next;
        free(premier);
        l->premier = temp;
    }
    free(l);
}

La deuxième remarque va énormément influer sur la manière dont la liste fusionnée sera créée:

Si tu ne veux pas garder les deux listes originelles, tu peux te contenter de déplacer les élément de ces listes vers la liste fusionnée, selon une fonction qui pourrait être proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
liste* fusion(liste* l1, liste* l2)
{
    /* créons la liste de destination */
    liste *finale =creerListe();
    if(finale)
    {
        /* tant qu'il y a un élément dans l'une des listes  */
        while(l1->premier || l2->premier)
        {
            /* si les deux listes ont un élément */
            if(l1->premier && l2->premier)
            {
                if(l1->premier->val < l2->premier->val)
                {
                    finale->push_back(l1->premier);
                    l1->premier = l1->premier->suivant;                
                }
                else
                {
                    finale->push_back(l2->premier);
                    l2->premier = l2->premier->suivant;    
                }
            }
            else if(l1->premier)
            {
                finale->push_back(l1->premier);
                l1->premier = l1->premier->suivant;  
            }
            else
            {
                finale->push_back(l2->premier);
                l2->premier = l2->premier->suivant;  
            }
        }
        /* on ne détruit les deux listes que si on a su créer la liste fusionnée */
        detruitListe(l1);
        detruitListe(l2);
    }
    return finale;
}
/* ATTENTION !!! les pointeurs respectifs sur les deux listes originelles sont
 * de facto invalidés... pense à les remettre à null dans la fonction
 * appelante
 */

Si, par contre, tu veux garder les listes originelles, la liste fusionnée va devoir contenir une copie des éléments des deux listes, ce qui pourrait prendre la forme de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
liste* fusion(liste* l1, liste* l2)
{
    liste* finale=creerListe();
    if(finale)
    {
        element* temp1 = l1->premier;
        element* temp2 = l2->premier;
        while(temp1 || temp2)
        {
            if(temp1 && temp2)
            {
                if(temp1->val < temp2->val)
                {
                    push_back(finale,creerElement(temp1->val));
                    temp1 = temp1->suivant;
                }
                else
                {
                    push_back(finale,creerElement(temp2->val));
                    temp2 = temp2->suivant;
                }
            }
            else if (temp1)
            {
                push_back(finale,creerElement(temp1->val));
                temp1 = temp1->suivant;
            }
            else
            {
                push_back(finale,creerElement(temp2->val));
                temp2 = temp2->suivant;
            }
        }
    }
    return finale;
}