c - C 中的哈希表(查找每个单词的频率)

Question

我想为我必须在我的大学发送的练习创建一个哈希表。该程序将打开多个文件，将每个文件的内容分解为 <<words>> ( token )，它将保存每个 <<word>>在哈希表中，每个 <<word>> 的频率.

如果单词已经在哈希表中，程序将增加单词的频率。

最后，程序将打印单词及其相应的频率。此外，频率应从最高词频到最低词频打印。<<words>>的比较将忽略大小写字母。

例如，如果文件包含:one two three four Two Three Four THREE FOUR FoUr它应该打印:

four 4
three 3
two 2
one 1

教授给了我们一个我们应该完成的模板，但我真的很困惑如何处理 insert_ht()和 clear_ht()功能以及比较一个。

代码如下:

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

#define HTABLE_SIZ 1001
#define MAX_LINE_SIZ 1024

/* Hash Table */
typedef struct node* link;
struct node { char *token; int freq; link next; };

link htable[HTABLE_SIZ] = { NULL }; /* Table of lists (#buckets) */
int size = 0; /* Size (number of elements) of hash table */

unsigned int hash (char *tok );
void insert_ht (char *data);
void clear_ht ( );
void print_ht ( );

void Process(FILE *fp);


int main(int argc, char *argv[])
{
    int i;
    FILE *fp;
    for (i=1; i < argc; i++)
    {
        fp = fopen(argv[i],"r");
        if (NULL == fp)
        {
            fprintf(stderr,"Problem opening file: %s\n",argv[i]);
            continue;
        }
    Process(fp);
    fclose(fp);
    }
    print_ht();
    clear_ht();
    return 0;
}


void Process(FILE *fp)
{
    const char *seperators = " ?!'\";,.:+-*&%(){}[]<>\\\t\n";

    char line[MAX_LINE_SIZ];
    char *s;
    while((fgets(line,MAX_LINE_SIZ, fp)) != NULL)
    {
        for (s=strtok(line,seperators); s; s=strtok(NULL,seperators))
            insert_ht(s);
        }
    }

/* Hash Function */
unsigned int hash(char *tok)
{
    unsigned int hv = 0;
    while (*tok)
        hv = (hv << 4) | toupper(*tok++);
    return hv % HTABLE_SIZ;
}


void insert_ht(char *token)
{
……………………………………………
}
void clear_ht()
{
……………………………………………
}
int compare(const void *elem1, const void *elem2)
{
……………………………………………
}
void print_ht()
{
    int i, j=0;
    link l, *vector = (link*) malloc(sizeof(link)*size);
    for (i=0; i < HTABLE_SIZ; i++)
        for (l=htable[i]; l; l=l->next)
            vector[j++] = l;
        qsort(vector,size,sizeof(link),compare);
        for (i=0; i < size; i++)
            printf("%-50s\t%7d\n",vector[i]->token,vector[i]->freq);
        free(vector);
}

Answer 1

我会在新帖子中回答您，因为评论很难详尽无遗。

1。分配器

Why would I need to use malloc then ? Shouldn't i write directly to the htable? (on the insert_ht() funtion)

您需要使用ma​​lloc，因为您在struct (char *token) 中声明了一个char 指针。问题是你永远不会初始化指向任何东西的指针，而且就你不知道 token 的大小而言，你需要 malloc 每个 token 。

但是，当您使用 strdup(token) 时，您不需要 malloc token，因为 strdup 需要。所以不要忘记释放每个 token 以避免内存泄漏。

2。段错误

我无法测试您的代码，但似乎以下行会导致段错误:

list = htable[hashval]->token 

事实上，您尝试在 htable[hashval] 为 NULL 时访问 token，并将 char * 分配给 link 类型(列表)。

你需要用这个循环:

for(list = htable[hashval]; list != NULL; list = list->next) { ... }

3。备注

• if (x=1) 应该是 if(x==1)。
• 如果不需要，不要 malloc new_list。
• 因为如果在 htable[hashval] 为 NULL 时使用 new_list，new_list->next = htable[hashval]; 会将 new_list->next 设置为 NULL。
• 您应该在 gcc 中使用 -Wall 选项(用于警告)并且您可以使用 valgrind 来了解您的段错误。在这种情况下，请使用 Debug模式 (-g) 的 gcc。