1 0 overview madame pince the head librarian at hogwarts has expressed an interest i 5187185
| 1.0 Overview | ||||
| Madame Pince, the head librarian at Hogwarts has expressed an interest in the new “Computational Magic” to Professor Dumbledore and has asked if it would be possible to obtain a program which would catalog and store information on all of the books in the Hogwarts Library. Professor Dumbledore has requested just such a utility program which will be implemented as a binary tree. | ||||
| 2.0 Requirements | ||||
| The student shall define, develop, document, prototype, test, and modify as required the software system. | ||||
| 2.1 This software system shall define a class, called Library which maintains a Binary Tree of instances of a structure called Book as defined in section 2.3. | ||||
| 2.2 The Library class shall implement all the functionality of a binary tree and shall contain variables and functions as described below: | ||||
| 2.2.1 Member variables:–this class shall contain one private member variable. This shall be a pointer to a Book structure and shall be named m_pRoot. The variable m_pRoot shall point to the first instance of Book in the tree. | ||||
| 2.2.2 Library(), ~Library–these functions are the default constructor and destructor. The destructor function shall delete all instances of Book from the tree by calling the recursive function destroyTree passing in the root. | ||||
| 2.2.3 bool buildLibrary(char *fileName)–this function takes a single argument, a character array giving the name of a data file (provided by the instructor). It will open the data file and read all data from the data file, create Book structures to hold the data, and call the addBook() function to add each book to the database. This function shall be provided by the instructor. This function shall be public. | ||||
| 2.2.4 bool addBook(Book *newBook)–this function takes a single argument, a pointer to a Book structure. It will then add this book to the binary tree of books. This function shall use the book number of the book as the key for insertion into the binary tree. It will return true if the book was successfully added to the tree or false if it failed to add the book. This function shall be public. | ||||
| 2.2.5 Book *removeBook(int bookNum)–this function takes a book identification number as it's only argument. It shall locate the book in the tree of books and remove this book from the binary tree. It will set the left and right pointers of the removed Book structure to NULL and return a pointer to the book. If the item was not found in the tree it shall return NULL. This function shall be public. Remember that if the node to be removed from the tree has two children it actually get's overwritten. So in this case you will need to create a duplicate Book structure, and copy the data out of the one to be overwritten. Then after completing the deletion for a node with two children return the pointer to the new duplicate Book. |
||||
| 2.2.6 Book *getBookByNumber(int bookNum)–this function takes a book identification number as its' only argument. It will then locate this book in the tree of books and return a pointer to the book. If the book was not found it shall return NULL. You may assume, in this case, that it is OK to return a pointer to a book in the tree without worrying about it giving access to other items in the tree. This function shall be public | ||||
| 2.2.7 Book *getBookByTitle(char *title)–this function takes a book title as a character array as its' only argument. It just calls the private overloaded getbookByTitle() function and returns whatever that call returns. This function shall be public | ||||
| 2.2.8 Book *getBookByTitle(char *title, Book *rt)–this function takes a book title as a character array, and a pointer to the root of a sub-tree as its' two arguments. It will then locate this book in the tree of books and return a pointer to the book. If the book was not found it shall return NULL. This must be a variation on the recursive traversal of a binary tree algorithm. (Note: It will take some careful thought to be sure this one works correctly. We will discuss this function in class.) You may assume, in this case, that it is OK to return a pointer to a book in the tree without worrying about it giving access to other items in the tree. This function shall be private | ||||
| 2.2.9 void printLibrary()–this is a public function which will just call the private function printAll() as defined in section 2.2.10. | ||||
| 2.2.10 void printOne(Book *book)–this function shall take a pointer to a Book structure and print on the screen all information in the structure. This shall include the book identification number, book title, and author. This function shall be private as it should only be called by the printAll() function defined in section 2.2.10. | ||||
| 2.2.11 void printAll(Book *rt)–this shall be a private function which is called by the public function printLibrary(). It takes a single argument, a pointer to the root of a tree. It will perform an in-order recursive traversal of the tree and print all information in each book in the tree. It can call the function printOne() to print the information on the Book passed in as an argument. | ||||
| 2.2.12 bool getNextLine(char *line, int lineLen)— this shall be a private function which can be called by the buildLibrary() function. It will read the next data line from the file referenced by the inFile argument and place it in the character array pointed to by the line argument. This function will be provided by the instructor. | ||||
| 2.2.13 void destroyTree(Book *rt)–this shall be a private function which can be called by the class destructor. It will recursively traverse the tree and delete all nodes from the tree. | ||||
| 2.3 This software system shall define a structure called Book which contains all information to define a book in the Hogwarts library. Code defining this structure shall be stored in a header file called Book.h. A Book.h file is included in the zip file which can be downloaded from the link given below. | ||||
| 2.3.1 An int, called bookNumber. This variable shall be used as the key. | ||||
| 2.3.2 A character array, called Title capable of holding strings of up to 127 characters. This array shall hold the title of a book. | ||||
| 2.3.3 A character array, called Author capable of holding strings of up to 64 characters. This array shall hold the author's name. | ||||
| 2.3.4 Two pointers, called left and right which shall point to Book structures and allow the building of binary trees of Book structures. | ||||
| 2.4 The Library class file and its' associated header file must be capable of being compiled and linked in with a driver program for testing. | ||||
| 3.0 Deliverables | ||||
|
These products shall be delivered to the instructor electronically via e-mail as specified below. buildLibrary() Function to be Added to the Library Class Note: In order to use the the function below you will need to add the following includes and the using namespace std command to your Library.cpp file. #include #include #include #include using namespace std; //————————————————————- // Function: buildLibrary() // Purpose: Build the library from a data file // Args: fileName – character array holding the name of the // datafile defining the library. // Returns; True if library was successsfully built. //————————————————————- bool Library::buildLibrary(char *fileName) { ifstream inFile; Book *bk; char line[128]; inFile.open(fileName, ifstream::in); if(!inFile.is_open()) { // inFile.is_open() returns false if the file could not be found or // if for some other reason the open failed. cout << “Unable to open file ” << fileName << “. nProgram terminating…n”; return false; } //first time reading file: Set GraphNode ID and Data while (getNextLine(inFile, line, 127)) //while the next line is readable { bk = new Book(); bk->left = bk->right = NULL; bk->bookNumber = atoi(line); // Read the book title getNextLine(inFile, line, 127); strcpy(bk->Title, line); // Read the author getNextLine(inFile, line, 127); strcpy(bk->Author, line); // Add this book to the tree addBook(bk); } return true; } getNextLine() Function to be Added to the Library Class //—————————————————————- // Function: getNextLine() // Purpose: Read a line from the data file skipping blank lines // and comment lines beginning with # // Args: inFile – reference argument to an open ifstream object // to read from. // line – character array into which the data line is read // lineLen – maximum number of characters which can be read // into the array line // Returns: True if a successful read was done. If False is // returned then the array line will be zero length. //—————————————————————- bool Library::getNextLine(ifstream &inFile, char *line, int lineLen) { int done = false; while(!done) { inFile.getline(line, lineLen); if(inFile.good()) // If a line was successfully read { if(strlen(line) == 0) // Skip any blank lines continue; else if(line[0] == '#') // Skip any comment lines continue; else done = true; // Got a valid data line so return with this line } else { strcpy(line, “”); return false; // Flag end of file with null string and return false } } // end while return true; // Flag successful read } |
||||