Histograms

In this assignment you use structs along with heap memory to create a histogram.

Main

Your main should do the following. Please note that you might need to look at the lower sections for more detail on each part.

Call the readWords function. This function will read in a number of words from the user. You are not to create the array in the main, but instead readWords will create it for you. Thus, you will need to setup a pointer to handle the return of the array. I also suggest creating a struct to help you with the strings. You array of words will just be an array of this struct:

typedef struct str { char letters[30]; } string;

As an example of what this call should look like in the main is the following:

string* words; int numWords; words = readWords(&numWords);

Next the main should call displayWords to display the words that were just read.

Next the main should call makeHistogram to create a histogram from the words. Similar to above, you are not to create an array for your histogram in the main. The histogram will be created using heap memory within the makeHistogram function and returned to the main. You will want to setup a struct to handle histograms. Your histogram will be an array of this struct. Note that the type of one of the fields is the previously defined struct for holding strings:

typedef struct hist { string word; int freq; } histogramEntry;

Next the main should call displayHistogram to display the histogram that was just created.

After displaying the histogram, the main should then call sortHistogram to sort the histogram into most frequent to least frequent.

And lastly, main is to call displayHistogram again to display the sorted histogram.

ReadWords

This function should dynamically allocate an array with space for 20 strings on the heap using malloc. It should then let the user enter strings, one by one, putting them into the slots of the array. When the user enters the word "done", the input will stop. The array should be returned as the return value. Note that if we created the array on the runtime stack we would not be able to return it this way.

You also need to get the number of words read in back to the main. However, since we are already returning the array we can't return two things. Thus, the main has to pass a pointer to an int and then we can use de-referencing to store a value back into the main's int.

DisplayWords and DisplayHistogram

These functions should take in the array of strings or the array of histogram entries and display them to the screen. Note that you will also need to pass in the size of the array as well. These are fairly straightforward functions.

MakeHistogram

This function needs to take as parameters both the array of words and the number of words in the array. It will create a histogram which is just an array of histogramEntry structs and return it. And just like with the readWords function, we will need to pass back the number of entries in the histogram array by pointer/de-reference.

The first thing the function should do is to create the space on the heap for the histogram. Note that at worst we will have all unique words and thus the array won't have to be bigger than the number of words entered.

For making the histogram I would suggest the following approach. Create a for loop that goes through each of the words in the words array. For each word, look through the histogram and see if you can find the word in the histogram so far. Remember that at the start the histogram is empty and will have a size of 0. If you find the word in the histogram, then increase the frequency of that word by 1. If you don't find the word, then add the word with a frequency of 1 to the end of the histogram, increasing the size of the histogram by 1.

SortHistogram

This function should take in the array of histogram entries along with the number of items in the histogram. It should sort the histogram from largest frequency to smallest. No new arrays need to be constructed to do this. You can simply sort the array in-place.

I would suggest using a Selection sort. That is, you look through all the elements in the array and find the largest one. Then you swap that value with the value at the 0th position. This gets the biggest in the first location. Then the whole process is repeated looking only at the values 1..n. Your code will have 2 nested loops if written correctly.

Sample Output

The following is a sample of what your output should look like:

Enter word 0:cat Enter word 1:dog Enter word 2:cat Enter word 3:fish Enter word 4:dog Enter word 5:bird Enter word 6:dog Enter word 7:done Words: 0: cat 1: dog 2: cat 3: fish 4: dog 5: bird 6: dog Histogram: 0: cat with freq of 2 1: dog with freq of 3 2: fish with freq of 1 3: bird with freq of 1 Histogram: 0: dog with freq of 3 1: cat with freq of 2 2: fish with freq of 1 3: bird with freq of 1