CODEWITHSUNDEEP
carrayspointerslinked-list
user3293434
user3293434

Reputation: 143

Symbol table implementation using hash table in C

I am trying to implement a simple symbol table that stores the strings in a hash table according to their hash values. The hash table in my program is an array of pointers to linked lists. we have 6 linked lists corresponding to each hash value.

The problem is that though the program runs, it replaces the old strings with the new string in each iteration.

my code is..

struct node{
    char *string;
    struct node *next;
};
struct node *hashtable[6];

int calchash(char *arr);
main()
    {
    char *line, a='n';
    int val, i;
            do{
            printf("Enter string:\n");
            scanf("%s", line);
            struct node *current;
            struct node *q= (struct node*)malloc(sizeof(struct node));
            q->string = line;
            q->next = NULL;
            val= calchash(line);
            if(hashtable[val] == NULL)
                    {
                    hashtable[val] = q;
                    current =q;}
            else{
                    current->next = q;
                    current = q;
                    }
            printf("Node created\n");
    for(i=0; i<6; i++)
            { printf("Hash value %d :\n", i);
            if(hashtable[i]==NULL)
                    {printf("No STRINGS!\n\n");}
            else
                    {struct node *t = hashtable[i];
                    while(t != NULL)
                            {printf("%s \n", t->string);
                            t = t->next;}
                    printf("\n\n");
                   }
            }

    printf("CONTINUE(y/n):\n");
    scanf(" %c", &a);
    }while(a!='n');
    }

int calchash(char *arr)
    {int i=0, ascii;
    int sum=0;
    while(arr[i] != '\0')
            {ascii = arr[i];
            if(ascii>=48 && ascii<=57)
                    {
                    sum+= 2*ascii;}
            else
                    {sum=sum+ ascii;}
            i++;
            }
    return ((sum*17+5)%6);
    }

And the output is: Enter string: az9

Node created

Hash value 0 : No STRINGS!

Hash value 1 : No STRINGS!

Hash value 2 : az9

Hash value 3 : No STRINGS!

Hash value 4 : No STRINGS!

Hash value 5 : No STRINGS!

CONTINUE(y/n): y

Enter string: Az9

Node created

Hash value 0 : No STRINGS!

Hash value 1 : No STRINGS!

Hash value 2 : Az9

Hash value 3 : No STRINGS!

Hash value 4 : Az9

Hash value 5 : No STRINGS!

CONTINUE(y/n): n

Can someone please tell me what changes are needed so as to retain the previous az9 string under hash value 2???

Upvotes: 0

Views: 3104

Answers (2)

pat
pat

Reputation: 12749

How does this not crash immediately? Neither line nor hashtable are initialized.

You will need to make a copy of the string to go into each hash node, probably with strdup. Currently, all of the nodes point to the same string buffer as line, so when you read a new string into line, all of the nodes will see it. This is why you must duplicate the string for each node. I wonder where the buffer ended up though, since you never initialized line...

Also, what is current? It is local to the loop, and appears unnecessary. You should just chain new nodes onto the head of the bucket, so you don't need to check if the bucket is empty.

The insert also does not check if the string is already present, so you will insert duplicates.

Upvotes: 1

Deduplicator
Deduplicator

Reputation: 45654

if(hashtable[val] == NULL) {
    hashtable[val] = q;
    current =q;
} else {
    current->next = q;
    current = q;
}

should be replaced with:

q->next = hashtable[val];
hashtable[val] = q;
// no need for current

Also, writing through any uninitialised pointer is UB, please allocate sufficient space first. Anything might happen...

Upvotes: 1

Related Questions