Transcript Programming Assignment #4 -- Binary Trees

Programming Assignment #4
Binary Trees
CS-2303
System Programming Concepts
(Slides include materials from The C Programming Language, 2nd edition, by Kernighan and Ritchie and
from C: How to Program, 5th and 6th editions, by Deitel and Deitel)
CS-2303, C-Term 2010
Programming
Assignment #4
1
Assignment
• Write a C++ program to
– Read one or more text files
– Build up a binary tree of words in those text
files
– Print out alphabetical list of words and number
of occurrences of each word
• Also total number of words
• In Visual Studio 2008
CS-2303, C-Term 2010
Programming
Assignment #4
2
Reading
• Deitel & Deitel, Chapter 19
• Especially §19.7–19.9
• Review Binary Trees
• Previous courses
• K&R §6.5
• D&D §12.7
CS-2303, C-Term 2010
Programming
Assignment #4
3
This Assignment
• Command line program
./PA4 outputFile inputFile1 inputFile2 ...
• Open and read each input file in turn
– Scan for words
– Store each word in binary tree
– Increment count of words previously seen
• Open and write to output
– List of words
– Count for each word
– Total number of distinct words
CS-2303, C-Term 2010
Programming
Assignment #4
4
Example Output
166
a
25
and
11
as
3
command
15
each
2
file
4
files
109
in
4
input
98
it
99
of
3
open
6
program
18
read
152
the
41
this
3
under
30
would
------------17
Total number of different words
CS-2303, C-Term 2010
Programming
Assignment #4
5
Notes
• Upper and lower case words are the same
– “This” and “this”
• Related words that are spelled differently
are different
– “Car” vs. “cars”
CS-2303, C-Term 2010
Programming
Assignment #4
6
Guidance
• Think through this problem in Java
• Use as inspiration
implementation
Don’t use templates from Standard
Template Library!
and
guideline
for
C++
You must build your own classes!
– One or more class interface files (.h)
– A corresponding class implementation file
(.cpp) for each class interface
– One or more .cpp files for main() and other
non-class functions
CS-2303, C-Term 2010
Programming
Assignment #4
7
Suggestion
• class treenode
• Members:–
• Pointers to left and right subtrees
• int count
• string word
• Constructor, destructor
• Add to or access left and right subtrees
CS-2303, C-Term 2010
Programming
Assignment #4
8
Suggestion (continued)
• class binaryTree
• Members:–
• root
• Constructor, destructor
• Methods to traverse tree, insert into tree, etc.
CS-2303, C-Term 2010
Programming
Assignment #4
9
Test Files
• Provided in project assignment
CS-2303, C-Term 2010
Programming
Assignment #4
10
Submission
• Build in Visual Studio
– If working on Mac or other system, port to VS
at least one day prior to due date
• Make clean before submitting
• Zip files together so grader can unzip and
build
• Project name:– PA4
• Submit zip file, README, output from test
cases
CS-2303, C-Term 2010
Programming
Assignment #4
11
Additional Notes
• See notes at the end of Programming
Assignment document
• Command line arguments (same as in C)
• Input and Output streams
• Not in Deitel and Deitel!
• Formatted output
CS-2303, C-Term 2010
Programming
Assignment #4
12
Questions?
CS-2303, C-Term 2010
Programming
Assignment #4
13