TsinghuaX: 30240184.1x Data Structures and Algorithm Design Part I 数据结构与算法设计(上)

Sorry, the course is taught in Mandarin.

本课程用中文教授。

虽然我们常说这门课对于数学基础和编程基础有一定的要求，但这并不意味着你需要精通所有相关课程。实际上，你只需掌握若干重要的数学概念及方法，以及C/C++语言编程的基本技巧。为确认自己是否适宜选修这门课程，不妨对照以下清单做一清点：

• C++语言程序设计基础：类、继承、重载、重写、虚方法、模板

• 离散数学基础: 集合、偏序集、良序、数学归纳法、级数、递归、递推

• 概率基础: 随机分布、概率、伯努利实验、数学期望、期望值的线性律

正如课程简介页面上所指出的，DSA需要兑现为具体的语言，但并不唯一地依赖于某一特定语言。正因为此，课程内容中也会涉及很多其它的语言（Java/Python/Perl/Ruby/...），它们之间的相互比较，对于我们理解DSA很有帮助。这也属于我们在课堂上，着重强调的拓展内容之一。因而对于这个问题，答案是肯定的。

但是非常遗憾地，因为我们的资源限制，我们在编程作业上也只能忍痛割爱，在OJ上以统一的编译、运行环境进行测试，因而对于C\C++的编程基础，我们还是有一定的要求：事实上在数据结构中也只是会用到部分的特性(比如C++里的类模板)。主要是能够使用就行了，只要学一些过基本的内容问题应该不大。

如大家所知，数据结构必然需要用到一些数学，但与程序语言一样，未必需要（也不可能）各方面都精通。事实上，本课程不涉及高深的数学知识，如果你的高中数学学得还行，那就应该能在小修小补的基础上应付。在课程简介信息中，我们尽可能罗列出了本课程所涉及的相关知识，尽管覆盖了不少学科，但若从仅是掌握其中所列知识点的话，即便从零基础开始，也花不了多少时间的。比如，建议你可以借助所给的关键词，在Wikipedia中逐条自学。

最终成绩由以下部分组成：

• 课后测验（Problem Set），共6次，每次10道题目，每题占1%，合计60%

• 编程习题（Programming Assignment），共2次，每次3道题目，合计40%

• 课后测验是我们对于学生对课程掌握程度的一种过程性评价，平均会在每章左右的时候放出一次，每次10道客观题，需要在规定的截止日期前作答。
• 编程习题则是由我们课程特色所决定的的一种习题形式，会与OJ http://dsa.cs.tsinghua.edu.cn/oj/ 绑定，请以自己注册edx的邮箱注册到该平台，我们会自动把OJ上的成绩同步到edx上。

数据结构与算法（依然简称DSA）是个非常开放的专题，学习过程没有终点，任何一门课程都不可能穷尽。然而有意思的是，反过来，它的学习过程也是分阶段逐层递进的。一门好的此类课程，应该可以让不同背景、不同基础、不同目标的学习者有一定的选择余地，这也是我们设计这门课的重要标准之一。

我喜欢将DSA比作汽车。
熟悉基本的数据结构的基本功能与使用方法，犹如拿驾照会开车能上道。
懂得不同DSA之间的差异及其适用场合，懂得针对问题需要选取适当的DSA，犹如懂得如何选购适宜于自己的汽车。
懂得对DSA做适当的裁剪、扩充和改造，并优化组合，犹如玩车的行家里手，有DIY的能力和乐趣。
探索DSA的优化极限，能够完成从内部优化到外部封装的整个过程，则是设计师与工程师的任务与要求。

因此只要定位清楚，心态平和，一些基本功相对薄弱的学生学习DSA是完全可行的。我讲授的另一门课程《计算几何》是面向本专业研究生的，但我对自己的要求却是，（在以上第一、二个层面上）要让高中生能听懂。如果实在遇到不能很快弄懂的，不妨直接跳过。好在，我会尽力使用初等的方法，并将相关的结论简明扼要地概括出来，如不愿推敲，先记下就是了，并不影响你继续前行。

最后，数据结构是典型的大学学习模式，不像中学，所有知识点都须面面俱到。学习的过程中，应更加关注自己“学到了什么”，而不是“什么还没学”。尽早地接触这种学习模式，相信对你日后的大学学习必有裨益。

课程大纲可以参见页面顶部的“Progress”

教材和配套习题解析可以在页面上方导航栏中的对应版块在线阅读

本课程所涉及的几乎所有代码，均以Visual Studio解决方案的形式汇编打包，共含50多个示例工程。读者可通过以下页面上的“示例代码”链接直接下载： http://dsa.cs.tsinghua.edu.cn/~deng/ds/dsacpp/
解压缩后，可在VS2008中打开dsacpp.sln，然后选择对应的工程、编译、运行。

