4. String-Array alphabetisch sortieren?!

String-Array alphabetisch sortieren?!

  • B

    Hy Leute, ich habe ein Problem.

    Ich habe eine Struktur mit 37 Datensätzen. Ich möchte nun die Namen aufsteigend sortieren.
    Das klappt soweit ganz gut. Nur möchte ich auch den zweiten Buchstaben sortieren, sofern der erste gleich ist, usw.

    Ich bekomme da nichts logisches hin. Mir würden nur mehrere Schleifen einfallen, die das Programm sicherlich ziemlich unübersichtlich machen.

    Hier mal mein Beispiel (Ist nicht meine Aufgabe, aber das Prinzip ist wichtig):

    //
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma pack(1)
#define PUFFER 50

struct Satz {
    char Name[PUFFER];}__attribute__ ((packed));

struct Temp {
    char TempName[PUFFER];}__attribute__ ((packed));

int main(int argc, const char * argv[]){

    struct Satz bib[6];
    struct Temp temp[6];

    int elemente=5, n=1, i=0;

    strcpy(bib[1].Name, "TU Chemnitz");
    strcpy(bib[2].Name, "TU Berlin");
    strcpy(bib[3].Name, "TU Bern");
    strcpy(bib[4].Name, "Akademie Gera");
    strcpy(bib[5].Name, "Uni Leipzig");

    while(elemente--)
    for(n = 1; n < elemente+1; n++)
    if(bib[n+1].Name[0] <= bib[n].Name[0]) {

        strcpy(temp[n].TempName,bib[n].Name);

        strcpy(bib[n].Name,bib[n+1].Name);

       strcpy(bib[n+1].Name, temp[n].TempName);
}

    i=1;
    while(i<6){
        printf("Eintrag Nr: %d\n", i);
        printf("Besteller: %s\n",bib[i].Name);
        printf("\n");
        i++;
    }

        return(0);
    }
    0
  • Mod

    qsort + strcmp = Fünfzeiler (Leider nicht nur eine Zeile, weil man für strcmp noch eine Wrapperfunktion braucht). Wenn du unbedingt willst, nimm statt strcmp einen anderen Vergleich (zum Beispiel einen, der Groß- und Kleinschreibung nicht beachtet), aber schreib doch bloß nicht alles selber neu, was es schon lange fertig gibt! Vor allem da qsort unendlich viel besser ist als dein Bubblesort (ein Algorithmus der typischerweise von Informatiklehrern als Anschauungsbeispiel genutzt wird, wie man es nicht macht).

    0
  • ?

    Falls du es doch selber machen musst:
    Eine (1) temp-Variable reicht. Das muss kein Array sein.

    Für den Vergleich schreibst du eine Funktion. Nimm dir ein Beispiel an strcmp (Oder nimm es gleich)

    Dann ist dein Vergleich statt (bib[n+1].Name[0] <= bib[n].Name[0]) nur (strcmp(bib[n+1].Name[0], bib[n].Name[0]) < 0)
    Kann auch > 0 sein, musst du mal drüber nachdenken

    Wenn du mehrere Elemente der struct vergleichen willst, musst du deine Funktion erweitern. Aber benutze in dieser dann strcmp

    0
  • B

    Ich weiß, dass Bubblesort Mist ist.
    Das passiert eben, wenn man vielleicht den falschen Dozenten hat?!

    Ich hab es jetzt mit einem qsort-Code umgesetzt.
    Es funktioniert soweit bei dem Beispiel. Ich versuche es jetzt mal bei meinem komplexeren Beispiel anzuwenden.

    //
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma pack(1)
#define PUFFER 50

struct Satz {
    char Name[PUFFER];}__attribute__ ((packed));

int compare( void const * lhs, void const * rhs )
{
    struct Satz * left  = ((struct Satz *) lhs);
    struct Satz * right = ((struct Satz *) rhs);

    int result = strcmp( left->Name, right->Name );
    if( result )
        return result;

    return 0;
}

