Supprimer une valeur dans un tableau

Version imprimable

Salut à tous, l'exercice dit :

Citation:

Ecrire un programme en "C" qui lit un entier (X) et un tableau (A) de type entier et élimine tous les occurrences de (X) dans (A) en tassant les éléments. {Faire un décalage}.

Le professeur veut une méthode dans laquelle on utilise la notion du pointeur pour résoudre ce problème.

J'ai essayé bien sûr avec cet exercice et j'ai coincé : voici le code de mon programme :
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 #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int val,n,pas,t[30]; int *p=t; printf("Entrer N : ");scanf("%d",&n); for(p=t;p<p+n;p++) {Printf("\nT : ");scanf("%d",p);} printf("\nVal : ");scanf("%d",&val); pas=0; for(p=t;p<t+n;p++) { if(*p!=val) *(p-pas)= *p; if(*p==val) pas++; } system("PAUSE"); return 0; }
Je crois que algorithmiquement c'est vrai mais d'un coté technique je ne sais pas comment faire.

23/02/2009, 12h34
Médinoc
Ce code est pratiquement illisble. Commence par le découper en fonctions (typiquement, garde le main pour l'entrée des paramètres, et fais-toi une fonction pour supprimer X du tableau).
Et aussi, utilise des noms de variable plus explicites (ou au moins, qui correspondent à l'énoncé).

Ensuite, au niveau algorithme, tu as accès à deux méthodes: La méthode "naïve" en O(n²), qui supprime l'élément et fait un décalage à chaque fois, et la méthode plus optimisée en O(n) qui fait le tout en une passe.
Si tu choisis la méthode naïve, pense à mettre la suppression d'un élément dans une autre fonction.

Dans tous les cas, ta fonction doit au minimum avoir ceci:
- En entrée: Un tableau avec sa taille, l'élément à supprimer
- En sortie: Le tableau modifié (sur place), et la nouvelle taille du tableau
Ainsi, comme fonction, je propose ceci:
Code:

1 2 3 4 #include <stddef.h> //Retourne la nouvelle taille du tableau size_t supprime_tous_les_x(int * a, size_t taille_a, int x);
Maintenant, code le contenu de la fonction supprime_tous_les_x(), ainsi que le main() pour l'appeler.

Code:

1 2 3 4 5 6 7 .... for(p=t;p<t+n;p++) // p+n est une erreur { printf("\nT : "); // Printf : Attention, le C est sensible à la casse scanf("%d",p); } ....
Note : Eviter plusieurs instructions par ligne , le programme est moins lisible :

Code:

{printf("\nT : ");scanf("%d",p);}

On n'est pas à quelques lignes près.

Resalut, merci encore pour vous : et voilà une amélioration au niveau de code pour qu'il soit être lisible :

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
#include <stdio.h>
#include <stdlib.h>
int effacer (int *x,int *a,int valsupp);
int affiche(int x,int *a);
int main(int argc, char *argv[])
{
  int n,t[30],val;
  int *p=t;
 
  printf("Entrer N : ");scanf("%d",&n);
  for(p;p<t+n;p++)
  {printf("\nT : ");scanf("%d",p);}
  printf("\nVal : ");scanf("%d",&val);
  system("cls");
  printf("Taille initial : \t%d\n",n);
  affiche(n,t);
  effacer(&n,t,val);
  printf("\n");
  affiche(n,t);
  printf("\n\ntTaille devient : \t%d\n",n);
  system("PAUSE");	
  return 0;
}
int effacer (int *x,int *a,int valsupp)
{
int pas = 0;     
int *p=a;
 
  for(p;p<a+*x;p++)
  {
      //Si le contenu de (*p) est différent à (valsupp)
      //Je déplace la case 
 
      *(p-pas)= *p;
      //Si le contenu de (*p) est égal à (valsupp) 
      //j'augmente le (pas) 
      if(*p==valsupp)
      pas++;
  }
  *x = (*x-pas);
  return 0;
}
int affiche(int x,int *a)
{
    int *p=a;
    for(p;p<a+x;p++)
    printf("%d : ",*p);
    return 0;
    }

Vos remarque SVP!:(:(

24/02/2009, 11h44
Médinoc
Ce code n'est pas aussi lisible que tu le penses.
Rien que cette fonction, qui appelle "x" une taille, alors que dans ce programme "x" désigne quelque chose de précis.
De plus, la notation "tableau" est ici plus pertinente que la notation "pointeur", pour la boucle
Code:

1 2 3 4 5 6 7 int affiche(int x,int *a) { int *p=a; for(p;p<a+x;p++) printf("%d : ",*p); return 0; }
Voici le code corrigé:
Code:

1 2 3 4 5 6 7 int affiche(size_t taille, int const *a) { size_t i; for(i=0 ; i<taille ; i++) printf("%d : ", a[i]); return 0; }
Si ton prof est maniaque, tu peux aussi virer le const et/ou remplacer les size_t par des unsigned int ou même des int, mais je te conseillerais plutôt de respecter les bonnes pratiques dès le début.

PS: Au passage, peut-être devrais-tu aussi déplacer la saisie dans une nouvelle fonction.

Cette fonction là est pire, car tu as changé la signification de x.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int effacer (int *x,int *a,int valsupp)
{
int pas = 0;     
int *p=a;
 
  for(p;p<a+*x;p++)
  {
      //Si le contenu de (*p) est différent à (valsupp)
      //Je déplace la case 
 
      *(p-pas)= *p;
      //Si le contenu de (*p) est égal à (valsupp) 
      //j'augmente le (pas) 
      if(*p==valsupp)
      pas++;
  }
  *x = (*x-pas);
  return 0;
}

Voici mes corrections:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int effacer(size_t *pTaille, int *a, int x)
{
	int offset = 0; //Med: Ce n'est pas un pas, mais un offset
	int *p = a;
 
	for(p ; p<a+*pTaille ; p++)
	{
		//Si le contenu de (*p) est différent à (valsupp)
		//Je déplace la case 
 
		*(p-offset)= *p;
		//Si le contenu de (*p) est égal à (valsupp) 
		//j'augmente le (pas) 
		if(*p==x)
			offset++;
	}
	(*pTaille) -= offset;
	return 0;
}

Et encore, je serais plutôt du genre à faire ceci:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
size_t recopier_sauf(int *dest, int const *source, size_t taille, int x)
{
	size_t i;
	size_t j=0;
	for(i=0 ; i<taille ; i++)
	{
		int val = source[i];
		if(val != x)
		{
			dest[j] = val;
			j++;
		}
	}
	return j;
}
 
int effacer(size_t *pTaille, int *a, int x)
{
	*pTaille = recopier_sauf(a, a, *pTaille, x);
	return 0;
}

25/02/2009, 00h23
raphamil

Médinoc:
A propos de la méthode en O(n), c'est bien celle qui consiste à recopier de façon sélective le tableau dans un autre, non ?
Or, tu as dis qu'il fallait le faire en place. Il n'y a pas un problème là ?

Citation:

Ensuite, au niveau algorithme, tu as accès à deux méthodes: La méthode "naïve" en O(n²), qui supprime l'élément et fait un décalage à chaque fois, et la méthode plus optimisée en O(n) qui fait le tout en une passe.

Citation:

Le tableau modifié (sur place)
25/02/2009, 11h47
Médinoc

C'est parce qu'on peut recopier de façon sélective le tableau dans lui-même.
C'est ce qui est fait par tous les codes postés (dans le mien, recopier_sauf() peut être appelée avec dest==source, c'est pourquoi il ne faut surtout pas déclarer ces paramètres en restrict).