Qsort basierend auf einer Spalte in einem c-string?
Frage
A class Projekt umfasst ein Array von Strings Sortieranlage, wobei jeder String eine gleiche Anzahl von Spalten wie folgt enthält:
Cartwright Wendy 93 Williamson Mark 81 Thompson Mark 100 Anderson John 76 Turner Dennis 56
Das Programm akzeptiert eine Befehlszeilenargument für die Spalte zu sortieren, und soll die sortierten Ketten unmodifizierten ausdrucken.
Ich möchte strtok verwenden jeder Zeichenfolge in Spalten aufzubrechen Kopien und machen structs für jede Zeile wie folgt aus:
struct line {
char * line;
char column_to_sort_on[MAX_COLUMN];
}
Mein Problem ist in dem Vergleichsfunktionszeiger, der qsort als arg nimmt. Wenn ich richtig verstehe, muss die Vergleichsfunktion zwei const void-Zeiger nehmen , um die Elemente zu sortieren , und ein int zurück. Dies bedeutet, dass ich keine Zeiger passieren kann in die Vergleichsfunktion Structs, weil das nicht das, was qsort Sortierung wird. Ich kann nicht in der Spaltennummer übergeben, um die Vergleichsfunktion zu sortieren, weil es nur zwei Argumente nehmen. Wie kann ich dieses Problem umgehen, diese Strings basierend auf bestimmte Spalten zu sortieren?
Bearbeiten Sorting begrenzt ist mein eigenes qsort oder wenn ich wirklich will. Geben Sie die Wahl, wähle ich qsort. :)
Bearbeiten # 2: Der Konsens scheint eine globale Variable für die Spaltennummer ist entweder zu verwenden, oder einfach nur qsort verwenden, um ein Array von Strukturen zu sortieren. Ich hatte nicht gedacht, nur die structs Sortieren und mit dem Zeiger in ihnen die ursprüngliche Zeichenfolge zu drucken. Ich denke, das ist, was ich tun werde. Danke für die Hilfe alle!
Lösung
Sie können die Strukturen wie folgt übergeben:
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);
Andere Tipps
Unter der Annahme, sind Sie mit qsort nicht darauf beschränkt, können Sie std :: sort mit einem Funktor Objekt, das speichert die Spaltennummer verwenden. Wenn Sie qsort verwenden müssen, eine schnelle und schmutzige Lösung wäre die Spaltennummer in einer globalen Variablen zu speichern und dass in der comparisson-Funktion verwenden.
Verschiedene Komparatorfunktionen, die alle die ganze Struktur nehmen, aber jeder nutzt nur eine Spalte für comparation.
C ++ oder C? Basierend auf Ihre Tags, gehe ich davon aus es C ++ ist. Lassen Sie uns STL Art und Weise versuchen.
Sie sollten verwenden std::sort
statt qsort
. std::sort
kann dabei nicht nur Funktionszeiger (im Vergleich zu seiner C Alternative), aber jedes Objekt , die als Funktion aufgerufen werden kann. Sie wissen vielleicht, dass die Klasseninstanzen als Funktionen mit operator()
aufgerufen werden können. Dann wird die Lösung ist einfach: eine „Funktor“ Klasse erstellen, die verschiedene Funktionen auf Konstruktion schaffen. Die Art Aufruf würde dann so aussehen:
std::sort(array, array+size, comparator(2 /* sort by column #2 */));
Die Funktor Klasse schafft effektiv einen sogenannten „Verschluss“: ein dynamisch erstellte Funktionsobjekt, die lokale Variablen hat, sie aber nicht mit anderen funktionalen Objekten auf diese Weise erstellt teilen. Es würde wie folgt aussehen:
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 */ };
};
Beachten Sie, dass anstelle von void-Zeiger Vergleich „Funktion“ (das heißt die Klasseninstanz Sie erstellen) Parameter char *
hat, so dass Sie nicht die Mühe, sich mit type casting.
In C leider können Sie dies nicht tun, um die andere Art und Weise als eine globale Variable zu schaffen.