CODEWITHSUNDEEP
cliststructhashtable
Giuseppe Fiorella
Giuseppe Fiorella

Reputation: 23

Hash table problems with values getting overwritten

I am testing for the very first time hash tables and I get such a weird error.

Here is my code:

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

#define MAX 40

typedef struct snode {
    char *nome;
    struct snode *next;
} TNode;

typedef TNode *TList;

typedef struct tht {
    TList *buckets;
    int nbuckets;
} THT;

TList Create_List();
TNode *Create_Node(char *);
TList Insert_List(TList, char *);
THT *Create_THT(int n);
void HT_Print(THT *ht);
THT *Insert_THT(THT *ht, char *name, int key);
int hash(char *name);
void Print_List(TList list);

int main() {
    THT *ht = Create_THT(5);
    char name[MAX];
    int key, contr;
    printf("INSERISCI 0 PER USCIRE O INSERIRE NOME \n");
    do {
        printf("\n INSERIRE NOME : ");
        scanf("%s", &name);  //AFTER THE SECOND INSERTION FROM THIS LANE VALUES CHANGE INSIDE ht?? why 
        key = hash(name);
        ht = Insert_THT(ht, name, key);
        printf("\n Inserisci 1 per continuare 0 per terminare ");
        scanf("%d", &contr);

    } while (contr != 0);
    HT_Print(ht);
    return 0;
}

TList Create_List() {
    return NULL;
}

TNode *Create_Node(char nome[MAX]) {
    TNode *node;
    node = malloc(sizeof(TNode));
    node->nome = nome;
    node->next = NULL;
    return node;
}

TList Insert_List(TList list, char info[MAX]) {
    TNode *tmp;
    TNode *node;
    node = Create_Node(info);
    tmp = list;
    if (list == NULL) {
        list = node;
    } else {
        while (tmp->next != NULL) {
            tmp = tmp->next;
        }
        tmp->next = node;
    }
    return list;
}

THT *Create_THT(int n) {
    int i;
    THT *ht = malloc(sizeof(THT));

    ht->buckets = malloc(n * sizeof(TList));
    for (i = 0; i < n; i++) {
        ht->buckets[i] = Create_List();
    }
    ht->nbuckets = n;
    return ht;
}

void HT_Print(THT *ht) {
    int i;
    for (i = 0; i < ht->nbuckets; i++) {
        Print_List(ht->buckets[i]);
    }
}

int hash(char *name) {
    return (name[0] - 'a');
}

THT *Insert_THT(THT *ht, char name[MAX], int key) {
    ht->buckets[key] = Insert_List(ht->buckets[key], name);
    return ht;
}

void Print_List(TList list) {
    while (list != NULL) {
        printf("%s", list->nome);
        list = list->next;
    }
}

I tested it with the debug. It's ok at the first insertion (for example I insert adam) but then something weird happens. The second time when I give as input the name like bob for example (since it's like a vocabulary of names) and I check the value of ht->buckets something changes inside.

I dont understand I didn't even get into the functions that modify effectively what's inside my hash table (ht) and inside it changes . I am getting crazy and I tried to find a solution but I really dont understand how from a command in a main that doesn't have to deal with my HT's struct values change inside that struct...

Upvotes: 1

Views: 206

Answers (2)

Olaf Dietsche
Olaf Dietsche

Reputation: 74108

Unrelated, but using English names and outputs makes it easier for everybody.

Just a guess, but inside Create_Node, you allocate memory for the new node but don't allocate memory for the name (nome).

You just copy the pointer to the passed array, which changes every time you insert a new name. Allocating memory for the name and copying the contents instead of the pointer should resolve this issue, e.g.

node->nome = strdup(nome);

Don't forget, that when you use the hash in a larger context, you must cleanup the hash and names eventually, which means freeing the memory for the nodes and names

free(node->nome);
free(node);

Create_Node receives a pointer to the array name in main. This array is reused every time a new name is input. This means, all nodes point to the same array, and so all nodes print the same (last input) name.

Allocating individual memory for each node and copying the array to this memory (strdup), solves the problem.

Upvotes: 2

chqrlie
chqrlie

Reputation: 145317

There are many problems in your code:

  • You hide pointers behind typedefs in typedef TNode *TList; This is error prone and confusing for readers of your code.
  • CreateNode does not make a copy of the memory pointed to by name. Given how you use this function, all nodes share the same array, so all nodes have the same name. Use node->nome = strdup(nome); to solve this problem.
  • scanf("%s", &name); is incorrect: the & is superfluous and you should specify the maximum number of characters to store to name to avoid buffer overflows. Use scanf("%39s", name);. Furthermore, you should test the return value to detect unexpected end of file.
  • Print_List does not separate the names. Use printf("%s\n", list->nome) to output them on separate lines.
  • You should free the hash table at the end of the program:
void Free_THT(THT *ht) {
    if (ht) {
        int i;
        for (i = 0; i < ht->nbuckets; i++) {
            TNode *list = ht->buckets[i];
            ht->buckets[i] = NULL;
            while (list != NULL) {
                TNode *node = list;
                list = list->next;
                free(node->name);
                free(node);
            }
        }
        free(ht->buckets);
        free(ht);
    }
}

Upvotes: 1

Related Questions