数据结构编程作业说明

清华大学计算机系 · 数据结构教学团队

目录

1. 课程与作业
2. 评分方式
3. 拓展题型
4. 课程要求

• 附：FAQ
• 附：多种编程语言
• 附：OJ 分档评测的图片说明
• 附：选做题目图片说明
• 附：OJ 使用技巧
• 附：输入输出技巧
• 附：一些常见逻辑错误
• 附：Visual Studio msvc 与 GNU gcc 的差异

1. 课程与作业

1. 作业概述

   编程作业在线提交，网址 http://dsa.cs.tsinghua.edu.cn/oj/ 。

   有些课程是公开课程（如 MOOC 等），在 Course->Select public courses 里直接选课。有些课程是私有课程，需要使用教师发放的邀请码选课，或直接由教师加进课堂。

   进入一个课堂，有若干次编程作业（简称 PA），并在左边显示 PA 截止时间。PA 标题的背景，绿色表示尚未截止，红色表示即将在一周内截止，灰色表示已经截止。

   每次 PA 有若干道题目，各题目在本次 PA 中占的权重在题目标题后的括号内。

   题目通常分为标题、描述、输入、输出、样例、限制、提示等部分。

   如无特殊说明，所有题目统一使用标准输入和标准输出。

   在“限制”部分，通常都指定了输入的取值范围，你的程序不必考虑范围之外的情况。

   在“限制”部分，有的题目限制了你能使用的方法。

   程序输出应与标准答案一致，请留意多余的空格、制表符、回车和换行。行末空格和文末换行一般不会影响评分。

   每题得分由黑盒测试和白盒评分组成，成绩比例详见“课程要求”节。

   提醒：应对算法的时间和空间复杂度做充分和准确的估计，正确但低效的程序无法获得高分。

2. 作业提交

   每道题需要在截止前在 OJ 上签署 Honor Code。截止前可以多次修改。

   在截止前提交代码至 OJ 并“标记为最终版本”（Mark it as final version）；截止前可以多次标记，也可以取消标记，以最后标记的为准。

   有的 PA 限制了能标记最终版本的题目数量。有的 PA 中有的题目属于同一组（Group），属于同一组的题目只能选做 1 道。详见“附：选做题目图片说明”节。

   有的课程要求每道题提交一份解题报告（Report）。截止前可以多次修改。

   每次提交的文件不要超过 200 KB。代码如果含有多个文件，可以将所有代码置于顶层目录直接打包（.zip、.tar、.tar.gz 等格式）提交，目录和文件名不能有空格、中文、特殊字符。

3. 无效的提交

   无效的提交记 0 分，包括（但不限于）以下方面：

   1. 未签署 Honor Code；

   2. 未在作业截止时间前标记最终版本；

   3. 标记的最终版本没有使用课程规定的编程语言；

   4. 标记的最终版本在 OJ 上无法通过编译；

   5. 未在题目“限制”部分规定的范围内选用数据结构和算法；（题目“提示”部分只是提供了一些方法，不具有约束力）

   注：如果需要提交 Report 但未提交，那么只会扣减本题这一部分的成绩，不会导致整题无效。

4. 补交（校内课堂）

   作业截止后一段时间内，允许补交，但分数会按时长有所折扣，直到折扣至 0。折扣系数如图所示。

   补交的作业（源代码、Report、Honor Code 文本）请第一时间以附件形式交到网络学堂课程答疑区，并在正文里说明情况。

   补交代码者必须同时补交实验报告，两部分成绩按同一比例折扣。补交实验报告者不必同时补交代码，仅对补交报告的成绩做折扣。

2. 评分方式

1. 诚信守则

   Honor Code 要记录，你在写程序的哪些模块时，做过哪些交流。与他人交流需具体到姓名（网络论坛上的交流可填写用户名），参考网络资料需具体到链接，以便教学团队了解交流程度和参考的内容。在作业纪律方面有违自己所做承诺者，将按Honor Code中所约定的方式受到处罚。

