c - 如何遍历C中的哈希表

Question

编辑:我添加了所有文件(.c、.h 和 Makefile)。该程序可以运行，但有很多内存泄漏。

http://dl.dropbox.com/u/21926200/Ngrams.tar.gz

如何遍历哈希表以调用 free()？我想知道是否需要创建一个单独的函数来在 htable 和结果上调用 free() 或者我可以在这段代码中完成它。有任何想法吗？我只需要在 htable 和结果上调用 free() 。

h_ptr *htable;
int tsize;

void new_table(int size)
{
    tsize = size;
    htable = (h_ptr *) calloc(size, sizeof(h_ptr));
    if (!htable) {
    fprintf(stderr, "Couldn't allocate hash array, exiting\n");
    exit(1);
    }

    // At the beginning, each element in the hash table
    // is a NULL pointer
    for(int i=0; i<size; i++)
      {
    htable[i]=NULL;
      }
}

// Allocate new element to store in hash table
h_ptr new_element(char *s)
{
    h_ptr result = (h_ptr) malloc(sizeof(h_rec));
    int wlen = strlen(s);
    if (wlen > llen) {
    lstring = s;
    llen = wlen;
    lcnt = 1;
    } else if (wlen == llen)
    lcnt++;
    if (!result) {
    fprintf(stderr, "Couldn't allocate hash element, exiting\n");
    exit(1);
    }

    result->word = s;
    result->freq = 1;
    result->next = NULL; 
    return result;
}

谢谢

Answer 1

在提供“整个程序”之前

鉴于 new_element() 中的信息功能:

result->word = s;
result->freq = 1;
result->next = NULL; 

我们必须推断(因为您没有包含实际信息)您的哈希表是一个数组，其中元素是单独分配的元素的链表，其中包含分配的名称、频率和指向下一项的指针。因此，释放哈希表涉及依次访问数组的每个元素，追查链表，释放名称和元素。

void free_hashtable(void)
{
    if (htable != 0)
    {
        for (int i = 0; i < tsize; i++)
        {
            h_ptr next = 0;
            for (h_ptr curr = htable[i]; curr != 0; curr = next)
            {
                next = curr->next;
                free(curr->word);
                free(curr);
            }
        }
        free(htable);
        htable = 0;
        tsize = 0;
    }
}

提供“整个程序”后

我们仍然没有数据结构，所以我们仍然不能真正说出发生了什么。因此，我们可以将其添加到代码的顶部:

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

typedef struct hash_table_entry
{
    int freq;
    struct hash_table_entry *next;
    char *word;
} *h_ptr;

但是，当我们添加它时出现的一个问题是:

 h_ptr result = (h_ptr) malloc(sizeof(h_rec));

编译器说:

error: 'h_rec' undeclared (first use in this function)

识别那条线。现在，您可能有一些 typedef，例如:

typedef struct hash_table_entry h_rec;

但我们不必猜测。请创建一个 SSCCE ( Short, Self-Contained, Correct Example )，这样我们就不必猜测了。

我使用以下代码编译代码:

gcc -O3 -g -std=c99 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes -Wold-style-definition ht.c -o ht 

编译器警告我:

ht.c:27:6: warning: no previous prototype for ‘lowercase’ [-Wmissing-prototypes]
ht.c:41:6: warning: no previous prototype for ‘new_table’ [-Wmissing-prototypes]
ht.c:59:7: warning: no previous prototype for ‘new_element’ [-Wmissing-prototypes]
ht.c:82:10: warning: no previous prototype for ‘hash_function’ [-Wmissing-prototypes]
ht.c:103:7: warning: no previous prototype for ‘save_string’ [-Wmissing-prototypes]
ht.c:116:7: warning: no previous prototype for ‘find_element’ [-Wmissing-prototypes]
ht.c:142:7: warning: no previous prototype for ‘sort_words’ [-Wmissing-prototypes]
ht.c:176:6: warning: no previous prototype for ‘insert_string’ [-Wmissing-prototypes]
ht.c:191:6: warning: no previous prototype for ‘init_token’ [-Wmissing-prototypes]
ht.c:201:7: warning: no previous prototype for ‘get_word’ [-Wmissing-prototypes]
ht.c:224:7: warning: no previous prototype for ‘get_token’ [-Wmissing-prototypes]
ht.c:276:6: warning: no previous prototype for ‘word_freq’ [-Wmissing-prototypes]
ht.c: In function ‘main’:
ht.c:322:5: warning: implicit declaration of function ‘add_string_option’ [-Wimplicit-function-declaration]
ht.c:323:5: warning: implicit declaration of function ‘add_int_option’ [-Wimplicit-function-declaration]
ht.c:328:5: warning: implicit declaration of function ‘parse_options’ [-Wimplicit-function-declaration]
ht.c:329:5: warning: implicit declaration of function ‘show_options’ [-Wimplicit-function-declaration]

