C++ Programming
Homework 9
● You may want to read about how to write a proper container with iterator before
you begin this homework. Here is a good starting point. And here is another.
Read this too.
● (35 pts) Write a class SetList and a class iterator inside class SetList that
allows forward iteration through it. Each ListNode will have info, next like we did
in the past with singly linked list. Note, sets keep their items in ascending
alphabetical order by item, but you can safely ignore this for SetList in this
homework. Note, you need not write all the methods required for a STL container.
You need only write the methods, operators, and iterators you use in your
Homework 8 problem 1 solution. MapArray will need operator []. Both will
probably need a non-const iterator. You may need to define the traits types (value
type, etc) for the container and the iterator. Many students get these incorrect
because they try to do mechanical translation of an example to SetList and
MapArray. That will likely lead to problems. You should think about what each
type should be. MapArray is more challenging because it contains pairs and you
must deal with first and second types too. SetList will have a head which is a
pointer to a ListNode like we’ve done several times already in homeworks
implemented as a linked list. ListNode should contain info and next. ListNode
must also be a template to work with the template SetList. It need not be nested
inside ListNode. I would put it in the file SetList.h above the definition of SetList.
● (35 pts) Write a class MapArray and a class iterator inside class MapArray that
allows random access iterator (random access) iteration through it. Note, the
elements of your Array must be pairs. Note, maps keep their items
in ascending alphabetical order by key, so yours should do that too because the
program must print out the frequencies in order by key.
SPOILER (HINT in white - select it to see it)
● Implement MapArray as an array of pointers to pairs. It should be very
similar to the char stack we implemented in Homework 1.
● Keep a counter that tells how many items are in this MapArray. It should
start at zero.
● You should implement operator []. You can also implement a find(string
index) function that returns the index of where it finds the pair that
contains the string index. It can return -1 if the string is not in this list. If it
is not in the array, insert it at the end (just like we did with stack). In either
case, return a reference to the second associated with the pair whose first
is the same as the index string.
● You can make your array of pair pointers very large to start (like 10000) so
you need not worry about growing the array. You will need a destructor to
free up the pairs you allocate inside the array of pair pointers.
END SPOILER
● (30 pts) Re-use your program from the previous homework problem 1 that counts
the frequency of words in the input and excludes stop words, but substitute your
two classes above for the STL classes you used last week. Use MapArray
(instead of Map) for the data structure that keeps counts of frequency of words
and use SetList (instead of Set or Vector) for the excluded stop words. Test your
program on the same sample inputs from the previous homework.
● Hint: first write class SetList and modify your Homework 8 problem 1 program to
use it. Get it working with std::Map and your SetList. Then change back to std::set
and write MapArray and change your program to use your MapArray. After you
get that to work, change your program to use both your SetList and your MapArray
and get it to work.
Specifics:
Submission should have the following file organization: Two files: hw9.zip and
report9.pdf
hw9.zip
|ucinetid_studentid |
|ucinetid_studentid |- SetList.h (contains both declaration and definition of SetList
class)
|ucinetid_studentid |- MapArray.h (contains both declaration and definition of MapArray
class)
|ucinetid_studentid |- main.cpp (Your modified HW8 program that counts frequency
of occurrence of words)
|ucinetid_studentid |- sample_doc.txt (from HW8)
|ucinetid_studentid |- stopwords.txt (from HW8)
|ucinetid_studentid |- frequency.txt
|ucinetid_studentid |- Makefile
Report :
Part 1) Include your whole SetList.h and MapArray.h and also main.cpp for the
function analysis. And explain how insertion is done in each of your SetList and
MapArray.
Part 2) show screenshot of compiling for your program with make command
Part 3) Run your programs with valgrind and include the screenshot.
Part 4) copy and title your,frequency.txt in the report.