4. Eintrag in hashtabelle

Eintrag in hashtabelle

  • ?

    hashing - wo ist der Fehler?
    Ich programmiere grad eine Hashtabelle,
    wobei die keys in Listen eingetragen werden sollen.
    Das Problem ist, dass ab dem 2. Eintrag ein Fehler
    auftritt, wobei alle bereits eingetragenen keys mit dem
    letzten key überschrieben werden.
    Zum Test hab ich mal feste Werte für die Eingabe genommen, (sind auskommentiert), da scheint alles zu funktionieren.
    Nur halt nicht, wenn der übergebene Wert eingetragen wird.
    Wer kann mir hier helfen?
    (P.S. Doppeleinträge hab ich noch nicht abgefangen, sind also noch erlaubt.)
    Mfg, Roland

    Quellcode:

    hash.h

/* headerdatei*/

#define BASIS 32
#define ZEILE 13  /* m, Länge der Hashtabelle, Primzahl */

typedef struct elem
{
    char *key; /* eingegebener Schlüssel */
     struct elem *next;
}elem;

typedef struct htable   /* Struktur für Hashtabelle */
{
    elem *head[ZEILE];  /* Array m lang mit Zeigern auf Listenanfang */
}htable;

/* Prototypen */
int code(char);
int h(char*,int);
void menu(void);

/* Prototypen für ADT Symboltabelle */
void init(htable *,int);
void hash_insert(htable *,int,char*);
void print_table(htable *htab,int);

htab.c

/* ADT Symboltabelle */

#include <stdio.h>
#include <stdlib.h>
#include "hash.h"

/***********  Funktion Hashtabelle initialisieren *************/
void init(htable *htab,int m)
{
    int i;
    for(i=0;i<m;i++) /* Hashtabelle ist m lang */
    {
        htab->head[i]=NULL;  /* alle Felder der Hashtabelle mit NULL-Zeigern füllen */
    }
}
/*********** Funktion Element einfügen ***********************/
void hash_insert(htable *htab,int s,char *eingabe)  /* s ist kodierte Eingabe(integer-zahl) */ 
{
    int z=0;
    elem *new_elem, *current;
    new_elem=malloc(sizeof(elem));
    if(new_elem==NULL)  printf("Fehler!!");

    current=htab->head[s];
    if(current==NULL)    /* wenn der Eimer noch leer */
    {
        htab->head[s]=new_elem;  /* Element wird jetzt in die Tabelle eingefügt */ 
        //new_elem->key="erstes"; /* test */  
    }
    else
    {
        while(current->next!=NULL)   /* letztes Element suchen */
        {
            current=current->next;
            z++;
        }
        current->next=new_elem;
        //new_elem->key="weiteres"; /* test */  
    }
        new_elem->next=NULL; /* Zeiger auf nächstes Element */
        new_elem->key=eingabe;/* das eingegebene Wort speichern */ /* evtl. auskommentieren */ 

        printf("Z ist: %d\n",z);
}
/************ Funktion Hash-tabelle anzeigen *****************/
void print_table(htable *htab,int m)
{
    int s;
    elem *current;
    printf("\nbin in print_table, groesse von htab: %d\n",m);
    for(s=0;s<m;s++)
    {
        printf("Eimer %d: ",s);
        current=htab->head[s];
        if(current==NULL)  printf("%s -",current);
        while(current!=NULL)  
        {
            printf(" %s -",current->key);
            current=current->next;
        }
        printf("\n");
    }
}                                       

client.c

/* Adresse für Schlüssel durch hashing ermitteln */
#include <stdio.h>
#include <stdlib.h>
#include "hash.h"

int main()
{
    int m=ZEILE,r,w;
    char eingabe[100];
    htable htab;

    init(&htab,m);  /* Hashtabelle init. */
    printf("initialisiere Hashtabelle...\n");

    menu();
    while(w!=5)
    {
        scanf("%d",&w);

        switch(w)
        {
            case 1: {
                        printf("Bitte geben Sie eine Zeichenkette als Schluessel ein:\n");
                        scanf("%s",&eingabe);
                        printf("\n");
                        r=h(eingabe,m);  /* Wort kodieren */
                        printf("Die Adresse fuer Ihren Schluessel lautet: %d\n",r);
                        hash_insert(&htab,r,eingabe);  /* Wort in die Hashtabelle eintragen */
                        break;
                    }
            case 2: {
                        break;
                    }
            case 3: {
                        print_table(&htab,m);   /* Ausgabe */
                        break;
                    }

            case 5: {
                        printf("Ende\n");
                        exit (0);
                    }
            default: break;
        }/* switch */
    printf("druecken Sie Enter fuer weiter...");
    fflush(stdin);
    getchar();
    menu();

    }/* while */
}/* main */

/****************** Funktion erstelle Menü ***********************/
void menu()
{
    int i;
    for(i=1;i<=2;i++) printf("\n");
    printf("Folgende Funktionen koennen Sie ausfuehren:\n\n");
    printf("\t1 Wort kodieren und einfuegen\n\t2 Wort in Hashtabelle suchen\n");
    printf("\t3 gesamte Hashtabelle ausgeben\n\t5 Ende\n");
    for(i=1;i<=6;i++) printf("\n");
    printf("ihre Wahl:");
    //for(i=1;i<=4;i++) printf("\n");
}

/******************* Funktion code **********************/ /* ermittelt die Stelle im Alphabet */
int code(char z)
{
    int i;
    char abc[26];
    for(i=0;i<=25;i++)
    {
        abc[i]=97+i;
        if(z==abc[i]) return i+1;
    }
    printf("sie haben andere Zeichen als kleine Buchstaben eingegeben");
    return(1);
}

