Discussion :

[benjamin_malaussene]

Bonsoir,

J'ai essayé de coder une procédure qui permet de supprimer les doublons dans un tableau de caractères, ils sont remplacés par un caractère vide et placés à la fin du tableau, mais ça ne marche pas :

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define NMAX 200
 
void gen_aleat( char v[], int n )
{
 int i;
 /* rand() retourne un entier aléatoire de l'ens {0,1,2,..,RAND_MAX} (RAND_MAX fixé à 32767 sous VC++)*/
 for(i = 0; i < n; i++) v[i] = rand()%(122-97) +97;/* pour avoir aussi des nbrs<0 */
}
 
void aff_vect( char v[], int n )
{
 int i;
 for( i = 0; i < n; i++ )
 {
	 printf( "%c", v[i] );
     if ( (i+1) % 10 == 0 ) printf( "\n" );
 }
 printf( "\n" );
}
 
void doublons (char v[], int n)
{
    int i;
    int j;
    int cpt;
    char echange;
 
    i = 0;
    while (i < n)
    {
        j = i + 1;
        while (j< n)
        {
            while (v[i]==v[j])
            {
                cpt = cpt + 1;
                v[j]=' ';
                echange = v[j];
                v[j] = v[n-cpt];
                v[n-cpt]=echange;
            }
            j = j +1;
        }
        i = i + 1;
    }
}
 
int main()
{
    char v[NMAX];
    int n;
    int ok;
 
    srand(time(NULL));
 
    do
    {
     printf( "Entrer le nb d'elements du vecteur ( <= %d ) : ", NMAX );
     ok = scanf( "%d", &n );
	 while( getchar( ) != '\n' );  /* ou fgets(vb,80,stdin)  avec  char vb[81];  */
   }while( !ok || n < 0 || n > NMAX );
 
    gen_aleat( v, n );
    printf( "Voici le tableau genere :\n" );
    aff_vect( v, n );
 
    printf("Voici le tableau apres suppression des doublons : \n");
    doublons(v,n);
 
    return 0;
}

[Sve@r]

Bonsoir

ils sont remplacés par un caractère vide et placés à la fin du tableau,

"vide" ça n'existe pas en prog. Donc tout caractère dédoublé est remplacé par un espace. Et au final tous les espaces dédoublés ils sont remplacés par quoi ???

mais ça ne marche pas :

Oui ben ici c'est un forum d'aide, pas un forum où on va réfléchir à ta place. A toi de mettre du printf() là où il faut pour vérifier que tes éléments correspondent à ce que tu attends...

Code :

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

1
2
3
4
5
6
7
8
9
 
            while (v[i]==v[j])
            {
                cpt = cpt + 1;
                v[j]=' ';
                echange = v[j];
                v[j] = v[n-cpt];
                v[n-cpt]=echange;
            }

Je ne comprends pas cette boucle tant que v[i] est égal à v[j] alors que dans le corps, v[j] change. Fatalement au premier tour de boucle, ils ne sont plus égaux (sauf si v[i] est égal à un espace ce qui ramène à ma première question). Accessoirement écrire v[j]=truc puis juste en dessous v[j]=chose c'est un peu idiot non ? Surtout pour la variable (mot signifiant "qui varie") "echange" qui ne contient en tout et pour tout qu'un simple espace et qui, donc, ne "varie" absolument pas...

Code :

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

/* ou fgets(vb,80,stdin)  avec  char vb[81];  */

J'ai déjà écrit un truc à ce sujet. Ce n'est pas la peine de poser des questions sur les forums si tu ne lis pas ce qu'on t'écrit !!!

[foetus]

Tu es au taquet avec tes tableaux: insertion dans un tableau, suppression de doublons, échange de cases:
PS: tu n'en as pas marre de faire des algos "sur place"

Sinon cpt = cpt + 1;, est indéterminée parce que cpt n'est pas initialisée.
Cela te pendait au nez en séparant la déclaration et l'initialisation

Et enfin tu t'y prends mal (ou alors je ne comprends pas ce que tu veux faire *) parce que cpt doit être décrémenté parce que initialisée à la dernière case.

* -> Tu préfères utiliser un nombre de cases remplies qu'une vrai case

[benjamin_malaussene]

Désolé je suis désespéré, j'ai modifié ma procédure mais ça ne marche toujours pas :

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define NMAX 200
 
void gen_aleat( char v[], int n )
{
 int i;
 /* rand() retourne un entier aléatoire de l'ens {0,1,2,..,RAND_MAX} (RAND_MAX fixé à 32767 sous VC++)*/
 for(i = 0; i < n; i++) v[i] = rand()%(122-97) +97;/* pour avoir aussi des nbrs<0 */
}
 