2. 黑盒测试 （即仅针对测例集，考察功能正确性、时间空间性能的测试）

   评测分为“五成测”“九成测”和“全集测”。

   “五成测”：测前 50% 的测试点。

   “九成测”：测前 90% 的测试点。

   “全集测”：测所有测试点。

   每题设置有“九成测”次数和每次罚分，参考“附：OJ 分档评测的图片说明”。

   作业截止后，统一对所有学生的最终版本进行“全集测”，用这次成绩来计算黑盒成绩。

   每题的黑盒成绩都需扣减“九成测”罚分，无论是否标记了最终版本。如果在没有标记最终版本的题目上使用了九成测，则这题会得负分。

   作业截止后，再经过一段预设的时间，可以自行“全集测”，次数不限。如果发现“全集测”成绩与黑盒测试成绩有较大差异，请在网络学堂课程答疑区提出复议。

3. 白盒评分

   先考察解题报告（Report），然后考察代码风格、模块划分、注释清晰度等。若没有提交 Report，则该题白盒记 0 分。

   解题报告请尽量使用纯文本，例如 TXT（*.txt）、markdown（*.md）等，内容包括（但不限于）：

   1. 所使用数据结构与算法的构思、原理和实现要点。

   2. 完成过程中遇到的问题，排除问题的主要过程、使用的方法和技巧，以及参考资料。

   3. 时间和空间复杂度的估算。

   4. （可选）介绍理论分析与实测效果的吻合程度，不吻合时进一步解释原因。

   5. （可选）所用方法的特别、新颖或创新之处。

部分课堂对白盒评分有更细化的要求，以网络学堂发布的白盒评分细则为准。

3. 拓展题型

1. 题型一：设计测例。题目提供一批有缺陷的程序，请设计测例暴露出这些程序的问题。设计测例时你需考虑边界情况和复杂度。

2. 题型二：性能分析。用至少两种方式实现相同接口的数据结构，并设计测例说明这几种实现的适用情况。

3. 后续也可能加入更多拓展题型，以实际题目为准。

4. 拓展题型的黑盒、白盒占比与其它题型不同，解题报告考察点也不同，具体要求在题面上说明。

4. 课程要求

1. MOOC 课堂（xuetangX, edX）

   不需要提交 Report。

   黑盒测试总是使用全集测。

   黑盒测试成绩占 100%，不进行白盒评分。

   不进行代码查重，不接受补交和复议。

   允许使用 C / C++ / JAVA 等语言。使用 C++ 时禁止使用 STL，计算几何课程除外。

   从 MOOC 晋级到 THU / CST 课堂的学生，在 THU / CST 课堂上也不需要签署 Honor Code 和提交 Report，不进行代码查重。

2. 校内课堂(含下列课程号: 30240184，00240074，20740124)

   需要提交 Report。

   作业截止前使用五成测 / 九成测，作业截止后一段时间后才开放全集测。

   黑盒测试成绩视情况占 60%~80%，白盒评分占剩余的分数。

   进行代码查重。有限地接受补交和复议。

   只允许使用 C / C++ 语言。禁止使用 STL，禁止将 STL 头文件复制到代码中或与代码一同提交。

   每次 PA 只能选做 N 题。有的题目被分组，同一组题目只能选做一道。

   另有拓展题型（LAB），必做，或按分组选做, 黑白盒占比有所不同。

1. 计算几何（课程号 70240183）

   需要提交 Report。

   黑盒测试成绩视情况占 60%~80%，白盒评分占剩余的分数。

   进行代码查重。有限地接受补交和复议。

   只允许使用 C / C++ 语言。大部分题目允许使用 STL；例外的题目在题面上注明，禁止将 STL 头文件复制到代码中或与代码一同提交。

   每次 PA 只能选做 N 题。有的题目被分组，同一组题目至多选做一道。

2. 其它课堂

   其它课堂由教师确定评分方案。

下表简要对比以上几个课堂的要求。

