suppression des occurences d'un element dans une liste simplement chainée

Version imprimable

Bonjour,

voici un exemple de code en c qui supprime toutes les occurrences d'un élément dans une liste simplement chaînée :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
void removeOccElem(cel** l , int elem){
     cel* ptr = *l ;
     cel* temp ;
 
     //l'element à supp est dans l'en-tete de la liste
     while(ptr  && ptr->elem==elem){
               *l= ptr->suiv ;
               free(ptr);
               ptr = *l ;
     }
     // supp des autres occurences
     while(ptr->suiv){
                 temp=ptr->suiv ;
                if(temp->elem==elem){
                      ptr->suiv=temp->suiv ;
                      free(temp);                                  
                }else{
                      ptr=ptr->suiv; 
                }
 
     }
}

Comment puis-je optimiser ce code ?
Merci
E. Bazoga

19/04/2017, 15h13
Matt_Houston

Quel est le problème rencontré ?
19/04/2017, 19h04
bazoga

Citation:

Envoyé par Matt_Houston

Quel est le problème rencontré ?

Aucun problème au niveau de l’exécution. je me demande si je peux l'améliorer encore ?

Bonjour,
avant d'optimiser il faut corriger → que se passe-t-il lorsque *l est NULL ? Si ptr devient NULL après la première boucle ?

Que penses-tu d'un code plus simple comme

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
cel *removeOccElem(cel* l , int elem){
    // si la liste n'est pas vide
    if (l!=NULL) {
        if (l->elem==elem) {
            // si l'élément à enlever est en tête
            cel *tmp=l->suiv;
            free(l);
            l=removeOccElem(tmp, elem);
        } else {
            l->suiv=removeOccElem(l->suiv, elem);
        }
    }
    return l;
}

Code non testé tapé à la volée.

19/04/2017, 20h09
bazoga

Citation:

Envoyé par picodev

Bonjour,
avant d'optimiser il faut corriger → que se passe-t-il lorsque *l est NULL ? Si ptr devient NULL après la première boucle ?

Merci pour la remarque, j'ajoute un simple test pour le cas d'une liste vide et ça va marcher. Je vais tester votre solution récursive.

Tapé très vite donc à prendre avec des pincettes, mais semble convenir à valgrind :

Code:

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
#include <stdio.h>
#include <stdlib.h>
 
 
typedef struct list_s {
    int elem;
    struct list_s *next;
} list_t;
 
 
list_t *append(list_t **l, int elem) {
    while (*l)
        l = &(*l)->next;
 
    *l = malloc(sizeof **l);
    if (*l) {
        const list_t e = { elem, NULL };
        **l = e;
    }
 
    return *l;
}
 
void clear(list_t **l) {
    while (*l) {
        list_t *const q = *l;
        *l = q->next;
        free(q);
    }
}
 
void remove_all(list_t **l, int elem) {
    list_t **p = l;
 
    while (*p) {
        list_t *const q = *p;
 
        if (q->elem == elem) {
            *p = q->next;
            free(q);
        }
        else
            p = &q->next;
    }
}
 
void dump(const list_t *l) {
    printf("[ ");
 
    while (l) {
        printf("%d ", l->elem);
        l = l->next;
    }
 
    puts("]");
}

Code:

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
#include <stdlib.h>
 
typedef struct list_s list_t;
 
list_t *append(list_t **, int);
void clear(list_t **);
void remove_all(list_t **, int);
void dump(const list_t *);
 
 
int main(int argc, char *argv[]) {
    (void)argc; (void)argv;
 
    list_t *l = NULL;
    dump(l);
 
    append(&l, 42);
    dump(l);
 
    append(&l, -1);
    append(&l, 10);
    append(&l, -1);
    append(&l, 2);
    append(&l, 18);
    append(&l, -1);
    dump(l);
 
    remove_all(&l, -1);
    dump(l);
 
    append(&l, 42);
    append(&l, 123456789);
    append(&l, 42);
    dump(l);
 
    remove_all(&l, 42);
    dump(l);
 
    clear(&l);
    dump(l);
 
    return 0;
}

Code:

1
2
3
4
5
6
7
8
9
$ gcc -std=c11 -pedantic -Wall -Wextra -g list.c main.c
$ ./a.out
[ ]
[ 42 ]
[ 42 -1 10 -1 2 18 -1 ]
[ 42 10 2 18 ]
[ 42 10 2 18 42 123456789 42 ]
[ 10 2 18 123456789 ]
[ ]