void aff_vect( char v[], int n )
{
 int i;
 for( i = 0; i < n; i++ )
 {
	 printf( "%c", v[i] );
     if ( (i+1) % 10 == 0 ) printf( "\n" );
 }
 printf( "\n" );
}
 
void doublons (char v[], int n)
{
    int i;
    int j;
 
    i = 0;
    while (i < n)
    {
        j = i + 1;
        while (j < n-1)
        {
            if (v[i]==v[j] && v[i]!= ' ')
                {
                    while (j < n-1)
                    {
                        v[j]=v[j+1];
                        j = j+1;
                    }
                    v[n-1]=' ';
                }
            j = j +1;
        }
        i = i + 1;
    }
 
 
}
 
int main()
{
    char v[NMAX];
    int n;
    int ok;
 
    srand(time(NULL));
 
    do
    {
     printf( "Entrer le nb d'elements du vecteur ( <= %d ) : ", NMAX );
     ok = scanf( "%d", &n );
	 while( getchar( ) != '\n' );
   }while( !ok || n < 0 || n > NMAX );
 
    gen_aleat( v, n );
    printf( "Voici le tableau genere :\n" );
    aff_vect( v, n );
 
    printf("Voici le tableau apres suppression des doublons : \n");
    doublons(v,n);
    aff_vect( v, n );
 
    return 0;
}

[Sve@r]

Désolé je suis désespéré, j'ai modifié ma procédure mais ça ne marche toujours pas :

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
while (i < n)
    {
        j = i + 1;
        while (j < n-1)
        {
            if (v[i]==v[j] && v[i]!= ' ')
                {
                    while (j < n-1)
                    {
                        v[j]=v[j+1];
                        j = j+1;
                    }
                    v[n-1]=' ';
                }
            j = j +1;
        }
        i = i + 1;
    }

Ben oui. Tant que tu n'auras pas dessiné sur un papier ton tableau avec tes lettres et schématisé le fonctionnement tu ne pourras pas le coder correctement (ce que foetus dit quand il parle d'algos "sur place").
Ici tu boucles tant que j < n-1 (pourquoi "n-1" alors que pour moi, si je dois comparer la première lettre du tableau avec toutes les autres, il me faudra alors dérouler le tableau de la suivante jusqu'à la fin et non m'arrêter une case avant !!!) puis en dessous de nouveau une boucle identique. Avec j qui s'incrémente. Donc quand la seconde boucle se termine, j est arrivé à la fin et la première boucle s'arrête aussi.
Si tu réfléchis 2mn avant de coder, tu te rendras compte que pour éliminer les doublons, il faut prendre la première lettre et comparer toutes les autres ; puis prendre la seconde et comparer toutes les autres ; et etc. Donc c'est deux boucles et non 3 !!!

[benjamin_malaussene]

C'est bon ça marche, j'ai remplacé j par k dans la 3e boucle et je l'ai initialisé à j :

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define NMAX 200
 
void gen_aleat( char v[], int n )
{
 int i;
 /* rand() retourne un entier aléatoire de l'ens {0,1,2,..,RAND_MAX} (RAND_MAX fixé à 32767 sous VC++)*/
 for(i = 0; i < n; i++) v[i] = rand()%(122-97) +97;/* pour avoir aussi des nbrs<0 */
}
 
void aff_vect( char v[], int n )
{
 int i;
 for( i = 0; i < n; i++ )
 {
	 printf( "%c", v[i] );
     if ( (i+1) % 10 == 0 ) printf( "\n" );
 }
 printf( "\n" );
}
 
void doublons (char v[], int n)
{
    int i;
    int j;
    int k;
 
    i = 0;
    while (i < n)
    {
        j = i + 1;
        while (j < n-1)
        {
            if (v[i]==v[j] && v[i]!= ' ')
                {
                    k =j;
                    while (k < n-1)
                    {
                        v[k]=v[k+1];
                        k = k+1;
                    }
                    v[n-1]=' ';
                }
            j = j +1;
        }
        i = i + 1;
    }
 
 
}
 
int main()
{
    char v[NMAX];
    int n;
    int ok;
 
    srand(time(NULL));
 
    do
    {
     printf( "Entrer le nb d'elements du vecteur ( <= %d ) : ", NMAX );
     ok = scanf( "%d", &n );
	 while( getchar( ) != '\n' );
   }while( !ok || n < 0 || n > NMAX );
 
    gen_aleat( v, n );
    printf( "Voici le tableau genere :\n" );
    aff_vect( v, n );
 
    printf("Voici le tableau apres suppression des doublons : \n");
    doublons(v,n);
    aff_vect( v, n );
 
    return 0;
}

