帶鏈接列表的Hashmap查找字數

Question

我一直在研究這個小項目很長一段時間，我無法弄清楚爲什麼我沒有得到預期的結果。我是C編程的初學者，所以我對指針和內存分配/釋放的理解是新手。無論如何，我已經構建了這段代碼，最初構建一個哈希函數，然後添加一個計數。但是，當我測試它時，有時計數有效，有時不計算。我不確定這是散列函數的錯誤，還是我設置計數方式的錯誤。文本文件一次只讀一行，是一個由十六進制組成的字符串。

struct node { 
    char *data; 
    struct node *next; 
    int count; /* Implement count here for word frequencies */ 
}; 

#define H_SIZE 1024 
struct node *hashtable[H_SIZE]; /* Declaration of hash table */ 

void h_lookup(void) 
{ 
    int i = 0; 
    struct node *tmp; 

    for(i = 0; i < H_SIZE; i++) { 

     for(tmp = hashtable[i]; tmp != NULL; tmp = tmp->next) { 
      if(tmp->data != 0) { 
         printf("Index: %d\nData: %s\nCount: %d\n\n", i, 
           tmp->data, tmp->count); 
      } 
     } 

    } 
} 


/* self explanatory */ 

void h_add(char *data) 
{ 
    unsigned int i = h_assign(data); 
    struct node *tmp; 
    char *strdup(const char *s); 


    /* Checks to see if data exists, consider inserting COUNT here */ 

    for(tmp = hashtable[i]; tmp != NULL; tmp = tmp->next) { 

     if(tmp->data != 0) { /* root node */ 
      int count = tmp->count; 
      if(!strcmp(data, tmp->data)) 

       count= count+1; 
      tmp->count = count; 
        return; 
     } 
    } 

    for(tmp = hashtable[i]; tmp->next != NULL; tmp = tmp->next); 

    if(tmp->next == NULL) { 
      tmp->next = h_alloc(); 
      tmp = tmp->next; 
      tmp->data = strdup(data); 
      tmp->next = NULL; 
      tmp->count = 1; 
    } else 
     exit(EXIT_FAILURE); 
} 

/* Hash function, takes value (string) and converts into an index into the array of linked lists) */ 

unsigned int h_assign(char *string) 
{ 
    unsigned int num = 0; 

    while(*string++ != '\0') 
      num += *string; 

    return num % H_SIZE; 
} 

/* h_initialize(void) initializes the array of linked lists. Allocates one node for each list by calling h_alloc which creates a new node and sets node.next to null */ 

void h_initialize(void) 
{ int i; 
    for(i = 0; i <H_SIZE; i++) { 
      hashtable[i] = h_alloc(); 
    } 

} 

/* h_alloc(void) is a method which creates a new node and sets it's pointer to null */ 

struct node *h_alloc(void) 
{ 
    struct node *tmp = calloc(1, sizeof(struct node)); 

    if (tmp != NULL){ 
     tmp->next = NULL; 
     return tmp; 
    } 

    else{ 
     exit(EXIT_FAILURE); 
    } 
} 

/* Clean up hashtable and free up memory */ 

void h_free(void) 
{ 
    struct node *tmp; 
    struct node *fwd; 
    int x; 

    for(x = 0; x < H_SIZE; x++) { 

      tmp = hashtable[x]; 
      while(tmp != NULL) { 
        fwd = tmp->next; 

       free(tmp->data); 
       free(tmp); 

       tmp = fwd; 

      } 
    } 
} 

Answer 1

我假定計數在不起作用時不會增加。有可能strdup不能爲新字符串分配內存並返回NULL。你應該檢查返回值並且如果失敗則正常退出。