哈希表打印「停止工作」

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()函數，查找...都對我來說運行良好。也就是說，你應該修復Adam指出的錯誤：無論如何，將輸入字符串存儲在未定義的地址都是嚴重的錯誤。

僅僅聲明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); 
} 

修復：

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