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

/* Struktur des Datensatzes  */
typedef struct stud_type_ {
    int    matnum;                /* Matrikelnummer,         */
    char   vorname[20];           /* Vorname und             */
    char   nachname[20];          /* Nachname sind Eintraege.*/

    /* Die Datenbank ist eine einfach verkettete Liste.      */
    struct stud_type_ *next_student;
} stud_type;

typedef struct sortier_liste_ {
    struct stud_type_ *student;     /* Pointer auf die eigentlichen Daten */
    struct sortier_liste_ *next;        /* einfache Verkettung */
} sortier_liste;

/* Initialisierung der Datenbank */
stud_type *studenten_liste = NULL;
sortier_liste *namen_liste = NULL;

/* fügt einen Namen per Rekursion in die Sortierliste ein */
void fuege_ein (stud_type *x, sortier_liste *current)
{   printf("a");
    if (current == NULL)        /* am Ende der Liste soll immer eingefügt werden */
    {   printf("b");
        sortier_liste *tmp;
        tmp = malloc(sizeof(sortier_liste));
        tmp->next = NULL;
        tmp->student = x;
        current = tmp;

    }
    else
    {
        if (strcmp(x->nachname, current->student->nachname) >= 0)
        /* wenn x >= curr, hänge x hinter curr ein */
        {   printf("c");
            sortier_liste *tmp;
            tmp = malloc(sizeof(sortier_liste));
            tmp->next = current;
            tmp->student = x;
            current = tmp;
        }
        /* x < curr, also geh ein Element weiter */
        else fuege_ein (x, current->next);
    }
}

/* erstellt eine "sortier_liste" */
void sort_by_name(stud_type *x, sortier_liste *sliste)
{
    if (x != NULL)
    {
        stud_type *curr;
        curr = x;
        fuege_ein(curr, sliste);
        while (curr->next_student != NULL)
            {
            printf("e\n");
            fuege_ein(curr->next_student, sliste);
            curr = curr->next_student;
            }
    }
    else printf ("Fehler: übergebene Studentenliste ist leer");
}


/* gibt eine "sortier_liste" aus */
void print_by_name(sortier_liste *current)
{
    while (current != NULL)
    {
        printf("d\n");
        printf("    Matrikelnummer %4i: %s %s\n",current->student->matnum, current->student->vorname,current->student->nachname);
        current = current->next;
    }

}

int is_empty()                     /* Ist die Datenbank leer? */
{
    return (studenten_liste==NULL);
}

/* Einfuegen eines Elementes */
void enqueue(int matnum, char vorname[20], char nachname[20])
{
    stud_type *curr, *next, *neuer_student;

    neuer_student = malloc(sizeof(stud_type));  /* Speicher fuer Element    */
    strcpy(neuer_student->vorname,vorname);     /* anfordern und mit Daten */
    strcpy(neuer_student->nachname,nachname);   /* fuellen.                 */
    neuer_student->matnum = matnum;

    curr = studenten_liste;                     /* Neues Element in DB einfuegen */

    if ((curr==NULL) || (curr->matnum > neuer_student->matnum))
    {
        neuer_student->next_student = curr; /* Sonderfall: an erster Stelle  */
        studenten_liste = neuer_student;    /* einfuegen                     */
    }
    else
    {
        next = curr->next_student;          /* Durchmustern der DB           */
        while ((next!=NULL) && (next->matnum < neuer_student->matnum))
        {
            curr = next;
            next = next->next_student;
        }
        neuer_student->next_student = next; /* Neues Element nach curr und   */
        curr->next_student=neuer_student;   /* vor next einfuegen            */
    }
}

/* Loeschen eines Elementes */
int dequeue(int matnum)
{
    stud_type *curr,*next;

    if (is_empty(studenten_liste))
        return 0;                           /* Rueckgabewert: Fehler!*/

    curr=studenten_liste;
    if (curr->matnum==matnum) {             /* Sonderfall: erstes Element */
        studenten_liste=curr->next_student; /* loeschen                    */
        free(curr);                         /* Speicher freigeben */
        return 1;                           /* Rueckgabewert: OK.  */
    }
    next=curr->next_student;                /* Durchmustern der DB    */
    while ((next!=NULL)&&(next->matnum<matnum))
    {
      curr=next;
      next=next->next_student;
    }

    if ((next==NULL)||(next->matnum!=matnum))
        return 0;                           /* Rueckgabewert: Fehler!    */

    curr->next_student=next->next_student;  /* Element loeschen          */
    free(next);                             /* Speicher wieder freigeben */

    return 1;                               /* Rueckgabewert: OK.        */
}

