1.任务简述


本学期 大要求同学们完成两个任务，第 一个是完成 C++ ST L 库中的 deque 库，即实现 一个双端队列 ，要求封装。第 二个是 map 库，即平衡树，要求封装。实现代码的接 口框架与头 文件，助教已经给出，同学们需要实现给出的接 口。


要求、框架接口与测试数据均https://github在：.com/Nerer/



ds2017

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 文件，到时候助教会分组收取。