对于最后四个名称，链接器无法找到它们。我们需要不使用不可用代码的代码。将您的代码简化为 SSCCE(注意自包含!)。

我已经删除了对这些函数的调用，并相应地简化了 main。当在它自己的源 ( ./ht < ht.c ) 上运行时，它会产生:

N-gram size 1
Running analysis... (This can take several minutes or more!)
 Initializing hash table...
 Inserting all n-grams into hash table in lowercase form...
 Sorting all hash table elements according to frequency...

Analysis Details:
(Top 10 list of n-grams)
82  '='
30  'int'
27  '0'
23  'if'
23  'char'
22  's'
16  '1'
16  'i'
14  'ls'
14  'h_ptr'

Analysis Summary:
817 total n-grams
211 unique n-grams
94 singleton n-grams (occur only once)
Most common n-gram (with 82 occurrences) is '='
Longest n-gram (1 have length 16) is 'hash_table_entry'
Total time = 0.002225 seconds

看起来不错...但在 valgrind 下运行优化的构建另一个故事出现了......但我已经得出结论，问题出在 strlen() 的优化实现中在我使用的特定版本的 GCC 中(部分原因是，在相同的代码上使用不同版本的 GCC 会使错误消失，并且因为错误是在调用 strlen() 时没有业务阅读在 5 个字节的分配中从偏移量 4 开始的 4 个字节)。

我添加了一个功能 print_hashtable() .我认为对于几乎任何非平凡的结构，像这样提供“打印”或“转储”功能都是值得的。

static void print_hashtable(FILE *fp, const char *tag)
{
    fprintf(fp, "Print hash table: %s\n", tag);
    fprintf(fp, "Size = %d; Address: %p\n", tsize, htable);
    if (htable != 0)
    {
        for (int i = 0; i < tsize; i++)
        {
            printf("Entry %d (%p)\n", i, htable[i]);
            h_ptr next = 0;
            for (h_ptr curr = htable[i]; curr != 0; curr = next)
            {
                next = curr->next;
                printf("Word: %s (freq %d; next %p)\n", curr->word, curr->freq, next);
            }
        }
    }
}

我在 sort_words() 之前插入了一个电话.这表明尽管哈希算法不是非常有效，但数据结构是完整的。

我还插入了对 print_hashtable() 的调用后 sort_words() ，这表明哈希表被排序过程全面破坏。排序阶段将哈希表消除为哈希表；唯一要做的就是释放整个表( free(htable) )。必须在函数 word_freq() 的底部释放所有表条目。 :

static void free_hashlist(h_ptr head)
{
    while (head != 0)
    {
        h_ptr next = head->next;
        printf("Free: %d (%s) %p -> %p\n", head->freq, head->word, (void *)head, (void *)next);
        free(head->word);
        free(head);
        head = next;
    }
}

static void word_freq(FILE *src, int details, int size)
{
    char *s;
    h_ptr list_head, ptr;

    printf(" Initializing hash table...\n");
    init_token(src);
    new_table(size);

    printf(" Inserting all n-grams into hash table in lowercase form...\n");
    while ((s = get_word()))
        insert_string(s);

    print_hashtable(stdout, "After reading data");

    printf(" Sorting all hash table elements according to frequency...\n");
    list_head = sort_words();

    if (details > 0)
    {
        printf("\nAnalysis Details:\n(Top %i list of n-grams)\n", details);
        ptr = list_head;
        while (ptr && details--)
        {
            printf("%d\t'%s'\n", ptr->freq, ptr->word);
            ptr = ptr->next;
        }
    }

    printf("\nAnalysis Summary:\n");
    printf("%d total n-grams\n", wcnt);
    printf("%d unique n-grams\n", ucnt);
    printf("%d singleton n-grams (occur only once)\n", scnt);
    printf("Most common n-gram (with %d occurrences) is '%s'\nLongest n-gram (%d have length %d) is '%s'\n",
            mcnt, mstring, lcnt, llen, lstring);

    free_hashlist(list_head);
}

并且 free_hashtable() 代码必须简化:

static void free_hashtable(void)
{
    if (htable != 0)
    {
        free(htable);
        htable = 0;
        lcnt = 0;
        lstring = 0;
        mcnt = 0;
        mstring = 0;
        scnt = 0;
        tsize = 0;
        wcnt = 0;
        ucnt = 0;
    }
}

int main(void)
{
    printf("\nRunning analysis... (This can take several minutes or more!)\n");
    word_freq(stdin, 10, 1024);
    printf("Total time = %f seconds\n", (double) clock() / CLOCKS_PER_SEC);
    free_hashtable();
    return 0;
}

在这个程序中，将指针和计数重置为空/零并不重要。另外， lstring和 mstring free_hashlist() 使指针失效，所以可以说那些应该在该函数中被清零/归零。

这对我来说是无泄漏的，并且最后只有系统分配的内存仍在使用。