int main(int argc, const char * argv[]){

     struct Satz bib[6];

    int elemente=5, i=0;

    strcpy(bib[1].Name, "TU Chemnitz");
    strcpy(bib[2].Name, "TU Berlin");
    strcpy(bib[3].Name, "TU Bern");
    strcpy(bib[4].Name, "Akademie Gera");
    strcpy(bib[5].Name, "Uni Leipzig");

    printf("Unsortiert:\n");
    i=1;
    while(i<6){
        printf("Eintrag Nr: %d\n", i);
        printf("Besteller: %s\n",bib[i].Name);
        printf("\n");
        i++;
    }

 qsort( bib, elemente, sizeof( struct Satz ), compare );

    printf("Sortiert:\n");
    i=1;
    while(i<6){
        printf("Eintrag Nr: %d\n", i);
        printf("Besteller: %s\n",bib[i].Name);
        printf("\n");
        i++;
    }

        return(0);
    }
    0

  • qsort greift auf bib[0] zu, welches undefinierten Inhalt besitzt; deshalb ist dein Programm Müll.

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define PUFFER 50

struct Satz {
  char Name[PUFFER];
};

int main(){

  struct Satz bib[5];

  int i;

  strcpy(bib[0].Name, "TU Chemnitz");
  strcpy(bib[1].Name, "TU Berlin");
  strcpy(bib[2].Name, "TU Bern");
  strcpy(bib[3].Name, "Akademie Gera");
  strcpy(bib[4].Name, "Uni Leipzig");

  qsort(bib, sizeof bib / sizeof*bib, sizeof*bib, strcmp);

  i = 0;
  while (i<5){
    printf("Eintrag Nr: %d\n", i);
    printf("Besteller: %s\n", bib[i].Name);
    printf("\n");
    i++;
  }

  return 0;
}

    http://ideone.com/9jMxPg

    0
  • B

    Funktioniert so einwandfrei. Davor gab es aber auch eine korrekte Ausgabe?
    Egal.

    Danke schon mal!

    Wenn ich aber mehr, als nur die Variable Namen habe?!
    Zum Beispiel steht jetzt in der Struktur noch Vorname.

    0
  • ?

    Bemme90 schrieb:

    Wenn ich aber mehr, als nur die Variable Namen habe?!
    Zum Beispiel steht jetzt in der Struktur noch Vorname.

    DirkB schrieb:

    Wenn du mehrere Elemente der struct vergleichen willst, musst du deine Funktion erweitern. Aber benutze in dieser dann strcmp

    Du musst, wenn beim erste Vergleich Gleichheit festgestellt wurde, einen zweiten machen.

    int result = strcmp( left->Name, right->Name );
     if( result )
        return result;
// hier landest du bei Gleichheit
      result = strcmp( left->VorName, right->VorName );

      return result;
}
    0
  • B

    Eine Sache hätte ich noch.

    Kann ich die Bezeichnung der Struktur irgendwie übergeben?

    Ich habe jetzt folgendes:

    int compare( void const * lhs, void const * rhs)
{
    struct Satz * left  = ((struct Satz *) lhs);
    struct Satz * right = ((struct Satz *) rhs);

    int result = strcmp( left->Name, right->Name);
    if(result)
        return result;

    return 0;
}

    Je nach Auswahl des Users startet eine eigene qsort.
    Mittlerweile 4 Stück.

    Ich hätte aber gerne nur eine qsort. Beim Aufruf soll die Bezeichnung der Struktur übergeben werden. Abhängig davon, ob der User den Vornamen, Nachnamen oder das Alter sortiert haben möchte.

    0

  • Das geht standardkonform erst mit C11 und

    __STDC_WANT_LIB_EXT1__