[Sve@r]

C'est bon ça marche, j'ai remplacé j par k dans la 3e boucle et je l'ai initialisé à j :

Non, ça ne marche pas
En faisant des tests, j'ai remarqué que "cbshadapys" devenait "cbshadpys". Certes le "a" dédoublé disparait mais le "s" dédoublé reste dédoublé.
Rajoute l'instruction strcpy(v, "cbshadapys") en fin de gen_alea() et tu pourras le vérifier toi-même. Et je t'ai déjà dit que 3 boucles ce n'était pas utile (et en prog, "pas utile" signifie "à ne pas faire" !!!)

Code c :

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

1
2
3
4
5
void gen_aleat( char v[], int n )
{
 int i;
 /* rand() retourne un entier aléatoire de l'ens {0,1,2,..,RAND_MAX} (RAND_MAX fixé à 32767 sous VC++)*/
 for(i = 0; i < n; i++) v[i] = rand()%(122-97) +97;/* pour avoir aussi des nbrs<0 */

Pourquoi 122-97 ? Pourquoi pas directement 26 (au fait, 122-97 ça fait 25 !!!)
Donc tu veux une lettre entre 'a' et 'z' tu demandes bêtement un rand() % 26 + 'a', ça t'évitera au-moins les erreurs de calcul !!!

[benjamin_malaussene]

Merci pour tes conseils, tu as raison il reste quand même des doublons. En fait la première boucle pointe sur une case du tableau, la deuxième boucle compare toutes les cases suivantes à la case pointée, et la 3e boucle décale tous les éléments sur la gauche si un doublon est trouvé, et rajoute un caractère vide à la fin du tableau. comment est ce que tu ferais pour supprimer tous les doublons ?

[foetus]

Très scolaire avec un booléen

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
#include<stdlib.h>
#include<stdio.h>
 
 
void init_tab(unsigned int** tab, unsigned int* len) {
    if ((tab == NULL) || (len == NULL)) { return; }
 
    unsigned int ftab[] = {1, 1, 5, 8, 9, 9, 6, 4, 3, 8 , 2, 7, 7, 9, 5, 4, 1, 10, 6, 11, 6};
    unsigned int flen = (sizeof(ftab) / sizeof(ftab[0])), pos = 0;
 
    (*tab) = malloc(flen * sizeof(unsigned int));
    (*len) = flen;
 
    for(; pos < flen; ++pos) {
        (*tab)[pos] = ftab[pos];
    }
}
 
 
void print_tab(unsigned int* tab, unsigned int len) {
    if (tab == NULL) { return; }
 
    unsigned int pos = 0;
 
    for(; pos < len; ++pos) {
        printf("%d ", tab[pos]);
    }
    printf("\n");
}
 
 
int main(int argc, char* argv[])
{
    unsigned int* tab = NULL;
    unsigned int* new_tab = NULL;
    unsigned int len = 0, index = 1, pos = 1, search = 0;
    unsigned char is_found = 0;
 
    init_tab(&tab, &len);
    print_tab(tab, len);
 
    for(pos = 1; pos < len; ++pos) {
        for(search = 0, is_found = 0; ((search < index) && (!is_found)); ++search) {
            if (tab[search] == tab[pos]) {
                is_found = 1;
            }
        }
 
        if (!is_found) {
            tab[index] = tab[pos];
            ++index;
        }
    }
 
    new_tab = realloc(tab, index * sizeof(unsigned int));
 
    if (new_tab == NULL) { return 0; }
 
    tab = new_tab;
    len = index;
    print_tab(tab, index);
 
    free(new_tab);
 
    return 0;
}

[Sve@r]

comment est ce que tu ferais pour supprimer tous les doublons ?

Ca dépend de ton besoin.
Si tu veux garantir l'ordre des lettres non dédoublées, il te faut alors effectivement "recoller" le reste de ton tableau chaque fois que tu as une lettre en double. Effectivement pour ça il faut une 3° boucle mais si c'est une boucle de "recollement" alors pas besoin de tester quoi que ce soit.
Si tu ne désires pas garantir l'ordre des lettres, alors pas beoin de 3° boucle. Tu places un pointeur sur la fin de ton tableau et dès que t'as trouvé une lettre dédoublée tu la permutes avec la dernière et tu décrémentes le le pointeur de fin.
On nomme ce critère (ordre garanti/non garanti) "stabilité". Il est très omniprésent dans les algorithmes de tris (si j'ai par exemple un jeu de cartes avec 2T, 3P, 4C, 2K et donc le 2 de trèfle placé avant le 2 de carreau avant le tri ; et que je trie par valeurs, j'aurai alors 2, 2, 3, 4 mais est-ce que je suis garanti d'avoir 2 de trèfle toujours avant le 2 de carreau..)

Démo

Code c :

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
99
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
 
#define NMAX 200
 
void gen_aleat( char v[], int n )
{
	int i;
	/* rand() retourne un entier aléatoire de l'ens {0,1,2,..,RAND_MAX} (RAND_MAX fixé à 32767 sous VC++)*/
	for(i = 0; i < n; i++) v[i] = rand() / (double)RAND_MAX * 26.0 + 'a';
	v[n]='\0';	// Et hop, mon vecteur devient une chaine !!!
}
 
void aff_vect(char v[])
{
	puts(v);
}
 
void unstable(char v[])
{
	char *deb, *cmp, *fin;
 
	// On se place sur la fin
	for (fin=v; *fin != '\0'; fin++);
 
	// On traite chaque caractère
	for (deb=v; *deb != '\0'; deb++)
	{
		// On compare le caractère avec les suivants
		for (cmp=deb+1; *cmp != '\0'; cmp++)
		{
			// Si le caractère est le même
			if (*deb == *cmp)
			{
				// On le permute avec le dernier
				fin--;
				*cmp=*fin;
				*fin='\0';
			}
		}
	}
}
 
void stable(char v[])
{
	char *deb, *cmp, *copie;
 
	// On traite chaque caractère
	for (deb=v; *deb != '\0'; deb++)
	{
		// On compare le caractère avec les suivants
		for (cmp=deb+1; *cmp != '\0'; cmp++)
		{
			// Si le caractère est le même
			if (*deb == *cmp)
			{
				// On recolle les suivants
				for (copie=cmp; *copie != '\0'; copie++)
					*copie=*(copie+1);
			}
		}
	}
}
 
int main()
{
	char v[NMAX];
	char copie[NMAX];
	int n;
	int ok;
 
	srand(time(NULL));
 
	do
	{
	 printf( "Entrer le nb d'elements du vecteur ( <= %d ) : ", NMAX );
	 ok = scanf( "%d", &n );
	 while( getchar( ) != '\n' );
	}while( !ok || n < 0 || n > NMAX );
 
	gen_aleat(v, n);
	printf("Voici le tableau genere (%d lettres): ", strlen(v));
	aff_vect(v);
 
	// Test algorithme instable
	strcpy(copie, v);
	unstable(copie);
	printf("Voici le tableau (instable) apres suppression des doublons (%d lettres): ", strlen(copie));
	aff_vect(copie);
 
	// Test algorithme stable
	strcpy(copie, v);
	stable(copie);
	printf("Voici le tableau (stable) apres suppression des doublons (%d lettres): ", strlen(copie));
	aff_vect(copie);
	return 0;
}

PS: mettre des commentaires aide aussi à réorganiser sa pensée durant le codage...

[benjamin_malaussene]

Salut foetus,

Merci bcp pour ta réponse, mais je ne suis pas assez calée en c pour comprendre ton code. Est ce que tu pourrais éventuellement traduire ton code en python, car on utilise la syntaxe du python dans nos cours d'algo. Sinon c'est pas grave, merci.

[foetus]

Simple je ne recopie pas la fin pour écraser un doublon (algo stable de Sve@r et apparemment ce que tu essayes de faire) ni je mets les uniques à la fin (algo unstable de Sve@r).

Je fais comme le Quick Sort , et ma suppression de doublons me semble stable
Tu as un tableau qui va de 0 à len.
Et tu as un index index (<- son petit nom) qui dit que les éléments entre 0 et (index - 1) sont uniques.

Donc tu commences avec index à 1, pour chaque élément de 1 à len, tu le testes s'il est unique, s'il n'est pas entre 0 et (index - 1) compris.
S'il est unique, tu le permutes (tu le mets à l'indice index) et tu incrémentes index

Non pas de python: je n'ai pas de compilateur pour tester

[Sve@r]

Je fais comme le Quick Sort , et ma suppression de doublons me semble stable

Quick Sort est un algo de tri instable. Pour le tien j'ai essayé de regarder mais en fait je me suis levé à 4h ce matin donc le cerveau c'est plus trop ça
Mais si tu garantis que les lettres non dédoublées sont repositionnées dans le même ordre qu'à l'origine alors il est stable

S'il est unique, tu le permutes (tu le mets à l'indice index) et tu incrémentes index

