计算机是现代社会中用于解决问题的重要工具，支撑这个工具高效运转的就是其后的各种系统程序、应用程序。图灵奖获得者N.Wirth写了一本经典著作“程序=算法+数据结构”。数据结构，是抽象的表示数据的方式；算法，则是计算的一系列有效、通用的步骤。算法与数据结构是程序设计中相辅相成的两个方面，是计算机学科的重要基石。

本课程将带领我们围绕着“算法+数据结构=程序”的思路，以问题求解为导向进行学习。希望能够帮助大家提高理论、抽象、设计的能力。在扎实的经典理论基础上，运用问题抽象、数据抽象、算法抽象来分析问题，应用适当的数据结构和算法来设计和实现相应的程序。通过课程学习，大家的抽象思维能力、问题求解能力将得到较大提升，编程能力和代码质量会有质的飞跃！

在求解实际问题方面，我们会学习到通过权衡时空和其他资源开销，利用数据结构来组织数据、设计高效的算法、完成高质量的程序以满足错综复杂的实际应用需要。

本课程采用张铭主编的国家“十一五”规划教材《数据结构与算法》（高等教育出版社）。适合计算机以及相关理工专业的本科生学习，建议先修过计算概论等课程，最好具备C++等面向对象的程序设计基础。对于具有C语言结构化程序设计基础的学生，本课程第0章补充了一些面向对象的基本内容。

课程所学到的内容会被利用到计算机科学后续的各个课程中，如操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等。希望可以为大家将来从事计算机相关的学习、研究和开发工作打下扎实的基础。

为积极响应国家低碳环保政策， 2021年秋季学期开始，中国大学MOOC平台将取消纸质版的认证证书，仅提供电子版的认证证书服务，证书申请方式和流程不变。

电子版认证证书支持查询验证，可通过扫描证书上的二维码进行有效性查询，或者访问 https://www.icourse163.org/verify，通过证书编号进行查询。学生可在“个人中心-证书-查看证书”页面自行下载、打印电子版认证证书。

完成课程教学内容学习和考核，成绩达到课程考核标准的学生（每门课程的考核标准不同，详见课程内的评分标准），具备申请认证证书资格，可在证书申请开放期间（以申请页面显示的时间为准），完成在线付费申请。

认证证书申请注意事项：

1. 根据国家相关法律法规要求，认证证书申请时要求进行实名认证，请保证所提交的实名认证信息真实完整有效。

2. 完成实名认证并支付后，系统将自动生成并发送电子版认证证书。电子版认证证书生成后不支持退费。

第一章 概论

1.1 课程介绍

1.2 问题求解

1.3 数据结构与抽象数据类型

1.4 算法特性及分类

1.5 算法效率与度量

1.6 补充 面向对象简介（选修）

1.7 补充 类的特殊成员（选修）

1.8 补充 模版函数与模版类（选修）

1.9 补充 输入输出流（选修）

2.0 教材勘误和源代码

第一章 概论 测验

第二章 线性表

2.1 线性结构

2.2 顺序表

2.3 链表

2.4 顺序表和链表的比较

第二章 线性表测验

第三章 栈与队列

3.1 栈

3.2 栈的实现方式

3.3 栈的应用

3.4 队列

3.5 队列的应用

第三章 栈与队列测验

第四章 字符串

4.1 字符串基本概念

4.2 字符串的存储与实现

4.3 字符串朴素匹配算法

4.4 KMP算法

第四章 字符串测验

第五章 二叉树（上）

5.1 二叉树的基本概念

5.2 二叉树的性质与抽象数据类型

5.3 二叉树的遍历

5.4 二叉树的存储结构

第五章 二叉树（上）测验

第五章 二叉树（下）

5.5 二叉搜索树

5.6 堆与优先队列

5.7 Huffman树及其应用

第五章 二叉树（下）测验

第六章 树

6.1 树的定义

6.2 树与二叉树的等价转换

6.3 树的抽象数据结构及树的遍历

6.4 树的链式存储结构

6.5 树的父指针表示法及其在并查集中的应用

6.6 树的顺序存储和K叉树

第六章 树测验

第七章 图

7.3 图的遍历

7.4 最短路径

7.5 最小生成树

7.1 图的概念和抽象数据类型

7.2 图的存储结构

第七章 图测验

第八章 内排序（上）

8.1 排序问题的基本概念

8.2 插入排序和Shell排序

8.3 选择排序和堆排序

8.4 交换排序（冒泡排序、快速排序）

第八章 内排序（上）测验

第八章 内排序（下）

8.5 归并排序

8.6 桶排序

8.7 基于静态链的基数排序

8.8 链式基数排序

8.9 索引排序

8.10 排序算法的时间代价

第八章 内排序（下）测验

第九章 外排序

9.1 文件组织

9.2 外排序

第九章 外排序测验

第十章 检索

10.1 检索的概念

10.2 基于线性表的检索

10.3 集合的检索

10.4 散列表的概念和散列函数

10.5 散列冲突处理

10.6 散列的实现及性能分析

第十章 检索测验

第十一章 索引

11.1 静态索引

11.2 倒排索引

11.3 B 树

11.4 B+ 树

11.5 位索引技术

11.6 红黑树

第十一章 索引测验

第十二章 高级数据结构（上）

12.1 多维数组

12.2 广义表

12.3 存储管理

第十二章 高级数据结构（上）测验

第十二章 高级数据结构（下）

12.4 Trie 树

12.5 AVL 树

12.6 伸展树

第十二章 高级数据结构（下） 测验

[1] 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008年 6月。普通高等教育“十一五”国家级规划教材。

Textbook: Ming Zhang, Tengjiao Wang, Haiyan Zhao, "Data Structures and Algorithms", Higher Education Press, 2008.

[2] 张铭，赵海燕，王腾蛟，《数据结构与算法实验教程》，高等教育出版社，2011年 1月。普通高等教育“十一五”国家级规划教材。

[3] 张铭、赵海燕、王腾蛟，《数据结构与算法－－学习指导与习题解析》，高等教育出版社，2005年 10月。 “十五”国家级规划教材配套参考书。

[4] S. Sahni ，《数据结构算法与应用—C++语言描述》 ，汪诗林等译，机械工业出版社，2000. 

[5] M. H. Alsuwaiyel, Algorithms Design Techniques and Analysis, 电子工业出版社影印，2003年1月。 

[6] T. H.Cormen, C. E.Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 高等教育出版社影印，2002年5月。 

[7] D. E.Knuth 著，苏运霖 译，《计算机程序设计艺术，第1卷基本算法》，国防工业出版社，2002年。 

[8] J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005.

[9] C. A. Shaffer, Data Structures and Algorithm Analysis in C++, Third Edition, Dover Publications., 2011.

[10] 王晓东，《算法设计与分析》 ，清华大学出版社，2003年1月。

[11] 课程源代码：https://media.openjudge.cn/upload/DSMooc/DSCode_ZhangWangZhao2008_06.rar