课程	MOOC	00240074/20740124	30240184	70240183
Report	不需要	需要	需要	需要
黑盒测试点	全集测	五成测 / 九成测	五成测 / 九成测	以 OJ 为准
黑盒评测比重	100%	60%~80%	60%~80%	60%~80%
白盒评分比重	0%	20%~40%	20%~40%	20%~40%
代码查重	无	有	有	有
补交 / 复议	不接受	有限接受	有限接受	有限接受
Java 等语言	接受	禁用	禁用	禁用
STL	禁用	禁用	禁用	大多数题可用
PA 得分方案	所有题	分组选做	分组选做 N 题	分组选做 N 题
拓展题型	无	有	有	无

附：FAQ

1. 杂项

   1. 助教的联系方式？

      对于校内学生，网络学堂课程答疑的帖子仅发帖人和教师、助教可见。统一使用网络学堂课程答疑联系教学团队。

   2. 课程讲义在哪下载？

      MOOC 学生和校内学生都从 http://dsa.cs.tsinghua.edu.cn/~deng/ds/dsacpp/ 获取讲义。

   3. 如何提问，并更加高效地得到有帮助的解答？

      描述问题时请不要过于概括，比如这样两个问题：

      “我本地运行正确怎么在OJ上就错了？”

      “我本地运行正确，为什么OJ上编译错误，并提示 main should return int？”

      显然，后者更能得到有帮助的回答。

2. OJ 使用说明

   1. OJ 上需要提交哪些文件？

      只需要提交源代码文件(*.cpp / *.c / *.h)，其余文件尽量不要一同打包。Report 只需要提交 readme.txt / .md 单文件。

   2. OJ 上的编译环境与本地有何不同，需要注意哪些问题？

      OJ 使用的是 64 位 Linux 系统 Ubuntu 18.04；C 语言编译器版本是 64 位 gcc-7，编译选项 -std=c11 -O2；C++ 语言编译器版本是 64 位 g++-7，编译选项 -std=c++14 -O2。它与 Visual Studio 中的 MSVC 编译器有一些小区别，例如：main 函数的返回值必须为 int，默认不会包含任何头文件等等。如果遇到了本地编译成功 OJ 编译失败的例子，可以借助搜索引擎，根据提示进一步修改源程序。

      主要区别在“附：Visual Studio msvc 与 GNU gcc 的差异”中列出。

   3. OJ 上是否禁止使用某些库？

      是的，在 OJ 上移除了大部分 STL 头文件，例如 vector、map、algorithm。原则上，只要你的作业能够通过编译，就没有任何问题。不过不包括手动把这些头文件与你的作业其他代码一同打包提交上来，也禁止使用别人写的模板库 :)

      我们确认以下库可以正常使用：用于输入输出的 cstdio、iostream、iomanip，泛型编程 functional、type_traits、initializer_list，数学运算 cmath，内存分配与异常处理 new、stdexcept，平台相关的类型和常量 cstdint、climits，对 C 标准库的直接封装 cstdlib、cstring、cassert、cstdarg，上述库依赖的库 string、tuple、utility 等。

      例如标准库 cstdlib 中的 std::qsort 函数是允许使用的。

      如果不确定某个头文件是否可以使用，不妨先交一个只 include 该头文件的代码试一下。

   4. 输入输出应该采用哪些函数？

      请使用 scanf 和 printf 来代替 cin 和 cout，某些情况下后者效率远远远远低于前者。更高效的读入是用 fread，然后手动解析文本。

   5. Runtime Error 是怎么回事？

      Runtime Error 是指程序在运行过程中出现了问题，通常是内存访问的问题，比如数组下标越界。一般这些问题在小规模测试的时候不会发现，而在 OJ 上大规模数据测试时候就容易暴露出来，所以请自行构造一些数据来调试程序。如果希望知道 OJ 返回错误代码的含义，可以参考 http://dsa.cs.tsinghua.edu.cn/oj/static/submission_result_explanation.html 。常见的有 6：断言或异常；8：整数除以 0 错；11：内存访问错误。

   6. 有什么快速定位越界和野指针的方法吗？

      Visual Studio 2019 已推出运行时地址检查功能，可在项目“属性 -> C/C++ -> 启用地址擦除系统（实验性）”开启。地址检查有助于及时发现隐蔽的越界。

      gcc 和 clang 编译器提供了更强大的运行时检查功能，不仅可以检查地址越界（编译选项 -fsanitize=address），还可以检查整数溢出等。

   7. 我的运行结果是 Time Limit Exceeded，时间 ≥ 2200 ms，是不是只要再做一些常数级优化就不会超时了？

      当超过题目规定的时限，OJ 会杀死进程。显示用时 ≥ 2200 ms，说明程序运行时间超过时限（2 s），并不说明程序只花 2200 ms 就能运行完。因此，不一定是把程序运行速度优化 200 ms 就能解决的。