/******************* Funktion hash ***********************/ /* kodiert das eingegebene Wort */
int h(char *v,int m)
{
    int r=0,a=BASIS,temp;
    for(;*v!=0;v++)
    {
        temp=r; /* r für Ausgabe am BS sichern */
        r=(a*r+ code(*v))%m;
        printf("(%d * %d + %d)(mod %d)=%d\n",temp,a, code(*v),m,r);
    }
    return r;
}
/****************************************************************/
    0
  • Q

    Sorry aber ich kapier dein proggie nicht 😕
    Aber ich glaub dass liegt daran, dass ich net mal weiss was ne hashtabelle is 🙄

    0
  • K

    Dein Fehler: Die vorletzte Zeile aus hash_insert()
    new_elem->key = eingabe; /* das eingegebene Wort speichern /
    speichert keineswegs den eingegebenen String, sondern nur dessen Anfangsadresse, und die ist stets die gleiche, nämlich
    char eingabe[100] aus main(), s. die Zeile
    hash_insert(&htab, r, eingabe); /     Wort in die Hashtabelle eintragen */
    aus der case 1 - Verzweigung in main().

    Darum besser so:
    new_elem->key = strdup(eingabe);
    Mußt aber drauf achten, daß auch beim Löschen der Hash-Tabelle später wieder
    free(elem->key)
    aufgerufen wird!

    0
  • ?

    Hi!
    Einfach gesagt, ist ne Hashtabelle eine Tabelle(Array mit bestimmter Länge), in der z.B. Strings, die mit irgendeinem Algorithmus kodiert wurden, eingefügt werden. Damit die Tabelle nicht unendlich lang wird, verwendet man als Einträge verkettete Listen, in die dann jeweils die Strings, die nach dem Kodieren den selben Wert haben, nacheinander eingetragen werden.
    Ich hoffe, Du kannst mir folgen, aber so mal schnell erklären ist schwierig. 😉

    Ich hab das Problem heut Nacht noch gelöst, es war ein Zeigerproblem.
    Um den eingegebenen String in ein Element einzutragen hab ich den Zeiger auf den String, also char *eingabe, an die Funktion hash_insert übergeben.
    Nun zeigten alle bereits eingetragenen Elemente auf den aktuellen übergebenen Wert und hatten demzufolge den gleichen Inhalt.
    Jetzt hab ich den String vor dem Einfügen in das Element nochmal einer neuen Variable zugeordnet, und plötzlich gehts.
    Was mich allerdings verwundert, bei einer ganz normalen verketteten Liste übergibt man doch auch den Zeiger auf einen Wert, egal ob nun *char, *void etc, wenn ein neues Element eingetragen wird.
    Und da geht es doch auch ohne Probleme! 😮 😕
    Mein Code sieht jetzt so aus:

    void hash_insert(htable *htab,int s,char eingabe[]) /* s ist kodierte Eingabe(integer-zahl) */ 
{
    char *string; /* neuer Zeiger, der dann den übergebenen String bekommt */ 
    elem *new_elem=NULL,*current=NULL;
    string=malloc(strlen(eingabe));
    sprintf(string,"%s",eingabe);
    printf("string ist %s\n",string);
    new_elem=malloc(sizeof(elem));
    if(new_elem==NULL)  printf("Fehler!!");
    new_elem->next=NULL; /* letztes Element zeigt immer auf NULL */
    new_elem->key=string; /* wenn hier eingabe steht, funzt es nicht */  /* das eingegebene Wort speichern */
    printf("key ist jetzt: %s\n",new_elem->key);
    current=htab->head[s]; 
    if(current==NULL)  htab->head[s]=new_elem;    /* wenn der Eimer noch leer */
    else 
    {
        while(current->next!=NULL)  current=current->next;    /* letztes Element suchen */
        current->next=new_elem;
    }
}

    Wer hat noch eine Idee?
    Mfg, Roland

    0
  • ?

    Hallo Krösus!
    Meine Antwort hat sich mit Deinem Beitrag grad überschnitten.
    Danke erstmal für Deinen Tipp! 🙂 Werde es so mal ausprobieren!!
    Du kannst mir ja nochmal erklären, warum es denn bei einer verketteten Liste genau so funktioniert und hier nicht. 🙄
    Mfg, Roland

    0
  • K

    WENN der Speicher des Strings nicht überschrieben wird (wie es der Fall war bei den festdefinierten Test-Strings und - nehme ich an - ebenso bei Deinen verketteten Listen), DANN ist Dein alter Code in Ordnung.
    ABER in der main()-Funktion hattest Du die eingegenen Strings alle in der selben Variablen char eingabe[100] abgespeichert (also ständig überschrieben), darum war dann auch die Ausgabe falsch. Deine neue Lösung mit malloc() und strcpy() [was genau dasselbe ist wie das von mir vorgeschlagene strdup()] kopiert den String dann an einer anderen Stelle im Speicher, die sich Deine Struktur dann merkt.
    MfG, Krösus

    0
  • W

    Hallo Krösus!
    Ich glaub ich habs jetzt einigermaßen verstanden, warum dass so ist.
    Bei der verketten Liste hab ich nämlich feste Int-Werte übergeben und keinen Zeiger. Bei Strings sieht die Sache ja nun anders aus, da es keinen Datentyp für eine Zeichenkette gibt und man den Zeiger darauf übergeben muss.
    Dann muss man halt den String an einer anderen Adresse sichern.
    Nochmal vielen Dank für die leicht verständliche Erklärung,
    Mfg, Roland 🙂

    0
Anmelden zum Antworten