Хеш-таблица на C (найдите частоту каждого слова)

Я отвечу вам в новом посте, потому что в комментариях сложно быть исчерпывающим.

1. Маллок

Тогда зачем мне использовать malloc? Разве мне не следует писать прямо в htable? (в функции insert_ht ())

Вам нужно использовать malloc, потому что вы объявляете указатель на char в struct (char *token). Дело в том, что вы никогда не инициализируете указатель ни на что, и, поскольку вы не знаете размер токена, вам нужно выполнить malloc каждый токен.

Но, поскольку вы используете strdup(token), вам не нужно сбрасывать токен, потому что это делает strdup. Так что не забудьте освободить каждый токен, чтобы избежать утечки памяти.

2. Segfault

Я не могу проверить ваш код, но похоже, что следующая строка вызывает ошибку сегментации:

list = htable[hashval]->token 

Действительно, вы пытаетесь получить доступ к токену, когда htable[hashval] имеет значение NULL, и присвоить символ * типу ссылки (списку).

Вам нужно выполнить цикл с этим:

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

3. Примечания

• if (x=1) должно быть if(x==1).
• Не выполняйте malloc new_list, если вам это не нужно.
• Поскольку new_list, если он используется, когда htable [hashval] равен NULL, new_list->next = htable[hashval]; установит new_list-> рядом с NULL.
• Вам следует использовать параметр -Wall в gcc (для предупреждений), и вы можете использовать valgrind, чтобы понять свои ошибки сегментации. В этом случае используйте gcc с режимом отладки (-g).

Двойное и окончательное редактирование: Ι нашел решение. Видимо по какой-то причине моя compare функция была неправильной. Я до сих пор не понял, почему, но вот правильный, надеюсь, кто-то еще сочтет этот пост полезным!

int compare(const void *elem1, const void *elem2)
{
    
     return (*(link*)elem2)->freq - (*(link*)elem1)->freq;
}

Изменить: удален старый ответ. Я думаю, нашел правильный путь, но сейчас у меня другая проблема. Функция compare работает некорректно. Мой printf в порядке, но он не сортирует их по частотам. Я хочу, чтобы они были отсортированы от высшего к низшему.

В этом примере: файл содержит -> один, два, три, четыре, два, три, четыре, три, четыре, четыре, и я получаю: два 2 один 1 четыре 4 три 3

Пока у меня должно получиться: четыре 4 три 3 два 2 один 1

Вот код. Не стесняйтесь помочь!

#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;
    printf("prin tin for \n");
    for (i=1; i < argc; i++)
    {
        printf("prin tin fopen \n");
        fp = fopen(argv[i],"r");
        if (NULL == fp)
        {
            fprintf(stderr,"Problem opening file: %s\n",argv[i]);
            continue;
        }
        printf("prin tin process \n");
    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)){
            printf("prin tin insert %s \n",s);
            insert_ht(s);
        }
            
        }
    }
    
/* Hash Function */
unsigned int hash(char *tok)
{
    printf("bike stin hash \n");
    unsigned int hv = 0;
    while (*tok)
        hv = (hv << 4) | toupper(*tok++);
    printf("VGAINEIIIIIIIIIIIIII %d \n",hv);
    return hv % HTABLE_SIZ;
}



void insert_ht(char *token)
{
    printf("bike stin insert %s \n",token);
    unsigned int hashval = hash(token);

    if (htable[hashval]==NULL){
        printf("mesa stin prwti if %u %s \n",hashval,token);
        //token = strdup(token);
        htable[hashval] = malloc(sizeof(token));
        htable[hashval]->token = token ;
        htable[hashval]->freq = 1;
        size++;
        
    }else {
        htable[hashval]->freq++;
    }
    printf("ta evale epitixws \n");
    
}



int compare(const void *elem1, const void *elem2)
{
    const struct node *p1 = elem1;    
    const struct node *p2 = elem2;
    
    if ( p1->freq < p2->freq)
      return -1;

   else if (p1->freq > p2->freq)
      return 1;

   else
      return 0;
}
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);
} 

Извините за мой плохой английский.

Я так думаю :

1. insert(char *token) берет слово из файла и помещает его в хеш-таблицу. Короче говоря, если слово существует в хеш-таблице, вам просто нужно увеличить его частоту. В противном случае вам нужно создать еще один узел и установить частоту равной 1, а затем добавить его в массив. В конце у вас будет одна запись для каждого уникального слова.

2. compare(const void *elem1, const void *elem2) будет использоваться qsort. Он возвращает 0, если elem1 = elem2, отрицательное число, если elem1 ‹elem2, и число> 0, если elem1> elem2. Передав сравнение в qsort, вы разрешите qsort сортировать массив в соответствии с вашими критериями.

3. clear_ht() может установить все значения массива в NULL, чтобы перезапустить другой счетчик?