/***********************************************************/
/* Die Kombination der verketteten Liste mit einem         */
/* gepointerten Array zur Beschleunigung der Zugriffszeit. */
/*---------------------------------------------------------*/
/* by Dirk Owerfeldt '89                                   */
/***********************************************************/

/*----------*/
/* Includes */
/*----------*/

#include <exec/types.h>
#include <stdio.h>

#define REG register
#define BOOLEAN BOOL
#define CHAR char

#define CLS   fputchar ( 0xc )
#define TASTE printf("-- Return --"); gets( name )

/*--------------------------------*/
/* Funktionsprototypen für ANSI-C */
/*--------------------------------*/

extern VOID eingabe ( VOID );
extern VOID zeige ( VOID );
extern VOID suche ( VOID );

/*-------------------*/
/* Die Datenstruktur */
/*-------------------*/

typedef struct DATENBLATT
{
     BYTE name[40];
     WORD alter;

     struct DATENBLATT *link;

}DATENBLATT;

DATENBLATT *Liste;

/*------------------------------------------------*/
/* Die Hilfsliste zur Beschleunigung der Zugriffe */
/*------------------------------------------------*/

#define BUCHSTABEN ('z'-'a')

DATENBLATT *arr[BUCHSTABEN];

#define INDEX(a) ('Z'-toupper(a))   /* Macht aus Buchstaben den Index */
                                    /* für das Hilfsarray             */

char name[40];     /* global, da in vielen Funktionen benutzt */


/*-------------------------------------------------*/
/* Einfügen eines neuen Datenblattes (name,alter)  */
/* hinter dem Listenelement, aus das p zeigt       */
/*-------------------------------------------------*/
/* Neu für kombinierte Systeme: Die Funktion gibt  */
/* einen Zeiger auf den eingefügten Eintrag zurück */
/*-------------------------------------------------*/

DATENBLATT *insert(p,name,alter)
DATENBLATT *p;
CHAR *name;
WORD alter;
{
   DATENBLATT *hp;

   hp = (DATENBLATT *) malloc(sizeof (DATENBLATT));

   hp->alter = alter;
   strcpy(hp->name,name);

   if(p!=NULL)
   {
      hp->link = p->link;
      p->link  = hp;
   }
   else
   {
      hp->link = Liste;
      Liste    = hp;
   }

   return(hp);   /* hp ist zwar lokal, aber es wird ja der Wert des    */
}                /* Zeigers zurückgegeben, und nicht der Zeiger selbst */


/*----------------------------------------*/
/* Durchsucht Liste nach einem Namen      */
/* Liefert Pointer auf gefundenes Element */
/* oder NULL, wenn name nicht auffindbar  */
/*----------------------------------------*/

DATENBLATT *find(name)
CHAR *name;
{
   DATENBLATT *hp;

   /*----------------------*/
   /* Anfangszeiger setzen */
   /*----------------------*/ 

   if((INDEX(name[0])<0)||(INDEX(name[0])>=BUCHSTABEN))
       hp=Liste;
   else
       hp=arr[INDEX(name[0])];

   while(hp!=NULL) 
   {
      if(!strcmp(name,hp->name))
         return(hp);

      hp = hp->link;
   }
   
   return(NULL);
}

/*--------------------------------------*/
/* Einfügen eines neuen Elementes unter */
/* Berücksichtigung der alphabetischen  */
/* Ordnung und setzten der Hilfsliste   */
/*--------------------------------------*/