微信用户请关注微信公众平台“THU数据结构MOOC”，课程的最新信息会通过此平台发布。

在微信中通过名称查找或者直接扫描以下二维码即可关注“THU数据结构MOOC”：

如果你不使用微信也没关系，重要的课程信息都会在课程公告中发布。

推荐的学习顺序：

1. C++语言程序设计基础
2. C++语言程序设计进阶
3. 数据结构
4. 然后就可以随便选了：软件工程、操作系统、网络技术与应用等

OJ是Online Judge（在线评测）的缩写，本课程的编程作业（占总成绩的40%）需要在该系统（http://dsa.cs.tsinghua.edu.cn/oj/）上自动评测。也就是你需要用同样的邮箱在OJ系统上注册并根据课程进度要求提交作业源代码。

非常遗憾地，目前只支持C/C++，正在探索支持其他语言的可能性（比如很多OJ都可以提交Java……看看别人家孩子）。

OJ系统使用的编译器是gcc 4.9.2,支持C++11。编程作业中只允许使用最基本的函数库，而不能使用STL、Boost等函数库。比如说map、vector等是属于STL，无法使用。事实上也很容易理解，数据结构要教会你怎么实现数据结构，如果都直接用别人写好的那怎么行呢？

将所有源代码（.cpp文件和.h文件等）直接打包成rar文件后提交即可，无需提交可执行程序。具体可以尝试一下Tutorial课堂，Tutorial课堂是帮助大家熟悉OJ平台和热身的课堂，在Tutorial课堂中提交的编程题不计入成绩，Tutorial课堂中目前有两个作业，其中第一个作业的若干道题纯粹是为了帮助大家熟悉作业提交过程，第二次作业中的习题有一定挑战性，欢迎大家尝试。

Honor Code是一个对自己作业的君子声明，你可以理解成安装软件的时候的那个"我同意此协议"。你不"同意此协议"就无法安装软件，你不提交HonorCode该次作业就不会被计分。顺便说句，故意抄袭他人代码并声称是自己的被视为可耻的行为。Report是作业报告，这是清华大学面授课堂的要求，大家可以不必提交Report。

对于"Wrong Answer": 请首先检查自己的程序是否符合题面的输入、输出格式要求，不要在输出里加多余的东西。因为系统会用给定的输入运行你的程序并将输出与正确答案比对，多余的输出会导致比对失败。

对于"Exceed Time Limit"和"Exceed Memory Limit": 程序运行超时和程序使用的内存超过限制，请从算法和编码两个角度进一步优化自己的程序。

事实上，“程序在我的机器上跑通过了”是个很不严格的说法，更严谨的说法是“程序在我的机器上用我的测例跑没出错”

而把程序放在OJ上跑的时候，OJ的测例则必然会与你的测例有不同之处——它可能有更庞（bao）大（li）的测例，也可能会是一些边（e）界（xin）测例。吾日三省吾身：边界情况未考虑乎？（Wrong Answer/Runtime Error）内存装不下乎？（Exceed Memory Limit）跑太慢乎？（Exceed Time Limit）

对应于后两种情况，优化是程序进步的阶梯，可能你需要一个更好的算法，也可能你的算法已经不错，只是差一个漂亮的实现。而对应于第一种情况，建议你测试更多测例以找出错误，事实上测试数据的构造也是课程训练的环节之一。我们也鼓励同学们互相交换测例以防微杜渐。

我们建议使用gcc编译器进行本地测试。对于非Windows用户gcc编译环境较容易配置，我们不再作过多说明。而对于Windows用户，我们推荐以下两种方式在本地配置gcc：MinGW与Cygwin

请先尝试换一个浏览器，若不是浏览器的问题，可向edx平台反映。

我们会提供下载，但由于网盘很不稳定，请密切关注讨论区里的学习资源汇总。

• 由不当言论引起的法律纠纷和其他相关责任自负。
• 不应出现与本课程无关的内容。
• 不得出现与本课程编程题目相关的代码。

特地补充一下，虽然我们禁止讨论区中出现与本课程题目相关的代码，但交流解题思路与测例则是被鼓励的。

在讨论区的讨论，我们使用的是Markdown语法，详情可以参见Markdown语法说明。特殊地，对于公式的输入，我们使用类似于如下的方式进行书写：

		\begin{equation}\
		\left( \sum_{k=1}^n a_k b_k \right)^2 \leq \left( \sum_{k=1}^n a_k^2 \right) \left( \sum_{k=1}^n b_k^2 \right) 
		\end{equation}
	

，效果如下：

北京时间每天晚上22:00-23:00是我们的集中答疑时间，我们将会在这一时间段内集中回答讨论区内的问题。如果同学日常生活比较繁忙，可以选择在这一时间段到讨论区查阅回复，而不必一直刷新讨论区页面“在线等，挺急的”。