Wikibooks

C-Programmierung: Aufgaben: Häufigkeit von Worten

Aufgabenstellung

Bearbeiten

Von einem Text ist die Häufigkeit der einzelnen Wörter zu bestimmen.'In diesem anspruchsvolleren Beispiel lernst du einige grundlegende IT-Aufgaben am Beispiel von Standard C näher kennen:

  • String splitten strtok
  • Suchen bsearch
  • Sortieren qsort
  • Assertions assert
  • Datenstruktur Map (Dictionary)
  • Callback-Funktion

Zum Verständnis der Musterlösung bietet es sich an, zunächst nur die Kommentare der Prototypen zu lesen und anschließend den Ablauf in main() zu verfolgen. Die konkreten Implementierungen der Funktionen danach sind erst danach interessant.

Wichtig ist die Erkenntnis, dass Funktionen einzelne, fachlich und technisch unabhängige Aufgaben übernehmen (Kapselung) und ausschließlich über Parameter und Return-Wert mit main oder wiederum anderen Funktionen kommunizieren. Im Beispiel erkennst du dies daran, dass jede Funktion einen Parameter für map definiert, denn die map stellt die grundlegende Datenstruktur für die Datenverarbeitung in diesem Beispielprogramm dar. Es erfolgt nirgends ein direkter Zugriff auf map, die Zugriffe sind nur innerhalb von Funktionen vorhanden. Dies bedeutet eine saubere Schnittstelle zu den Daten und trägt wesentlich zur Übersichtlichkeit im Code bei.

Eine Map besteht immer aus einer Menge von key/value-Paaren, wobei jeder key in der gesamten Map immer eindeutig ist. Im Beispiel ist der key (Schlüssel) das Wort selbst (string) und der value (Wert) die Anzahl des Vorkommens des Wortes im Gesamttext.

Als Callback bezeichnet man eine bereitzustellende Funktion (die üblicherweise vom Anwender selbst implementiert werden kann), die einer anderen Funktion (also einem anderen Programmkontext) übergeben und ausschließlich dort aufgerufen wird. Im Beispiel dienen die Funktionen

  • strcmp+sortiert als Callback für bsearch,qsort
  • ausgabe+zaehlen als Callback für die Map (loop)

Beim Suchen mit bsearch ist zu beachten, dass die dort implementierte binäre Suche nur funktioniert, wenn die Daten bereits sortiert vorliegen. Deshalb erfolgt in der Funktion add nach jedem Hinzufügen eines neuen Elements eine Komplettsortierung mit qsort, wobei dieselbe Callback-Funktion sortiert verwendet wird, wie später bei bsearch.

Für die Gestaltung einer MultiMap wäre es auch ausreichend, wenn die Sortierung nur einmalig nach dem letzten add erfolgt, und bei add selbst gar keine Suche nach bereits existierenden Elementen erfolgt.

 

Merke
Eine Suche mit bsearch bedingt immer eine vorige Sortierung der Daten (z.B. mit qsort) und der gleichen Callback-Funktion, bzw. einer Funktion, die die gleichen Sortierung liefert.


Musterlösung

Bearbeiten

Online-Compiler ideone 

#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 Wörtern und Einfügen in Map */
  for (z = 0, wort = strtok(ek, " .!?,"); wort != NULL; wort = strtok(NULL, " .!?,"), z++)
  {
    add(map, wort);
  }

  printf("Anzahl Wörter: %d\n", z);
  printf("Anzahl verschiedene Wörter: %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 Wörter (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 Wörter 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;
}
Abgerufen von „https://de.wikibooks.org/w/index.php?title=C-Programmierung:_Aufgaben:_Häufigkeit_von_Worten&oldid=773319“