3. 作业说明

   1. 必须采用题目中【提示】所指出的方法吗？

      不是的，题目中的【提示】只是一种可行思路，不排除有更好的思路，可以任意选择方法。但是如果题目正文和题目的【限制】中对方法有限制，那么必须遵守。

   2. 标记的 Final Version 必须是九成测版本吗？

      不是的。因为作业截止后会统一对所有学生的最终版本进行“全集测”，所以无论标记了五成测还是九成测版本，其得分都会被这次全集测取代。

   3. 九成测机会可以借给他人吗？

      一方面，为了公平性，不允许借和出借九成测机会；另一方面，把代码提交到他人的帐号违反了 Honor Code，为本课程所禁止。

   4. 如果我使用了九成测机会，但最终没有选做这道题，还会罚分吗？

      会罚分。这道题的黑盒分数将以负分计入本次 PA 的黑盒总分。

   5. 程序调试了很久没有调通，可以使用助教来进行调试吗？

      由于调试工作量实在太大，所以助教不会来帮助大家进行调试 :) 比较建议大家在同学中寻找一些小黄鸭小伙伴来互相帮助调试，这样双方都会有明显的进步，助教自己的程序就是这样调试的。有些课堂可能会提供线下答疑，可以在线下答疑的时候前往咨询一些调试建议。

   6. 题面上的“输入样例”就是第一个测试点吗？

      不一定，输入样例与测试点没有直接联系。

   7. 教材上的示例代码可以直接在作业中使用吗？

   • 支持借鉴、学习教材中的代码，用来改善自己程序的效率；
   • 如果直接使用教材中的代码，需要进行声明；
   • 原则上，并不鼓励使用教材和课件中的代码，鼓励同学们自己实现、完善相应的数据结构；
   • 教材中的代码，更多的是一种原理的示范，并不保证正确性，如果因此出现 Bug，请同学们自负后果。

   1. 作业雷同后果如何？

      这会给双方都带来极大的困扰，因为会导致记 -100 分，太惨了 :)

      提前说明的是本课程对作业雷同的判定比较严格，所以请大家独立完成作业。

      需要强调的是，在签署的 Honor Code 中，你已承诺“我未曾也不会向同一课程（包括此后各届）的同学复制或公开我这份程序的代码，我有义务妥善保管好它们”。

   2. PA 得分能超过 100 吗？

      不能，黑盒、白盒成绩分别封顶。

      对于有选做题目的课堂，可能有的组合会使起评分超过 100 分。但是无论如何，如果黑盒总分（加权）超过 100，那么得分截断到 100 分；白盒总分亦然。

附：多种编程语言

请先核对“课程要求”节，确认你所在的课程允许使用多种编程语言。否则，即便你通过了黑盒测试也不计这题的成绩。

这些语言的运行效率比 C / C++ 差一些，可能无法通过一些题目。

