#include <stdio.h>   /* printf,puts    */
#include <string.h>  /* strncat,strtok */
#include <stdlib.h>  /* bsearch,qsort  */
#include <assert.h>  /* assert         */
 
/* Typdefinition für Map-Element */
typedef struct {
  char string[21];
  int i;
} Eintrag;
 
/* max. Größe der Map */
enum { MAPSIZE = 1000 };
 
/*
   Funktions-Prototypen
   */
 
/* fügt einen String in die Map ein (oder erhöht den Zähler wenn schon vorhanden) */
void add(Eintrag *map, const char *string);
 
/* durchläuft alle Elemente der Map und ruft für jedes die übergebene Funktion auf */
void loop(const Eintrag *map, void(*callback)(const Eintrag*, void*), void*);
 
/* Callback-Funktion: gibt ein Element auf stdout aus */
void ausgabe(const Eintrag*, void*);
 
/* Callback-Funktion: summiert Häufigkeiten der Elemente */
void zaehlen(const Eintrag*, int*);
 
/* zählt die aktuell in der Map vorhandenen Elemente */
int count(const Eintrag *map);
 
/* Callback-Funktion für qsort zum Sortieren der Map nach Häufigkeit (absteigend) */
int sortiert(const void *a, const void *b);
 
 
int main()
{
  char ek[] = \
    "Wer reitet so spät durch Nacht und Wind?             "\
    "Es ist der Vater mit seinem Kind.                    "\
    "Er hat den Knaben wohl in dem Arm,                   "\
    "Er faßt ihn sicher, er hält ihn warm.                "\
 
    "Mein Sohn, was birgst du so bang dein Gesicht?       "\
    "Siehst Vater, du den Erlkönig nicht!                 "\
    "Den Erlenkönig mit Kron' und Schweif?                "\
    "Mein Sohn, es ist ein Nebelstreif.                   "\
 
    "Du liebes Kind, komm geh' mit mir!                   "\
    "Gar schöne Spiele, spiel ich mit dir,                "\
    "Manch bunte Blumen sind an dem Strand,               "\
    "Meine Mutter hat manch gülden Gewand.                "\
 
    "Mein Vater, mein Vater, und hörest du nicht,         "\
    "Was Erlenkönig mir leise verspricht?                 "\
    "Sei ruhig, bleibe ruhig, mein Kind,                  "\
    "In dürren Blättern säuselt der Wind.                 "\
 
    "Willst feiner Knabe du mit mir geh'n?                "\
    "Meine Töchter sollen dich warten schön,              "\
    "Meine Töchter führen den nächtlichen Reihn           "\
    "Und wiegen und tanzen und singen dich ein.           "\
 
    "Mein Vater, mein Vater, und siehst du nicht dort     "\
    "Erlkönigs Töchter am düsteren Ort?                   "\
    "Mein Sohn, mein Sohn, ich seh es genau:              "\
    "Es scheinen die alten Weiden so grau.                "\
 
    "Ich lieb dich, mich reizt deine schöne Gestalt,      "\
    "Und bist du nicht willig, so brauch ich Gewalt!      "\
    "Mein Vater, mein Vater, jetzt faßt er mich an,       "\
    "Erlkönig hat mir ein Leids getan.                    "\
 
    "Dem Vater grauset's, er reitet geschwind,            "\
    "Er hält in den Armen das ächzende Kind,              "\
    "Erreicht den Hof mit Mühe und Not,                   "\
    "In seinen Armen das Kind war tot.                    "\
    ;
 
  Eintrag map[MAPSIZE] = { 0 };  /* Definition der Map (hier als Array) */
 
  char *wort;
  int z, h;
 
  /* Aufsplitten nach Worten und Einfügen in Map */
  for (z = 0, wort = strtok(ek, " .!?,"); wort != NULL; wort = strtok(NULL, " .!?,"), z++)
  {
    add(map, wort);
  }
 
  printf("Anzahl Worte: %d\n", z);
  printf("Anzahl verschiedene Worte: %d\n", count(map));
 
  puts("sortiert nach Namen");
  loop(map, ausgabe, 0);                              /* die Map ist hier wegen qsort+strcmp aufsteigend nach Wort-Strings sortiert */
 
  puts("sortiert nach Häufigkeit");
  qsort(map, count(map), sizeof(Eintrag), sortiert);  /* sortieren der Map nach Häufigkeit der Worte (absteigend) */
  loop(map, ausgabe, 0);
 
  h = 0;
  loop(map, zaehlen, &h);
  printf("Summe der Häufigkeiten: %d\n", h);  /* die Summe der Häufigkeiten muss der Anzahl der Worte entsprechen */
  assert(h == z);                             /* sonst liefert assert hier einen Fehler + Programmabbruch         */
 
  return 0;
}
 
