#ifndef __LINLIST#define __LINLIST#include <stdio.h>////////////////////////////////////////////////////////////////////////// LinList  (SLink)////////////////////////////////////////////////////////////////////////template <class DATA> struct SLink {    DATA *d;                    // Zeiger auf Element-Daten    SLink<DATA> *next;          // Zeiger auf naechstes Element    SLink<DATA> *prev;          // Zeiger auf vorhergehendes Element    SLink();    ~SLink();};template <class DATA> SLink<DATA>::SLink(){    d = NULL;    next = prev = NULL;}template <class DATA> SLink<DATA>::~SLink(){    delete d;}////////////////////////////////////////////////////////////////////////// LinList////////////////////////////////////////////////////////////////////////template <class DATA> class LinList{protected:    SLink<DATA> *first;         // Rootzeiger des Datenbestands    SLink<DATA> *last;          // Zeiger auf letztes Element    int anz;                    // Anzahl der belegten Elemente in der Liste    SLink<DATA> *akt;           // zeigt auf aktuelles Element    int akt_index;              // Index des zuletzt mit get geholten Elementspublic:    LinList();    virtual ~LinList();    int get_num()               // gibt Anzahl der im Index belegten Elements        { return anz; }         // zurueck        void check();               // ueberprueft Konsistenz der Liste    void insert(DATA *f);       // haengt ein Element vorne an die Liste an    bool erase();               // loescht aktuelles Element aus der Liste    DATA * get(int i);          // liefert i-tes Element    DATA * get_first();         // liefert erstes Element im Index    DATA * get_last();          // liefert erstes Element im Index    DATA * get_next();          // liefert naechstes Element im Index    DATA * get_prev();          // liefert vorhergehendes Element im Index};template <class DATA> LinList<DATA>::LinList(){    anz = 0;    akt_index = -1;    akt = first = last = NULL;}template <class DATA> LinList<DATA>::~LinList(){    SLink<DATA> *hf;    // Elemente freigeben    akt = first;    while (akt != NULL)    {	hf = akt->next;	delete akt;	akt = hf;    }}template <class DATA> void LinList<DATA>::insert(DATA *f){    SLink<DATA> *sd;    // neuen Rahmen erzeugen    sd = new SLink<DATA>;    sd->d = f;    // Zeiger umbiegen    sd->next = first;    sd->prev = NULL;    if (first != NULL)	first->prev = sd;    // first, last und anz berichtigen    anz++;    first = sd;    if (last == NULL)	last = sd;    // Position ist undefiniert    akt = NULL;    akt_index = -1;}template <class DATA> bool LinList<DATA>::erase(){    SLink<DATA> *n_akt;    // Liste leer oder akt nicht definiert?    if (akt)    {	// Element ist erstes Element	if (akt == first)	{	    // Element ist einziges Element	    if (akt == last)	    {		akt_index = -1;		first = last = NULL;		n_akt = NULL;	    }	    else	    {		// Element ist erstes Element, aber nicht leztes		(akt->next)->prev = NULL;		first = akt->next;		n_akt = first;		akt_index = 0;	    }	}	else	{	    // Element ist letztes Element	    if (akt == last)	    {		(akt->prev)->next = NULL;		last = akt->prev;		n_akt = NULL;		akt_index = -1;	    }	    else	    // Element ist mitten in der Liste	    {		(akt->next)->prev = akt->prev;		(akt->prev)->next = akt->next;		n_akt = akt->next;		akt_index++;	    }	}	// Speicher freigeben	delete akt;	// aktuelles Element setzen	akt = n_akt;	// anz berichtigen	anz--;	return TRUE;    }    return FALSE;}template <class DATA> DATA* LinList<DATA>::get(int i)// liefert das i-te Element in der Liste{    bool ahead;   // wenn ahead TRUE ist, wird in next-Richtung gesucht    int j;    // liegt das i-te Element ueberhaupt in der Liste?    if (i >= anz)	return NULL;    // ist die Liste schon auf das i-te Element positioniert?    if (i == akt_index)	return akt->d;    // hat eine Positionierung der Liste stattgefunden?    if (akt_index == -1)    {	// i liegt naeher an first, als an last	if (i < (anz / 2))	{	    akt = first;	    akt_index = 0;	    ahead = TRUE;	}	else	{	    akt = last;	    akt_index = anz - 1;	    ahead = FALSE;	}    }    else    {	// die gewuenschte Position liegt vor der aktuellen	if (i < akt_index)	{	    // liegt i naeher an first, als an akt_index?	    if ((akt_index - i) > i)	    {		akt = first;		akt_index = 0;		ahead = TRUE;	    }	    else		ahead = FALSE;	}	else	{	    // liegt i naeher an last, als an akt_index?	    if ((i - akt_index) > ((anz-1) - i))	    {		akt = last;		akt_index = anz - 1;		ahead = FALSE;	    }	    else		ahead = TRUE;	}    }    // gesuchter Index liegt in next - Richtung      if (ahead)    {	for (j = akt_index; j < i; j++)	{	    if (!akt)		error("LinList::get: List seems to be inkonsistent", TRUE);	    akt = akt->next;	}    }    else    {	for (j = akt_index; j > i; j--)	{	    if (!akt)		error("LinList::get: List seems to be inkonsistent", TRUE);	    akt = akt->prev;	}    }    akt_index = i;    return akt->d;}template <class DATA> DATA* LinList<DATA>::get_first(){    akt = first;    if (akt != NULL)    {	akt_index = 0;	return akt->d;    }    else	return NULL;}template <class DATA> DATA* LinList<DATA>::get_last(){    akt = last;    if (akt != NULL)    {	akt_index = anz - 1;	return akt->d;    }    else	return NULL;}template <class DATA> DATA* LinList<DATA>::get_next(){    akt = akt->next;    if (akt != NULL)    {	akt_index++;	return akt->d;    }    else    {	akt_index = -1;	return NULL;    }}template <class DATA> DATA* LinList<DATA>::get_prev(){    akt = akt->prev;    if (akt != NULL)    {	akt_index--;	return akt->d;    }    else    {	akt_index = -1;	return NULL;    }}template <class DATA> void LinList<DATA>::check(){    SLink<DATA> *f, *old_f;    int myanz;    char buffer[255];    old_f = first;    // Liste muss ganz leer sein    if (old_f == NULL)    {	if (last != NULL)	    error("LinList::check: first == NULL, last != NULL", FALSE);	if (anz != 0)	    error("LinList::check: first == NULL, anz != 0", FALSE);	return;    }    myanz = 1;    if (old_f->prev != NULL)    {	error("LinList::check: Listenkopf.prev ungleich NULL", FALSE);	return;    }    for (f = old_f->next; f != NULL; f = f->next)    {	if (f->prev != old_f)	{	    error("LinList::check: Rueckwaertsverkettung fehlerhaft", FALSE);            return;        }	if (old_f->next != f)	{	    error("LinList::check: Vorwaertsverkettung fehlerhaft", FALSE);            return;        }	old_f = f;	myanz ++;	if (myanz > anz)	{	    sprintf(buffer, "LinList::check: anz (%d != %d) passt nicht", myanz, anz);	    error(buffer, FALSE);	    return;	}    }    if (old_f->next != NULL)    {	error("LinList::check: Listenende.next ungleich NULL", FALSE);	return;    }    if (last != old_f)    {	error("LinList::check: last ungleich Listenende", FALSE);	return;    }    if (myanz != anz)    {	sprintf(buffer, "LinList::check: anz (%d != %d) passt nicht", myanz, anz);	error(buffer, FALSE);    }}////////////////////////////////////////////////////////////////////////// SortedLinList////////////////////////////////////////////////////////////////////////template <class DATA> class SortedLinList : public LinList<DATA>{    bool increasing;public:    SortedLinList();    void set_sorting(bool _increasing); // wenn increasing gleich TRUE, wird                                 // aufsteigend einsortiert                                // DIESE FUNKTION MUSS VOR DEM ERSTEN EINFUEGEN                                 // GERUFEN WERDEN !!!!!!!!!!!    void insert(DATA *f);       // fuegt ein Element durch direktes Einfuegen ein    void sort(bool _increasing);// sortiert die Liste