Read n words and count how often each one appears. Print each different word with its count, in the order the words first appeared. Use a hash table with chaining to find each word quickly.
What to build
A word counter that finds each word through a hash table with chaining.
Requirements
- Hash each word to a bucket, and search that bucket's chain with
strcmp. - Add a new entry when the word is not there, and otherwise add one to its count.
- Print the words in the order they first appeared.
Input
The first line has n (1 ≤ n ≤ 1000). The next line has the n words, separated by spaces. Each word has 1 to 20 lowercase letters.
Output
One line for each different word: the word, a space, and its count.
Constraints
1 ≤ n ≤ 1000, and each word has 1 to 20 lowercase letters.
Example
Input:
7
the cat and the dog and the
Output:
the 3
cat 1
and 2
dog 1
Why it works
The hash sends a word straight to one short chain, so only a few words are compared. A separate list keeps the order of first appearance, which the table itself does not.
Examples
7 the cat and the dog and the
the 3 cat 1 and 2 dog 1
1 hello
hello 1
Hints
Hint 1
Keep the different words in an array, in the order they first appear, each with its count.
Hint 2
A hash table of 101 buckets holds, for each bucket, a chain of entries; hash each word with h = h * 31 + c.
Hint 3
To count a word, walk its bucket's chain with strcmp; add a new entry if it is not there.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <string.h>
#define BUCKETS 101
typedef struct entry {
char word[21];
int count;
struct entry *next; // the next entry in the same bucket
} Entry;
Entry words[1000]; // every different word, in first-seen order
int distinct = 0;
Entry *table[BUCKETS];
unsigned hash(const char *s) {
unsigned h = 0;
for (int i = 0; s[i] != '\0'; i++) h = h * 31 + s[i];
return h % BUCKETS;
}
void add(const char *w) {
unsigned b = hash(w);
for (Entry *e = table[b]; e != NULL; e = e->next) {
if (strcmp(e->word, w) == 0) {
e->count++;
return;
}
}
Entry *e = &words[distinct++];
strcpy(e->word, w);
e->count = 1;
e->next = table[b];
table[b] = e;
}
int main(void) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
char w[21];
scanf("%20s", w);
add(w);
}
for (int i = 0; i < distinct; i++) printf("%s %d\n", words[i].word, words[i].count);
return 0;
}