Discussion :

[karioka78]

Je dois codé un programe en C pour créer un tableau d'identifiants alphanumériques. Il faut rentrer les identifiants de facon dynamique et en utilisant le tri par insertion avec la recherche dichotomique.

J'ai du mal avec la fonction Position Insertion si quelqu'un pouvait m'aider...je suis super novice en C.

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <stdio.h>
#include <stdlib.h>
# define N 10
 
/* Déclaration des variables globales*/
char saisie[20+1]; /*Tableau de char pour la saisie*/
char* table[N][20]; /*Tableau des identifiants*/
 
void Presentation()
{
   /* Présentation du programme */
   printf("*******************************************\n");
   printf("* Tableau d'identifiants alpha-numeriques *\n");
   printf("*******************************************\n\n");
   /* Présentation du nb max d'identifiants */
   printf("Le nombre maximum d'identifiants est de %d\n\n", N);  
}
 
/*Saisie dans une variable de nom buf*/
void SaisieBuf()
{
   char buf[20+1];
   /* Demande de saisie de l'identifiant */
   printf("Veuillez entrer un identifiant :\n");
   /* Lecture de l'identifiant */
   scanf("%s",&buf);
   strcpy(saisie,buf);
   //printf("\n%s\n",saisie);
}
 
int TestUtilisateur()
{
   char rep[3];
   printf("Souhaitez-vous continuer la saisie ? oui / non \n");
   scanf("%s",&rep);
   if(strcmp(rep,"oui")==0) return 1;
   else {return 0;}
}
 
int NonDepassement(int TailleTab)
{
   if (TailleTab<N) return 1;
   else return 0;
}
 
void Insertion(int indice, int TailleTab)
{
   int j;
   for(j=indice;j<TailleTab;j++)
   {
      printf("%s \n",table[j]);        
      *table[j+1]=(char *)malloc(sizeof(table[j]));
      strcpy(*table[j+1],*table[j]);
   }
   *table[indice]=(char *)malloc(strlen(saisie));
   strcpy(*table[indice],saisie);
   free(saisie);
}
 
int PositionInsertion(char val[], int TailleTab)
{
   int gauche,droite,milieu;
   gauche=0;
   droite=TailleTab;
   while(gauche<droite)
   {
      milieu = (gauche+droite)/2;
      if(strcmp(val,table[milieu])<0) droite=milieu;
      else gauche=milieu;
   }
   return gauche;
}
 
void Affichage()
{
   int z;
   for(z=0;z<N;z++){printf("%s\n",*table[z]);}  
}
 
/*
void Doublon()
{}
*/
 
int main(int argc, char *argv[])
{
   int i=0;
   int indice;
   Presentation();
   while(NonDepassement(i)==1)
   {
      SaisieBuf();
      //printf("\n%s\n",saisie);
      indice=PositionInsertion(saisie,i);
      printf("\n%d\n",indice);
      i++;
      Insertion(indice,i);
      if(i>1)
      {
         if(TestUtilisateur()==0)break;
      }
   }
   Affichage();
   system("PAUSE");	
   return 0;
}

[Beldom]