1. Java 支持

   OJ 现已支持提交 Java 源代码，JDK 版本是 11。可以提交一个单独的 Main.java 文件，也可以提交压缩包。

   • 主类必须是 Main，写在 Main.java 里

   • Main 必须属于默认包。如果提交的是压缩包，Main.java 要置于顶层目录

   • 使用标准输入、标准输出

   • 如果抛出异常（或错误），或者调用 System.exit 以非 0 值退出，则评测结果为 Exit xx，不得分

   • 题目的空间限制无效，不测量内存使用量，只需物理内存占用量在 2 GB 以内即可

   对应于“Tutorial”第一题“0.加法(Add)”，Main.java 的示例代码如下：

   import java.util.Scanner;
   
   public class Main {
     public static void main(String[] args) {
       Scanner in = new Scanner(System.in);
       int a = in.nextInt();
       int b = in.nextInt();
       System.out.println(a + b);
     }
   }

   注：该示例代码没有考虑 int 类型的范围，因此不能通过后几组较大（A + B >= 2 的 31 次方）的数据。

2. Python 支持

   OJ 现已支持提交 Python 源代码，Python 版本是 2.7。可以提交一个单独的 main.py 文件，也可以提交压缩包。

   • 直接执行的文件是 main.py

   • 如果提交的是压缩包，main.py 要置于顶层目录，运行的当前目录就是 main.py 所在的目录

   • 使用标准输入、标准输出

   • 如果抛出异常，或者调用 exit 以非 0 值退出，则评测结果为 Exit xx，不得分

   • 题目的空间限制无效，不测量内存使用量，只需物理内存占用量在 2 GB 以内即可

   对应于“Tutorial”第一题“0.加法(Add)”，main.py 的示例代码如下：

   if __name__ == '__main__':
       a, b = raw_input().split()
       print int(a) + int(b)

3. Python3、PyPy、PyPy3

   Python3 版本是 3.6。main.py 默认使用 python2 运行，如需使用 Python3，请在 main.py 的第一行加“#!/usr/bin/env python3”，其它要求与 Python2 相同。示例代码如下：

   #!/usr/bin/env python3
   if __name__ == '__main__':
       a, b = input().split()
       print(int(a) + int(b))

   PyPy 是一种“运行时优化”（JIT）的 Python 解释器，通常比原生 Python 运行得更快。指定选用 PyPy（兼容 2.7）的方法是第一行加“#!/usr/bin/env pypy”，指定选用 PyPy3（兼容 3.6）的方法是第一行加“#!/usr/bin/env pypy3”。

附：OJ 分档评测的图片说明

作业截止前，有两个测试按钮。“50% Judge”进行“五成测”，不限制次数。“90% Judge”进行“九成测”，次数有限，且会根据使用次数罚分。

使用“九成测”机会时，提交页面会显示一行警告。

你还可以为每次提交做批注，这样，批注会显示在测试结果的右边，以便你在众多提交中分辨你的每次提交。

显示的分数是通过的测试点占所有测试点的比例，因此“五成测”最高 50 分，“九成测”最高 90 分。

作业截止后，再经过一段预设的时间，可以自行“全集测”，次数不限。如果发现“全集测”成绩与黑盒测试成绩有较大差异，可以申请复议，详见作业说明“黑盒测试”。

附：选做题目图片说明

有的 PA 只允许选做若干道，如上图所示。超过5道则无法标记最终版本，从而无法得分。如果没有此提示，则没有此限制，但你还是要满足分组选做限制。

有的 PA 中，题目被分组，同一组里的题目只允许选做 1 道，如上图所示。超过 1 道则无法标记最终版本，从而无法得分。如果没有显示 Group，则该题没有此限制。

各题目在 PA 中占的权重在题目标题后的括号内，权重不尽相同。选做的题目不同， “起评分”就不同。例如在上图中，选做 THU2017 2-2-1、THU2017 2-3-1，即使所有题目都获得满分，此次 PA 也只能获得 25% + 20% + 20% + 25% = 90% 的分数；如果选做 THU2017 2-2-2、THU2017 2-3-3，则起评分为 105%。

对于每次 PA，黑盒、白盒成绩分别封顶：如果黑盒总分（加权）超过 100，那么得分截断到 100 分；白盒总分亦然。

建议根据题目难度、自己的时间和能力选做题目。

附：OJ 使用技巧

1. OJ 首页上有 OJ 使用手册（guide）、视频教程（video guide）、本编程作业说明（PA handbook）。

