You will implement four basic data structures: linear list, linked list, hash map, and self balanced tree in this project. The latest code scheme can be downloaded here. A simple tester is available here for your reference.

Change History

(Apr 22) First version released.
(Apr 23) Version 2 released. Renamed "remove by index" method from "remove" to "removeIndex"; add in ArrayList and LinkedList should always return true.
(Apr 26) Version 3 released. Added const qualifier to Entry::getKey() and Entry::getValue(); updated description of Iterator::remove().

Structure

The package includes the following files:

ArrayList.h. You need to write an array-backed linear list in this file.
LinkedList.h. You need to write a linked list in this file.
HashMap.h. You need to write a hash map in this file.
TreeMap.h. You need to write a tree map in this file.
ElementNotExist.h. Exception class.
IndexOutOfBound.h. Exception class.
html/. Generated html documentations (start from html/index.html).
latex/. Generated latex documentations (start from latex/refman.pdf).

Deadline

Initial submission: You need to hand in your project before May 31, including your implementations of the four data structures, and any additional files that they depend on.
Second submission: Jun8.

Testing

Your project will be compiled with gcc 4.7 and judged with test cases.

Result

Test cases for both submissions are the same. Time limit is 10s for each test case. If you have any questions, please contact TAs no later than Jun 10.

Second Submission

鉴于好多同学re的出乎自己意料、以及哈希表开得不够大、甚至编译失败等各种原因，决定允许第二次提交。最后的分数这样算：对于每个数据点，如果第一次过了，那么这个点分数不变；如果第一次没过、第二次过了，那么这个点得70%的分数。

提交截止时间是6月8日晚上23:59:59，请大家抓紧调试。