问题描述:

As practice (I'm a student), I'm implementing a basic string to int hash table in C. I have (I think) everything working, except the print table function. It starts to work, but Windows says "hashtable.exe has stopped working" after printing out three entries of one bucket, and I know the other ones are valid because I can retrieve their values at the command prompt thing I have. Here is my code, and any advice is valued:

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

}

网友答案:

You can't use the value of a variable until you assign it one. In main, you pass the value of i to scanf, but you haven't assigned it a value yet. So you are passing scanf a garbage address which causes the program to crash when scanf tries to store something at that nonsense location.

网友答案:

Oddly enough your program compiles and runs fine as-is on my system, even the print_table() function, the lookups... all runs fine for me. That said, you should fix the error Adam pointed out: storing the input string at an address that is undefined is a serious bug regardless.

Merely declaring char *i; will result in i containing an address equal to whatever was last on the execution stack at that location. In other words, it could be anything. Because of this, the program may actually work sometimes on some computers and other times not, depending on whether i happens to contain a valid address. That might explain why your program worked as-is on my computer but not on yours.

Instead you could write:

char i[128];

...and...

scanf("%s", i);
网友答案:

Here's modified code that can explain what's wrong (from function 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);
    }
相关阅读:
Top