VOID fast_insert(name,nummer)
CHAR *name;
WORD nummer;
{
   register DATENBLATT *hp,*np;
   CHAR                anf_buchst;

   np=NULL;

   /*----------------------*/
   /* Anfangszeiger setzen */
   /*----------------------*/ 

   anf_buchst = INDEX(name[0]);

   if((anf_buchst<0)||(anf_buchst>=BUCHSTABEN))
        hp=Liste;
   else
   {
      if(arr[anf_buchst]==NULL)
           hp=Liste;
      else
           hp=arr[anf_buchst];
   }

   while(hp!=NULL)
   {
      if(strcmp(name,hp->name)<0)
         break;

      np=hp;
      hp=hp->link;
   }

   /* Wenn erster Charakter kein Buchstabe (A-Z) ist, darf kein */
   /* Eintrag in die Hilfsliste erfolgen                        */

   if((anf_buchst<0)||(anf_buchst>=BUCHSTABEN))
   {
        insert(np,name,nummer); 
        return;
   } 


   /*-----------------------------*/
   /* Jetzt kommen die drei Fälle */
   /*-----------------------------*/


   if(arr[anf_buchst]==NULL)
   {
        arr[anf_buchst]=insert(np,name,nummer);   /* Fall 1 */
   }        
   else
      if(np!=NULL)
      {
         insert(np,name,nummer);                  /* Fall 2 */
      }
      else
      {
         np = NULL;                               /* Fall 3 */
         hp = Liste;

         while(hp!=NULL)
         {
            if(strcmp(name,hp->name)<0)
               break;

            np=hp;
            hp=hp->link;
         }
         
         arr[anf_buchst]=insert(np,name,nummer);
      }
}



/*********************/
/* DAS HAUPTPROGRAMM */
/*********************/

VOID main( VOID )
{
   BOOLEAN  schleife=TRUE;
   REG WORD i;
   CHAR     c[80];

   /*----------------------*/
   /* Liste initialisieren */
   /*----------------------*/

   Liste = NULL;

   /*--------------------------*/
   /* Hilfsarray intialisieren */
   /*--------------------------*/

   for(i=0;i<BUCHSTABEN;i++)
        arr[i]=NULL;

   /*-----------*/
   /* Hauptmenü */
   /*-----------*/

   while(schleife)
    {
      CLS;

      printf("** Verkettete Listen Teil II **\n");
      printf("**     by Dirk Owerfeldt     **\n\n");

      printf("Menü:\n\n");
      printf("1) Kartei erweitern\n");
      printf("2) Name suchen\n");
      printf("3) Kartei listen\n");
      printf("9) Ende\n\n");

      printf("Ihre Wahl: ");
      gets(c); 

      printf("\n\n");

      CLS;
      switch( c[0] ) 
      {
        case '1': eingabe();
                  break;

        case '2': suche();
                  break;

        case '3': zeige();
                  break;

        case '9': schleife=FALSE;
                  break;
      }
   }
}

/*---------------------------------------------*/
/* Neue Elemente einlesen, bis name='ende' ist */
/*---------------------------------------------*/

VOID eingabe()
{
   CHAR s_alter[40];

   CLS;

   printf("** Neue Elemente eintragen **\n\n");
   printf("(Beenden durch name='ende')");

   while(TRUE)
   {
        printf("\nName : "); gets(name);
        if(!strcmp(name,"ende")) break;   
    
        printf("Alter: "); gets(s_alter);
        fast_insert(name,atoi(s_alter));
   }
}

/*----------------------------------------------*/
/* Ausgabe aller Namen in der verketteten Liste */
/*----------------------------------------------*/

VOID zeige()
{
   struct DATENBLATT *hp;

   printf("\nAlle Namen der Liste:\n\n");

   hp=Liste;              
   while(hp!=NULL)                   /* bis Liste zuende ist */
   {
      printf( "%s\n", hp->name);     /* Ausgabe des Namens   */
      
      hp = hp->link;                 /* hp zeigt jetzt auf   */    
   }                                 /* nächstes Elemant     */
                                     /* (oder enthält NULL)  */                           

   printf("\n\n-- RETURN --"); gets(name);
}

/*-----------------------------*/
/* Suche Namen bis name='ende' */
/*-----------------------------*/

VOID suche()
{
   DATENBLATT *p;

   printf("** Elemente suchen **\n\n");
   printf("(Beenden durch suchname='ende')");  

   while(TRUE)
   {
        printf("\nSuchen nach : "); gets(name);
        if(!strcmp(name,"ende")) break;   

        if((p=find(name))!=NULL)
           printf("Name gefunden! Das Alter ist: %d\n",p->alter);
        else
           printf("Name nicht in der Liste vorhanden!\n");         
   }
}