Ха sh таблицы проблем с перезаписью значений

Question

Я тестирую в первый раз ха sh таблицы и получаю такую ​​странную ошибку.

Вот мой код:

#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;
    }
}

Я протестировал его с помощью отладки , Это нормально при первой вставке (например, я вставляю adam), но затем происходит нечто странное. Во второй раз, когда я даю в качестве входных данных имя, например, bob (так как это словарь словаря), и я проверяю значение ht->buckets, внутри что-то меняется.

Я не понимаю, я даже не попал в функции, которые эффективно изменяют то, что находится внутри моей таблицы ha sh (ht) и внутри нее меняется. Я схожу с ума, и я пытался найти решение, но я действительно не понимаю, как из команды в main, которая не должна иметь дело с изменением значений структуры моего HT внутри этой структуры ...

Answer 1

Не имеет отношения, но использование имен и выходов Engli sh упрощает задачу для всех.

---

Просто предположение, но внутри Create_Node вы выделяете память для нового узла, но не выделить память для имени (nome).

Вы просто копируете указатель на переданный массив, который изменяется каждый раз, когда вы вставляете новое имя. Выделение памяти для имени и копирование содержимого вместо указателя должно решить эту проблему, например:

node->nome = strdup(nome);

Не забывайте, что когда вы используете ha sh в более широком контексте, вы должны очистить ha sh и имена со временем, что означает освобождение памяти для узлов и имен

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

---

Create_Node получает указатель на массив name в main. Этот массив используется повторно каждый раз, когда вводится новое имя. Это означает, что все узлы указывают на один и тот же массив, и поэтому все узлы печатают одно и то же (последнее входное) имя.

Выделение отдельной памяти для каждого узла и копирование массива в эту память (strdup ), решает проблему.

Answer 2

В вашем коде много проблем:

• Вы скрываете указатели за typedefs в typedef TNode *TList; Это может привести к ошибкам и сбить с толку читателей вашего кода.
• CreateNode не делает копию памяти, на которую указывает name. Учитывая, как вы используете эту функцию, все узлы совместно используют один и тот же массив, поэтому все узлы имеют одинаковое имя. Для решения этой проблемы используйте node->nome = strdup(nome);.
• scanf("%s", &name); неверно: & является лишним, и вы должны указать максимальное количество символов для хранения в name, чтобы избежать переполнения буфера. Используйте scanf("%39s", name);. Кроме того, вы должны проверить возвращаемое значение, чтобы обнаружить неожиданный конец файла.
• Print_List не разделяет имена. Используйте printf("%s\n", list->nome) для вывода их в отдельных строках.
• Вы должны освободить таблицу ha sh в конце программы:

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);
    }
}