Hashtable

HER ER KODEN..





#include <stdlib.h>


    struct somestruct
    {
        int key;
        char * Html;
          };
   
    #define LLHITEM struct somestruct
    #define LLHKEY(p) ((p).key)
    #define LLHSLOTS 7919 /* the 1000th prime number */

/*
*  Hash table item structure
*/
struct item
{
        LLHITEM d;
        struct item *next;
};

/*
*  The hash table itself
*/
typedef struct item *LLHTABLE[LLHSLOTS];

/*
*  Hash function
*
*  Parameters:
*
*    key        Some hash table item's key
*
*  Return values:
*
*    >= 0        The item's hash value
*
*    <= -1      Error, the hash value cannot be calculated
*/
typedef int LLHFUNC(int key);

/*
*  llhinit: Initialize the hash table
*
*  Parameters:
*
*    t          Hash table (duh!)
*/
void llhinit(LLHTABLE t)
{
    int i = LLHSLOTS;

    while (i --) {
        t[i] = NULL;
    }
}

/*
*  llhlookup: Access an item
*
*  Parameters:
*
*    t          Hash table
*
*    f          Pointer to hash function
*
*    key        Value uniquely identifying the item to be looked for
*
*  Return values:
*
*    non-NULL    The item in question was found; the return value is
*                a pointer to the corresponding record in the hash table.
*
*    NULL        The item was not found in the hash table. Either it just
*                isn't in there, or the hash function returned an error.
*/


LLHITEM * llhlookup(LLHTABLE t, LLHFUNC *f, int key)
{
    int slot;
    struct item *tmp;

    if ((slot = (*f)(key) % LLHSLOTS) < 0) {
        return NULL;
    };
    tmp = t[slot];
    while (tmp) {
        if (LLHKEY(tmp->d) == key) {
            return &tmp->d;
        }
        tmp = tmp->next;
    }
    return NULL;
}

/*
*  llhinsert: Insert an item into the hash table
*
*  Parameters:
*
*    t          Hash table
*
*    f          Pointer to hash function
*
*    d          Item to be inserted
*
*  Return values:
*
*    nonzero    The item was inserted successfully
*
*    zero        The item could not be inserted. Either the function could
*                not allocate the amount of memory necessary to store it,
*                or the hash table already contains an item with the same
*                key, or the hash function returned an error.
*
*  Note:
*
*    If you know for sure that key values are in fact unique identifiers,
*    that is, that the calling functions will never try to make the hash
*    table contain two items with the same key at the same time, you can
*    speed up the function considerably by deleting the first statement.
*/
int llhinsert(LLHTABLE t, LLHFUNC *f, LLHITEM d)
{
    int slot;
    struct item *tmp;

    /* delete this line to insert items in constant time: */
    if (llhlookup(t, f, LLHKEY(d))) return 0;

    if ((slot = (*f)(LLHKEY(d)) % LLHSLOTS) < 0
        || (tmp = malloc(sizeof(struct item))) == NULL) {
        return 0;
    }
    tmp->d = d;
    tmp->next = t[slot];
    t[slot] = tmp;
    return 1;
}

/*
*  llhremove: Remove an item from the hash table
*
*  Parameters:
*
*    t          Hash table
*
*    f          Pointer to hash function
*
*    key        Value uniquely identifying the item to be looked for
*
*  Return values:
*
*    nonzero    The item was removed successfully.
*
*    zero        The item could not be removed. Either it just wasn't
*                found in the hash table, or the hash function returned
*                an error.
*/
int llhremove(LLHTABLE t, LLHFUNC *f, int key)
{
    int slot;
    struct item **tmp, *kill;

    if ((slot = (*f)(key) % LLHSLOTS) < 0) {
        return 0;
    }
    tmp = &t[slot];
    while (*tmp) {
        if (LLHKEY((*tmp)->d) == key) {
            kill = *tmp;
            *tmp = (*tmp)->next;
            free(kill);
            return 1;
        }
        tmp = &((*tmp)->next);
    }
    return 0;
}





int main(){
   
return 0;   
}

kunne du ikke specificere dit spørgsmål lidt, så er det nemmere at svare ;-)

Jo, hvordam laver jeg selv hashfunktionen, når den type defineret som den er??

Den funktion du skal implementere skal være af typen LLHFUNC.
Defineret som :
    typedef int LLHFUNC(int key);

f.eks.

int minHashFunc( int key)
{

}

Kroppen af funktionen faldt ud :

int minHashFunc( int key)
{
  return key%11;
}

Det er selvfølgeligt vigigt at vælge selve hash funktionen så den giver så få dublerede nøgler som muligt

Ja, du  har sq ret min ven. Men hvordan ved den at det er den funktion som den skal kalde, når den ikke engang hedder det samme? Jeg mener man kan jo have mange funktioner som modtager og retunere en integer i sit program..

Når du kalder de forskellige llh funktioner skal din hashfunktion med som parameter f.eks. : );

  llhinsert( hashTabel, minHashFunc, element )
                        -----------

OKAY! Du har fortjent dine point.. Lige en ting her på falderebet. Ved du tilfældigvis hvad det vil sige at dereferencere en pointer?? Der er ingen point at hente denne gang. :-)

Dereference til en pointer vil sige at man refererer til indholdet, og ikke til selve pointeren, eksempel :

main()
  int b;
  int *a;

  b = 5;
  a = &b; // &b giver adressen på b, dvs a peger nu på b.

  printf("a = 0x%x *a = %d\n", a, *a);
}

// *a refererer til indholdet af a - dette er "dereference"

Okay TAK! Jeg troede bare at det var noget med to pointere efter hinanden, altså fx **P det har jeg nemlig set flere gange.