bitte um hilfe - hashing

Angabe:

gegeben sei eine anzahl von kundensätze, die aus einer datei eingelesen und in einem dyn array gespeichert ist. Strktur

struct info

{
int kndr
char *vonrname
char *nachname

}

diese kundensätze sollen mittles hash-speicherung effektiver verwaltet werden. Es soll dazu ein hasharray mit 211 elementen angelegt werden. Die kollisionsauflösung soll mittels verketteter listen erreich werden. die knoten haben folgende strutur

struct node
{
char *key
struct info *info;
struct node *next;
}
Der hierin enthaltene Schlüsseltwert <key>, aus dem der hashwert zu errechnen ist, soll aus den ersten vier buchstaben des namens gebildet werden. Folgender Algorithmus ist für die Ermittlung des Hashwertes zu implementeren:

unsigned Hashwert :=0
für alle Zeichen c des Schlüssels:
Hashwert := (HashWert * 64 + <ASCII-Wert von c> % M

wobei M die Anzahl der Speicherplätze darstellt.

Nach dem Einlesen der Daten aus einer Datei und dem abspeichern in einem Array wird die hashspeicherung vorgenommen. dazu werden die Datensätze iterativ in den hashspeicher übernommen.
Anschließend geht das Programm in eine Endlosschleife über, die die Eingabe eines Suchschlüssels und die darauf folgende Ausgabe aller auf den Suchschlüssel passsenden Kundensätze ermöglicht.
Die Eingabe der Zeichenfolge "QUIT als suchschlüsssel beendet die Schleife und das Programm terminiert.

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

#define M       211     // Die Anzahl der Elemente des Hasharrays
#define SKEYLEN 4       // Die Länge des Schlüssels eines Knotens

struct node
{
   char *key;
   struct info *info;
   struct node *next;
};

struct info
{
   int kdnr;
   char *vorname;
   char *nachname;
};

// Prototypen
void         hashlistinitialize();
int          readfile();
void         hashlistinsert(char *key, struct info *info);
struct info *hashlistsearchpos(char *key, struct node **last);
void         hashlistprint();
unsigned     hash(char *key);

// Globals
struct node *heads[M];    // Das Hasharray
struct node *z;           // Das gemeinsame Tail-Element aller Listen
struct info *array;       // Hilfsarray für die eingelesenen Kundensätze

int main()
{
	char t_skey[81];       // Eingabepuffer für den Suchschlüssel
   int  count;            // Die Anzahl der Datensätze
   int  i;
   char key[SKEYLEN+1];   // Puffer für den Schlüssel
   struct info *result;
   struct node *pos;
   hashlistinitialize();

   // Datei 'kunden.txt' einlesen
   count = readfile();

   // Gelesene Daten in Hashliste eintragen
   for(i = 0; i < count; i++)
   {
      // Schlüssel erzeugen
      strncpy(key, array[i].nachname, SKEYLEN);
      key[SKEYLEN] = '\0';

      // Einfügen in Hashliste
      hashlistinsert(key, &array[i]);
   }  

   // Ausgabe der Hashwerte und der zugeordneten Schlüssel
   hashlistprint();

   // Suchschleife
   for(;;)
   {
      // Eingabe des Suchschlüssels
      printf("Suchschluessel (%d Buchstaben) oder QUIT: ", SKEYLEN);
      scanf("%s", t_skey);
      if(!stricmp(t_skey, "QUIT"))  // Programmende?
         break;

      strncpy(key, t_skey, SKEYLEN);
      key[SKEYLEN] = '\0';
      key[0] = toupper(key[0]); // Absichern, dass 1. Buchstabe des
                                //Suchschlüssels ein Großbuchstabe ist

      // Headelement der verketteten Liste adressieren, die
      // den Suchschlüssel enthält.
      // TODO: Head-Element der zu <key> gehörenden Liste in <pos> speichern
      pos = ...

      // Iteration über die verkettete Liste und Ausgabe
      while(result = hashlistsearchpos(key, &pos))
      {
         printf("h: %3d ", hash(key));
         printf("Info: KdNr: %d\tName: %s, %s\n",
            result->kdnr, result->nachname, result->vorname);
      }
   }
   return 0;
}

/*
*  hash():
*  Die Hash-Funktion
*/
unsigned hash(char *key)
{
   // TODO: Hier die Hashfunktion implementieren
}

/*
*  hashlistinsert():
*  Fügt einen Knoten mit dem Schlüssel <key> und der Information <info>
*  in die Hashliste ein. Dabei wird der Index im Hasharray errechnet und
*  der Knoten an die zu diesem Index gehörige verkettete Liste angehängt.
*/
void hashlistinsert(char *key, struct info *info)
{
    unsigned h = // TODO: Code zur Erzeugung des Hashwertes einfügen

    // TODO: Code einfügen, der die beiden folgenden Teilschritte ausführt

    // 1. Neuen Knoten anlegen

    // 2. Knoten in die verkettete Liste an der Stelle heads[h] einhängen

}

/*
*  hashlistsearchpos():
*  Parameter: <skey> Suchschlüssel
*             <last> Pointer auf die Adresse des zuletzt gefundenen Nodes
*  Liefert den nächsten Node zurück, wobei dessen Schlüssel dem Suchschlüssel
*  gleichen muss
*/
struct info *hashlistsearchpos(char *skey, struct node **last)
{
   struct node *t;
   t = (*last)->next;
   strcpy(z->key, skey);         // Aktuellen Suchkey im z-Knoten ablegen
   while(strcmp(t->key, skey))
   {
      t = t->next;
   }
   *last = t;
   return t->info;
}

/*
*  hashlistinitialize(): Legt im Hasharray M leere Listen an
*/
void hashlistinitialize()
{
   int i;
   // z-Konten anlegen
   z = (struct node *)malloc(sizeof *z);
   z->next = z; z->info = NULL;
   z->key = (char *)malloc((SKEYLEN + 1)*sizeof(char));

   // TODO: Leere Listen an allen Speicherplätzen des Array heads[] anlegen
}

/*
*  hashlistprint(): Gibt das komplette Hasharray mit allen Schlüsseln aus
*/
void hashlistprint()
{
   struct node *temp;
   struct info *tempinfo;
   int i;
   for(i=0; i<M; i++) 
   {
      temp = heads[i]->next;
      printf("%d: ", i);
      while(temp != z) 
      {
         tempinfo = temp->info;
         printf("%s ", temp->key);
         temp = temp->next;
      }
      printf("\n");
      if(!((i+1) % 24))
         getch();
   }
}

/*
* Readfile(): Liest Kunden.txt in ein dynamisches Array ein
*/
int readfile()
{
   FILE *f;
   int  count = 0;
   char buffer[256];
   char nname[81];
   char vname[81];
   char *ptr;
   int  kdnr;

   f = fopen("kunden.txt", "rt");
   if(f)
   {
      for(;;)
      {

         if(!fgets(buffer, 255, f))
            break;
         count++;
         ptr = strtok(buffer, ", ");
         if(ptr)
         {
            strcpy(nname, ptr);
            ptr = strtok(NULL, " \t");
            if(ptr)
            {
               strcpy(vname, ptr);
               ptr = strtok(NULL, "\n");
               if(ptr)
                  kdnr = atoi(ptr);
            }
         }
         if(count == 1)
         {
            array = (struct info *)malloc(sizeof(struct info));
         }
         else
         {
            array = (struct info *)realloc(array, count * sizeof(struct info));
         }
         array[count - 1].kdnr     = kdnr;
         array[count - 1].nachname = strdup(nname);
         array[count - 1].vorname  = strdup(vname);
      }
   }
   fclose(f);
   return count;
}

CStoll

Wie die Hashfunktion gebildet werden soll, steht doch schon in deiner Aufgabe Das mußt du nur nach C übersetzen ("für alle Zeichen" wird zu einer for()-Schleife).

Zum Einfügen:

h = hash(key);
struct node* new_node = malloc(sizeof(struct node));
//node-Elemente füllen
//node "richtig" in heads[h] einfügen (entweder am Anfang, am Ende oder an alphabetisch richtiger Stelle

wie ist das gemeint?

//node "richtig" in heads[h] einfügen (entweder am Anfang, am Ende oder an alphabetisch richtiger Stelle

CStoll

In der Aufgabe steht nicht drin, in welcher Reihenfolge die Elemente in den verketteten Listen eingetragen werden sollen. Das kannst du entweder am Anfang (new_node->next=*heads[h];*heads[h]=new_node;), am Ende (while(pos->next!=NULL)pos=pos->next;pos->next=new_node;) oder irgendwo in der Mitte machen.

thx schon mal für deine hilfe vorher hätte da noch ne frage, wäre zuppi wenn du das auch beantworten könntest

wie siehts damit aus?

// TODO: Leere Listen an allen Speicherplätzen des Array heads[] anlegen

for(i=0;i<M;i++)
{
heads[i] = (struct node*) malloc(sizeof(struct node));
heads[i]->key = (char *)malloc((SKEYLEN + 1)*sizeof(char));
heads[i]->next=NULL;

CStoll

geht doch viel einfacher: "for(i=0;i<M;++i) heads[i]=NULL;"
(NULL steht dann für Listenende - d.h. du mußt bei deinen Suchprozeduren abbrechen, wenn pos==NULL erreicht ist)

so würde meine schleife aussehen ist diese korrekt?

unsigned hash(char *key) 
{ 
     int HashWert = 0; 
     int i; 
     for (i = 0; i < SKEYLEN; i++) 
     { 
         HashWert = (HashWert * (64 + (int)key[i]))%211; 
     } 

     return HashWert;

CStoll

*vergleicht die Funktion mit der Aufgabe* Die Klammern sind falsch gesetzt und laut Aufgabe solltest du mit unsigned rechnen. Außerdem solltest du deine Konsanten auch nutzen (wenn du später mal die Größe des Feldes ändern willst, stehst du sonst vor einem Problem).

unsigned int i, HashWert = 0; 

for (i = 0; key[i]; i++) 
    { 
    HashWert = (HashWert * 64 + key[i])%211); 
    } 

return HashWert; 
}

CStoll

Fast

unsigned int i, HashWert = 0; 

for (i = 0; /*key[i]*/i<SKEYLEN; i++) 
    { 
    HashWert = (HashWert * 64 + key[i])%/*211*/M); 
    } 

return HashWert; 
}

hehe noch ein hänger:

// TODO: Head-Element der zu <key> gehörenden Liste in <pos> speichern
pos = ??

thx für die antworten

CStoll

zu key gehört die Liste mit dem Index hash(key) - deren Kopf findest in ..dreimal darfst du raten.. heads.

(Achja, selber denken wäre auch nicht verkehrt :))

h = hash(key); 

    struct node* new_node; 

    if(!(new_node = (struct node*)malloc(sizeof(struct node)))) 
         return; 

    if(!(new_node->key = (char *)malloc((SKEYLEN + 1)*sizeof(char)))) 
        return; 

    new_node->info = info; 
    new_node->key = key; 

    new_node->next = heads[h]->next; 
    heads[h]->next = new_node;

CStoll

sizeof(char) ist per Definition 1
Und eventuell solltest du, wenn das Zuweisen von key schiefgeht, auch den reservierten Speicher wieder freigeben.