在提供“整个程序”之前
给定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(简短、独立、正确的示例),这样我们就不必猜测了。
我使用以下代码编译代码:
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()
没有业务的调用中,从偏移量 4 开始读取 4 个字节,分配 5 个字节)。
我添加了一个功能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()
after的调用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
andmstring
指针被 无效free_hashlist()
,因此可以说那些应该在该函数中清零/归零。
这对我来说是无泄漏的,最后只有系统分配的内存仍在使用中。