Discussion :

[arnodujura]

Bonjour,
je suis débutant, je travaille sur les listes chainées, j'aimerais avoir le code d'une fonction qui supprime les doublons dans une liste.

...voici mon type liste, il marche j'ai les fonctions d'affichage, d'insertion etc... qui fonctionnent parfaitement.

Code :

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

1
2
3
4
5
6
7
struct maille{
	int valeur;
	struct maille *suivant;
};
 
typedef struct maille Maillon;
typedef Maillon *Liste;

[souviron34]

et quelle est ta proposition ??

[Médinoc]

Mon conseil 1: Deux boucles imbriquées (complexité: O(n²))
Mon conseil 2: Tu tries la liste, puis tu trouveras plus facilement les doublons (complexité: O(n) pour la suppression, mais pour le tri d'une liste chaînée je ne sais pas).

[arnodujura]

Alors je précise, ma liste est déjà trié, mais il y a des doublons...
C'est le sujet de mon TP, faut pas essayer de comprendre pourquoi la fonction d'insertion trie et autorise les doublons...
J'ai une liste chainée trié, il y a des doublons et je veux les supprimer, je commence seulement en c, je n'arrive pas a réaliser cette fonction...

[cedriku]

Bonjour,

est ce que ta liste peut contenir n'importe quel entier ou bien tu connais le maximum qu'elle puisse avoir ??

Si oui et que ce maximum n'est pas "trop grand" alors il y a un moyen simple et efficace en utilisant un tableau de booleen annexe dont la taille vaut l'entier maximum que ta liste peut contenir. Dans ce tableau (notons le tab) une case i vaut 1 si l'entier i a deja ete trouve dans la liste. L'algorithme consiste alors a parcourir la liste et pour chaque entier X lu, tu test si tab[X]=1. Si oui alors c'est que l'entier X a deja ete lu avant et donc il faut le supprimer, sinon alors c'est que c'est la premiere fois que tu rencontre X et donc tu mets 1 dans tab[X] (pour dire que l'entier X appartient a ta liste). Du coup, la prochaine fois que tu rencontrera l'entier X alors en testant tab[X] tu sauras qu'il faut le supprimer.

Enfin bon cet algo est tres efficace etant donne qu'il est lineaire en le nombre d'element de la liste mais a l'inconvenient d'utiliser un tableau qui peut etre de taille tres tres grande (si le maximum de ta liste est un nombre tres grand voir infini !).

D'ou la question: est ce que tu as des hypotheses sur tes entiers dans ta liste ?

[Médinoc]

Si elle est déjà triée, c'est simple: Tu parcours la liste, en mémorisant la valeur (et sûrement aussi l'adresse) du dernier élément parcouru, et si l'élément courant est égal, tu supprimes l'élément courant (en utilisant par exemple l'adresse du précédent)

[arnodujura]

Pr répondre à cedriku : non je n'ai pas de maximum donc je ne pense pas que ta solution avec un tableau soit optimisé...

La solution pour moi est celle de médinoc, c'est ce que je veux faire depuis le début sauf que je n'arrive pas à le coder... je n'arrive pas à supprimer l'élément courant...

[diogene]

Le problème de base est "Comment supprimer un élément d'une liste chaînée".

C'est assez simple à écrire pour une liste doublement chaînée, mais plus délicat pour une liste simplement chaînée puisque, comme le mentionne Médinoc, il faut avoir l'adresse du chaînon précédant celui que tu veux enlever pour reconstituer le chaînage.

Dans ton cas, heureusement, c'est plus simple puique tu veux simplement supprimer les doublons et que ta liste est classée.
Ton problème se simplifie en "Comment supprimer le chaînon suivant un chaînon donné".

Par conséquent :

1- Tu ne supprime jamais le chaînon de tête et la tête de liste n'est donc pas modifiée

2-a- Si la liste n'est pas vide, désigner le chaînon de tête comme chaînon courant
sinon, c'est fini.

2-b- Tant que le suivant du chaînon courant existe et fait doublon avec le chaînon courant, supprimer le chaînon suivant.

2-c- Si le (nouveau) suivant du chaînon courant existe (et donc d'après 2-b ne peut être un doublon) , changer le chaînon courant pour son (nouveau) suivant
Sinon, c'est fini