#include <stdio.h>
#include <stdlib.h>
#define MAX_HASH 10
#define M 31

struct plz{
            char ort[255];
            unsigned int plz;
            struct plz *next;
          };

struct plz *hash_tabelle[MAX_HASH];


struct plz *insert(char *o, unsigned int p)
{
 struct plz *pointer;
 /*Hashwert (bucket) an hash_adresse (0-9)*/
 int hash_adresse = hash_funktion(o);

 /*printf("%d\n",hash_adresse);*/

 /*Zeiger auf errechnete Tabellenadresse durch hash_funktion*/
 pointer = hash_tabelle[hash_adresse];
 /*Wir suchen freien Platz für einen neuen Eintrag in hash_tabelle[hash_adresse]*/
 while(pointer != NULL)
  {
    if(strcmp(o, pointer->ort) == 0)  /*Stadt gleich?*/
     if(pointer->plz == p)    /*Postleitzahlen auf gleich?*/
      {
        printf("%s mit PLZ %d ist bereits vorhanden\n",o,p);
        return pointer; /*Doppelte Einträge vermeiden*/
      }
    pointer=pointer->next;
  }

 /*Speicher für neues Element allokieren*/
 pointer = (struct plz *)malloc(sizeof(struct plz));
 if(pointer == NULL)
  {
    fprintf(stderr, "Konnte keinen Speicher für neue PLZ reservieren\n");
    return NULL;
  }
 strcpy(pointer->ort, o);
 pointer->plz = p;
 pointer->next = hash_tabelle[hash_adresse];
 hash_tabelle[hash_adresse] = pointer;

 return pointer;
}

/*Funktion zur Suche in Hash-Tabelle*/
struct plz *search_in_hash(char *o)
{
  struct plz *pointer;
 /*Hashwert (bucket) an hash_adresse (0-9)*/
 int hash_adresse = hash_funktion(o);

 /*printf("%d\n",hash_adresse);*/

 /*Zeiger auf errechnete Tabellenadresse durch hash_funktion*/
 pointer = hash_tabelle[hash_adresse];

 /*Jetzt wollen wir schauen ob es für o einen Eintrag in der Tabelle gibt*/
 while(pointer != NULL)
  {
   if(strcmp(pointer->ort, o) == 0)
     printf("PLZ für %s ist %d\n",o,pointer->plz);
   pointer = pointer->next;
  }
}



/*Die Hash-Funktion zur Berechnung des Hashwertes eines Strings*/
int hash_funktion(char *string)
{
 unsigned int hash_adresse;
 unsigned char *pointer;

 hash_adresse=0;
 pointer = (unsigned char *)string;

 while(*pointer != '\0')
  {
    hash_adresse = M * hash_adresse + *pointer;
    pointer++;
  }
 return hash_adresse % MAX_HASH;
}



int main()
{
  insert("Friedberg", 86316);
  insert("Augsburg", 86136);
  insert("Stuttgart", 71345);

  search_in_hash("Augsburg");
  search_in_hash("Friedberg");
  search_in_hash("Stuttgart");

  return 0;
}