Utilise la balise code (le # )! Et fait un effort d'indentation.

Là, c'est vraiment illisible, donc très compliqué de t'aider !

Edit : Mes commentaires au fur et à mesure :

Dans ton while, plutôt que de faire appel à une fonction, fait directement la comparaison.
Plutôt que deux if enchainé, utilise &&. De même, i == 0 équivaut à !i .
Voici un exemple possible (Je continue ma lecture au fur et à mesure)

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
int main(int argc, char *argv[])
{
    int i = 0;
    int indice;
 
    Presentation();
    while (i < N)            /* ICI, ne pas faire appel à une fonction pour une simple comparaison ! */
     {
         SaisieBuf();
         //printf("\n%s\n",saisie);
         indice = PositionInsertion(saisie,i);
         printf("\n%d\n",indice);
         i++;
         Insertion(indice,i);
         if (i > 1 && !TestUtilisateur())      /* Utilise un opérateur logique && plutôt que deux if d'affilée... */
              break;
     }
 
     Affichage();
     system("PAUSE"); /* Pourquoi ne pas utiliser pause() ? */
     return 0;
}

[aoyou]

Je pense que tu as déjà un souci dès la 7ème ligne

Code :

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

char* table[N][20];

Tu ne déclares pas un tableau d'identifiants mais une matrice d'identifiants.

Petite chose : quitte à faire un #define pour N pourquoi ne pas en faire un pour 20 aussi ?

[karioka78]

Merci et désolé pour la présentation.

Je vous ai pas menti je suis vraiment novice...

si je veux déclarer un tableau d'identifiants comment faire? J'ai vu des posts ou ils déclarent des tableaux à deux dimensions en faisant :

char **table[][]

a quoi servent les deux étoiles c'est des pointeurs de pointeurs..??

[Beldom]

En effet, ton problème viens de ce que tu déclares.

Tu veux un tableau de pointeur, donc char Tab[][] et pas char *Tab[][]...

Corrige ca et ta fonction devrait aller un peu mieux.

Par contre, tu as des enormes fuites de mémoire !
Et quand je dis enorme...

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
void Insertion(int indice, int TailleTab)
{
   int j;
   for(j=indice;j<TailleTab;j++)
   {
      printf("%s \n",table[j]);        
      *table[j+1]=(char *)malloc(sizeof(table[j]));
      strcpy(*table[j+1],*table[j]);
   }
   *table[indice]=(char *)malloc(strlen(saisie));
   strcpy(*table[indice],saisie);
   free(saisie);
}

Tu fais un nouveau malloc à chaque passage dans ta boucle, sans jamais free l'ancien...
Et en plus, tu me donne vraiment l'impression d'allouer n'importe comment, mais je n'en suis pas tout à fait certain...

En partant sur un principe de tableau de pointeur (Donc : char Tab[N][20 + 1]), qui devrait correspondre à tes besoins, et en partant de la fin pour aller vers l'indice qu'il te faut pour pouvoir free sans problème :

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
void Insertion(int indice, int TailleTab)
{
   int j;
   for (j =  TailleTab - 1; j >= indice; j--)
   {
      printf("%s \n",table[j]);   
      table[j + 1] = malloc(sizeof(table[j]) * strlen(table[j]));
      strcpy(table[j + 1], table[j]);
      free(table[j]);
   }
 
   table[indice] = malloc(sizeof(table[indice] * strlen(saisie));
   strcpy(table[indice], saisie);
 /*    free(saisie); */             /* saisie n'a jamais été malloc, il ne faut donc pas la free. C'est une variable globale déclarée en "dur". */
}

J'ai pas de quoi tester sous la main, mais ca devrait être plus correct selon moi, même si on inverse le sens. Ca évite les écrasements par erreur de données...
A vérifier donc, mais plus probable...

[karioka78]

Ok j'ai compri pour la mémoire j'avoue que ce qui parraissait logique pour moi ne l'est pas du tout en fait. Cependant il y a un problème lors le l'allocation :

Code :

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

table[j + 1] = malloc(sizeof(table[j]) * strlen(table[j]));

le compilateur me dit que les types sont incompatibles

[aoyou]

malloc retourne un pointeur que tu essaies d'affecter à un char[20]...

si tu as défini ton tableau ainsi (à préciser car on ne sait pas)

Code :

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

char table[N][20];

Tu n'as plus besoin d'allouer la mémoire (Table[i] contient un char[20])

[karioka78]

Ok sauf qu'on me demande d'allouer dynamiquement chaque élément à la demande au cours de la sasie

[aoyou]

Alors tu définis ta table ainsi.

Code :

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

char *table[N];

Tu définis une table de N chaînes de caractères mais attention d'allouer la mémoire.

Tu n'as donc plus de problèmes de types incompatibles en faisant ton malloc().

[karioka78]

Daccord je vais essayer et encore merci pour votre aide

[karioka78]

Le programme plante à l'éxecution, il me dit qu'il y a une erreur de segmentation mais il ne précise pas où, je suppose que c'est lors de l'allocation de la mémoire..

Je vous remet le code

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
 
#include <stdio.h>
#include <stdlib.h>
# define N 10
# define L 20
 
/* Déclaration des variables globales*/
char saisie[L+1]; /*Tableau de char pour la saisie*/
char *table[N]; /*Tableau des identifiants*/
 
void Presentation()
{        /* Présentation du programme */
  printf("*******************************************\n");
  printf("* Tableau d'identifiants alpha-numeriques *\n");
  printf("*******************************************\n\n");
      /* Présentation du nb max d'identifiants */
  printf("Le nombre maximum d'identifiants est de %d\n\n", N);  
}
 
 
 
/*Saisie dans une variable de nom buf*/
void SaisieBuf()
{
  char buf[L+1];
  /* Demande de saisie de l'identifiant */
  printf("Veuillez entrer un identifiant :\n");
  /* Lecture de l'identifiant */
  scanf("%s",&buf);
  strcpy(saisie,buf);
}
 
 
 
int TestUtilisateur()
{
     char rep[3];
     printf("Souhaitez-vous continuer la saisie ? oui / non \n");
     scanf("%s",&rep);
     if(strcmp(rep,"oui")==0) return 1;
     else {return 0;}
}
 
 
void Insertion(int indice, int TailleTab)
{
   int j;
   for (j =  TailleTab - 1; j >= indice; j--)
   {
      printf("%s \n",table[j]);   
      table[j + 1] = (char *)malloc(sizeof(table[j]) * strlen(table[j]));
      strcpy(table[j + 1], table[j]);
      free(table[j]);
   }
 
   table[indice] = (char *)malloc(sizeof(table[indice]) * strlen(saisie));
   strcpy(table[indice], saisie);
 
}
 
 
int PositionInsertion(char val[], int TailleTab)
{
     int gauche,droite,milieu;
     gauche=0;
     droite=TailleTab;
     while(gauche<droite){
                        milieu = (gauche+droite)/2;
                        if(strcmp(val,table[milieu])<0) droite=milieu;
                        else gauche=milieu;
                        }
     return gauche;
}
 
 
 
void Affichage()
{
   int z;
   for(z=0;z<N;z++){printf("%s\n",table[z]);}  
}
 
int main(int argc, char *argv[])
{
    int i = 0;
    int indice;
 
    Presentation();
    while (i < N)            
     {
         SaisieBuf();
         indice = PositionInsertion(saisie,i);
         i++;
         Insertion(indice,i);
         if (i > 1 && !TestUtilisateur())      
              break;
     }
 
     Affichage();
     system("PAUSE");
     return 0;
}

[gl]

Le programme plante à l'éxecution, il me dit qu'il y a une erreur de segmentation mais il ne précise pas où, je suppose que c'est lors de l'allocation de la mémoire..

Il a plusieurs causes dans ton programme qui peuvent provoquer une telle erreur:

* Utilisation de scanf("%s", ...) qui ne verifie pas la taille saisie. Je pense par exemple a l'extrait

Code :

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

1
2
3
4
5
     char rep[3];
     printf("Souhaitez-vous continuer la saisie ? oui / non \n");
     scanf("%s",&rep);
     if(strcmp(rep,"oui")==0) return 1;
     else {return 0;}

ou scanf va recuperer 4 bytes (3 caracteres de "oui" ou "non" + le '\0' final) pour les stocker dans un tableau de 3 bytes, tu as un beau debordement de buffer (et je ne parle pas de l'utilisateur distrait ou mal intetionne qui tape une chaine beucoup plus longue).
Utilises plutot fgets() pour effectuer la saisie.

Et au passage c'est scanf("%s", rep); pas scanf("%s", &rep);

* Allocation de chaine trop courte, en effet strlen() donne le nombre de caracteres de la chaine, '\0' non compris. Ce n'est donc pas strlen(table[j]) mais strlen(table[j])+1 qui faut utiliser lors des allocations, sans quoi strcpy (qui copie bien le '\0') va ecrire un byte de plus que la taille du tableau.

* Utilisation de strcpy qui ne verifie pas la taille de la destination. A remplacer par strncpy avec forcage du '\0' final voire mieux strncat avec un buffer destination correctement initialise.

* Aucune verification du retour de malloc. Si l'allocation echoue, tu vas quand meme utilise le pointeur ==> BUG

[karioka78]

Merci gl je vais modifier tout ca.

[crocodilex]

Le programme plante à l'éxecution, il me dit qu'il y a une erreur de segmentation mais il ne précise pas où, je suppose que c'est lors de l'allocation de la mémoire..

Je vous remet le code

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
char *table[N]; /*Tableau des identifiants*/

void Insertion(int indice, int TailleTab)
{
   int j;
   for (j =  TailleTab - 1; j >= indice; j--)
   {
      printf("%s \n",table[j]);   
      table[j + 1] = (char *)malloc(sizeof(table[j]) * strlen(table[j]));
      strcpy(table[j + 1], table[j]);
      free(table[j]);
   }
 
   table[indice] = (char *)malloc(sizeof(table[indice]) * strlen(saisie));
   strcpy(table[indice], saisie); 
}

Dans la fonction Insertion(), le pointeur table[j] n'est pas encore initialisé (du moins il est initialisé à NULL car variable globale).
Donc il y a de grande chance que le plantage vienne de la fonction strlen(), car celle-ci ne doit pas aimer un pointeur null en argument.

Autre chose en passant : il manque un include de string.h

[aoyou]

Le programme plante à l'éxecution, il me dit qu'il y a une erreur de segmentation mais il ne précise pas où

Ca... il ne te dira jamais où.

Apprends à utiliser un debugger. Il est possible que tu sois sous Visual C++ et le debugger de Visual est vraiment facile d'utilisation. Le debugger a l'avantage de te dire aussitôt quelle ligne est en cause... au lieu de supposer...

Exemple de debugging sous Linux

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
 
gdb tri
GNU gdb 6.3-debian
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "i386-linux"...Using host libthread_db library "/lib/tls/libthread_db.so.1".
 
(gdb) r
Starting program: tri
*******************************************
* Tableau d'identifiants alpha-numeriques *
*******************************************
 
Le nombre maximum d'identifiants est de 10
 
Veuillez entrer un identifiant :
2
(null)
 
Program received signal SIGSEGV, Segmentation fault.
0xb7f1d363 in strlen () from /lib/tls/libc.so.6
(gdb) backtrace
#0  0xb7f1d363 in strlen () from /lib/tls/libc.so.6
#1  0x08048606 in Insertion (indice=0, TailleTab=1) at tri.c:50
#2  0x0804878a in main (argc=1, argv=0xbfbfae94) at tri.c:93

Comme il a déjà été dit, ça plante à tri.c ligne 50 soit

Code :

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

      table[j + 1] = (char *)malloc(sizeof(table[j]) * strlen(table[j]));

Rapide, efficace, à toi de jouer...

[karioka78]

Merci a tous il n'y a plus qu'une erreur au niveau du tri, je vous met le programme au cas où...

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
# define N 10
# define L 20
 
/* Déclaration des variables globales*/
char saisie[L+1]; /*Tableau de char pour la saisie*/
char *table[N]; /*Tableau des identifiants*/
 
 
 
void Presentation()
{        /* Présentation du programme */
  printf("*******************************************\n");
  printf("* Tableau d'identifiants alpha-numeriques *\n");
  printf("*******************************************\n\n");
      /* Présentation du nb max d'identifiants */
  printf("Le nombre maximum d'identifiants est de %d\n\n", N);  
}
 
 
 
/*Saisie dans une variable de nom buf*/
void SaisieBuf()
{
  char buf[L+1];
 
  /* Demande de saisie de l'identifiant */
  printf("Veuillez entrer un identifiant :\n");
  /* Lecture de l'identifiant */
  scanf("%s",buf);
  strcpy(saisie,buf);
  //printf("\n%s\n",saisie);
}
 
 
 
int TestUtilisateur()
{
     char rep[4];
 
     printf("Souhaitez-vous continuer la saisie ? oui / non \n");
     scanf("%s",rep);
     if(strcmp(rep,"oui")==0) return 1;
     else {return 0;}
}
 
 
 
int NonDepassement(int TailleTab)
{
     if (TailleTab<N) return 1;
     else return 0;
}
 
void Insertion(int indice, int TailleTab)
{
   int j;
 
   for (j =  TailleTab; j > indice; j--)
 
       {
             table[j] = table[j-1];
 
       }
 
   table[indice] = (char *)malloc(strlen(saisie)+1);
 
   if( table[indice] == NULL )
       {
        fprintf(stderr,"Allocation impossible");
        exit(EXIT_FAILURE);
       }
   else    
   strcpy(table[indice], saisie);
}
 
 
 
int PositionInsertion(int TailleTab)
{
     int gauche,droite,milieu;
     gauche=0;
     droite=TailleTab;
 
     while(droite-gauche>1)
                         {
                              milieu = (gauche+droite)/2;
                              printf("Milieu= %d",milieu);
                              if(strcmp(saisie,table[milieu])<0) 
                              droite=milieu;
                              else gauche=milieu;
                         }
     return gauche;
}
 
 
 
void Affichage()
{
   int z;
   for(z=0;z<N;z++)
   {
                   if(table[z] != NULL)
              printf("%s\n",table[z]);
   }  
}
 
 
 
 
/*
void Doublon()
{}
*/
 
 
 
 
int main(int argc, char *argv[])
{
    int i = 0;
    int indice;
    Presentation();
 
    while (i < N)            
          {
           if (i > 1 && !TestUtilisateur())      
           break;
 
           SaisieBuf();
 
           indice = PositionInsertion(i);
           printf("\n%d\n",indice);
           Insertion(indice,i);
           i++;
           }
 
    Affichage();
 
    system("PAUSE");
    return 0;
}

[diogene]

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 Insertion(int indice, int TailleTab)
{
   int j;
 
   for (j =  TailleTab - 1; j >= indice; j--)
 
       {
             printf("%s \n",table[j-1]);   
 
             table[j + 1] = (char *)malloc(sizeof(table[j]) * strlen(table[j])+1);
 
             if( table[j + 1] == NULL )
                 {
                  fprintf(stderr,"Allocation impossible");
                  exit(EXIT_FAILURE);
                 }
 
             strcpy(table[j + 1], table[j]);
             free(table[j]);
       }.....

table est un tableau de pointeur qui contient l'adresse des chaînes allouées dynamiquement. Pour faire une place dans ce tableau pour mettre l'adresse d'une nouvelle chaîne, il n'y a pas besoin de recopier les anciennes chaînes mais simplement de déplacer les pointeurs:

Code :

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

1
2
3
4
5
void Insertion(int indice, int TailleTab)
{
   int j;  
   for (j = TailleTab - 1; j > indice; j--)   table[j] = table[j-1]
   ....

Suite :

Code :

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

1
2
3
4
5
6
7
8
9
...
   table[indice] = (char *)malloc(sizeof(table[indice]) * strlen(saisie)+1);  
   if( table[indice] == NULL )
       {
        fprintf(stderr,"Allocation impossible");
        exit(EXIT_FAILURE);
       }      
   strcpy(table[indice], saisie);
}

Pourquoi sizeof(table[indice]) (taille d'un pointeur!) intervient-il dans la place allouée pour la nouvelle chaîne ?

Code :

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

1
2
3
4
5
6
7
8
9
...
   table[indice] = malloc(strlen(saisie)+1);  
   if( table[indice] == NULL )
       {
        fprintf(stderr,"Allocation impossible");
        exit(EXIT_FAILURE);
       }      
   strcpy(table[indice], saisie);
}

[karioka78]

C'est bon j'ai fait les modifications cependant j'ai toujours ce problèlme de tri avec les deux premières entrées. Est-ce qu'il faut que je rajoute un tri sur les deux premiers éléments saisis ou bien je peux le faire via ma fonction de tri par insertion avec recherche dichotomique ?

J'ai mis la dernière version du programme dans mon dernier post.

[diogene]

C'est bon j'ai fait les modifications cependant j'ai toujours ce problèlme de tri avec les deux premières entrées. Est-ce qu'il faut que je rajoute un tri sur les deux premiers éléments saisis

La recherche dichotomique aboutira finalement à deux elements consécutifs. Mais, il faut situer la nouvelle chaîne par rapport à ces deux éléments. Je crois que ce qui suit doit marcher :

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
int PositionInsertion(int TailleTab)
{
     int gauche,droite,milieu;
     if(TailleTab == 0) return 0;
     droite=TailleTab-1;
     gauche=0;         
     while(droite-gauche>1)
                         {
                             milieu = (gauche+droite)/2;
                             printf("Milieu= %d",milieu);
                             if(strcmp(saisie,table[milieu])<0)
                             droite=milieu;
                             else gauche=milieu;
                         }
     if(strcmp(saisie,table[droite])>0) gauche = droite+1;
     else if(strcmp(saisie,table[gauche])>0) gauche = droite;
     return gauche;
}

[karioka78]

Un grand merci a tous ceux qui ont bien voulus m'aidés cela m'a permis d'y voir plus clair sur l'allocation dynamique de mémoire, les tableaux de chaines de caractères et la recherche dichotomique....!!!