Ben en fait c'est bon, il est stable. Puisque selon ta description, l'élément "i" va sur l'élément "index" et que index s'incrémente immédiatement, alors l'élément "i+k1" (à l'origine placé après "i" puisque k1 positif) sera placé sur l'élément "index+k2" (k2 positif aussi) donc pas forcément avec le même écart qu'à l'origine mais quand-même après l'élément "index". L'ordre relatif de deux élements est donc assuré

Bon maintenant que les différentes méthodes ont été montrées, je m'allonge dans le canapé et je somnole en regardant un épisode de "Columbo" pendant qu'Armay ingurgite tout ça

[Sve@r]

En plus, je viens de me rendre compte que ça ne marche pas dans le cas spécial où la lettre traitée est égale à la dernière. Ca permute certes mais la nouvelle lettre fait encore doublon avec la lettre en cours d'évaluation. Et l'algo pensant avoir réglé le soucis passe à la lettre suivante et ne s'en préoccupe plus => le doublon reste

Solution effectivement: remplacer le test de la comparaison par une boucle (tu avais raison). Ceci dit, avec un algo proprement construit dès le départ (malgré ce cas particulier non traité), le réparer devient alors très facile.

Code c :

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
99
100
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
 
#define NMAX 200
 
void gen_aleat( char v[], int n )
{
	int i;
	// rand() retourne un entier aléatoire de l'ens {0,1,2,..,RAND_MAX} (RAND_MAX fixé à 32767 sous VC++)
	// for(i = 0; i < n; i++) v[i] = rand() / (double)RAND_MAX * 26.0 + 'a';
	for (i = 0; i < n; i++) v[i] = rand() / (double)RAND_MAX * 10.0 + 'a';  // En limitant à 10 lettres j'augmente les chances d'avoir un ou plusieurs doublons
	v[n]='\0';	// Et hop, mon vecteur devient une chaine !!!
}
 
