Description
In this lab you will build a city database in a couple of different ways. Next week’s lab will be a continuation of this one.
Each database record will contain the name of a city (string of arbitrary length, you may use the string type for this) and the city coordinates expressed as two integers x and y. You may assume that no data file will have more than 100 cities in it. You are to implement the database in two different ways:
Data structure 1: unordered array
Data structure 2: AVL tree
For both structures the following operations must be implemented:
- insert or delete a record by name
- delete a record by coordinates
For the AVL tree you must show that the rotations needed for insertions and deletions are working correctly. Design your own test data and print out enough information to convince yourself (and Mehrdad) that the rotations are working correctly. You must also be able to print out a level order traversal of the tree just to check that it was built correctly. For this you should use the algorithm from lab 2. Print out an asterisk (*) for null pointers. (It’s easier to draw the tree if you know, for example, that a node has only one child.)
You may either code both structures in the same program or, if you wish, do two separate programs. You are responsible for completely testing your program(s) to make sure all the functions are working properly, so build a small database (15 – 20 cities) to test your program. The file containing the database should have the following structure:
city1name x1 y1
city2name x2 y2
Structure the tests in any way you want, but what you turn in must clearly indicate that your functions are working correctly. If you do any input from the terminal to test your code, include a screen capture showing the commands or output them to an output file so it is clear exactly how the testing was done.
You must turn in all the code you wrote, a copy of the database you used, a level order traversal of the AVL tree built from your database, a description of how your testing was structured, and the results of the testing. Please include any necessary explanations in a README_yourlastname file.
Due date for all labs is midnight on Saturday.
