2017-2018学年 第 一学期《数据结构A》 大作业说明
2017年 数据结构A类 大作业
数据结构A类助教组上海 交通 大学
2017-2018学年 第 一学期《数据结构A》 大作业说明
1.任务简述
本学期 大作业要求同学们完成两个任务，第 一个是完成 C++ ST L 库中的 deque 库，即实现 一个双端队列 ，要求封装。第 二个是 map 库，即平衡树，要求封装。实现代码的接 口框架与头 文件，助教已经给出，同学们需要实现给出的接 口。
作业要求、框架接口与测试数据均https://github在：.com/Nerer/
2.任务要求
2.1 简要说明
同学们需要在截 止 日期前，完成以上两个STL库的时限，助学们完成的库进 行 测试，以及分组进 行 code review，通过测试结果和code review结果来确定 大家的得分。
2.2 截 止时间
deque截 止时间：2017年 11 月12 日
map截 止时间：2017年 12 月9 日
2.3 文件说明
除了 带有框架和接 口的空头 文件以外，助教还会提供两个是 exceptions.hpp， 里 面带有异常处理 时需要返回的库，另外 一个是utility.hpp， 里 面带有pair类，同学们在编写代码时可直接使 用。
3.测试说明
测试过程 大致为，建 立 一个 test.cpp 来 include 待测试的头 文件，然后进 行 一些调 用，如果在规定 时间内程序正确结束且结果输出与答案相符，则认为该测试点通过。测试点有两个， 一个是基础测试， 一个是提 高测试。
2017-2018学年 第 一学期《数据结构A》 大作业说明
基础测试占总分的 60%，提 高测试占总分的 40%。测试数据以及结果会在 一开始和 框架 一起发到指定 网址上，同学们可 自 行 测试 比对，任务截 止后，助教会进 行 三轮实际测试，第 一轮 为 pretest，不 算成绩，测试后公布结果给 大家 DEBUG，第 二轮测试就通过的数据点，获得该测试点全部分数，第三轮测试结束后，助教会公布测试结果，两天后第 二轮测试没通过的同学可以参与第三 轮测试，如果第三轮测试通过了 第 二轮没过的测试点，则或者该测试点的 一半分数。 全部测试结束后，我们会进 行 CodeReview来考察 大家对实现框架和细节的理 解程度。会结合测试的分数和CodeReview情况进 行 最后的评分。
具体分数分布:两个任务各占期末总评的 10 分，我们会结合测试分数以及 code review结果进 行 给分。如果觉得有困难的同学可以随时和助教沟通，如果在测试中表现的不 是 非常好，但根据代码以及CodeReview情况，助教也会酌情给分。
请注意 一点:千万保证程序不 要出现内存泄漏 ，因为测试数据 里 面包含对于是否内存泄漏 的检测。
4.Bonus
deque部分不 设 立bonus。map部分，使 用 比AVL
实现，且在前两轮测试中通过了 所有测试点，会在总评部分获得少量 加分（1到2分，该分数不 受 大作业部分满分20分的限制）。
只要在前两轮通过所有测试点并且CodeReview情况正常，就可以获得 大作业部分的满分。因此对于bonus 大家不 要过度追求，实现正确基础部分最重要。
5.提交说明
提交时，将 自 己实现好的头 文件与上 文中提到的带有异常返回类以及pair类的两个头 文件放在 一起，然后将三个 文件都放 入 一个 文件夹当中， 文件夹 用学号 + 姓名的 方式命名，然后压缩成rar 文件，到时候助教会分组收取。
