/***************************************************************/
/* Prof. Dr. Carsten Vogt                                      */
/* FH Koeln, Fak. 07 / Nachrichtentechnik                      */
/* http://www.nt.fh-koeln.de/vogt                              */
/*                                                             */
/* Beispielprogramme Nr. 57-60                                 */
/* der frueheren Vorlesung Datenverarbeitung                   */
/*                                                             */
/* Die Datei enthaelt eine Sammlung von Basisfunktionen        */
/* zur Arbeit mit einfach verketteten Listen:                  */
/* - Einfuegen: vorn, hinten, an eine beliebige Stelle         */
/* - Ausfuegen                                                 */
/* - Durchlaufen mit Ausgabe                                   */
/*                                                             */
/* ACHTUNG: Die Datei enthaelt kein Hauptprogramm main() und   */
/* ist daher so nicht ausfuehrfaehig.                          */
/***************************************************************/

#include <stdio.h>

/* Typdefinition fuer die Elemente einer einfach verketteten Liste */

typedef struct listelem {
  int              wert;    /* Eintrag des Elements */
  struct listelem  *next;   /* Zeiger auf naechstes Listenelement */
} listelem;

/* Variable fuer den Listenkopf = Zeiger auf das erste Listenelement */

listelem *head;

/* Funktion einfueg(): fuegt nach einem bestimmten Listenelement ein
                       neues ein. */

int einfueg(listelem *nachdiesem, listelem *einzufueg) {

 /* nachdiesem: Element, nach dem eingefuegt werden soll
    einzufueg:  einzufuegendes Element */

 /* Test, ob einer der beiden Parameter den Nullzeiger enthaelt.
    Wenn ja: Abbruch mit Rueckgabe des Fehlercodes -1 */

 if ((nachdiesem==NULL)||(einzufueg==NULL)) return -1;

 /* Einketten des neuen Elements */

 einzufueg->next = nachdiesem->next;
 nachdiesem->next = einzufueg;

 /* Rueckgabe des Codes 0 = ok */

 return 0;

}

/* Funktion neuerst(): fuegt ein neues erstes Listenelement ein. */

int neuerst(listelem **liste, listelem *einzufueg) {

 /* liste:      Liste, in die eingefuegt werden soll
    einzufueg:  einzufuegendes Element */

 /* Test, ob einer der beiden Parameter den Nullzeiger enthaelt.
    Wenn ja: Abbruch mit Rueckgabe des Fehlercodes -1 */

 if ((einzufueg==NULL)||(liste==NULL)) return -1;

 /* Einketten des neuen Elements mit Aenderung von liste */

 einzufueg->next = *liste;
 *liste = einzufueg;

 /* Rueckgabe des Codes 0 = ok */

 return 0;

}

/* Funktion neuletzt(): fuegt ein neues letztes Listenelement ein. */

int neuletzt(listelem **liste, listelem *einzufueg) {

    /* liste:      Liste, in die eingefuegt werden soll
       einzufueg:  einzufuegendes Element */

 listelem *hilfzeig;

 /* Test, ob einer der beiden Parameter den Nullzeiger enthaelt.
    Wenn ja: Abbruch mit Rueckgabe des Fehlercodes -1 */

 if ((einzufueg==NULL)||(liste==NULL)) return -1;

 if (*liste==NULL) {

  /* Falls Liste leer, Aenderung von liste */

  einzufueg->next = NULL;
  *liste = einzufueg; }

 else {

  /* Falls Liste nicht leer: Durchlaufen und Einketten hinten */

  /* Setze hilfzeig auf den Listenanfang */

  hilfzeig = *liste;
  while (hilfzeig->next!=NULL)
    /* Verschiebe hilfzeig um ein Element nach hinten,
       solange das Listenende noch nicht erreicht ist */
    hilfzeig = hilfzeig->next;

  /* hilfzeig zeigt jetzt auf das letzte Listenelement.
     Fuege einzufueg dahinter ein. */

  einfueg(hilfzeig,einzufueg);

 }

 /* Rueckgabe des Codes 0 = ok */

 return 0;

}

/* Funktion ausfueg(): fuegt ein Element aus einer Liste aus. */

int ausfueg(listelem **liste, listelem *auszufueg) {

    /* liste:      Liste, aus der ausgefuegt werden soll
       auszufueg:  auszufuegendes Element */

 listelem *hilfzeig;

 /* Test, ob einer der beiden Parameter den Nullzeiger enthaelt.
    Wenn ja: Abbruch mit Rueckgabe des Fehlercodes -1 */

 if ((auszufueg==NULL)||(liste==NULL)) return -1;

 /* Test, ob Liste leer. Wenn ja: Fehler */
 if (*liste==NULL) return -1;    /* -1 = Fehler */

 if (auszufueg==*liste) {

  /* auszufuegendes Element ist das erste:
     verschiebe Listenkopf um eins nach hinten */

  *liste=(*liste)->next;

  return 0;   /* 0 = ok */

 }

 /* Setze hilfzeig auf den Listenkopf. */

 hilfzeig = *liste;

 /* Suche des Vorgaengers des auszufuegenden Elements */

 while (hilfzeig->next!=auszufueg) {

  /*  Verschiebe hilfzeig jeweils um ein Element nach hinten,
      bis es auf den Vorgaenger von auszufueg zeigt. */

  if (hilfzeig->next == NULL)
   /* Listenende ist erreicht => auszufeug ist nicht in der Liste => Fehler */
   return -1;

  hilfzeig = hilfzeig->next;

 }

 /* Kette den Nachfolger von hilfzeig = auszufueg aus */

 hilfzeig->next = hilfzeig->next->next;

 return 0;   /* 0 = ok */

}

/* Funktion durchlauf(): durchlaeuft eine Liste von vorn nach hinten
                         und gibt dabei ihre Elemente aus. */

void durchlauf(listelem *liste) {

 /* liste: zu durchlaufende Liste */

 listelem *hilfzeig;

 hilfzeig = liste;

 while (hilfzeig!=NULL) {
  /* Schleife durch alle Listenelemente */
  printf("%d ",hilfzeig->wert);
  hilfzeig = hilfzeig->next;
 }

 printf("\n");

}