/***************************************************************/
/* Prof. Dr. Carsten Vogt                                      */
/* FH Koeln, Fak. 07 / Nachrichtentechnik                      */
/* http://www.nt.fh-koeln.de/vogt                              */
/*                                                             */
/* Beispielprogramm p08020200.c                                */
/* aus "C fuer Java-Programmierer", Hanser-Verlag              */
/*                                                             */
/* Demonstriert wird der Umgang mit einfach verketteten Listen.*/
/***************************************************************/

#include <stdio.h>

typedef struct listenknoten {
  int  wert;
  struct listenknoten  *next;
} listenknoten;

int einfuegen_kopf(listenknoten **kopf, listenknoten *einzufueg) {
 if ((einzufueg==NULL)||(kopf==NULL)) return -1;
 einzufueg->next = *kopf;
 *kopf = einzufueg;
 return 0;
}

int einfuegen_nach(listenknoten *nachdiesem, listenknoten *einzufueg) {
 if ((nachdiesem==NULL)||(einzufueg==NULL)) return -1;
 einzufueg->next = nachdiesem->next;
 nachdiesem->next = einzufueg;
 return 0;
}

int einfuegen_ende(listenknoten **kopf, listenknoten *einzufueg) {
 listenknoten *ende;
 if ((einzufueg==NULL)||(kopf==NULL)) return -1;
 if (*kopf==NULL) {
  einzufueg->next = NULL;
  *kopf = einzufueg; }
 else {
  ende = *kopf;
  while (ende->next!=NULL)
    ende = ende->next;
  einfuegen_nach(ende,einzufueg);
 }
 return 0;
}

listenknoten *entfernen_kopf(listenknoten **kopf) {
 listenknoten *kopf_alt;
 if ((kopf==NULL)||(*kopf==NULL)) return NULL;
 kopf_alt = *kopf;
 *kopf=(*kopf)->next;
 return kopf_alt;
}

listenknoten *entfernen_ende(listenknoten **kopf) {
 listenknoten *vor_ende, *ende;
 if ((kopf==NULL)||(*kopf==NULL)) return NULL;
 if ((*kopf)->next==NULL) {
  ende = *kopf;
  *kopf = NULL;
  return ende;
 }
 vor_ende = *kopf;
 while (vor_ende->next->next!=NULL)
  vor_ende = vor_ende->next;
 ende = vor_ende->next;
 vor_ende->next = NULL;
 return ende;
}

listenknoten *entfernen(listenknoten **kopf, listenknoten *auszufueg) {
 listenknoten *vor_auszufueg;
 if ((auszufueg==NULL)||(kopf==NULL)||(*kopf==NULL)) return NULL;
 if (auszufueg==*kopf) {
  *kopf=(*kopf)->next;
  return auszufueg;
 }
 vor_auszufueg = *kopf;
 while (vor_auszufueg->next!=auszufueg) {
  if (vor_auszufueg->next == NULL)
   return NULL;
  vor_auszufueg = vor_auszufueg->next;
 }
 vor_auszufueg->next = auszufueg->next;
 return auszufueg;
}

void durchlaufen(listenknoten *kopf) {
 listenknoten *laufzeiger;
 laufzeiger = kopf;
 printf("-------------\n");
 while (laufzeiger!=NULL) {
  printf("%d ",laufzeiger->wert);
  laufzeiger = laufzeiger->next;
 }
 printf("ENDE\n-------------\n\n");
}

listenknoten *suchen(listenknoten *kopf, int gesuchter_wert) {
 listenknoten *laufzeiger;
 laufzeiger = kopf;
 while (laufzeiger!=NULL&&laufzeiger->wert!=gesuchter_wert)
  laufzeiger = laufzeiger->next;
 return laufzeiger;
}

int main(void) {

 listenknoten *kopf = NULL;

 listenknoten *neu, *nachdiesem, *auszufuegen, *result;

 int wahl, wahl2, neuer_wert, gesuchter_wert, errcode;

 do {

  do {

   printf("\nBitte Funktion auswaehlen:\n\n");
   printf("( 1 )  Listeninhalt ausgeben\n");
   printf("( 2 )  Eintrag einfuegen\n");
   printf("( 3 )  Eintrag entfernen\n");
   printf("( 0 )  Programmende\n");

   scanf("%d",&wahl);

  } while (wahl<0 || wahl>3);

  printf("\n");

  switch(wahl) {

   case 1:

    durchlaufen(kopf);

    break;

   case 2:

    printf("Wert des neuen Eintrags: ");
    scanf("%d",&neuer_wert);

    neu = (listenknoten *) malloc(sizeof(listenknoten));
    neu->wert = neuer_wert;
    neu->next = NULL;

    printf("\nWohin einfuegen?\n\n");
    printf("( 1 )  Listenkopf\n");
    printf("( 2 )  Listenende\n");
    printf("( 3 )  nach einem bestimmten Eintrag\n");

    scanf("%d",&wahl2);

    switch(wahl2) {

     case 1: errcode = einfuegen_kopf(&kopf,neu);
             if (errcode!=0) printf("FEHLER\n");
             break;

     case 2: errcode = einfuegen_ende(&kopf,neu);
             if (errcode!=0) printf("FEHLER\n");
             break;

     case 3: printf("\nNach welchem Wert einfuegen? ");
             scanf("%d",&gesuchter_wert);
             nachdiesem = suchen(kopf,gesuchter_wert);
             if (nachdiesem!=NULL) {
                errcode = einfuegen_nach(nachdiesem,neu);
                if (errcode!=0) printf("FEHLER\n");
               }
              else
               printf("\nEintrag nicht vorhanden\n");
             break;

     }

    break;

   case 3:

    printf("\nWelchen Knoten entfernen?\n\n");
    printf("( 1 )  Listenkopf\n");
    printf("( 2 )  Listenende\n");
    printf("( 3 )  Knoten mit bestimmtem Wert\n");

    scanf("%d",&wahl2);

    switch(wahl2) {

     case 1: result = entfernen_kopf(&kopf);
             if (result!=NULL)
               printf("Entfernt: %d\n",result->wert);
              else
               printf("FEHLER\n");
             break;

     case 2: result = entfernen_ende(&kopf);
             if (result!=NULL)
               printf("Entfernt: %d\n",result->wert);
              else
               printf("FEHLER\n");
             break;

     case 3: printf("Wert des zu entfernenden Knotens: ");
             scanf("%d",&gesuchter_wert);
             auszufuegen = suchen(kopf,gesuchter_wert);
             if (auszufuegen!=NULL) {
               result = entfernen(&kopf,auszufuegen);
               if (result!=NULL)
                printf("Entfernt: %d\n",result->wert);
               else printf("FEHLER\n");
              }
              else
               printf("\nEINTRAG NICHT VORHANDEN\n");

     }

    break;
    
  }

 } while (wahl!=0);

 return 0;

}