ECE114 Intro to C/C++ Programming Spring 2020
Assignment #5
(due on Thursday, 2/27, 11:59pm)
Upload your SOURCE FILE (.c) to Blackboard with the file name hw5_LastName_FirstName.c
The first few lines of your source file should contain a comment header such as:
// ///////////////////////////////////////////////////
// File:
// Author:
// Date //
// This file contains a function that is used to
// determine the amount of legs on a farm. //
// The user is prompted for the numbers and
// types of animals and calculates the number
// of legs.
// ///////////////////////////////////////////////////
You SHOULD NOT submit executable files (The Blackboard does accept .exe files); however, try to run your program successfully before you submit your source files. No late assignment!! Never show or talk about your code to your classmates. If you meet a problem submitting your files to Blackboard, you can email Prof. Kastner your assignment by the due time.
Grading: (20 points in total)
hw5_Kastner_Steve.c Steve Kastner
1/30/20
Correctness
No errors, input/output correct, output presented nicely, compiles without warnings
14 points
Solution
Code follows requirements is efficient and easy to follow (indenting is highly recommended)
4 points
Code comments
Code is sufficiently commented
2 points
1
Q1.
Write a program that sorts a series of user-inputted words in ascending order. Here are the details:
i) Each word will be no longer than 20 characters.
ii) First, ask the user for the number of words to be inputted, and then start taking
words from the user. Continue with the rest of the program (sorting,
printing, etc.) when that many words have been taken.
iii) Dynamically allocate a string for each word and use a char pointer to pointer (char **) to manage the strings. The char pointer to pointer is essentially an array of char pointers. This pointer must be dynamically
allocated as well.
iv) Sort the array of words using qsort. (Check below)
v) Print the words sequentially after having sorted the whole array.
You have been provided with a skeleton file (hw5_skeleton.c) with lots of comments and function prototypes to help complete this assignment. Please work with that file.
About the program structure:
Let¡¯s break down the problem.
Every word can be represented as a string, which is simply pointer to a character (char*) in C. We need a way to efficiently store multiple words, such that the entire collection of words can be processed together using qsort. How do we do that?
Simple, we can use an array of pointers. Note that an array representation of any data type (say an int[ ]), simply degenerates to a pointer to that type (int*), pointing to the first element in the array. Simply, our array of char*s (read: strings) can simply be represented as a char** (pointer TO a pointer to char), pointing to the first element in the array of char*s (read: strings). The diagram below should help.
words
ECE114 Intro to C/C++ Programming Spring 2020
words[0] = *words
words[1] = *(words + 1)
words[2] = *(words + 2)
words[3] = *(words + 3)
words[4] = *(words + 4)
2
ECE114 Intro to C/C++ Programming Spring 2020
Essentially, words is the pointer to pointers to chars. Each pointer to char is a word (string), and words is pointing to the first in the list.
Where does dynamic memory allocation come in to play?
When you get to know how many words the user will input, you need to allocate the space for that many char*s (read: strings). This is the first malloc operation you must perform. This operation returns to you a pointer to the start of the allocated memory. What¡¯s that? A pointer to a pointer of chars? That¡¯s words (the char**) we use to manage all the words.
So far, you¡¯ve only created space for POINTERS to chars, not the chars themselves. For every user input, you must actually allocate enough memory to store the characters corresponding to the strings themselves. This is the other malloc operation you must perform, one for every word the user inputs. Each of these malloc operations will return to you a pointer to the start of the allocated memory. What¡¯s that? A pointer to chars? That¡¯s the word (the char*) you will be using to handle each word at a time, until of course they are added into the array of char pointers (words), after which you can use word to handle a different word.
Finally, after you are done using your dynamically allocated memory, you MUST (!!) free the memory. This free operation will require you to first deallocate each word, and then words itself. If it helps you think: each malloc has to be paired with a free.
About qsort:
Qsort is a C standard library (stdlib) function that implements a polymorphic sorting algorithm for arrays of arbitrary objects/data types according to a user- provided comparison function. [https://en.cppreference.com/w/c/algorithm/qsort]
The simplified function prototype for Qsort is:
qsort(void* ptr, int count, int size, int (*comp)(const void*, const void*))
Let¡¯s break down the prototype.
i) void* ptr – Pointer to the array to be sorted. In our case, this is the char** used
to store our words.
ii) int count – The number of elements in the array.
iii) int size – The size of each element in the array. This will be sizeof(char*).
iv) int(*comp) (…) – This is a function pointer, corresponding to the comparator
function we will write to compare words. Note that this comparator function MUST take in two void pointers and return an integer corresponding to the comparison result. More on this later.
Functions we will need:
To help organize this program, we will need to implement the following functions:
3
i) char* inputWord(void)
This function allocated memory for a word and prompts for user input. You will need malloc here. Note: for this program you can assume that the user is strictly inputting alphabetic strings. As such, input verification for any numeric characters in user input is not required.
ii) void addWord(char*, char**, int)
This function adds the string (char *) corresponding to a user-inputted word into the array of strings (char **). The int parameter is used as an index to insert the new word.
iii) void printWords(char**, int)
This function will print the list of words inputted by the user. Use it to print both the sorted and unsorted lists. The integer parameter will correspond to the word count.
iv) int compareWords(const void*, const void*)
This function is the comparator function for the qsort. Note that it takes two const void pointers. These pointers are actually pointers TO the elements in the array to be sorted. They are passed in as void pointers to maintain generality/polymorphism of the qsort function. In our case, these pointers will be casted to char** inside the comparator function. This makes sense because the parameters were supposed to point to elements in the array, making them pointers to pointers of chars.
The actual comparison function will be very easy. Use the strcmp function from the strings library to return a result for the string comparison. NOTE: To access the strings, you will need to use a dereference operation.
v) void freeMemory(char**,int)
This function will deallocate all the dynamically allocated memory throughout the program. Call this right before returning from main( ).
4
ECE114 Intro to C/C++ Programming Spring 2020
Sample output:
ECE114 Intro to C/C++ Programming Spring 2020
Hints:
i) Calling the qsort function is simpler than you may perceive. The only caveat is that you need to pass the function pointer of your comparator function, so don¡¯t forget to use the & operator.
ii) It¡¯s best to take user input using fgets. The function prototype for fgets is as
follows:
char * fgets ( char * str, int num, FILE * stream );
iii) Do not forget to clear the newline character at the end of your string after using fgets.
5