 |
Project 2 |
| CSC 220 |
with AVL Tree Abstract Data Type using Templates
Assignment
First create a complete template AVLTree Abstract Data Type that implements a type independent AVL Tree container. Your implementation must contain at least the following methods, or their equivalents, within its public interface:
AVLTree default constructor and constructor that takes a tree node parameter as the root.
iterator insert(T& newvalue);
iterator find(T& value)
preorderIterator& preorderbegin()
preorderiterator& preorderend()
postorderIterator& postorderbegin()
postorderIterator& postorderend()
You may use the supplied example code as a guide on how to implement the iterators. All iterators must implement at least a working dereference operator, operator*, and the prefix increment operator, operator++() or the postfix increment operator++(int).
You will need to require that any data type that works with your AVLTree has the operator< defined. Your AVLTree must be a self-contained "raw code", "from scratch" implementation, written entirely by you, using only standard ANSI C++.
Then create a program that first reads in the supplied file WordRand.txt, and stores it in your AVLTree. WordRand.txt is a text file that contains over 100,000 unique English words, one per line, in random order.
Important revision from after class on 10/22: After you create the AVLTree filled with the words from WordRand.txt, but before you get the filename from the user, use both your preorder and postorder interators to print out the first 25 words in your AVLTree. This should be about six or eight lines of code.
After reading in WordRand.txt, your program must get the name of any text file from the user, and search the file for all words that are not contained in your AVLTree. When it finds a word not in the tree, your program must print the word, the line number, and the line that contains the word. Design your program so that it prints all output both to the screen and identically to a file called Results.txt.
Your program should store and compare the words without regard to case. The file words are in all capitals. You may ignore all numbers and symbols, that is all characters except ASCII 'A' through 'Z' and 'a' through 'z'. Within reason, you may decide exactly what a "word" is. If you want, a "word" may be any contiguous series of alphabetic characters in the file.
Be sure to check your code on Microsoft Visual C++ Version 6 in one of Parkland's labs, and make sure it works and the code is properly indented and formatted. I will grade your projects using Microsoft Visual C++ Version 6 exclusively
Grading
Project 2 is worth 20 points toward the final grade. It will be graded according to the criteria on the Project 2 Grade Report. You will be given a hard-copy of your Grade Report during the Interactive Grading (see Date immediately following). You are required to keep the Grade Reports for all your projects until you have your final grade at the end of the semester, in case there is a question about the grade of any of your projects.
Your project will be interactively graded on Monday, October 29th. On Wednesday, October 17th, each student will sign up for a specific 10 minute period for grading on the following Wednesday. You may have your project graded before October 29th, if you like, by making arrangements with the instructor. You will have until the interactive grading date of Project 3 to upgrade any deficiencies in your Project 2.
 |
Office: M233a | Phone: 353-2250 | sbadman@parkland.edu | |