Chinese ID number (for example 330302199808180355) contains 3 parts. The first part (6 digits) is the district code. Every city has a unique district code, Here 330302 is the code of Wenzhou city Lichen district. The second part is birthday (8 digits), 4 digits for year, 2 digits for month, and 2 digits for day. The last part (4 digits) is validation number. You are required to design a data structure for Chinese id numbers and the algorithms to implement searching for it. For above example, 33 is Zhejiang province code, all Zhejiang id begin with 33. 0400 is the code for Wenzhou city, Luchen district. 1998 is the year of his birth date. 08 is the month of his birth date. 18 is the day of birth date. 0355 is is validation number. For sake of simplicity, the validation sequence is all digit not letter, but actually, some id number end with x. Requirements: You are required to use concept and method you have learned in DSA coarse to design a program which can do fast searching on Chinese ID number. Your answer contains two parts: First part, designing. The second implementing. In the first part, you have to design a data structure and algorithm. Data structures of id number and id searching. In this part you explain your design (including data structure and algorithm) in natural language, as much detail as possible. 1. You are required to design data structure to hold all this id numbers from main.txt. 2. You are required to design an algorithm to do id searching. You should try to make the searching as fast as possible. (Tips: Algorithm and data structure are often closely related to each other). 3. Read the id number from the file into the program. 4. Test your program with test file (test.txt) and show searching result. 5. Show the performance of your program in the form of Assc and ASLunsucc 6. Comment on your design from time complex and space complex.
Already registered? Login
Not Account? Sign up
Enter your email address to reset your password
Back to Login? Click here