errno_t qsort_s(void *base, rsize_t nmemb, rsize_t size,int (*compar)(const void *x, const void *y,void *context),void *context);
    0
  • B

    Sieht das kompliziert aus.

    Ich hab keine Ahnung, aus welchen Bestandteilen deine Code-Zeile besteht.
    Auch nicht, an welcher Stelle etwas übergeben wird?!

    So sieht es jetzt bei mir aus:

    Main:

    qsort(temp, ElementeTemp, sizeof*temp, compareBesteler);

    Funktion:

    int compareBesteller( void const * lhs, void const * rhs)
{
    struct Satz * left  = ((struct Satz *) lhs);
    struct Satz * right = ((struct Satz *) rhs);

    int result = strcmp( left->Besteller, right->Besteller);
    if(result)
        return result;

    return 0;
}

    Anstatt "Besteller" soll es meine Variable drinstehen

    0
  • Mod

    Wutz schrieb:

    Das geht standardkonform erst mit C11

    Auf welche Neuerung beziehst du dich?

    Bemme90 schrieb:

    Sieht das kompliziert aus.

    Ich hab keine Ahnung, aus welchen Bestandteilen deine Code-Zeile besteht.
    Auch nicht, an welcher Stelle etwas übergeben wird?!

    Das ist die Signatur einer Funktion aus der Bibliothek des Microsoft C-Compilers. Das ist fast die gleiche Signatur wie beim normalen qsort, aber die Vergleichsfunktion erlaubt die Übergabe eines weiteren Datenzeigers (der Kontext). Und die qsort_s-Funktion erlaubt die Übergabe eben dieses Zeigers, den sie dann an die Vergleichsfunktion übergeben wird.
    Diesen Zeiger könnte man beispielsweise auf einen Wert zeigen lassen, der das Offset des gewünschten Datenfeldes im struct angibt. Die Vergleichsfunktion arbeitet dann nicht mehr mit einem festen Member des structs, sondern mit struct + Offset.

    Solch ein Feature könnte man auch nachbauen, indem man den Kontext global macht. Ist aber nicht sehr schick.

    0

  • Mit VisualStudio 2013 sieht ein Beispiel zu qsort mit zusätzlichem Parameter z.B. so aus:

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

#ifndef _MSC_VER
#error nur mit MSVC
#endif

enum { NAME, VORNAME, ORT };
typedef struct {
  char name[80], vorname[80], ort[80];
} Person;

int cmp(void*c, const void*a, const void*b)
{
  const Person *x = a, *y = b;
  switch ((int)c){
  case NAME:    return strcmp(x->name, y->name);
  case VORNAME: return strcmp(x->vorname, y->vorname);
  case ORT:     return strcmp(x->ort, y->ort);
  }
}

int main()
{
  Person person [] = { { "schmidt", "hugo", "berlin" }, { "meyer", "egon", "rom" }, { "lehmann", "werner", "paris" } };
  qsort_s(person, 3, sizeof *person, cmp, NAME);
  for (int i = 0; i < 3; ++i) printf("%s\t%s\t%s\n", person[i].name, person[i].vorname, person[i].ort);
  qsort_s(person, 3, sizeof *person, cmp, VORNAME);
  for (int i = 0; i < 3; ++i) printf("%s\t%s\t%s\n", person[i].name, person[i].vorname, person[i].ort);
  qsort_s(person, 3, sizeof(Person), cmp, ORT);
  for (int i = 0; i < 3; ++i) printf("%s\t%s\t%s\n", person[i].name, person[i].vorname, person[i].ort);
  return 0;
}

    Die Ausgabe entsprechend:

    lehmann werner  paris
meyer   egon    rom
schmidt hugo    berlin
meyer   egon    rom
schmidt hugo    berlin
lehmann werner  paris
schmidt hugo    berlin
lehmann werner  paris
meyer   egon    rom

    Unsinnigerweise haben die MS-Leute die Parameter der compare-Funktion vertauscht ggü. dem C11 Standard, auch wieder Sutter-Müll.
    Aber immherhin haben sie überhaupt was im Angebot, die gcc-Leute lassen sich wieder mal lange bitten, selbst in 4.8.1 habe ich diese C11-Funktion nicht finden können.

    0
Anmelden zum Antworten