void aff_vect(char v[])
{
	puts(v);
}
 
void unstable(char v[])
{
	char *deb, *cmp, *fin;
 
	// On se place sur la fin
	for (fin=v; *fin != '\0'; fin++);
 
	// On traite chaque caractère
	for (deb=v; *deb != '\0'; deb++)
	{
		// On compare le caractère avec les suivants
		for (cmp=deb+1; *cmp != '\0'; cmp++)
		{
			// Tant que le caractère est le même
			while (*deb == *cmp)
			{
				// On le permute avec le dernier
				fin--;
				*cmp=*fin;
				*fin='\0';
			}
		}
	}
}
 
void stable(char v[])
{
	char *deb, *cmp, *copie;
 
	// On traite chaque caractère
	for (deb=v; *deb != '\0'; deb++)
	{
		// On compare le caractère avec les suivants
		for (cmp=deb+1; *cmp != '\0'; cmp++)
		{
			// Tant que le caractère est le même
			while (*deb == *cmp)
			{
				// On recolle les suivants
				for (copie=cmp; *copie != '\0'; copie++)
					*copie=*(copie+1);
			}
		}
	}
}
 
int main()
{
	char v[NMAX];
	char copie[NMAX];
	int n;
	int ok;
 
	srand(time(NULL));
 
	do
	{
	 printf( "Entrer le nb d'elements du vecteur ( <= %d ) : ", NMAX );
	 ok = scanf( "%d", &n );
	 while( getchar( ) != '\n' );
	}while( !ok || n < 0 || n > NMAX );
 
	gen_aleat(v, n);
	printf("Voici le tableau genere (%d lettres): ", strlen(v));
	aff_vect(v);
 
	// Test algorithme instable
	strcpy(copie, v);
	unstable(copie);
	printf("Voici le tableau (instable) apres suppression des doublons (%d lettres): ", strlen(copie));
	aff_vect(copie);
 
	// Test algorithme stable
	strcpy(copie, v);
	stable(copie);
	printf("Voici le tableau (stable) apres suppression des doublons (%d lettres): ", strlen(copie));
	aff_vect(copie);
	return 0;
}

Comment ai-je trouvé la cause du problème ? Tout simplement en affichant mes variables et mon tableau pendant le traitement. Voici ce qu'était mon code pendant ma phase debug

Code c :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
			// Si le caractère est le même
			if (*deb == *cmp)
			{
				printf("deb=%d, cmp=%d, fin=%d ", deb - v, cmp - v, fin - v);
				aff_vect(v);
				// On le permute avec le dernier
				fin--;
				*cmp=*fin;
				*fin='\0';
				aff_vect(v);
				puts("");
			}

