Supprimer doublon d'un tableau

Version imprimable

Bonjour à tous,

Je suis nouvelle et je débute en C++.

j'essaie d'enlever les doublons d'un tableau tab[10]={5,3,6,3,3,8,4,7,8,5} pour avoir au final un tableau sans doublon tabSansDoublon [7]={5,3,6,8,4,7}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
tabSansDoublon [0] = tab[0]; 
        t=1;
        for ( i= 1; i<=nb-1; i++){
            for( j = 0; j<=i; j++){
                if (tab[i] == tab[j]){
                }
            }
                tabSansDoublon [t] = tab[i];
                t++;
 
        }
        for( k=0; k<=t; k++)
        cout<< tabSansDoublon [k];
 
 
        }

Si vous pouvez m'aider à me dire ce qui ne va pas. merci

14/02/2014, 09h54
LittleWhite

Bonjour,

L'idée est de faire la chose suivante :
Pour chaque élément du tableau d'origine :
- Parcourir le tableau de destination à la recherche de cette élément
- s'il n'existe pas, rajouter cet élément
- s'il existe, passer à l'élément suivant

Notez que grâce aux structures de données du C++ (vector, map et autre) vous pouvez vous en sortir en codant le strict minimum.
14/02/2014, 11h22
imperio
Je rejoins l'avis de LittleWhite concernant les conteneurs C++, les vectors sont bien plus simples a utiliser. Cependant si tu tiens absolument a rester dans cette logique, je te conseille de t'y prendre de cette facon :
Code:

