QuickSort pour tableau de char

**deck_bsd** · 24/10/2006, 17h09

Bonjour/Bonsoir a tous,

Voila mon problème, je veu appliquer le quicksort a un tableau de char, le code de la fonction est ok, mais pas le passage du tableau. Pourtant je pense que c'est comme cela que l'ont passe en paramètre un tableau de char. Voici 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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 void tri_Qksort(int m,int n,char * szStr[]);
 int partition(int m,int n,char * szStr[]);
 
int main(int argc, char *argv[])
{
  char szStr[7][200] = {{"un"},{"trois"},{"quatre"},{"cinq"},{"AAA"},{"B"},{"b"}};
  int iDeb=0,iFin = 7,i;
 
  /*Affichage tableau non trié*/
  for(i = 0;i<7;++i){
        printf("%s ",szStr[i]);
  }
 
  /* Appel du tri. */
  tri_Qksort(iDeb,iFin,szStr);
 
  printf("\n");
 
  /* Affichage tableau trié. */
  for(i = 0;i<7;++i){
        printf("%s ",szStr[i]);
  }
 
  getch();	
  return 0;
}
 
 int partition(int m,int n,char * szStr[])
 {
     char pivot[200];
     strcpy(pivot,szStr[m]);
     int i = m-1;
     int j = n+1; // indice final du pivot
 
     while (1)
     {
       do
      {
         j--;
       } while (strcmp(szStr[j],pivot)<0);
       do
      {
         i++;
       }while (strcmp(szStr[i],pivot)>0);
       if (i<j)
      {
         char temp[200];
         strcpy(temp,szStr[i]);
         strcpy(szStr[i],szStr[j]);
         strcpy(szStr[j],temp);
       }
      else
      {
         return j;
      }
     }
 }
 void tri_Qksort(int m,int n,char * szStr[]) {
   if (m<n) {
     int p = partition(m,n,szStr);
     tri_Qksort(m,p,szStr);
     tri_Qksort(p+1,n,szStr);
   }
 }

Merci d'avance pour votre aide.

**elghadi_mohamed** · 24/10/2006, 17h28

bonjour

essaye de faire:

Code :

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

1
2
void tri_Qksort(int m,int n,char **szStr)

**deck_bsd** · 24/10/2006, 17h34

Cela revient au mm

Et puis je l'avai dja esseye avt

**elghadi_mohamed** · 24/10/2006, 17h47

Envoyé par deck_bsd

Bonjour/Bonsoir a tous,

.... Pourtant je pense que c'est comme cela que l'ont passe en paramètre un tableau de char.

vaudrais ecrire tableau de string!!!

**deck_bsd** · 24/10/2006, 17h51

Mdr oui, mais bon on se comprend. Mais la n'est pas le problème :s

**Jean-Marc.Bourguet** · 24/10/2006, 18h41

szStr est un tableau de tableau de char.
Ta fonction prend un pointeur vers pointeur sur char.
C'est normal que tu ne puisses pas lui passer szStr.

Possiblité 1: un modifie le type de szStr pour un faire un tableau de pointeurs sur char. Elle pourra alors être convertie implicitement en un pointeur vers pointeur vers char.

Code :

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

char* szStr[] = { "un", ... };

Possibilité 2: tu modifies ta fonction pour qu'elle prenne un pointeur vers tableau de char. szStr pourra alors être convertie implicitement en un pointeur vers tableau de char.

Code :

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

void tri_Qksort(int m,int n,char (*szStr)[200]);

**diogene** · 24/10/2006, 18h43

Code :

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

1
2
3
4
5
  char szStr[7][200] = {{"un"},{"trois"},{"quatre"},{"cinq"},{"AAA"},{"B"},{"b"}};
....
tri_Qksort(iDeb,iFin,szStr);
..... 
void tri_Qksort(int m,int n,char * szStr[])....

Le type de l'argument est incorrect : ce n'est pas un tableau de pointeur sur char. Le type écrit ici est équivalent à char** szStr
Si on veut conserver la nature bidimensionnelle de l'argument, szStr est un pointeur sur un tableau de 200 char

Code :

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

void tri_Qksort(int m,int n,char (* szStr)[200])....

Le 200 est obligatoire pour que le compilateur puisse interpréter correctement le code du style

Code :

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

strcpy(pivot,szStr[m]);

Une autre alternative est de la déclarer comme char*, ce qu'il est puisqu'il est l'adresse d'un char.

Code :

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

void tri_Qksort(int m,int n,char * szStr)....

Dans ce cas, le calcul du début des éléments du tableau est de la responsabilité du programmeur :

Code :

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

strcpy(pivot,szStr +m*200);

**Emmanuel Delahaye** · 24/10/2006, 18h53

Envoyé par deck_bsd

Voila mon problème, je veu appliquer le quicksort a un tableau de char, le code de la fonction est ok, mais pas le passage du tableau. Pourtant je pense que c'est comme cela que l'ont passe en paramètre un tableau de char. Voici le code :

Si le but est simplement de trier, pourquoi tu n'utilises pas qsort() ? C'st fait pour ça. Il y a juste à fournir une fonction de comparaison basée sur strcmp()...

Ca se fait en 5 lignes de code, appel compris...

Si c'est un exercice d'implémentation de quicksort, c'est aure chose...

**deck_bsd** · 24/10/2006, 18h53

J'avai déjà esseye certaine soluce que vous venez de me dire, mais le problème est tjrs là et il persiste. :s je ne comprend vraiment pas

**deck_bsd** · 24/10/2006, 18h59

Yop Emmanuel Delahaye

Non cela n'ai en rien un exercice, enfin si, pour mon savoir personnel lol. Ben qsort ok je veu bien, mais j'apprend rien. Ici aparement le code fonctionne, c'est le passage du tableau qui ne va pas

.

**diogene** · 24/10/2006, 19h11

Si tu remplace partout dans les en-tête de fonction tes

Code :

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

char * szStr[]

par

Code :

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

char (* szStr)[200]

, ca marche!

**deck_bsd** · 24/10/2006, 19h26

Oui effect , cela fonctionne, hum now c'est mon tri qui va pas didjou.

**Jean-Marc.Bourguet** · 24/10/2006, 19h44

Il faut te décider: est-ce que tu travailles avec des intervalles semi-ouverts (l'indice de fin ne fait pas partie de l'intervalle) comme de coutume en C, ou bien avec des intervalles fermés (l'indice de fin fait partie de l'intervalle). Dans le code ci-dessus, c'est parfois l'un, parfois l'autre.

**deck_bsd** · 24/10/2006, 19h50

intervalles fermé .

QuickSort pour tableau de char

C

Discussions similaires

Partager

Partager