/* Auslesen eines Elementes. */
int get_student(int matnum, char vorname[20], char nachname[20])
{
    stud_type *curr;

    curr=studenten_liste;               /* Durchmustern der DB   */
    while ((curr!=NULL)&&(curr->matnum<matnum))
        curr=curr->next_student;
    if ((curr==NULL)||(curr->matnum!=matnum))
        return 0;                      /* Rueckgabewert: Fehler! */
    else
    {
        strcpy(vorname,curr->vorname);
        strcpy(nachname,curr->nachname);
        return 1;                        /* Rueckgabewert: OK.   */
    }
}

 /* Test der Listenfunktionen. */
int main() {
    int matnum;
    char vorname[20],nachname[20];
    stud_type *curr;

    printf(">>> Fuege neuen Studenten in die Liste ein: Bill Clinton [6666] ...\n");
    enqueue(6666,"Bill","Clinton");

    printf(">>> Fuege neuen Studenten in die Liste ein: Hillary Clinton [4711] ...\n");
    enqueue(4711,"Hillary","Clinton");

    printf(">>> Fuege neuen Studenten in die Liste ein: Newt Gingrich [9999] ...\n");
    enqueue(9999,"Newt","Gingrich");

    printf(">>> Test, ob die Matrikelnummer 0815 bereits erfasst wurde ...\n");
    if (get_student(815,vorname,nachname))
        printf("    Matrikelnummer %4i: %s %s\n",815,vorname,nachname);
    else
        printf("    Matrikelnummer %4i ist unbekannt\n",815);

    printf(">>> Fuege neuen Studenten in die Liste ein: Monica Lewinsky [0815] ...\n");
    enqueue(815,"Monica","Lewinsky");

    printf(">>> Loesche die Matrikelnummer 4711 ...\n");
    if (dequeue(4711))
        printf("    Matrikelnummer %4i geloescht\n",4711);
    else
        printf("    Matrikelnummer %4i war nicht erfasst\n",4711);

    printf(">>> Test ob die Studentenliste leer ist ...\n");
    if (is_empty())
        printf("    Die Studentenliste ist leer \n");
    else
        printf("    Die Studentenliste ist nicht leer \n");

    printf(">>> Test, ob die Matrikelnummer 6666 bereits erfasst wurde ...\n");
    if (get_student(6666,vorname,nachname))
        printf("    Matrikelnummer %4i: %s %s\n",6666,vorname,nachname);
    else
        printf("    Matrikelnummer %4i ist unbekannt\n",6666);

    printf(">>> Loesche die Matrikelnummer 9998 ...\n");
    if (dequeue(9998))
        printf("    Matrikelnummer %4i geloescht\n",9998);
    else
        printf("    Matrikelnummer %4i war nicht erfasst\n",9998);

    printf(">>> Loesche die Matrikelnummer 9999 ...\n");
    if (dequeue(9999))
        printf("    Matrikelnummer %4i geloescht\n",9999);
    else
        printf("    Matrikelnummer %4i war nicht erfasst\n",9999);

    printf(">>> Gebe alle erfassten Studenten aus ...\n");
    curr = studenten_liste;

    enqueue(22223, "Gerhard", "Polt");
    enqueue(1231,"Max", "Mustermann");

    sortier_liste *lex_ordnung;
    lex_ordnung = malloc(sizeof(sortier_liste));
    lex_ordnung = NULL;
    sort_by_name(studenten_liste, lex_ordnung);



    while(curr!=NULL)
    {
        printf("    Matrikelnummer %4i: %s %s\n",
               curr->matnum, curr->vorname,curr->nachname);
        curr=curr->next_student;
    }

    print_by_name(lex_ordnung);

    return 0;
}