bitte um hilfe - hashing

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.