int count(const Eintrag *map)
{
  int i = 0;
  for (; i < MAPSIZE && map[i].i; i++);
  return i;
}
 
void add(Eintrag *map, const char *string)
{
  Eintrag *e = bsearch(string, map, count(map), sizeof(Eintrag), strcmp);
  if (e == NULL)
  {
    int new = count(map);   /* neuer Eintrag notwendig */
    map[new].i = 1;
    strncat(map[new].string, string, 20);
    qsort(map, new + 1, sizeof(Eintrag), strcmp);
  }
  else
  {
    e->i++;  /* wenn schon vorhanden, dann nur entsprechenden Zähler erhöhen */
  }
}
 
void loop(const Eintrag *map, void(*callback)(const Eintrag*, void*), void*data)
{
  int i;
  for (i = 0; i < count(map); i++)
  {
    callback(&map[i], data);
  }
}
 
void ausgabe(const Eintrag *e, void *dummy)
{
  printf("%-20s %d\n", e->string, e->i);
}
 
void zaehlen(const Eintrag *e, int *h)
{
  *h += e->i;
}
 
int sortiert(const void *a, const void *b)
{
  const Eintrag *x = a, *y = b;
  return y->i - x->i;
}
 
 

I2luY2x1ZGUgPHN0ZGlvLmg+ICAgLyogcHJpbnRmLHB1dHMgICAgKi8KI2luY2x1ZGUgPHN0cmluZy5oPiAgLyogc3RybmNhdCxzdHJ0b2sgKi8KI2luY2x1ZGUgPHN0ZGxpYi5oPiAgLyogYnNlYXJjaCxxc29ydCAgKi8KI2luY2x1ZGUgPGFzc2VydC5oPiAgLyogYXNzZXJ0ICAgICAgICAgKi8KCi8qIFR5cGRlZmluaXRpb24gZsO8ciBNYXAtRWxlbWVudCAqLwp0eXBlZGVmIHN0cnVjdCB7CiAgY2hhciBzdHJpbmdbMjFdOwogIGludCBpOwp9IEVpbnRyYWc7CgovKiBtYXguIEdyw7bDn2UgZGVyIE1hcCAqLwplbnVtIHsgTUFQU0laRSA9IDEwMDAgfTsKCi8qCiAgIEZ1bmt0aW9ucy1Qcm90b3R5cGVuCiAgICovCgovKiBmw7xndCBlaW5lbiBTdHJpbmcgaW4gZGllIE1hcCBlaW4gKG9kZXIgZXJow7ZodCBkZW4gWsOkaGxlciB3ZW5uIHNjaG9uIHZvcmhhbmRlbikgKi8Kdm9pZCBhZGQoRWludHJhZyAqbWFwLCBjb25zdCBjaGFyICpzdHJpbmcpOwoKLyogZHVyY2hsw6R1ZnQgYWxsZSBFbGVtZW50ZSBkZXIgTWFwIHVuZCBydWZ0IGbDvHIgamVkZXMgZGllIMO8YmVyZ2ViZW5lIEZ1bmt0aW9uIGF1ZiAqLwp2b2lkIGxvb3AoY29uc3QgRWludHJhZyAqbWFwLCB2b2lkKCpjYWxsYmFjaykoY29uc3QgRWludHJhZyosIHZvaWQqKSwgdm9pZCopOwoKLyogQ2FsbGJhY2stRnVua3Rpb246IGdpYnQgZWluIEVsZW1lbnQgYXVmIHN0ZG91dCBhdXMgKi8Kdm9pZCBhdXNnYWJlKGNvbnN0IEVpbnRyYWcqLCB2b2lkKik7CgovKiBDYWxsYmFjay1GdW5rdGlvbjogc3VtbWllcnQgSMOkdWZpZ2tlaXRlbiBkZXIgRWxlbWVudGUgKi8Kdm9pZCB6YWVobGVuKGNvbnN0IEVpbnRyYWcqLCBpbnQqKTsKCi8qIHrDpGhsdCBkaWUgYWt0dWVsbCBpbiBkZXIgTWFwIHZvcmhhbmRlbmVuIEVsZW1lbnRlICovCmludCBjb3VudChjb25zdCBFaW50cmFnICptYXApOwoKLyogQ2FsbGJhY2stRnVua3Rpb24gZsO8ciBxc29ydCB6dW0gU29ydGllcmVuIGRlciBNYXAgbmFjaCBIw6R1Zmlna2VpdCAoYWJzdGVpZ2VuZCkgKi8KaW50IHNvcnRpZXJ0KGNvbnN0IHZvaWQgKmEsIGNvbnN0IHZvaWQgKmIpOwoKCmludCBtYWluKCkKewogIGNoYXIgZWtbXSA9IFwKICAgICJXZXIgcmVpdGV0IHNvIHNww6R0IGR1cmNoIE5hY2h0IHVuZCBXaW5kPyAgICAgICAgICAgICAiXAogICAgIkVzIGlzdCBkZXIgVmF0ZXIgbWl0IHNlaW5lbSBLaW5kLiAgICAgICAgICAgICAgICAgICAgIlwKICAgICJFciBoYXQgZGVuIEtuYWJlbiB3b2hsIGluIGRlbSBBcm0sICAgICAgICAgICAgICAgICAgICJcCiAgICAiRXIgZmHDn3QgaWhuIHNpY2hlciwgZXIgaMOkbHQgaWhuIHdhcm0uICAgICAgICAgICAgICAgICJcCgogICAgIk1laW4gU29obiwgd2FzIGJpcmdzdCBkdSBzbyBiYW5nIGRlaW4gR2VzaWNodD8gICAgICAgIlwKICAgICJTaWVoc3QgVmF0ZXIsIGR1IGRlbiBFcmxrw7ZuaWcgbmljaHQhICAgICAgICAgICAgICAgICAiXAogICAgIkRlbiBFcmxlbmvDtm5pZyBtaXQgS3JvbicgdW5kIFNjaHdlaWY/ICAgICAgICAgICAgICAgICJcCiAgICAiTWVpbiBTb2huLCBlcyBpc3QgZWluIE5lYmVsc3RyZWlmLiAgICAgICAgICAgICAgICAgICAiXAoKICAgICJEdSBsaWViZXMgS2luZCwga29tbSBnZWgnIG1pdCBtaXIhICAgICAgICAgICAgICAgICAgICJcCiAgICAiR2FyIHNjaMO2bmUgU3BpZWxlLCBzcGllbCBpY2ggbWl0IGRpciwgICAgICAgICAgICAgICAgIlwKICAgICJNYW5jaCBidW50ZSBCbHVtZW4gc2luZCBhbiBkZW0gU3RyYW5kLCAgICAgICAgICAgICAgICJcCiAgICAiTWVpbmUgTXV0dGVyIGhhdCBtYW5jaCBnw7xsZGVuIEdld2FuZC4gICAgICAgICAgICAgICAgIlwKCiAgICAiTWVpbiBWYXRlciwgbWVpbiBWYXRlciwgdW5kIGjDtnJlc3QgZHUgbmljaHQsICAgICAgICAgIlwKICAgICJXYXMgRXJsZW5rw7ZuaWcgbWlyIGxlaXNlIHZlcnNwcmljaHQ/ICAgICAgICAgICAgICAgICAiXAogICAgIlNlaSBydWhpZywgYmxlaWJlIHJ1aGlnLCBtZWluIEtpbmQsICAgICAgICAgICAgICAgICAgIlwKICAgICJJbiBkw7xycmVuIEJsw6R0dGVybiBzw6R1c2VsdCBkZXIgV2luZC4gICAgICAgICAgICAgICAgICJcCgogICAgIldpbGxzdCBmZWluZXIgS25hYmUgZHUgbWl0IG1pciBnZWgnbj8gICAgICAgICAgICAgICAgIlwKICAgICJNZWluZSBUw7ZjaHRlciBzb2xsZW4gZGljaCB3YXJ0ZW4gc2Now7ZuLCAgICAgICAgICAgICAgIlwKICAgICJNZWluZSBUw7ZjaHRlciBmw7xocmVuIGRlbiBuw6RjaHRsaWNoZW4gUmVpaG4gICAgICAgICAgICJcCiAgICAiVW5kIHdpZWdlbiB1bmQgdGFuemVuIHVuZCBzaW5nZW4gZGljaCBlaW4uICAgICAgICAgICAiXAoKICAgICJNZWluIFZhdGVyLCBtZWluIFZhdGVyLCB1bmQgc2llaHN0IGR1IG5pY2h0IGRvcnQgICAgICJcCiAgICAiRXJsa8O2bmlncyBUw7ZjaHRlciBhbSBkw7xzdGVyZW4gT3J0PyAgICAgICAgICAgICAgICAgICAiXAogICAgIk1laW4gU29obiwgbWVpbiBTb2huLCBpY2ggc2VoIGVzIGdlbmF1OiAgICAgICAgICAgICAgIlwKICAgICJFcyBzY2hlaW5lbiBkaWUgYWx0ZW4gV2VpZGVuIHNvIGdyYXUuICAgICAgICAgICAgICAgICJcCgogICAgIkljaCBsaWViIGRpY2gsIG1pY2ggcmVpenQgZGVpbmUgc2Now7ZuZSBHZXN0YWx0LCAgICAgICJcCiAgICAiVW5kIGJpc3QgZHUgbmljaHQgd2lsbGlnLCBzbyBicmF1Y2ggaWNoIEdld2FsdCEgICAgICAiXAogICAgIk1laW4gVmF0ZXIsIG1laW4gVmF0ZXIsIGpldHp0IGZhw590IGVyIG1pY2ggYW4sICAgICAgICJcCiAgICAiRXJsa8O2bmlnIGhhdCBtaXIgZWluIExlaWRzIGdldGFuLiAgICAgICAgICAgICAgICAgICAgIlwKCiAgICAiRGVtIFZhdGVyIGdyYXVzZXQncywgZXIgcmVpdGV0IGdlc2Nod2luZCwgICAgICAgICAgICAiXAogICAgIkVyIGjDpGx0IGluIGRlbiBBcm1lbiBkYXMgw6RjaHplbmRlIEtpbmQsICAgICAgICAgICAgICAiXAogICAgIkVycmVpY2h0IGRlbiBIb2YgbWl0IE3DvGhlIHVuZCBOb3QsICAgICAgICAgICAgICAgICAgICJcCiAgICAiSW4gc2VpbmVuIEFybWVuIGRhcyBLaW5kIHdhciB0b3QuICAgICAgICAgICAgICAgICAgICAiXAogICAgOwoKICBFaW50cmFnIG1hcFtNQVBTSVpFXSA9IHsgMCB9OyAgLyogRGVmaW5pdGlvbiBkZXIgTWFwIChoaWVyIGFscyBBcnJheSkgKi8KCiAgY2hhciAqd29ydDsKICBpbnQgeiwgaDsKCiAgLyogQXVmc3BsaXR0ZW4gbmFjaCBXb3J0ZW4gdW5kIEVpbmbDvGdlbiBpbiBNYXAgKi8KICBmb3IgKHogPSAwLCB3b3J0ID0gc3RydG9rKGVrLCAiIC4hPywiKTsgd29ydCAhPSBOVUxMOyB3b3J0ID0gc3RydG9rKE5VTEwsICIgLiE/LCIpLCB6KyspCiAgewogICAgYWRkKG1hcCwgd29ydCk7CiAgfQoKICBwcmludGYoIkFuemFobCBXb3J0ZTogJWRcbiIsIHopOwogIHByaW50ZigiQW56YWhsIHZlcnNjaGllZGVuZSBXb3J0ZTogJWRcbiIsIGNvdW50KG1hcCkpOwoKICBwdXRzKCJzb3J0aWVydCBuYWNoIE5hbWVuIik7CiAgbG9vcChtYXAsIGF1c2dhYmUsIDApOyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8qIGRpZSBNYXAgaXN0IGhpZXIgd2VnZW4gcXNvcnQrc3RyY21wIGF1ZnN0ZWlnZW5kIG5hY2ggV29ydC1TdHJpbmdzIHNvcnRpZXJ0ICovCgogIHB1dHMoInNvcnRpZXJ0IG5hY2ggSMOkdWZpZ2tlaXQiKTsKICBxc29ydChtYXAsIGNvdW50KG1hcCksIHNpemVvZihFaW50cmFnKSwgc29ydGllcnQpOyAgLyogc29ydGllcmVuIGRlciBNYXAgbmFjaCBIw6R1Zmlna2VpdCBkZXIgV29ydGUgKGFic3RlaWdlbmQpICovCiAgbG9vcChtYXAsIGF1c2dhYmUsIDApOwoKICBoID0gMDsKICBsb29wKG1hcCwgemFlaGxlbiwgJmgpOwogIHByaW50ZigiU3VtbWUgZGVyIEjDpHVmaWdrZWl0ZW46ICVkXG4iLCBoKTsgIC8qIGRpZSBTdW1tZSBkZXIgSMOkdWZpZ2tlaXRlbiBtdXNzIGRlciBBbnphaGwgZGVyIFdvcnRlIGVudHNwcmVjaGVuICovCiAgYXNzZXJ0KGggPT0geik7ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvKiBzb25zdCBsaWVmZXJ0IGFzc2VydCBoaWVyIGVpbmVuIEZlaGxlciArIFByb2dyYW1tYWJicnVjaCAgICAgICAgICovCgogIHJldHVybiAwOwp9CgppbnQgY291bnQoY29uc3QgRWludHJhZyAqbWFwKQp7CiAgaW50IGkgPSAwOwogIGZvciAoOyBpIDwgTUFQU0laRSAmJiBtYXBbaV0uaTsgaSsrKTsKICByZXR1cm4gaTsKfQoKdm9pZCBhZGQoRWludHJhZyAqbWFwLCBjb25zdCBjaGFyICpzdHJpbmcpCnsKICBFaW50cmFnICplID0gYnNlYXJjaChzdHJpbmcsIG1hcCwgY291bnQobWFwKSwgc2l6ZW9mKEVpbnRyYWcpLCBzdHJjbXApOwogIGlmIChlID09IE5VTEwpCiAgewogICAgaW50IG5ldyA9IGNvdW50KG1hcCk7ICAgLyogbmV1ZXIgRWludHJhZyBub3R3ZW5kaWcgKi8KICAgIG1hcFtuZXddLmkgPSAxOwogICAgc3RybmNhdChtYXBbbmV3XS5zdHJpbmcsIHN0cmluZywgMjApOwogICAgcXNvcnQobWFwLCBuZXcgKyAxLCBzaXplb2YoRWludHJhZyksIHN0cmNtcCk7CiAgfQogIGVsc2UKICB7CiAgICBlLT5pKys7ICAvKiB3ZW5uIHNjaG9uIHZvcmhhbmRlbiwgZGFubiBudXIgZW50c3ByZWNoZW5kZW4gWsOkaGxlciBlcmjDtmhlbiAqLwogIH0KfQoKdm9pZCBsb29wKGNvbnN0IEVpbnRyYWcgKm1hcCwgdm9pZCgqY2FsbGJhY2spKGNvbnN0IEVpbnRyYWcqLCB2b2lkKiksIHZvaWQqZGF0YSkKewogIGludCBpOwogIGZvciAoaSA9IDA7IGkgPCBjb3VudChtYXApOyBpKyspCiAgewogICAgY2FsbGJhY2soJm1hcFtpXSwgZGF0YSk7CiAgfQp9Cgp2b2lkIGF1c2dhYmUoY29uc3QgRWludHJhZyAqZSwgdm9pZCAqZHVtbXkpCnsKICBwcmludGYoIiUtMjBzICVkXG4iLCBlLT5zdHJpbmcsIGUtPmkpOwp9Cgp2b2lkIHphZWhsZW4oY29uc3QgRWludHJhZyAqZSwgaW50ICpoKQp7CiAgKmggKz0gZS0+aTsKfQoKaW50IHNvcnRpZXJ0KGNvbnN0IHZvaWQgKmEsIGNvbnN0IHZvaWQgKmIpCnsKICBjb25zdCBFaW50cmFnICp4ID0gYSwgKnkgPSBiOwogIHJldHVybiB5LT5pIC0geC0+aTsKfQoK