Hash Table Print «Остановка работы»

Question

Как практика (я студент), я реализую базовую таблицу string до int хеш-таблицы в C. У меня (я думаю) все работает, кроме print table function. Он начинает работать, но Windows говорит «hashtable.exe перестает работать» после распечатки трех записей одного ведра, и я знаю, что другие являются действительными, потому что я могу получить их значения в командной строке, что у меня есть. Вот мой код, и любые советы оцениваются:

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

const char ESC_STRING[] = "zzzz"; 

struct a_container { 
    char *string; 
    int value; 
    struct a_container *next; 
}; 

typedef struct a_container Container; 

struct c_list { 
    Container **arr; 
    int size; 
    int bits; 
}; 

typedef struct c_list Table; 

void print_entry(Container *c) { 
    printf("%s%s%d", c -> string, ", ", c -> value); 
} 

void print_table(Table *t) { 
    Container *e; 
    int i; 
    int length = t -> size; 
    printf("%d\n", length); 
    for(i = 0; i < length; i++) { 
     printf("%d\n", i); 
     if(t -> arr[i] == NULL) printf("%s\n", "Null bucket."); 
     for(e = t -> arr[i]; e != NULL && e -> string != NULL; e = e -> next) { 
      print_entry(e); 
     } 
    } 
} 

Container *make_cont() { 
    Container *new; 
    new = malloc(sizeof(Container)); 
    if(new == NULL) return NULL; 

    new -> next = NULL; 

    return new; 
} 

Container *make_entry(char *key, int value) { 
    Container *n = make_cont(); 

    n -> string = key; 
    n -> value = value; 

    return n; 
} 

Table *make_table(int size) { 
    Table *tab = NULL; 
    int i; 
    int j = 2 << (size - 1); 

    if(size < 1) return NULL; 

    tab = malloc(sizeof(Table)); 
    tab -> arr = malloc(sizeof(Container) * j); 

    for(i = 0; i < size; i++) { 
     tab -> arr[i] = NULL; 
    } 

    tab -> size = j; 
    tab -> bits = size; 

    return tab; 
} 

void associate(Table *hashtable, char *key, int value) { 
    int index = hash_index(hashtable, key, hashtable -> bits); 
    Container *e = NULL; 
    Container *n = NULL; 

    if(hashtable -> arr[index] == NULL) { 
     e = make_entry(key, value); 
     hashtable -> arr[index] = e; 
     return; 
    } 

    else { 
     e = hashtable -> arr[index]; 
     n = make_entry(key, value); 
     hashtable -> arr[index] = n; 
     n -> next = e; 
    } 
} 

int retrieve(Table *hashtable, char *look) { 
    int index = hash_index(hashtable, look, hashtable -> bits); 
    Container *e = NULL; 

    //if(hashtable -> arr[index] == NULL) exit(1); 

    e = hashtable -> arr[index]; 
    while(e != NULL && e -> string != NULL && strcmp(look, e -> string) > 0) { 
     e = e -> next; 
    } 

    if(e == NULL || e -> string == NULL || strcmp(look, e -> string) != 0) { 
     exit(1); 
    } else { 
     return e -> value; 
    } 
} 

//djb2 algorithm by dan bernstein 
//http://www.cse.yorku.ca/~oz/hash.html 
unsigned long hash_code(char *key) { 
    unsigned long hash = 5381; 
    int c; 

    while(c = *key++) { 
     hash = ((hash << 5) + hash) + c; 
    } 

    return hash; 
} 

int hash_index(Table *hashtable, char *query, int bits) { 
    unsigned long hashCode = hash_code(query); 
    unsigned int fold = 0; 
    unsigned int h; 
    int trim = 2 << (bits - 1); 
    int mask = trim - 1; 

    for(h = hashCode; h != 0; h >>= bits) { 
     fold ^= h; 
    } 

    fold &= mask; 
    return fold; 
} 

int main() { 
    char *i; 
    Table *hashtable = make_table(3); 

    associate(hashtable, "Erica", 323); 
    associate(hashtable, "Kitty", 18); 
    associate(hashtable, "Dawg", 3); 
    associate(hashtable, "Dahhhhhhg", 43); 
    associate(hashtable, "Kat", 7); 

    //print_table(hashtable); 

    while(1) { 
     printf("%s", "Look something up: "); 
     scanf("%s", i); 
     if(strcmp(i, ESC_STRING) == 0) break; 
     printf("%d\n", retrieve(hashtable, i)); 
    } 

    return 0; 
} 

Answer 1

Вы не можете использовать значение переменной, пока не присвоите ее одному. В main вы передаете значение i в scanf, но вы еще не присвоили ему значение. Таким образом, вы передаете scanf адрес мусора, который вызывает сбой программы, когда scanf пытается сохранить что-то в этом глупоном месте.

Answer 2

Как ни странно, ваша программа компилируется и работает нормально как есть в моей системе, даже функция print_table(), поиск ... все работает отлично для меня. Тем не менее, вы должны исправить ошибку, которую указал Адам: сохранение входной строки по адресу, который не определен, является серьезной ошибкой.

Просто объявление char *i; приведет к тому, что i содержит адрес, равный тому, что было последним в стеке выполнения в этом месте. Другими словами, это может быть что угодно. Из-за этого программа может фактически работать иногда на некоторых компьютерах, а иногда и не в зависимости от того, содержит ли i действительный адрес. Это может объяснить, почему ваша программа работает как на моем компьютере, но не на вашем.

Вместо этого вы могли бы написать:

char i[128]; 

... и ...

scanf("%s", i); 

Answer 3

Вот модифицированный код, который может объяснить, что это не так (от функции print_table):

if (t->arr[i] == NULL) printf("%s\n", "Null bucket."); 
// what happens when t->arr[i] == NULL ? 
// e->string is a NULL pointer deference. 
for (e = t->arr[i]; e != NULL && e->string != NULL; e = e->next) { 
    print_entry(e); 
} 

Fix:

if (t->arr[i] == NULL) 
    printf("%s\n", "Null bucket.");  
else 
    for (e = t->arr[i]; e != NULL && e->string != NULL; e = e->next) { 
     print_entry(e); 
    }