2. 在黑盒测试结果页面，有解释评测结果的含义的链接 http://dsa.cs.tsinghua.edu.cn/oj/static/submission_result_explanation.html 。

3. Runtime Error 的 signal 同样反映了某种信息，可以查阅相关资料了解0各个 signal 的意义。参考 http://dsa.cs.tsinghua.edu.cn/oj/static/unix_signal.html 。

4. 几种主要的读入数据方法，大多数情况下性能是 fread > getchar > scanf > cin 的顺序。

5. OJ 上的编译器采用的是 gcc（g++），对于 Linux 和 Mac 用户可以无缝衔接，而如果使用 Windows 的同学希望能够在本地编译与 OJ 编译之间较快衔接的话，可以考虑使用 MinGW。

6. 评测所依赖的输出流是 stdout，而使用 stderr 的输出不会被纳入最终评测——但如果你使用 stderr 进行调试却没有在提交中移除，这将显著地拖累你程序的性能。

7. Windows 和 Linux 上换行符有 "\r\n" 跟 "\n" 的差别，你的程序最好有一定鲁棒性，能处理两种情况。

8. Linux 文件系统区分大小写，因此 #include "foo.h" 不能与 Foo.h 对应。

9. 常用的调试工具包括 gdb、MSVC debugger、室友、小黄鸭。

10. 如果不确定某一特性是否为 OJ 所支持，不妨动手试一试。

附：输入输出技巧

1. 判断输入结束

   有些编程作业题并未指明测试数据的组数，此时需要自己判断输入结束。其实，根据题意正确处理输入数据也是同学们在这门课中需要练习的编程能力之一。

   处理输入的方法很简单，使用 C++ 风格的 cin，可以这样写

   int a, b, c;
   while (cin >> a >> b >> c)
   { /* blablabla */ }

   如果使用 C 风格的 scanf() 函数，则可根据其返回值做出判断，具体地可以这样写：

   int a, b, c;
   while (scanf("%d%d%d", &a, &b, &c) != EOF)
   { /* blablabla */ }

   当格式输入流读到文件末尾时会返回 EOF，于是 while 退出。

2. 过滤空白字符 有些题目是这样的输入格式：

   E 6
   M
   E 2
   M

   即字母、数字混输。如果用 getchar 或 scanf 的 %c 参数，会受到行末空白符（比如空格、换行等）的困扰。cin 到字符串、scanf 的 %s 参数都会自动过滤空白符。使用标准库的功能来过滤空白符，会使程序逻辑更清晰。示例代码：

   char buf[8];
   int x;
   while (scanf("%s", buf) != EOF) {
     switch (buf[0]) {
     case 'E':
       scanf("%d", &x);
       /* balabala */
     }
   }

3. 重定向

   为便于反复测试及再现运行过程，可采用输出、输入重定向的方法。 你只需事先将输入数据存成文件，运行时系统会自动从中获取输入。其效果完全等同于你从（作为默认输入流的）键盘逐项输入。 类似地，你也可以指定另一文件，并使运行的结果自动存入其中。其效果完全等同于从（作为默认输出流的）屏幕截取输出结果。 重定向的好处很多：可以避免手工输入的出错，忠实可靠地重复测试；可以实现大规模数据的输入；可以完整精确地记录程序的输出，以便事后的对比分析；可以省去默认输入、输出流占用的大量时间，更加准确地测量程序的执行效率。

方法一：修改源文件，指定重定向的输入、输出文件

例如，若希望从文件 input.txt 中获取输入，将输出保存到文件 output.txt 中，则可在主程序开头增加如下语句：

```
  #ifndef _OJ_
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  #endif
```

注意：如果用 C++ 风格的 cin / cout 的话，还要在前面引用头文件的部分加入 `#include <cstdio>`。

OJ 在编译程序的时候会定义名为 `_OJ_` 的宏，所以上面这段语句会在 OJ 运行的时候被跳过。

