Qsort basé sur une colonne dans une c-string?
Question
Un projet de classe consiste à trier un tableau de chaînes, chaque chaîne contenant un nombre égal de colonnes comme suit:
Cartwright Wendy 93 Williamson Mark 81 Thompson Mark 100 Anderson John 76 Turner Dennis 56
Le programme accepte un argument de ligne de commande pour la colonne à trier sur, et devrait imprimer les chaînes triées non modifiées.
Je voudrais utiliser strtok pour briser des copies de chaque chaîne en colonnes, et de faire struct pour chaque ligne comme ceci:
struct line {
char * line;
char column_to_sort_on[MAX_COLUMN];
}
Mon problème est le pointeur de la fonction de comparaison qui qsort prend comme un arg. Si je comprends bien, la fonction de comparaison doit prendre deux pointeurs const void aux éléments à trier , et retourner un entier. Cela signifie que je ne peux pas passer des pointeurs à structs dans la fonction de comparaison parce que ce n'est pas ce qsort sera tri. Je ne peux pas passer le numéro de colonne pour trier à la fonction de comparaison, car elle ne peut prendre deux args. Comment puis-je contourner ce pour trier ces chaînes basées sur des colonnes spécifiques?
modifier Le tri est limité à qSort ou moi-même si je veux vraiment. Donnez le choix, je choisis qsort. :)
modifier # 2: Le consensus semble être soit utiliser une variable globale pour le numéro de colonne, ou tout simplement utiliser qsort pour trier un tableau de struct. Je n'y avais pas pensé que le tri des struct, et en utilisant le pointeur en eux pour imprimer la chaîne d'origine. Je pense que ce que je vais faire. Merci pour l'aide tout!
La solution
Vous pouvez passer les struct comme ceci:
struct line {
char * line;
char column_to_sort_on[MAX_COLUMN];
}
...
line* Lines[max_lines]; // here you store the structs
int
cmp_lines( const void *elem1, const void *elem2 )
{
line* line1 = *(line**)elem1;
line* line2 = *(line**)elem2;
// do the comparisons
}
qsort(Lines, max_lines, sizeof(line*), cmp_lines);
Autres conseils
En supposant que vous n'êtes pas limité à l'utilisation qsort, vous pouvez utiliser std :: sort, avec un objet foncteur qui stocke le numéro de colonne. Si vous devez utiliser qsort, une solution rapide et sale serait de stocker le numéro de colonne dans une variable globale et l'utiliser dans la fonction comparisson.
Les différentes fonctions de comparaison, tous qui prennent la struct ensemble, mais chacun utilise une seule colonne pour comparation.
C ++ ou C? Sur la base de vos tags, je suppose que c'est C ++. Essayons chemin STL.
Vous devez utiliser std::sort
au lieu de qsort
. std::sort
peut non seulement prendre le pointeur de fonction (par rapport à son alternative C), mais tout objet qui peut être appelée en fonction. Vous savez que les instances de classe peuvent être appelés fonctions avec operator()
. Ensuite, la solution est simple: créer une classe « foncteur » qui va créer des fonctions différentes sur la construction. L'appel de tri alors ressembler à ça:
std::sort(array, array+size, comparator(2 /* sort by column #2 */));
La classe foncteur crée effectivement un soi-disant « fermeture »: un objet fonctionnel créé dynamiquement qui a des variables locales, mais ne les partage pas avec d'autres objets fonctionnels créés de cette façon. Il ressemblerait à ceci:
class comparator{
private: unsigned int field_n;
public: comparator(unsigned int _field_n) : field_n(_field_n) {};
public: int operator () (char const * lhs, char const * rhs)
{ /* compare here fields with index field_n */ };
};
Notez qu'au lieu de (l'instance de classe à savoir la création) « fonction » comparaison des pointeurs vide a des paramètres char *
, de sorte que vous ne vous préoccupez pas de coulée de type.
En C, malheureusement, vous ne pouvez pas le faire dans l'autre sens que de créer une variable globale.