Stringtabelle mit Funktionspointer sortieren

[Erko (Gast)]

Habe hier eine Stringtabelle erstellt:

#include <stdio.h>
#include <stdlib.h>

void printStringTable(char **store){
    int i;
    for(i = 0; i < 4; i++)
        printf("String[%d] = %s\n", i, *(store+i));
}

int main()
{
    char **stringtabelle = malloc(4*sizeof(char*));
    *stringtabelle = "Karku";
    *(stringtabelle+1) = "Marku";
    *(stringtabelle+2) = "Parku";
    *(stringtabelle+3) = "Farku";

    printStringTable(stringtabelle);
    return 0;
}

und mache gerade eine Übungsaufgabe für Funktionspointer. Ich weiß aber 
leider überhaupt keinen Weg oder wie es mit Funktionspointer effizienter 
wird. Meine Idee wäre es ja nach Anfangsbuchstaben zu sortieren, jedoch 
steht in der Angabe ausdrücklich mit Funktionspointer.

Mein Problem ist: Wieso eigentlich Funktionspointer zum Sortieren? Ich 
kann mir das überhaupt nicht vorstellen.

Kann mich wer aufklären?

Gruß

[Peter II (Gast)]

Erko schrieb:
> Kann mich wer aufklären?

schau dir doch mal die qsort Funktion an

http://www.gnu.org/software/libc/manual/html_node/Array-Sort-Function.html

dann wirst du merken, das man dafür einen funktionszeiger braucht.

[Erko (Gast)]

Peter II schrieb:
> dann wirst du merken, das man dafür einen funktionszeiger braucht.

Eigentlich ging es mir um das Konzept. Ich will gar nicht wissen wie 
qsort funktioniert. Ich will nur eine Idee, damit ich mir überlegen kann 
wie ich das selber realisiere

[Peter II (Gast)]

Erko schrieb:
> Eigentlich ging es mir um das Konzept. Ich will gar nicht wissen wie
> qsort funktioniert. Ich will nur eine Idee, damit ich mir überlegen kann
> wie ich das selber realisiere

musst du auch nicht. Verwende doch erst mal qsort. Wenn das funktioniert 
kannst du dein eigenes qsort schreiben.

[Erko (Gast)]

Peter II schrieb:
> musst du auch nicht. Verwende doch erst mal qsort. Wenn das funktioniert
> kannst du dein eigenes qsort schreiben.

Ok, aber ich verstehe nicht ganz, wie qsort funktioniert?
In der Anleitung (hier: 
http://www.cplusplus.com/reference/cstdlib/qsort/ ) ist das Beispiel 
etwas wirr.

Welche Compare Funktion soll ich zB der FUnktion qsort geben? Im 
Beispiel steht das hier:

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

Erstens: Ich verstehe nicht was sich dieser Rückgabewert eigentlich 
bringt (was er ergibt weiß ich)
Zweitens, ich habe andere Quellen im Internet, die andere Compares 
haben. Aber heh?? Wie soll das alles funktionieren?

[Rene H. (Gast)]

Bildlich so:

http://m.youtube.com/watch?v=ywWBy6J5gz8&desktop_uri=%2Fwatch%3Fv%3DywWBy6J5gz8

:-)

Grüsse,
René

[Joachim D. (Firma: JDCC) (scheppertreiber)]

Herrlich :-)))

[Peter II (Gast)]

Erko schrieb:
> Aber heh?? Wie soll das alles funktionieren?

genau das ist ja der punkt. Es wird mit funktionspointern gearbeitet. 
Der Qsort Funktion muss man einen Funktion mitgeben, die den Vergleich 
von 2 Einträgen macht. Sonst könnte Qsort ja nicht beliebige Dinge 
sortieren.

[Rolf Magnus (Gast)]

Erko schrieb:
> Welche Compare Funktion soll ich zB der FUnktion qsort geben?

Na eine, die zwei Strings nach den von dir gewünschten Sortierkriterien 
vergleicht.

> Im Beispiel steht das hier:
> int compare (const void * a, const void * b)
> {
>   return ( *(int*)a - *(int*)b );
> }
> Erstens: Ich verstehe nicht was sich dieser Rückgabewert eigentlich
> bringt (was er ergibt weiß ich)