Tu remarqueras que je n'ai mis les affichages que dans les cas de doublons repérés (sinon je ne m'en sortais plus). Et le résultat (avec des commentaires perso pour t'aider à comprendre)

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
$ ./essai
Entrer le nb d'elements du vecteur ( <= 200 ) : 10
Voici le tableau genere (10 lettres): dbbbbeccac  // Il y a 4 "b" d'affilée puis deux "c" et un dernier "c"
 
deb=1, cmp=2, fin=10 dbbbbeccac  // Ici il évalue la position 1 (première lettre "b") et il trouve un doublon avec la position 2 (seconde lettre "b")
dbcbbecca  // Ensuite il a permuté la position 2 (le second "b") avec la dernière lettre (ici "c"). Le second "b" disparait - Le tableau se termine donc au "a"
 
deb=1, cmp=3, fin=9 dbcbbecca // Ici il évalue la position 1 (première lettre "b") et il trouve un doublon avec la position 3 (troisième lettre "b")
dbcabecc  // Ensuite il a permuté la position 3 (le troisième "b") avec la dernière lettre (ici "a"). Le troisième "b" disparait - Le tableau se termine donc au troisième "c"
 
deb=1, cmp=4, fin=8 dbcabecc  // Ici il évalue la position 1 (première lettre "b") et il trouve un doublon avec la position 4 (quatrième lettre "b")
dbcacec  // Ensuite il a permuté la position 4 (le quatrième "b") avec la dernière lettre (ici "c"). Le quatrième "b" disparait - Le tableau se termine donc au second "c" qui passe alors troisième (instabilité démontrée)
 
deb=2, cmp=4, fin=7 dbcacec  // Maintenant il évalue la position 2 (première lettre "c") et il trouve un doublon avec la position 4 (seconde lettre "c")
dbcace  // Ensuite il a permuté la position 4 (le second "c") avec la dernière lettre (qui était aussi un "c"). Le second "c" disparait mais l'autre a pris sa place. Et l'algo pensant avoir traité le second "c" en doublon ne s'en occupe plus et déroule ensuite tranquilement le reste du tableau "ace" qui n'ont aucun problème de doublon en aval.
 
Voici le tableau (instable) apres suppression des doublons (6 lettres): dbcace

Ainsi tu vois que trouver la cause d'un soucis n'est pas forcément de suite évident. Il faut déjà avoir une idée de l'endroit où se situe le soucis puis ensuite, faire comme les experts Miami: investiguer et réfléchir...

[foetus]

Pour supprimer les doublons, faire un espèce d'algo glouton de gauche à droite en écrasant les doublons à droite d'un caractère avec le dernier caractère (qui ne soit pas un doublon), tout en réduisant/ maintenant artificiellement la taille du tableau



Et Armays me dit qu'il ne comprend rien à mon algo: je comprends, trop simple, 2 boucles for, 10 lignes avec un booléen qu'on peut supprimer

[Sve@r]

Bon, devant un tel déballage je ne pouvais faire moins que regarder ton code. Qui est effectivement moins glouton que le mien (je traite chaque doublon de la même façon alors qu'en optimisant, je ne traiterais que le dernier)

@Armays: explications du code de foetus: il fait partir un index à 0 qui servira de repère (d'où sa comparaison avec Quick Sort). Puis, chaque élément du tableau qui n'est pas déjà en double dans la partie située entre le début et l'index est alors recopié dans l'élément [index] qui, ensuite, s'incrémente. Donc les doublons ne sont pas recopiés.
Et à la fin, la position de l'index donne la taille du nouveau tableau (il reste des éléments à droite de l'index bien sûr puisque rien n'est venu les écraser mais on est certain que ces éléments sont déjà en double donc on s'en fout). Et effectivement l'algo est stable.

@foetus: le realloc final est inutile car la nouvelle taille est plus petite que l'ancienne. Et dans ce cas, realloc (son but est d'augmenter la taille d'un tableau, pour pouvoir mettre de nouveaux éléments) ne fait rien

[foetus]

@foetus: le realloc final est inutile car la nouvelle taille est plus petite que l'ancienne. Et dans ce cas, realloc (son but est d'augmenter la taille d'un tableau, pour pouvoir mettre de nouveaux éléments) ne fait rien

\HS on

La documentation dit:

The content of the memory block is preserved up to the lesser of the new and old sizes, even if the block is moved to a new location.

Donc on peut supposer 2 choses, pour le cas où la nouvelle taille est plus petite que l'ancienne:

• realloc échange l'ancienne taille avec la nouvelle plus petite, et que la partie "supérieure" est désormais libre.
• realloc peut bouger le bloc pour cause de fragmentation. Par exemple, il y a un trou à boucher et avec la nouvelle taille, notre bloc va [plus ou moins] dans le trou.

Mais bon je te l'accorde , ce ne sont pas nos programmes qu'ils vont fragmenter la mémoire de façon importante

\HS off

[Sve@r]

La documentation dit:

The content of the memory block is preserved up to the lesser of the new and old sizes, even if the block is moved to a new location

Pour ce que j'en comprends (moi et l'anglais ça fait 47), ça dit juste que le contenu du bloc mémoire d'origine est conservé même si le bloc est transféré ailleurs. Mais je comprends un sous-entendu que je pense implicite, c'est que le bloc ne sera transféré que s'il doit-être agrandi.

realloc échange l'ancienne taille avec la nouvelle plus petite, et que la partie "supérieure" est désormais libre.

Moui, ça semble logique. Si la zone commence à l'adresse 0x100 et qu'on alloue 10 octets, les adresses de 0x100 à 0x109 seront réservées. Ensuite si on passe la zone à 5, ça re-réservera alors 0x100 à 0x104 et peut-être que les adresses de 0x105 à 0x109 seront utilisées par un nouveau malloc...

realloc peut bouger le bloc pour cause de fragmentation. Par exemple, il y a un trou à boucher et avec la nouvelle taille, notre bloc va [plus ou moins] dans le trou.

C'est une hypothèse envisageable et qui dénote un esprit de recherche méritoire.
Mais perso je ne pense pas. Parce que ça impliquerait à chaque realloc (inférieur j'entends) une recherche voir si "par hasard" il y aurait un trou adéquat à boucher. Gros algo pour petits résultats non ???

Ceci dit, j'ai pondu un petit test

Code c :

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
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <sys/types.h>
 
#define TEST (100000)
 
typedef struct {
	char *adr;
	size_t n;
} t_test;
 
int main()
{
	t_test tab[TEST];
	t_test *pt;
	char *new;
	size_t i;
 
	srand(time(NULL));
 
	for (i=0, pt=tab; i < TEST; i++, pt++)
	{
		pt->n=rand() / (double)RAND_MAX * 10000 + 1000;
		pt->adr=malloc(pt->n * sizeof(char));
	}
	for (i=0, pt=tab; i < TEST; i++, pt++)
	{
		if (pt->adr == NULL)
		{
			printf("tab[%d] => null\n", i+1);
			continue;
		}
		new=realloc(pt->adr, pt->n / 2 * sizeof(char));
		if (new != pt->adr)
		{
			printf("tab[%d]: 0x%p/0x%p\n", i+1, pt->adr, new);
			if (new != NULL) pt->adr=new;
		}
	}
	for (i=0, pt=tab; i < TEST; i++, pt++)
		free(pt->adr);
}

Hé ben j'ai fait tourner ce programme une dizaine de fois, je n'ai jamais vu apparaitre de changement d'adresses dans les 100000 pointeurs alloués puis réalloués... (mais si on change la formule et qu'on alloue n*2, alors des changements il y en a en masse )

Je suis en train de réfléchir à un autre algo pour vérifier la première hypothèse...

[edit]
Ok, j'ai pondu un second code pour vérifier ta première hypothèse. Mon algo est le suivant: Chaque tableau est alloué de X puis réalloué à X/2 (je mémorise X/2 et X).
Ensuite, je regarde chaque tableau alloué et j'examine si son adresse se trouve comprise entre le X/2 et le X d'un autre tableau de la liste

Ce qui donne ce code

Code c :

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
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <sys/types.h>
#define TEST (100000)
 
typedef struct {
	char *adr;
	size_t orig;
	size_t new;
} t_test;
 
int main()
{
	t_test tab[TEST];
	t_test *pt;
	char *new;
	size_t i;
 
	srand(time(NULL));
 
	// Allocations et réallocations des différents tableaux
	for (i=0, pt=tab; i < TEST; i++, pt++)
	{
		pt->orig=rand() / (double)RAND_MAX * 10000 + 1000;
		pt->adr=malloc(pt->orig * sizeof(char));
		if (pt->adr == NULL)
		{
			printf("tab[%d] => null\n", i+1);
			continue;
		}
		pt->new=pt->orig/2;
		new=realloc(pt->adr, pt->new * sizeof(char));
		if (new != pt->adr)
		{
			printf("tab[%d]: 0x%p/0x%p\n", i+1, pt->adr, new);
			if (new != NULL) pt->adr=new;
		}
	}
 
	// Examen de chaque adresse allouée
	for (i=0, pt=tab; i < TEST; i++, pt++)
	{
		size_t j;
		t_test *cmp;
		for (j=0, cmp=tab; j < TEST; j++, cmp++)
		{
			char *deb=cmp->adr + cmp->new;
			char *fin=cmp->adr + cmp->orig;
 
			if (pt->adr >= deb && pt->adr < fin)
			{
				printf("tab[%d] (0x%p) inclus dans tab[%d] (0x%p, 0x%p-0x%p)\n", i+1, pt->adr, j+1, cmp->adr, deb, fin);
				break;
			}
		}
	}
	for (i=0, pt=tab; i < TEST; i++, pt++)
		free(pt->adr);
	return 0;
}

Et c'est confirmé en masse. En fait, chaque nouveau tableau alloué a son adresse effectivement comprise entre le X/2 et le X du tableau précédent (parfois même trois tableaux n+1, n+2 et n+3 ont chacun leur adresse dans la plage d'origine du tableau n) . Tu avais raison pour ta première hypothèse

