/*
   Doppelt verkettete Listen

   Ein kleines Beispiel für dynamische Datenstrukturen in C++,
   aber ohne objektorientierte Programmierung

   Verbrochen von Jens Gelhar am 13.01.92
*/


#include <stream.h>
#include <string.h>


// * * * Datentypen * * *

struct Eintrag          // ein einzelner "Telefonbuch"-Eintrag
{
  Eintrag *next, *prev;         // Vorgänger und Nachfolger

  char name[30];                // Name und...
  char nummer[20];              // Telefonnummer
};


struct Liste            // sortierte Liste von Einträgen
{
  Eintrag *anfang, *ende;       // erstes bzw. letztes Listenelement
};


// * * * Funktionen * * *

void Init(Liste &L)
 // Initialisiert eine Listenstruktur, indem sie ihre beiden
 // Pointer auf 0 setzt:
 { L.anfang = 0;
   L.ende   = 0;
 }


void Ausgabe (const Liste &L)
 // Telefonbuch ausgeben
 {
   for(Eintrag *E = L.anfang; E; E = E->next)
       cout << E->name << ": " << E->nummer << "\n";
 }


Eintrag *Einfueg(Liste &L, const char Name[], const char Nummer[])
 // fügt einen neuen Eintrag in die Liste ein
 {
  // neues Element erzeugen:
  Eintrag *neu = new Eintrag;

  if (!neu) return 0;           // kein Speicher frei!

  // neues Element initialisieren:
  strcpy(neu->name, Name);
  strcpy(neu->nummer, Nummer);

  // Richtige Position zun Einfügen suchen:
  Eintrag *pos = L.anfang;

  while (pos!=0 && strcmp(pos->name, Name) < 0)
    pos = pos->next;

  // Element in Liste einhängen, dabei diverse Sonderfälle beachten:

  if (pos == 0)
  // Sonderfall: Anfügen an das Ende der Liste
  {
    Eintrag *alt = L.ende;    // altes Listenende

    if (alt != 0)
    // allgemeiner Unter-Fall: wirklich anhängen
    {
      alt->next = neu;
      neu->prev = alt;
      neu->next = 0;
      L.ende = neu;
    }
    else
    // spezieller Spezialfall: Liste ist noch leer
    { neu->next = 0;
      neu->prev = 0;
      L.anfang = neu;
      L.ende = neu;
    }
  }
  else
  if (pos->prev == 0)
  // Sonderfall: Neues Element an Listenanfang hängen
  {
    pos->prev = neu;
    neu->next = pos;
    neu->prev = 0;
    L.anfang = neu;
  }
  else
  // allgemeiner Fall: Element in Liste einhängen
  {
    Eintrag *vor = pos->prev;
    // "neu" zwischen "vor" und "pos" einhängen:
    vor->next = neu;
    neu->prev = vor;
    neu->next = pos;
    pos->prev = neu;
  }

  // Fertig, Zeiger auf neues Element zurückgeben:
  return neu;

 }

void AllesLoeschen(Liste &L)
 // löscht sämtliche Listenelemente
 {
  Eintrag *p = L.anfang;

  while(p)
    { Eintrag *hilf = p;
      p=p->next;
      delete hilf;
    }
  Init(L);
 }

void Loeschen(Liste &L, Eintrag *E)
 // Löscht das Element, auf das "E" zeigt, aus Liste "L"
 {
  // Vorgänger unf Nachfolger des zu löschenden Elements
  Eintrag *vor = E->prev, *nach = E->next;

  if (vor)
  // Element hat Vorgänger: Dann dessen Nachfolger umsetzen
    vor->next = nach;
  else
  // kein Vorgänger: Dann Listenanfang aktualisieren
    L.anfang = nach;

  if (nach)
  // Element hat Nachfolger: Dann dessen Vorgänger verändern
    nach->prev = vor;
  else
  // kein Nachfolger, also Listenende anpassen
    L.ende = vor;

  delete(E);
 }


Eintrag *Suche(const Liste &L, char *Name)
 // Sucht einen Eintrag mit diesem Namen und gibt Zeiger auf das
 // zugehörige Listenelement zurück, oder 0 bei Fehler
 {
  for( Eintrag *p = L.anfang;
       p && strcmp(p->name, Name);
       p = p->next );
  return p;
 }


// * * *  Hauptprogram  * * *

void main()
{
  // Eine Liste wird deklariert und initialisiert:

  Liste l;
  Init(l);

  // Ein paar Beispieldaten werden eingefügt:

  Einfueg(l, "Harley-Davidson", "001-414/342-4680");
  Einfueg(l, "Boris Becker", "0815/4711");
  Einfueg(l, "James Bond", "007/26731");
  Einfueg(l, "Maxon", "06196/481813");
  Einfueg(l, "Zaphod Beeblebrox", "00042/08154242");
  Einfueg(l, "Luxemburg", "00352");
  Einfueg(l, "Queensr\0377che", "795069");
  Einfueg(l, "Fishbone", "4676152");

  // Einen Datensatz suchen und ggf. löschen:

  Eintrag *e = Suche(l,"Maxon");
  if (e)
    Loeschen(l, e);
  else
    cout << "Name nicht gefunden!\n";

  // restliche Liste ausgeben:
  Ausgabe(l);

  // ...und wieder aufräumen:
  AllesLoeschen(l);

}