Er ist das Vergleichsergebnis, das von qsort benutzt wird, um zu 
entscheiden, ob zwei Elemente vertauscht werden sollen oder nicht.
Ein Rückgabewert >0 heißt, daß dein verlgeich den ersten Wert als 
"größer" als den zweiten Wert betrachtet, <0 heißt, daß der erste Wert 
kleiner ist. Wenn sie beide gleich sind, muß 0 rauskommen.
Vielleicht ist folgende für qsort äquivalente Variante besser 
verständlich:

int compare (const void * a, const void * b) 
{
    const int* Wert1 = (const int*)a;
    const int* Wert2 = (const int*)b;

    if (*Wert1 < *Wert2)
        return -1;
    else if (*Wert1 > *Wert2)
        return 1;
    else
        return 0;
}

> Zweitens, ich habe andere Quellen im Internet, die andere Compares
> haben.

Na wenn man immer die selbe bräuchte, wäre das ganze ja recht sinnlos.

> Aber heh?? Wie soll das alles funktionieren?

Das ist eine etwas allgemein formulierte Frage.

[Rene H. (Gast)]

Joachim Drechsel schrieb:
> Herrlich :-)))

Braucht etwas Geduld, man muss bloss die Taktfrequenz erhöhen. Dennoch 
ist es gut veranschaulicht.

Grüsse,
René

[Erko (Gast)]

Ich bringe es irgendwie nicht zusammen, es ist weniger das was mich in 
der compare FUnktion beruhigt, sondern eher das wasbeim Aufruf ist. Ich 
kriege 1 Warnung, die ich nicht wirklich für verständlich halte

#include <stdio.h>
#include <stdlib.h>

void printStringTable(char **store);
int compare(char *string1, char *string2);

int main()
{
    char **stringtabelle = malloc(4*sizeof(char*));
    *stringtabelle = "Karku";
    *(stringtabelle+1) = "Marku";
    *(stringtabelle+2) = "Parku";
    *(stringtabelle+3) = "Farku";

    printStringTable(stringtabelle);

    qsort(stringtabelle[0], 4, 6, compare);

    return 0;
}

int compare(char *string1, char *string2){
    return 0;
}

void printStringTable(char **store){
    int i;
    for(i = 0; i < 4; i++)
        printf("String[%d] = %s\n", i, *(store+i));
}

Außerdem wie soll das denn qsort anstellen die strings zu vertauschen? 
Ich sehe das irgendwie noch nicht ganz ein.

Danke für die ganzen Tipps.

[Yalu X. (yalu) (Moderator)]

Offtopic:

Wollte gerade fragen, ob die schenkelklatschenden Jungs denn auch schon 
den Heapsort und den Mergesort implementiert haben, habe aber die 
Antwort selber gefunden:

  http://www.youtube.com/user/AlgoRythmics/videos

Die Laufzeiten für die einzelnen Algorithmen kann man dem Link ebenfalls 
entnehmen. Dabei schneidet der Quicksort schlechter ab, als sein Name 
vermuten lässt. Das kann aber auch an dem verwendeten Speichermodell 
liegen :)

Der Heapsort liegt wohl noch beim Programmierer, ähm Choreographen.


Ontopic:

Erko schrieb:
> qsort(stringtabelle[0], 4, 6, compare);

Das erste Argument ist nicht richtig: qsort erwartet hier das zu 
sortierende Array und nicht nur dessen erstes Element.

Das dritte Argument sollte die Größe eines Array-Elements sein. Überlege 
dir, welchen Typ die Array-Elemente haben.

Die Compiler-Warnung kommt aber vom letzten Argument: Gemäß Anleitung 
der qsort-Funktion muss die compare-Funktion folgendermassen deklariert 
sein:

int compare (const void *p1, const void *p2);

Erko schrieb:
> Außerdem wie soll das denn qsort anstellen die strings zu vertauschen?

Wenn die richtigen Argumente übergeben werden, kennt qsort die 
Startadresse des Arrays und die Größe jedes Elements. Damit kann die 
Funktion auch die Startadresse des i-ten Elements berechnen. Soll das 
i-te mit dem j-ten Element vertauscht werden, werden einfach die beiden 
Startadressen berechnet und jeweils soviele nachfolgende Bytes 
vertauscht, wie die Elemente groß sind. Um zu entscheiden, welche 
Elemente zu vertauschen sind, wird die compare-Funktion mit den 
Startadressen von jeweils zwei Elementen aufgerufen.

Zusätzlich zu den Funktionspointern lernst du bei dieser Aufgabe sicher 
auch noch eine Menge über Datenpointer und Arrays sowie das Umcasten von 
Datenpointern.