[Médinoc]

Mais je comprends un sous-entendu que je pense implicite, c'est que le bloc ne sera transféré que s'il doit-être agrandi.

Intuitivement c'est le cas, et probablement dans pas mal d'implémentations, mais je ne crois pas que ce soit explicitement garanti. Et donc, une implémentation best-fit pourrait déplacer le bloc mémoire pour le placer dans un "seau" plus petit...

[-Eks-]

Bonjour,

Si on peut créer deux tableaux (un avec le tableau d'origine et un avec le tableau déboublonné comme le fait Sve@r dans son code d'exemple), tant qu'à faire, on peut créer un 3ème tableau qui va fonctionner comme une table de hachage permettant de noter les lettres vues.

Comme on n'en a que 26, avec les 26 lettres minuscules, cela ne prend pas beaucoup d'espace.

Cela donne une fonction dedoublonner() comme ceci :

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
void dedoublonner(char * v_dedoublonne, char * v) {
	/* curseurs */
	char * cur_v = v;
	char * cur_v_d = v_dedoublonne;
	/* pour stocker les lettres vues */
	char alpha[26] = { '\0' };
 
	/* parcourir v */
	while (*cur_v) {
		/* si la lettre n'a pas déjà été vue */
		if (!alpha[*cur_v - 'a']) {
			/* noter qu'on l'a vue */
			alpha[*cur_v - 'a'] = *cur_v;
			/* ajouter la lettre à v_dedoublonne, et déplacer son curseur */
			*cur_v_d = *cur_v;
			cur_v_d++;
		}
		cur_v++;
	}
}