方法二：在 IDE 中通过设置命令行，重定向输入、输出文件 以 Visual Studio 为例，可打开对应工程的“属性页”，在“配置属性”下的“调试”页，设置“命令行参数”。

输入参数不多时，可直接键入。例如 ADD 一题，键入“100 200”即可。若其中包含特殊字符，则需以'^'引导，或者使用一对半角括号消除歧义。

若输入参数多，且不止一行，则可将其存成一个文件。比如，可在“命令行参数”中键入:

`< D:\test\input.txt`（注意起始字符"<"不能省略）

为将程序的输出保存至指定文件，可在“命令行参数”中继续键入：

`> D:\result\output.txt`（同样地，起始字符">"也不能省略）

若不希望覆盖文件原有的内容，只需用">>"替换以上的">"，即可将每次运行的输出追加至 D:\result\output.txt。

输入、输出的重定向可同时采用并生效。比如可在“命令行参数”中键入：

`< D:\test\input.txt >> D:\result\output.txt`

重定向文件的具体路径与文件名可自行选择，但若包含空格，则需使用一对半角引号消除歧义，比如：

`< "D:\my test\input.txt" >> "D:\my result\output.txt"`

1. 帮助资料

   关于输入输出的进一步问题，可以自己查阅相关手册或资料。

   也可参考标准手册，以上输入输出方法都是 C / C++ 标准输入输出，在 manual 中都有详细介绍。

   cin：http://www.cplusplus.com/reference/iostream/cin/

   scanf：http://linux.die.net/man/3/scanf

   对比：http://www.byvoid.com/blog/fast-readfile/

附：一些常见逻辑错误

1. swtich 里忘记加 break，导致多个 case 后的语句都被执行。

2. int *a = new int[n] 误写成 int *a = new int(n)。前者申请了 n 个 int 的空间；而后者只申请了一个 int 的空间，并初始化为 n。

3. 用 scanf 输入 long long 类型变量时，对应的格式串误用成 %d，应为 %lld。

4. 在函数里开了很大的数组，导致运行时栈溢出。错误示例：

   int main() {
     int a[10000000];
     return 0;
   }

   可以使用动态内存分配，避免栈溢出，例如：

   int main() {
     int *a = new int[10000000];
     delete[] a;
     return 0;
   }

5. 计算溢出。错误示例：

   int a = 1000000, b = 1000000;
   long long c = a * b;

   程序会先在 int 范围内计算 a * b，再把溢出后的结果赋值给 c。正确写法是 c = (long long)a * (long long)b。

6. 使用有副作用的表达式时，表达式求值顺序影响结果

   例如 a[i] = b[i++]，求值顺序可能相当于 a[i] = b[i]; i++，也可能相当于 tmp = b[i]; i++; a[i] = tmp。

7. 有返回值的函数漏 return 语句。

   行为是不确定的，有的编译器会恰巧返回你想要返回的变量，而一般不会。

8. 指针引用了临时对象

   使用指针时需要注意对象的生存期。在函数体内（或语句块内）定义的对象，出函数体时会析构，之后其值可能会被复写或重复利用；new、malloc 分配的内存不会被自动释放。

9. strcpy / memcpy 的源地址和目标地址有重叠。

10. 留意编译器给出的 warning，有可能对应着一个 bug。

附：Visual Studio msvc 与 GNU gcc 的差异

1. msvc 可能会自动 include 一些头文件，gcc 编译提示函数找不到。

2. 使用 scanf 等函数会警告 not safe(warning 4996)，msvc 推荐使用 scanf_s ，但是这个不属于 C / C++ 标准，gcc 没有。

3. gcc 也没有 itoa（数字转换为字符串的函数）。

4. gcc 上，模板类继承模板类，two phase name lookup，调用父类函数会提示找不到，需要用 this-> 调用。

5. gcc 禁止 void main。main 函数必须 return 0，如果返回值非 0，也会被认为是运行时错误，不得分。

6. http://dsa.cs.tsinghua.edu.cn/oj/static/submission_result_explanation.html 列出了一些常见编译错误的解决方法。

---

数据结构编程作业说明