// Übung für Strukturen und Pointer: Einfach verkettete Liste
//
// Aufruf: liste zahl1 zahl2 zahl3 ...
//
// Klaus Kusche, 2012

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

// ein Eintrag unserer Liste
struct eintrag {
  int zahl;     // die Zahl
  int anz;      // wie oft ist diese Zahl bisher vorgekommen?
  struct eintrag *next;  // Pointer auf den nächsten Eintrag
};

typedef struct eintrag eintrag;

eintrag *neu(int z, eintrag *n);
eintrag *find(eintrag **head, int z);
void print(eintrag *head);

// Die Funktion soll einen Pointer auf ein neu angelegtes Element liefern
// und dieses Element mit zahl = z, anz = 0 und Nachfolger = n befüllen
eintrag *neu(int z, eintrag *n)
{
  // leg neuen Speicher für einen Eintrag an und lass p darauf zeigen
  eintrag *p = (eintrag *) (malloc(sizeof(eintrag)));
  if (p == NULL) {
    fprintf(stderr, "Speicher anlegen schiefgegangen?!\n");
    exit(EXIT_FAILURE);
  }
  p->zahl = z;
  p->anz = 0;
  p->next = n;
  return p;    // Returnwert = Pointer auf den neuen Eintrag
}

// Die Funktion soll das Element mit der Zahl z in der Liste finden
// und einen Pointer darauf zurückgeben.
// Gibt es noch kein Element mit der Zahl z,
// soll ein neues Element erzeugt
// und an der richtigen Stelle in die Liste gehängt werden,
// sodass die Liste aufsteigend nach den Zahlen sortiert bleibt.
// Da die Funktion head ändern muss, 
// wenn ein neues Element ganz vorne eingefügt wird,
// muss head "by Reference" übergeben werden!
// D.h. head_p ist ein Pointer auf die Head-Variable im main
// und daher ein Pointer auf einen Pointer
eintrag *find(eintrag **head_p, int z)
{
  eintrag *akt_elem_p;  // Pointer auf das aktuelle Element der Liste
  eintrag *next_elem_p; // Pointer auf das Element nach akt_elem_p
  eintrag *neu_elem_p;  // Pointer auf das neu angelegte Element

  // Lass akt_elem_p auf das erste Element der Liste zeigen
  // also auf das Element, auf das der head im main zeigt
  akt_elem_p = *head_p;
  // Wenn es noch kein erstes Element gibt (Liste leer),
  // oder wenn die Zahl im ersten Element größer als die gesuchte Zahl ist...
  if ((akt_elem_p == NULL) || (akt_elem_p->zahl > z)) {
    // ... dann erzeuge ein neues Element mit der Zahl
    // und dem bisher ersten Element der Liste als Nachfolger
    // (bei bisher leerer Liste ist der Nachfolger eben NULL)...
    neu_elem_p = neu(z, akt_elem_p);
    // das neue Element soll vorderstes Element der Liste werden
    // ==> speichere den Pointer darauf im Head-Pointer von main
    *head_p = neu_elem_p;
    // und gib den Pointer auf das neue Element zurück
    return neu_elem_p;
  } else {
    // Liste durchlaufen: akt_elem_p zeigt auf das aktuelle Element
    for (;;) {   
      if (akt_elem_p->zahl == z) {
        // Das aktuelle Element enthält die gesuchte Zahl
        // ==> den Pointer auf das aktuelle Element zurückgeben
        return akt_elem_p;
      }
      next_elem_p = akt_elem_p->next;  // Nachfolger des aktuellen Elementes
      // Wenn es keinen Nachfolger gibt
      // (d.h. akt_elem_p ist das letzte Element der Liste)
      // oder wenn die Zahl im Nachfolger größer ist als die gesuchte Zahl ...
      if ((next_elem_p == NULL) || (next_elem_p->zahl > z)) {
        // ... dann erzeuge ein neues Element mit der Zahl
        // und dem bisherigen Nachfolger des aktuellen Elementes als Nachfolger
        // (war das aktuelle Element das letzte Element der Liste,
        // dann ist der Nachfolger des neuen Elementes eben NULL) ...
        neu_elem_p = neu(z, next_elem_p);
        // ... und hänge das neue Element
        // als neuen Nachfolger von akt_elem_p in die Liste
        akt_elem_p->next = neu_elem_p;
        // und gib den Pointer auf das neue Element zurück
        return neu_elem_p;
      }
      // Sonst: Geh für den nächsten Schleifendurchlauf in der Liste eins weiter
      // d.h. der Nachfolger des aktuellen Elementes wird das aktuelle Element
      akt_elem_p = next_elem_p;  
    }
  }
}

// Ausgeben der gesamten Liste
// diesmal wird head normal (d.h. by value) übergeben,
// d.h. head ist ein Pointer auf das erste Listenelement
void print(eintrag *head)
{
  // Liste mit p von Anfang bis zum Ende durchlaufen
  for (eintrag *p = head; p != NULL; p = p->next) {
    printf("%d:%d ", p->zahl, p->anz);
  }
  printf("\n");
}

int main(int argc, const char *argv[])
{
  // Listenkopf (zeigt auf das erste Element der Liste)
  // Am Anfang gibt es kein erstes Element, daher NULL
  eintrag *head = NULL;

  for (int i = 1; i < argc; ++i) {
    // suche die i-te Zahl bzw. füge sie neu ein ...
    eintrag *p = find(&head, atoi(argv[i])); 
    ++(p->anz);     // ... erhöhe ihren Zählerstand um 1
    print(head);    // und gib die ganze Liste aus
  }
  
  exit(EXIT_SUCCESS);
}