Question

C Programming Language on Linux - Word Frequency Program

Please write a Program in C that will accept a text file name as a command-line argument via a main program that will do the following:

First, read the file (first pass) and create a linked list of words (in their order of occurrence), with the frequency of each word set to 0.

Then, read the file (second pass) and for each word identified, search the linked list, and when found, increment the word frequency by 1.

Now, create a function called PrintList. This will print out each word and its respective word frequency count in the order of appearance.

Next, sort the linked list alphabetically (assuming that each word starts with a letter) and then invoke the PrintList function.

Finally, sort the linked list in decreasing order of word frequency (ignoring the alphabetic order for words with the same frequency) and then invoke the PrintList function.

Answer 1

Steps to make this program:

• First, make a file words.txt and save it in the same folder you are saving your C program file.
• Then write in the file one word per line.
• In the last line write END because while reading the file you are not reading the last line.

• Then make a file WordFrequency.c and write the following code and then save.
• Below is the fully tested code explained in comments:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*Declaring a node of the linked list*/
struct node
{
char word[100];
int freq;
struct node*next;
};
struct node *insert(struct node *head, char data[100])
{
int i;
struct node *tmp;
/*If there is no element in linked list then inserting data as first element*/
if(head==NULL)
{
tmp=(struct node*)malloc(sizeof(struct node));
for(i=0;i<100;i++)
tmp->word[i]=data[i];
tmp->freq=0;
head=tmp;
tmp->next=NULL;
return head;
}
/*Otherwise inserting data at the end of the linked list by traversing the whole linked list*/
struct node* p=head;
while(p->next!=NULL)
p=p->next;
tmp=(struct node*)malloc(sizeof(struct node));
for(i=0;i<100;i++)
tmp->word[i]=data[i];
tmp->freq=0;
tmp->next=NULL;
p->next=tmp;
return head;
}
void incrementfreq(struct node *head,char data[100])
{
struct node *p=head;
/*Traversing through the list*/
while(p->next!=NULL)
{
/*When word appears in linked list increasing its frequency and breaking from the loop*/
if(strcmp(p->word,data)==0)
{
p->freq+=1;
break;
}
p=p->next;
}
}
void printlist(struct node *head)
{
/*Printing the list by traversing through the list*/
struct node* p=head;
while(p!=NULL)
{
/*Not printing the words with 0 frequency*/
if(p->freq!=0)
{
printf("Word: %s",p->word);
printf("Frequency: %d ",p->freq);
}
p=p->next;
}
}
void sortalphabetic(struct node*head)
{
struct node *p,*q;
char data[100];
int tmp;
/*Selection sort by exchanging the data*/
for(p=head;p->next!=NULL;p=p->next)
{
for(q=p->next;q!=NULL;q=q->next)
{
/*If a word in left of linked list is not in alphabetic order with a word in right of linked list*/
if(strcmp(p->word,q->word)>0)
{
/*Swapping those two nodes*/
strcpy(data,p->word);
strcpy(p->word,q->word);
strcpy(q->word,data);
tmp=p->freq;
p->freq=q->freq;
q->freq=tmp;
}
}
}
}
void sortfrequency(struct node *head)
{
int tmp;
struct node *p,*q;
char data[100];
/*Selection sort by exchanging the data*/
for(p=head;p->next!=NULL;p=p->next)
{
for(q=p->next;q!=NULL;q=q->next)
{
/*If a word's freq in left of linked list is lesser than a word in right of linked list*/
if(p->freq<q->freq)
{
/*Swapping those two nodes*/
strcpy(data,p->word);
strcpy(p->word,q->word);
strcpy(q->word,data);
tmp=p->freq;
p->freq=q->freq;
q->freq=tmp;
}
}
}
}
int main()
{
FILE *fileptr;
char data[100];
/*Prompting user for file name*/
printf("Enter file name: ");
char filename[100];
scanf("%s",filename);
/*Opening the file*/
fileptr=fopen(filename,"r");
/*Declaring head pointer of the linked list*/
struct node *head=NULL;
/*Reading data from file line by line except last line and appending to the linked list*/
while(fgets(data,100,fileptr)!=NULL)
{
head=insert(head,data);
}
/*Closing the file*/
fclose(fileptr);
FILE *fileptr1;
/*Again opening the file*/
fileptr1=fopen(filename,"r");
/*Incrementing frequency of items in linked list by reading from the file line by line except the last line*/
while(fgets(data,100,fileptr1)!=NULL)
{
incrementfreq(head,data);
}
/*Closing the file*/
fclose(fileptr1);
/*Printing the file*/
printf("Printing the list with frequencies: ");
printlist(head);
/*Sorting the list by alphabetic order by selection sort of exchanging the data*/
sortalphabetic(head);
/*Printing the file*/
printf("Printing the list after sorting in alphabetic order: ");
printlist(head);
/*Sorting the list by decreasing order of frequency by selection sort of exchanging the data*/
sortfrequency(head);
/*Printing the file*/
printf("Printing the list after sorting in decreasing order of frequency ");
printlist(head);
return 0;
}

Sample output for the above input file words.txt