Cela accélère et simplifie considérablement l'algorithme, plus besoin de décaler, recoller, etc., on fait cela en une boucle while.

Il faut aussi que v_dedoublonne soit initialisé à zéro dans main, par exemple lors de sa déclaration avec :

Code :

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

char v_dedoublonne[NMAX] = { '\0' };

Ce n'est plus un traitement "en place", car il faut un 2ème tableau, mais c'est efficace :-)

Voilà un code complet d'exemple utilisant la base de Sve@r pour illustrer le fonctionnement de cette fonction dedoublonner() :

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
 
#define NMAX 200
 
void gen_aleat(char v[], int n) {
	int i;
	/* rand() retourne un entier aléatoire de l'ens {0,1,2,..,RAND_MAX} (RAND_MAX fixé à 32767 sous VC++)*/
	for (i = 0; i < n; i++)
		v[i] = rand() / (double) RAND_MAX * 26.0 + 'a';
	v[n] = '\0';	// Et hop, mon vecteur devient une chaine !!!
}
 
void aff_vect(char v[]) {
	puts(v);
}
 
void dedoublonner(char * v_dedoublonne, char * v) {
	/* curseurs */
	char * cur_v = v;
	char * cur_v_d = v_dedoublonne;
	/* pour stocker les lettres vues */
	char alpha[26] = { '\0' };
 
	/* parcourir v */
	while (*cur_v) {
		/* si la lettre n'a pas déjà été vue */
		if (!alpha[*cur_v - 'a']) {
			/* noter qu'on l'a vue */
			alpha[*cur_v - 'a'] = *cur_v;
			/* ajouter la lettre à v_dedoublonne, et déplacer son curseur */
			*cur_v_d = *cur_v;
			cur_v_d++;
		}
		cur_v++;
	}
}
 
int main() {
	char v[NMAX];
	char v_dedoublonne[NMAX] = { '\0' };
	int n;
	int ok;
 
	srand(time(NULL ));
 
	do {
		printf("Entrer le nb d'elements du vecteur ( <= %d ) : ", NMAX);
		ok = scanf("%d", &n);
		while (getchar() != '\n')
			;
	} while (!ok || n < 0 || n > NMAX);
 
	gen_aleat(v, n);
	printf("Voici le tableau genere (%d lettres): ", strlen(v));
	aff_vect(v);
 
	/* dedoublonnage */
	dedoublonner(v_dedoublonne, v);
	printf("tableau dédoublonné (%d lettres): ", strlen(v_dedoublonne));
	aff_vect(v_dedoublonne);
	return 0;
}

Eks