String Array mit qsort sortieren
-
Würde ich ja, aber du solltest dir zumindest die Mühe machen zu versuchen zu verstehen was mein Programm macht. Offensichtlich hast du es ja nicht mal ausgeführt sondern einfach mal irgendwie in dein Programm kopiert, und dann auch noch falsch..
-
Ja hast wohl Recht, entschuldige für das.
Nun gut, dann gehn wirs an:
Hab mir dein Programm jetzt Mal an sich genauer angeschaut, werd aber trotzdem nicht schlau daraus:
Ich hab ein 2dimensionales char Array strings.
In der zweiten Zeile häng ich schon, was passiert da? Hab die Schreibweise einfach noch nicht gesehen! Is das ein Array von Pointern, wo jeder Pointer auf strings verweist? Vielleicht wirds klarer wenn ich Mal weiß, was das is.MFG Zoltamor
-
Zoltamor schrieb:
In der zweiten Zeile häng ich schon, was passiert da? Hab die Schreibweise einfach noch nicht gesehen! Is das ein Array von Pointern, wo jeder Pointer auf strings verweist? Vielleicht wirds klarer wenn ich Mal weiß, was das is.
Das ist ein Pointer auf ein char[256].
-
Ok, also ein unbenanntes char, das genau dieselben Elemente aufweist wie strings, richtig? Also es zeigt darauf.
die for-Schleife: brauch ich da nirgends Klammern, oder wieso rennt das so?
der qsort Befehl: der Beginn is strings, Anzahl der Elemente is p-strings, Größe der Elemente is die sizeof(*p) und die compare-Funktion (wobei ich nicht genau weiß was die macht)
MFG Zoltamor
-
Zoltamor schrieb:
Ok, also ein unbenanntes char, das genau dieselben Elemente aufweist wie strings, richtig? Also es zeigt darauf.
Häh, was? Es ist ein Pointer auf ein Array mit 256 char-Elementen. Nicht mehr und nicht weniger. Da es auf den Anfang eines Arrays von diesen 256-char-Arrays zeigt, kann man sich mittels Pointerarithmetik (googlen, falls der Begriff unbekannt ist!) durch die verschiedenen 256-char-Array-Elemente dieses Arrays hangeln.
(Warum machst du deine Arrays eigentlich 257 Zeichen lang, wenn du 255 Zeichen aufnehmen möchtest? 256 würde doch reichen: 255 Zeichen + Nullterminierung. Ich fürchte, du hast die Bedeutung von Arraydefinitionen nicht richtig verstanden)
die for-Schleife: brauch ich da nirgends Klammern, oder wieso rennt das so?
Du hast die Schleife gar nicht verstanden. Sie ist leer. Achte auf das Semikolon. Deine Klammern da machen überhaupt nichts und die Einrückung passt nicht zur Syntax. So wie cooky451 das formatiert hat, passt das schon. Würde ja auch herzlich wenig Sinn machen, das Sortieren und Ausgeben nochmals in eine Schleife zu packen. (Dir ist klar, dass die Zeilen 10-12 in cooky451s Programm sortieren und ausgeben?)
der qsort Befehl: der Beginn is strings, Anzahl der Elemente is p-strings, Größe der Elemente is die sizeof(*p) und die compare-Funktion (wobei ich nicht genau weiß was die macht)
Dann schlag es nach! Wenn man eine Funktion mit komischen Argumenten sieht, dann reimt man sich diese nicht zusammen, sondern guckt in eine Referenz:
http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/(Wobei ich noch erwähnen sollte, dass du es dir richtig zusammengereimt hast)
comparator
Function that compares two elements. The function shall follow this prototype:int comparator ( const void * elem1, const void * elem2 );
The function must accept two parameters that are pointers to elements, type-casted asvoid*. These parameters should be cast back to some data type and be compared.The return value of this function should represent whether
elem1is considered less than, equal to, or greater thanelem2by returning, respectively, a negative value, zero or a positive value.Irgendwie muss qsort ja wissen, wie man zwei Elemente vergleicht. strcmp ist da schon passend von der Funktionalität her (Ein einfaches < würde bei Zeichenketten schließlich nicht funktionieren), man muss die Funktion bloß noch entsprechend casten, damit die Signatur stimmt.
c.rackwitz schrieb:
Wenn du selber Code schreibst, musst du ihn auch verstehen. Code ist kein Haufen von wahllos zusammengeschmissenen Buchstaben und Zeichen, Code ist Logik pur. Du musst genau wissen, warum du wo und welches Zeichen setzt.
Das gilt natürlich besonders, wenn man anderer Leute Code übernimmt.
-
Ok.
Bezüglich Array-länge: Wird die Null-Terminierung unter Windows oder Linux, 1 von beiden, nicht bei einem als 2 Zeichen angesehen? Hat mir zumindest Mal jemand so erklärt, deshalb noch 1 zusätzlich, vielleicht ist es auch Unsinn?Da hast du leider recht, die Schleife hab ich wirklich nicht verstanden :(. Die Abgrenzung mit Semikolon ist mir natürlich bewusst und ich hab sie auch bemerkt, aber den Aufbau verstehe ich trotzdem nicht ganz --> for-Schleife mit Semikolon am Schluss, warum? Normalerweise wenn sie keine {} hat zählt nur die nächste Zeile, aber was hat es hiermit auf sich? Wie du bereits erwähnt hast gehört dies ja nicht zur Schleife dazu. Was die diversen Berechnungen hier aber machen, das ist mir einfach ein Rätsel! Tut mir leid, vielleicht bin ich im Moment einfach wirklich begriffsstützig
qsort hab ich auch vorher schon nachgeschlagen, eh genau dort wo du hinverweist, ich wollte auch nur wissen ob die ersten 3 Parameter so richtig interpretiert sind von mir, und der vierte, naja, der vergleicht praktisch 2 Pointer, aber was für welche?
Ich will ihn auch wirklich verstehen! Es bringt mir für die Zukunft eh nix, jetzt irgendwas zu kopieren, selbst wenn es funktioniert, Erklärungen sind 1000 Mal mehr Wert, das weiß ich
MFG Zoltamor
-
Zoltamor schrieb:
Ok.
Bezüglich Array-länge: Wird die Null-Terminierung unter Windows oder Linux, 1 von beiden, nicht bei einem als 2 Zeichen angesehen? Hat mir zumindest Mal jemand so erklärt, deshalb noch 1 zusätzlich, vielleicht ist es auch Unsinn?Du denkst an Zeilenumbrüche. Aber auch das spielt im Programm keine Rolle, sondern nur dann, wenn du zum Beispiel Daten (nicht-binär) in eine Datei schreibst. Dann werden in Windows alle '\n'-Zeichen zu einer Zweizeichenkombination (ich glaube \r\n (oder war es \n\r?)) umgewandelt (und zwar automatisch!).
Da hast du leider recht, die Schleife hab ich wirklich nicht verstanden :(. Die Abgrenzung mit Semikolon ist mir natürlich bewusst und ich hab sie auch bemerkt, aber den Aufbau verstehe ich trotzdem nicht ganz --> for-Schleife mit Semikolon am Schluss, warum? Normalerweise wenn sie keine {} hat zählt nur die nächste Zeile, aber was hat es hiermit auf sich?
Die Schleife hat bereits alles im Kopf, was sie machen soll. Daher braucht sie keinen Körper. Man könnte sie auch so schreiben:
while (1) { if !(p != namen + sizeof(namen) / sizeof(*namen)) break; if !(fgets(*p, sizeof(*p), stdin) != NULL) break! ++p; }Jetzt sollte auch klarer sein, was das überhaupt macht. Zeile 3 prüft, ob man am Ende des vorreservierten Arrays ist und bricht gegebenenfalls ab. Zeile 5 liest eine Zeile ein und überprüft den Rückgabewert der Lesefunktion (das ist immer eine gute Idee!). Tritt ein Fehler auf, wird abgebrochen. Fehler bedeutet bei dieser Aktion normalerweise Dateiende, das heißt effektiv wird bis zum Dateiende gelesen oder bis 256(257)-Strings gelesen wurden, was eher eintritt.
Zeile 7 setzt dann den Zeiger p auf das nächste 256-char-Array aus dem großen Array strings. Ich habe oben in meiner Antwort noch das Stichwort Pointerarithmetik reineditiert, als du schon geantwortet hast.
qsort hab ich auch vorher schon nachgeschlagen, eh genau dort wo du hinverweist, ich wollte auch nur wissen ob die ersten 3 Parameter so richtig interpretiert sind von mir, und der vierte, naja, der vergleicht praktisch 2 Pointer, aber was für welche?
Irgendwie muss die Funktion qsort zwei Elemente vergleichen. Da C nicht die Abstraktionstechniken von C++ kann, muss ein allgemeiner Vergleich für eine allgemeine Sortierfunktion über void-Zeiger mit entsprechenden Casts erfolgen. Das Thema ist vermutlich ein bisschen zu hoch für einen Anfänger. Um das zu verstehen könntest du ja mal eine einfache Sortierfunktion für ein Integerfeld schreiben (es muss ja nicht gleich quicksort sein, ein einfacher Algorthmus reicht zum Üben auch). Wenn du weißt, das alle Elemente Integer sind, kannst du zwei Elemente mittels '<' vergleichen. Wenn du dann versuchst, diese Funktion zu verallgemeinern, dass sie Arrays von irgendwelchen Typen sortieren kann (die du vorher nicht kennst!), dann kann das nicht mehr funktionieren (Zeichenketten zum Beispiel kann man nicht mit < verlgeichen). Dann musst du dir eine allgemeine Vergleichsfunktion vom Nutzer übergeben lassen, die zu den Elementen passt. Und eine allgemeine Funktion, die zwei Parameter von irgendeinem Typ nehmen kann und dann einen Vergleichswert zurückgibt, die kann in C nur über void-Zeiger funktionieren, da man void-Zeiger in und aus allen anderen Zeigertypen umwandeln kann.
-
Zoltamor schrieb:
Ok.
Bezüglich Array-länge: Wird die Null-Terminierung unter Windows oder Linux, 1 von beiden, nicht bei einem als 2 Zeichen angesehen? Hat mir zumindest Mal jemand so erklärt, deshalb noch 1 zusätzlich, vielleicht ist es auch Unsinn?Falsch gemerkt. Nullterminierung ist immer '\0', sonst nichts. Was unterschiedlich ist, ist das Zeilenende. Das ist unter Unix nur "\n", während unter Windows "\r\n" üblich ist. Wenn du also wirklich bis zu 255 Buchstaben + Zeilenende lesen möchtest, bräuchtest du theoretisch 258 Zeichen. Window wandelt im Textmodus aber \r\n zu \n. Sind wir bei 257 Zeichen. Interessant, wenn man wirklich sicher gehen will, dass Name und Zeilenende passen braucht man tatsächlich 257 Zeichen, es sei denn man führt noch extra Tests durch.
Zoltamor schrieb:
Da hast du leider recht, die Schleife hab ich wirklich nicht verstanden :(. Die Abgrenzung mit Semikolon ist mir natürlich bewusst und ich hab sie auch bemerkt, aber den Aufbau verstehe ich trotzdem nicht ganz --> for-Schleife mit Semikolon am Schluss, warum? Normalerweise wenn sie keine {} hat zählt nur die nächste Zeile, aber was hat es hiermit auf sich?
Ein ";" entspricht einer leeren Answeisung. Ist also gleichbedeutend mit {}:
for (; a; b;); for (; a; b;) {} while (a) b; while (a) { b; }Alles gleich.
Zoltamor schrieb:
qsort hab ich auch vorher schon nachgeschlagen, eh genau dort wo du hinverweist, ich wollte auch nur wissen ob die ersten 3 Parameter so richtig interpretiert sind von mir, und der vierte, naja, der vergleicht praktisch 2 Pointer, aber was für welche?
Der letzte Parameter ist: "ein Zeiger auf eine Funktion die int zurückgibt und als Parameter zwei Pointer auf void nimmt.".
Das sind const void*, weil qsort ja den Datentypen der verglichen wird nicht kennen kann. Je ein const void* zeigt auf ein Element, und die Funktion soll diese Elemente vergleichen.Da wir strings vergleichen wollen und es bereits eine Funktion gibt die genau das macht was wir wollen, nehmen wir die einfach. Nur passt die Signatur nicht, allerdings sind const void* und const char* ganz gut kompatibel, sodass wir einfach casten können.
(Das const bedeutet übrigens, dass das worauf der Pointer zeigt nicht verändert werden soll.)
-
cooky451 schrieb:
Falsch gemerkt. Nullterminierung ist immer '\0', sonst nichts. Was unterschiedlich ist, ist das Zeilenende. Das ist unter Unix nur "\n", während unter Windows "\r\n" üblich ist. Wenn du also wirklich bis zu 255 Buchstaben + Zeilenende lesen möchtest, bräuchtest du theoretisch 258 Zeichen. Window wandelt im Textmodus aber \r\n zu \n. Sind wir bei 257 Zeichen. Interessant, wenn man wirklich sicher gehen will, dass Name und Zeilenende passen braucht man tatsächlich 257 Zeichen, es sei denn man führt noch extra Tests durch.
Nein. Die Umwandlung erfolgt irgendwo tief in den Eingeweiden des Dateistreams. Sämtliche Lesefunktionen die darauf arbeiten und erst recht dein Hauptprogramm bekommen davon gar nichts mehr mit. Das fgets sieht nur ein \n, wo in der Datei \r\n stand.
-
SeppJ schrieb:
Das fgets sieht nur ein \n, wo in der Datei \r\n stand.
Du hast meinen Punkt nicht verstanden. 255 Zeichen für den Namen + \n + \0 macht de facto 257.
-
Wirklich klarer wird mir der erste Teil der Schleife leider auch nicht, der 2te is jetzt logisch, aber der Anfang:
Was macht das Rufzeichen vor der Anweisung? Normalerweise würde ich sagen, wenn der Ausdruck falsch ist, aber wenn ich versuche das so zu kompilieren, kommt ein Error. Hätte es nicht den gleichen Effekt, wenn ich das Rufzeichen weglasse, und nicht != sondern == abfrage? Dann funktioniert es nämlich.
Dann: Kannst du mir noch erklären, was genau du in der Schleife (Zeile 3) berechnest? Oder eher, warum du das so berechnest?
Und bezüglich qsort: was meinst du mit casten? Und was mir noch aufgefallen ist, warum sortiert es die Namen verkehrt?
MFG
-
Ach komm, was solls. Hier:
#include <stdlib.h> #include <stdio.h> #include <string.h> int main(void) { char strings[256][257]; // 256 Arrays mit je 257 chars char (*p)[257] = strings; // Ein Pointer auf ein Array mit 257 chars. Zeigt jetzt auf das erste Array von strings. // Hier wird eingelesen for (; p != strings + sizeof(strings) / sizeof(*strings) && fgets(*p, sizeof(*p), stdin) != NULL; ++p); // sizeof(strings) / sizeof(*strings) berechnet wie viele Elemente strings hat, das sind hier 256 // p darf also nicht strings + arraygröße(strings) sein. // Diese Bedingung wird zu erst getestet, wenn sie wahr ist, wird fgets() aufgerufen. // *p ist ein Array, das zerfällt bei der Übergabe in einen Zeiger auf das erste Element. // (Wie du es auch schon kennst von eindimensionalen Puffern.) // sizeof(*p) gibt hier 257 zurück. // ++p lässt p sizeof(*p) byte weiter nach vorne zeigen. // (Dort liegt dann das jeweils nächste Array[257] aus strings) // Hier wird sortiert. Nach "casten c++" kannst du selbst googlen. qsort(strings, p - strings, sizeof(*p), (int (*) (const void*, const void*))strcmp); // Das hier ist die Ausgabe, wie du siehst wird rückwärts ausgegeben. // Das letzte Element wird als erstes ausgegeben und so weiter. while (p-- != strings) printf("%s", *p); return 0; }Edit: Zu SeppJs !: Da hat er Klammern vergessen.
-
Danke schonmal vielmals, langsam wird mir alles klar!
Ich hab das mit qsort jetzt noch ein bisschen anders gelöst, und zwar so:
meine Aufruffunktion ist
qsort (namen, zahler, sizeof(char*), compare);die Funktion compare schaut so aus:
int compare (const void * a, const void * b) { return strcmp(a,b); }is ja eig. nur die längere Version von dir.
Soweit funktioniert das auch, allerdings hab ich ein kleines Problem: ich will die Strings ein wenig anders sortieren, und zwar so, dass aA vor Aa is, was hier leider nicht der Fall is.
Könnt ihr mir nochmal helfen? Wäre wirklich sehr dankbar!
MFG Zoltamor
-
Dann musst du dir deine eigene
strcmp()bauen.Wenn du den Quellcode von
strcmp()hast, wirst du sehen, dass das eine ziemlich einfache Funktion ist.Die strcmp-Versionen, die zumindest Groß/kleinschreibung ignorieren heissen meist
strcasecmpoderstrcmpi.
Auch dazu solltest du Quellen finden, damit du das anpassen kannst.Bedenke noch das
qsortnur darauf achtet, ob die Werte <0 , ==0 oder >0 sind.
Es muss nicht -1 oder +1 sein
-
Ok, hab das ganze jetzt ein wenig anders gelöst, und zwar so:
int compare (const void * a, const void * b) { int result = 0; char* string1 = (char*) a; char* string2 = (char*) b; //run through all chars in the string for(int i = 0;i<255;i++) { // compare each char case insensitive result = strncasecmp(string1+i,string2+i,1); result*=2; // if a char is the uppercase variant of the other strings char and the words have the same length add 1 to the result do differentiate between upper and lower if(isupper((int)string1[i])!= 0 && result == 0 && strlen(string1)==strlen(string2)) result+=1; else if( isupper((int)string2[i])!= 0 && result == 0 && strlen(string1)==strlen(string2)) result=-1; if(result != 0) break; } return result; }Allerdings hab ich einen Error, und keine Ahnung was dieser bedeutet:
error: 'for' loop initial declaration used outside C99 mode
der Aufruf mit qsort ist dieser:
qsort (namen, zahler, sizeof(char*), compare);Was is da falsch gelaufen?
MFG Zoltar
-
Zoltamor schrieb:
Allerdings hab ich einen Error, und keine Ahnung was dieser bedeutet:
error: 'for' loop initial declaration used outside C99 mode
der Aufruf mit qsort ist dieser:
qsort (namen, zahler, sizeof(char*), compare);Guck doch mal genau auf den Fehler. Der ist ganz woanders.
Schleifen der Form
for(Deklaration;...)darfst du erst ab C99-Standard. Das musst du bei deinem Compiler anscheinend aktivieren (-std=c99 bei GCC), sofern er es überhaupt kann (ja, der MS Compiler kann C99 (das 99 steht für 1999) überhaupt nicht und wird es wohl auch nie können).Deine Vergleichsfunktion ist übrigens ziemlich sicher total falsch, außer du möchtest ganz was anderes als ich vermute. Was soll die machen? Groß-/Kleinschreibung beim Vergleich ignorieren?
-
Mein Programm sortiert jetzt zwar Klein- vor Großbuchstaben, aber nur den ersten char! Obwohl ich natürlich jeden String nach klein- und großschreibung sortieren will.. Könnt ihr mir sagen, wo der Fehler ist?
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <ctype.h> #include <stdbool.h> int compare (const void * a, const void * b) { int result = 0; char* string1 = (char*) a; char* string2 = (char*) b; int i=0; for(i = 0;i<255;i++) { // compare each char case insensitive result = strncasecmp(string1+i,string2+i,1); result*=2; // if a char is the uppercase variant of the other strings char and the words have the same length add 1 to the result do differentiate between upper and lower if(isupper((int)string1[i])!= 0 && result == 0 && strlen(string1)==strlen(string2)) result+=1; else if( isupper((int)string2[i])!= 0 && result == 0 && strlen(string1)==strlen(string2)) result=-1; if(result != 0) break; } return result; } int main(int argc, char *argv[]) { FILE *datei; char arr[257]; //da Namen maximal 255 Zeichen lang int zahler=0; int i; int vergleich_r; int c=0; if(argc==4) datei = fopen(argv[2], "r"); else datei = fopen(argv[1], "r"); while ((c = fgetc(datei)) != EOF) //geht dur Datei bis zum Ende { if( (c >='a' && c <='z') || (c >='A' && c <='Z') || c=='-' || c==' ' || c=='\n' ) //wenn es nur aus diesen Zeichen besteht { } else { fprintf(stderr,"sortnames: wrong input format\n"); return 1; break; } } fclose(datei); if(argc==4) datei = fopen(argv[2], "r"); else datei = fopen(argv[1], "r"); if(datei == NULL) { if(argc==4) //wenn 4 Parameter übergeben sind und Input Datei nicht vorhanden ist { fprintf(stderr,"sortnames: cannot open input file: %s\n",argv[2]); return 1; } else //wenn x Parameter übergeben sind und Input Datei nicht vorhanden ist { fprintf(stderr,"sortnames: cannot open input file: %s\n",argv[1]); return 1; } } while(fgets(arr, 257,datei) != NULL) //bei jeder eingelesenen Zeile { zahler++; } fclose(datei); if(argc==4) datei = fopen(argv[2], "r"); else datei = fopen(argv[1], "r"); char namen[zahler][255]; for(i=0;i<zahler;i++) { fgets(namen[i], 255, datei); // printf("Namen Stelle %d: %s",i,namen[i]); } fclose(datei); if(argc<3) //zu wenig Parameter { fprintf(stderr,"sortnames: wrong number of input or output files\n"); return 1; } if (argc==4) { vergleich_r = strcmp(argv[1],"-r"); //wenn 4 Parameter, muss der an Stelle 1 die Option sein, also -r if (vergleich_r == 0) //wenn 4 Parameter sind und -r { qsort (namen, zahler, sizeof(char*), compare); if(argc==4) datei = fopen(argv[3], "w"); else datei = fopen(argv[2], "w"); if(datei == NULL) { if(argc==4) //wenn 4 Parameter übergeben sind und Output Datei nicht gelesen werden ann { fprintf(stderr,"sortnames: cannot open output file: %s\n",argv[3]); return 1; } else //wenn x Parameter übergeben sind und Output Date nicht gelesen werden kann { fprintf(stderr,"sortnames: cannot open output file: %s\n",argv[2]); return 1; } } for(i=zahler;i>=0;i--) { fputs (namen[i],datei); } fclose(datei); } else //4 Parameter, aber kein -r { fprintf(stderr,"sortnames: wrong option %c\n",argv[1][1]); return 1; } } else //3 Parameter { qsort (namen, zahler, sizeof(char*), compare); if(argc==4) datei = fopen(argv[3], "w"); else datei = fopen(argv[2], "w"); if(datei == NULL) { if(argc==4) //wenn 4 Parameter übergeben sind und Output Datei nicht gelesen werden ann { fprintf(stderr,"sortnames: cannot open output file: %s\n",argv[3]); return 1; } else //wenn x Parameter übergeben sind und Output Date nicht gelesen werden kann { fprintf(stderr,"sortnames: cannot open output file: %s\n",argv[2]); return 1; } } for(i=0;i<zahler;i++) { fputs (namen[i],datei); } fclose(datei); } return 0; }MFG Zoltamor
-
Das
for(int i = 0;i<255;i++)ist für Strings schon mal großer Mist, da ein String ja auch mal weniger Zeichen enthalten kann.Du musst doch nur wenn strcasecmp 0 zurückliefert und strcmp != 0 vom Ergebnis von strcmp das Vorzeichen ändern.
if ( !(result = strcasecmp(string1,string2))) /* Es sind die gleichen Woerter) */ result = -strcmp(string1,stringg2); /* Bei 0 sind sie gleich, sonst willst du das umgekehrte Verhalten */
-
Ja aber es ist halt die maximale Länge, also sehe ich da kein Problem oder?
Grundsätzlich funktioniert das sortieren ja, nur dass er mir nur den ersten char nach Groß- und Kleinschreibung sortiert (also klein vor groß), aber warum ist die Frage? Ich vergleiche ja eh die kompletten Strings...
MFG
-
Zoltamor schrieb:
Ja aber es ist halt die maximale Länge, also sehe ich da kein Problem oder?
Sehr schlechte Einstellung.
Strings enden beim Stringendezeichen '\0' und nicht nach 254 Zeichen wie bei dir.
Einmal richtig programmiert und du kannst es immer wieder ohne Änderung verwenden.
Zudem vergleichst du ja jedes Zeichen einzeln mit einer Stringfunktion.
Das macht man eigentlich direkt mit den Zeichen:
result = (int)*(string1+i)-(int)*(string2+i); // Der * ist kein mal sondern das Dereferenzierungszeichen