1 2 3 4 5 6 7 for (int i = 0; i < tab_size; ++i) for (int j = i; j < tab_size; ++j) if (tab[i] == tab[j]) { memmove(); //cherche ce qu'il faut mettre la --tab_size; j = i - 1; }
Voila en gros ce que je ferais, je te laisse remplacer les parties manquantes (en l'occurrence la suppression des doublons puisque c'est ce qui t'interesse).

merci, pour vos réponse je suis d'accord avec LittleWhite

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
tabSansDoublon [0] = tab[0]; 
        t=1;
//Parcourir le tableau de destination à la recherche de cette élément
        for ( i= 1; i<=nb-1; i++){
            for( j = 0; j<=i; j++){
//s'il existe, passer à l'élément suivant, ici j'ai la boucle
                if (tab[i] == tab[j]){
                }
            }
//s'il n'existe pas, rajouter cet élément
                tabSansDoublon [t] = tab[i];
                t++;
 
        }
        for( k=0; k<=t; k++)
        cout<< tabSansDoublon [k];
 
 
        }

imperio, je n'ai pas vraiment saisie :oops: ton algo

Littlewhite, j'ai essayé de suivre ton raisonnement:

Code:

1
2
3
4
5
6
7
8
   tabSansDoublon [0] = tab[0];
        t=1;
        for ( i= 1; i<=nb-1; i++){
            if (tab[i] != tab[i-1]){
               tabSansDoublon [t] = tab[i];
                t++;
                 }
           }

sa ne marche pas :-(

Quel code devons nous corriger ?
Les deux sont faux :aie:
Déjà soyez précis sur l'indentation, dans le premier code, il est dur de voir les début et fin des for/if.
Voici comment il doit être présenté :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 tabSansDoublon [0] = tab[0]; t=1; //Parcourir le tableau de destination à la recherche de cette élément for ( i= 1; i<=nb-1; i++){ for( j = 0; j<=i; j++){ //s'il existe, passer à l'élément suivant, ici j'ai la boucle if (tab[i] == tab[j]){ } } //s'il n'existe pas, rajouter cet élément tabSansDoublon [t] = tab[i]; t++; } for( k=0; k<=t; k++) cout<< tabSansDoublon [k]; }
Voyons maintenant ce qui ne va pas ?
Code:

1 2 if (tab[i] == tab[j]){ }
Un test où vous ne faites rien ?
Que se passe t-il (que devrait t-il se passer) lorsque l'on trouve un élément qui est déjà présent ?

Ensuite :
Code:

1 2 3 4 5 6 7 8 for( j = 0; j<=i; j++){ //s'il existe, passer à l'élément suivant, ici j'ai la boucle if (tab[i] == tab[j]){ } } //s'il n'existe pas, rajouter cet élément tabSansDoublon [t] = tab[i]; t++;
Ok, nous avons une boucle for ... mais, techniquement, pour moi, elle semble ne rien faire. Ensuite, on copie l'élément du tableau d'origine, vers la destination.

:whistle: Il y a peut être quelque chose à modifier, non ?

14/02/2014, 22h06
JolyLoic

Petit détail par rapport à l'algorithme proposé par LittleWhite : Il n'est pas optimal. Dès que tu auras beaucoup de données à gérer, il va mettre trop longtemps. Ce qui n'est pas forcément gênant dans le cadre d'un exercice d'apprentissage, mais pourrait le devenir. Et dans le cadre d'un apprentissage, c'est aussi intéressant de voir pourquoi c'est le cas. Donc, une fois que tu auras un algorithme qui marche, je t'invite à en calculer la complexité, et à réfléchir comment faire mieux.

j'ai essayé de modifié if (tab[i] == tab[j]) par != et enlever un for

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
tabSansDoublon [0] = tab[0]; 
t=1;
	//Parcourir le tableau de destination à la recherche de cette élément
	for ( i= 1; i<=nb-1; i++){
	      if (tab[i] != tab[i-1]){ //si pas d'égalité on ajoute  et si égalité sa boucle non?
		    tabSansDoublon [t] = tab[i];
		    t++; 
              }
	}
 
	for( k=0; k<=t; k++){
	    cout<< tabSansDoublon [k];
        }

15/02/2014, 02h41
imperio

Si tu commences a tester toutes les comparaisons de nombres partout dans ton code t'es pas sorti de l'auberge... Reflechis avant de coder.

1. on parcourt le tableau tant que tab[j] != tab[i]
2. on trouve un doublon
3. on supprime le doublon (en decalant tout le tableau pour supprimer la valeur par exemple, memmove le fait)
4. on reprend a l'ancienne position et c'est reparti pour un tour.

A ce niveau c'est de l'algorithmique basique, il faut juste que tu reflechisses calmement avant de coder. Ecris le raisonnement sur une feuille de papier si ca peut t'aider (je le fais relativement souvent donc j'approuve cette methode). Inutile de revenir nous dire a chaque fois que t'as change un if que ca ne fonctionne toujours pas. On n'est pas la pour le faire a ta place et ca n'aurait de toute facon aucun interet pour toi.
15/02/2014, 18h33
nathaliepak

Merci pour votre aide,

Imperio, je ne connais pas encore la fonction memmove je débute tout juste, j'essai d'abord de faire sans.

Je vous tient au courant de mon avancement
15/02/2014, 20h41
imperio

La fonction memmove est la pour nous faciliter la vie, il est tout a fait possible de faire sans. Si jamais tu veux savoir ce qu'elle fait, regarde ici.

Si tu as la possibilité d'utiliser la STL et C++11, tu peux faire ça simplement:
si tu n'as pas besoin de respecter l'ordre des éléments:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 #include <set> #include <vector> #include <algorithm> #include <iostream> int main() { int tab[10]={5,3,6,3,3,8,4,7,8,5}; std::set<int> uniq(std::begin(tab), std::end(tab)); std::vector<int> result(std::begin(uniq), std::end(uniq)); std::for_each(std::begin(result), std::end(result), [](int i){ std::cout << i << " "; } ); std::cout << std::endl; }
si tu peux utiliser boost, c'est encore plus simple:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include <iostream> #include <boost/range/algorithm/for_each.hpp> #include <boost/range/adaptor/uniqued.hpp> #include <boost/range/algorithm/sort.hpp> int main() { int tab[10]={5,3,6,3,3,8,4,7,8,5}; using namespace boost; using namespace adaptors; for_each(sort(tab) | uniqued, [](int i){ std::cout << i << " "; } ); std::cout << std::endl; }
si tu as besoin de respecter l'ordre de tes éléments et que tu peux utiliser boost, c'est également quelques lignes de code:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include <set> #include <iostream> #include <boost/range/algorithm/for_each.hpp> #include <boost/range/adaptor/filtered.hpp> int main() { int tab[10]={5,3,6,3,3,8,4,7,8,5}; using namespace boost; using namespace adaptors; std::set<int> uniq; auto result = tab | filtered([&uniq](int i){ return uniq.insert(i).second; }); for_each(result, [](int i){ std::cout << i << " "; } ); std::cout << std::endl; }
Bon après j'ai conscience que ça ressemble fortement à un exercice mais c'est pour illustrer le fait qu'avec les bons outils, on évite de trop se prendre la tête et on évite ainsi de nombreuses sources (potentielles) de bug.

Citation:

Envoyé par CedricMocquillon

Bon après j'ai conscience que ça ressemble fortement à un exercice mais c'est pour illustrer le fait qu'avec les bons outils, on évite de trop se prendre la tête et on évite ainsi de nombreuses sources (potentielles) de bug.

Pas besoin de boost pour si peu
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 int tab[10]={5,3,6,3,3,8,4,7,8,5}; int s=0; // garder l'ordre std::set<int> uniq; for(int i=0; i<10; ++i) { if(uniq.insert(tab[i]).second) { tab[s++] = tab[i]; } } for(int i=0; i<s; ++i) { std::cout << tab[i]; } // ou sans garder l'ordre std::sort(tab, tab+10); s = std::distance(tab, std::unique_copy(tab, tab+10, tab)); for(int i=0; i<s; ++i) { std::cout << tab[i]; }
Mais effectivement le but ici est très certainement de coder l'algo à la main.