Основная проблема, с которой вы сталкиваетесь, это попытка отсортировать хеш-таблицу с помощью цепочки связанных списков. Когда происходит коллизия хешей, размер вашей таблицы не изменяется, вы просто используете связанный список для хранения слова, вызывающего коллизию в том же table[index], связанном со словом, уже сохраненным там. Вот что делает add.
Это может легко привести к тому, что содержимое вашей хеш-таблицы будет выглядеть так:
table[ 0] = NULL
table[ 1] = foo
table[ 2] = NULL
table[ 3] = |some|->|words|->|that|->|collided| /* chained bucket */
table[ 4] = other
table[ 5] = words
table[ 6] = NULL
table[ 7] = NULL
...
Вы не можете просто qsort таблица и надеяться получить правильные частоты слов. qsort не может знать, что "some" - это только начальное слово в связанном списке, все, что qsort получает, это указатель на "some" и sizeof(word).
Чтобы сделать жизнь намного проще, просто забудьте хеш-таблицу и используйте динамически распределенный массив word**. Вы можете использовать аналогичное добавление, где вы увеличиваете количество вхождений для дубликатов, и вы избегаете всех проблем с цепочками. (и если вы предоставляете автоматическое хранение для каждого слова, оно оставляет вам простые free() ваших указателей, и все готово)
Следующий пример принимает 2 аргумента. Первое имя файла, из которого нужно прочитать слова, и (необязательно) второе целочисленное значение, ограничивающее отсортированный вывод тем самым верхним числом слов. Структура words_t использует автоматическое хранение для word, ограниченное 32 символами (самое большое слово в словаре без ограничений - 28 символов). Вы можете изменить способ слов или читать, чтобы проанализировать ввод и игнорировать знаки препинания и множественное число по желанию. Нижеследующее разграничивает слова во всех пунктуациях (кроме дефиса) и отбрасывает множественное число слов (например, оно хранит "Mike" при обнаружении "Mike's", отбрасывая "'s")
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>
#define MAXC 32 /* max word length is 28-char, 29-char is sufficient */
#define MAXW 128 /* initial maximum number of words to allocate */
typedef struct {
char word[MAXC]; /* struct holding individual words */
size_t ninst; /* and the number of times they occur */
} words_t;
/* function prototypes */
void *addword (words_t *words, const char *word, size_t *wc, size_t *maxw);
void *xrealloc (void *ptr, size_t psz, size_t *nelem);
/* qsort compare function for words_t (alphabetical) */
int cmpwrds (const void *a, const void *b)
{
return strcmp (((words_t *)a)->word, ((words_t *)b)->word);
}
/* qsort compare function for words_t (by occurrence - descending)
* and alphabetical (ascending) if occurrences are equal)
*/
int cmpinst (const void *a, const void *b)
{
int ndiff = (((words_t *)a)->ninst < ((words_t *)b)->ninst) -
(((words_t *)a)->ninst > ((words_t *)b)->ninst);
if (ndiff)
return ndiff;
return strcmp (((words_t *)a)->word, ((words_t *)b)->word);
}
int main (int argc, char **argv) {
int c = 0, nc = 0, prev = ' ', total = 0;
size_t maxw = MAXW, wc = 0, top = 0;
char buf[MAXC] = "";
words_t *words = NULL;
FILE *fp = fopen (argv[1], "r");
if (!fp) { /* validate file open for reading */
fprintf (stderr, "error: file open failed '%s'.\n", argv[1]);
return 1;
}
if (argc > 2) { /* if 2 args, convert argv[2] to number of top words */
char *p = argv[2];
size_t tmp = strtoul (argv[2], &p, 0);
if (p != argv[2] && !errno)
top = tmp;
}
/* allocate/validate initial words */
if (!(words = calloc (maxw, sizeof *words))) {
perror ("calloc-words");
return 1;
}
while ((c = fgetc(fp)) != EOF) { /* read each character in file */
if (c != '-' && (isspace (c) || ispunct (c))) { /* word-end found */
if (!isspace (prev) && !ispunct (prev) && /* multiple ws/punct */
!(prev == 's' && nc == 1)) { /* exclude "'s" */
buf[nc] = 0; /* nul-terminate */
words = addword (words, buf, &wc, &maxw); /* add word */
nc = 0; /* reset char count */
}
}
else if (nc < MAXC - 1) { /* add char to buf */
buf[nc++] = c;
}
else { /* chars exceed MAXC - 1; storage capability of struct */
fprintf (stderr, "error: characters exceed %d.\n", MAXC);
return 1;
}
prev = c; /* save previous char */
}
if (!isspace (prev) && !ispunct (prev)) /* handle non-POSIX end */
words = addword (words, buf, &wc, &maxw);
if (fp != stdin) fclose (fp); /* close file if not stdin */
qsort (words, wc, sizeof *words, cmpinst); /* sort words by frequency */
printf ("'%s' contained '%zu' words.\n\n", /* output total No. words */
fp == stdin ? "stdin" : argv[1], wc);
/* output top words (or all words in descending order if top not given) */
for (size_t i = 0; i < (top != 0 ? top : wc); i++) {
printf (" %-28s %5zu\n", words[i].word, words[i].ninst);
total += words[i].ninst;
}
printf ("%33s------\n%34s%5d\n", " ", "Total: ", total);
free (words);
return 0;
}
/** add word to words, updating pointer to word-count 'wc' and
* the maximum words allocated 'maxw' as needed. returns pointer
* to words (which must be assigned back in the caller).
*/
void *addword (words_t *words, const char *word, size_t *wc, size_t *maxw)
{
size_t i;
for (i = 0; i < *wc; i++)
if (strcmp (words[i].word, word) == 0) {
words[i].ninst++;
return words;
}
if (*wc == *maxw)
words = xrealloc (words, sizeof *words, maxw);
strcpy (words[*wc].word, word);
words[(*wc)++].ninst++;
return words;
}
/** realloc 'ptr' of 'nelem' of 'psz' to 'nelem * 2' of 'psz'.
* returns pointer to reallocated block of memory with new
* memory initialized to 0/NULL. return must be assigned to
* original pointer in caller.
*/
void *xrealloc (void *ptr, size_t psz, size_t *nelem)
{ void *memptr = realloc ((char *)ptr, *nelem * 2 * psz);
if (!memptr) {
perror ("realloc(): virtual memory exhausted.");
exit (EXIT_FAILURE);
} /* zero new memory (optional) */
memset ((char *)memptr + *nelem * psz, 0, *nelem * psz);
*nelem *= 2;
return memptr;
}
( примечание: выходные данные сортируются в порядке убывания вхождения и в алфавитном порядке, если слова имеют одинаковое количество вхождений)
Пример использования / Вывод
$ ./bin/getchar_wordcnt_top dat/damages.txt 10
'dat/damages.txt' contained '109' words.
the 12
a 10
in 7
of 7
and 5
anguish 4
injury 4
jury 4
mental 4
that 4
------
Total: 61
Примечание: чтобы использовать вашу хеш-таблицу в качестве основы для хранения, вам, как минимум, нужно создать массив указателей на каждое слово в вашей хеш-таблице, а затем отсортировать массив указателей. В противном случае вам нужно будет продублировать хранилище и скопировать слова в новый массив для сортировки. (это было бы несколько неэффективным подходом памяти). Создание отдельного массива указателей для каждого слова в вашей хеш-таблице для сортировки - это единственный способ, которым вы должны затем вызвать qsort и избежать проблемы цепочки-корзины.