数据结构

课程概况

“数据结构”是计算机科学与技术专业、软件工程专业甚至于其它电气信息类专业的重要专业基础课程。它所讨论的知识内容和提倡的技术方法，无论对进一步学习计算机领域的其它课程，还是对从事大型信息工程的开发，都是重要而必备的基础。
程序设计解决问题往往有多种方法，且不同方法之间的效率可能相差甚远。程序的时间和空间效率，不仅跟数据的组织方式有关，也跟处理流程的巧妙程度有关。本课程将介绍并探讨有关数据组织、算法设计、时间和空间效率的概念和通用分析方法，帮助学员学会数据的组织方法和一些典型算法的实现，能够针对问题的应用背景分析，选择合适的数据结构，从而培养高级程序设计技能。

注意：本课程只涉及最基础的数据结构和与之关联的最基本的算法，更多更复杂的数据结构和经典的解决优化问题的算法，将在后续课程中介绍。

本课程的特点是，对每一种重要的经典数据结构，我们都会从实际应用问题出发，导出其定义、实现（存储）方法以及操作实现，并以更丰富的综合应用案例和练习题帮助学员增强对理论的感性认识，从而明白这些数据结构为什么存在以及在什么情况下可以最好地解决什么样的问题。

坚持完成本课程学习、并按照要求完成所有练习的学员，应该具备了PAT（Programming Ability Test）甲级需要的所有基础知识，辅以充分的英语阅读能力和熟练的编程能力，应可以取得优良成绩。

课程大纲

第一讲基本概念（1:15:26）[陈越]
1.1 什么是数据结构（4节共32:43）
1.2 什么是算法（3节共22:41）
1.3 应用实例：最大子列和问题（3节共20:02）

第二讲线性结构（2:19:00）[何钦铭]
2.1 线性表及其实现(6小节共45:04)
2.2 堆栈(4小节共39:51)
2.3 队列(2小节共15:45)
2.4 应用实例：多项式加法运算(1小节10:37)
小白专场：多项式乘法与加法运算- C实现（3小节共27:43）

第三讲树(上) （1:50:08）[何钦铭]
3.1 树与树的表示(5小节共38:54)
3.2 二叉树及存储结构(2小节共16:43)
3.3 二叉树的遍历(4小节共37:02)
小白专场：树的同构 - C语言实现（2小节共17:29）

第四讲树（中）（1:06:31）[何钦铭]
4.1 二叉搜索树(3小节共20:57)
4.2 平衡二叉树(2小节共22:53)
小白专场：是否同一棵二叉搜索树- C实现（3小节共22:41）
线性结构之习题选讲[陈越]：Reversing Linked List（3小节共13:08）

第五讲树（下）（1:53:28）[何钦铭]
5.1 堆（4小节共30:05）
5.2 哈夫曼树与哈夫曼编码（3小节共19:52）
5.3 集合及运算（2小节共12:57）
小白专场：堆中的路径 - C语言实现（1小节共7:51）
小白专场[陈越]：File Transfer - C语言实现（4小节共42:43）

第六讲图（上）（1:29:32）[陈越]
6.1 什么是图（3小节共24:02）
6.2 图的遍历（4小节共22:22）
6.3 应用实例：拯救007（1小节共14:40）
6.4 应用实例：六度空间（1小节共8:06）
小白专场：如何建立图- C语言实现（6小节共20:22）

第七讲图（中）（2:11:35）[陈越]
树之习题选讲-Tree Traversals Again（2小节共12:16）
树之习题选讲-Complete Binary Search Tree（3小节共25:47）
树之习题选讲- Huffman Codes（3小节共18:11）
7.1 最短路径问题（6小节共56:38）
小白专场：哈利•波特的考试- C语言实现（4小节共18:43）

第八讲图（下）（57:02）[陈越]
8.1 最小生成树问题（2小节共20:16）
8.2 拓扑排序（2小节共27:57）
图之习题选讲-旅游规划（2小节共8:49）

第九讲排序（上）（1:11:44）[陈越]
9.1 简单排序（冒泡、插入）（4小节共23:26）
9.2 希尔排序（1小节共9:29）
9.3 堆排序（2小节共10:27）
9.4 归并排序（3小节共28:22）

第十讲排序（下）（54:20）[陈越]
10.1 快速排序（4小节共25:25）
10.2 表排序（2小节共12:41）
10.3 基数排序（3小节共12:13）
10.4 排序算法的比较（1小节共4:01）

第十一讲散列查找（1:43:39）[何钦铭]
11.1 散列表(2小节共13:43)
11.2 散列函数的构造方法(2小节共13:05)
11.3 冲突处理方法(6小节共36:26)
11.4 散列表的性能分析(1小节10:26)
11.5 应用实例:词频统计(1小节6:01)
小白专场[陈越]：电话聊天狂人- C语言实现（4小节共23:58）

第十二讲综合习题选讲（30:12） [陈越]
习题选讲-Insert or Merge（2小节共11:51）
习题选讲-Sort with Swap(0,*)（2小节共11:06）
习题选讲-Hashing - Hard Version（1小节共7:15）

预备知识

学过一门编程语言，具有一定编程基础，即可理解主要内容，因为数据结构本质上是不依赖于编程语言的，且编程练习平台可以接受十余种语言代码的提交。但由于算法描述多用类似C语言的伪码，所以如果学过C语言会更容易接受。
如果还对计算机处理离散结构的基本理论和方法有较为系统的理解（即预修“离散数学”），则对更扎实地掌握本课程内容有很大帮助，但并不是必须的。

证书或学分

这门课的一个重要目的是，帮助大家明白一些经典的数据结构为什么存在、以及在什么情况下可以最好地解决什么样的问题。要做到这一点，非自己动手解决问题不可。
与程序设计课程类似，每一周的课后，我们都留有两类练习，一类是在线完成的选择、是非或填空题，以下称作“在线练习”；一类是在PAT（Programming Ability Test）网站（http://pat.zju.edu.cn/）上的编程练习题，以下称作“编程练习”。你可以自己注册帐户，随时进行练习，并不限于发布练习的时段。注意：你的PAT账号所用的电子邮箱必须和中国MOOC的账号所用的相同。如果忘记帐号或密码，请用你注册时登记的电子邮箱发求助信到 chenyue@zju.edu.cn。
课程过半时，我们还会安排一次期中考试，是在线完成的选择、是非或填空题，不包括编程题。期中考试在一周内用连续的60分钟完成均有效。
最后，在期末后一周，我们会安排一次在线期末考试，需要在某一天内用连续的120分钟完成。

本课程获得证书的资格，由以下因素决定：
在线练习：必须完成全部在线练习。成绩无所谓，但是留有未做的练习则不能获得证书；
编程练习：必须在期末考试前获得整个课程的全部练习题分数的30%，才能获得证书，但是分数不会带入总评成绩；
期中考试：得分占总评分数的40%；
期末考试：得分占总评分数的60%；
满足条件1和2并且总评成绩达到60分及以上者，可以获得本课程的合格证书。
在课程结束后的12个月内，参加一次PAT甲级考试，获得70分及以上者，可以获得优秀证书。