课程简介
计算机是现代社会中用于解决问题的重要工具，支撑这个工具高效运转的就是其后的各种系统程序、应用程序。图灵奖获得者N.Wirth写了一本经典著作“程序=算法+数据结构”。数据结构，是抽象的表示数据的方式；算法，则是计算的一系列有效、通用的步骤。算法与数据结构是程序设计中相辅相成的两个方面，是计算机学科的重要基石。
本课程将带领我们围绕着“算法+数据结构=程序”的思路，以问题求解为导向进行学习。希望能够帮助大家提高理论、抽象、设计的能力。在扎实的经典理论基础上，运用问题抽象、数据抽象、算法抽象来分析问题，应用适当的数据结构和算法来设计和实现相应的程序。通过课程学习，大家的抽象思维能力、问题求解能力将得到较大提升，编程能力和代码质量会有质的飞跃！
在求解实际问题方面，我们会学习到通过权衡时空和其他资源开销，利用数据结构来组织数据、设计高效的算法、完成高质量的程序以满足错综复杂的实际应用需要。
本课程采用张铭主编的国家“十一五”规划教材《数据结构与算法》（高等教育出版社）。适合计算机以及相关理工专业的本科生学习，建议先修过计算概论等课程，最好具备C++等面向对象的程序设计基础。对于具有C语言结构化程序设计基础的学生，本课程第0章补充了一些面向对象的基本内容。
课程所学到的内容会被利用到计算机科学后续的各个课程中，如操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等。希望可以为大家将来从事计算机相关的学习、研究和开发工作打下扎实的基础。
课程大纲
概论
1.1课程介绍
1.2问题求解
1.3数据结构与抽象数据类型
1.4算法特性及分类
1.5算法效率与度量
1.6补充面向对象简介（选修）
1.7补充类的特殊成员（选修）
1.8补充模版函数与模版类（选修）
1.9补充输入输出流（选修）
第一章概论测验
线性表
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.4KMP算法
第四章字符串测验
二叉树（上）
5.1二叉树的基本概念
5.2二叉树的性质与抽象数据类型
5.3二叉树的遍历
5.4二叉树的存储结构
第五章二叉树（上）测验
二叉树（下）
5.5二叉搜索树
5.6堆与优先队列
5.7Huffman树及其应用
第五章二叉树（下）测验
树
6.1树的定义
6.2树与二叉树的等价转换
6.3树的抽象数据结构及树的遍历
6.4树的链式存储结构
6.5树的父指针表示法及其在并查集中的应用
6.6树的顺序存储和K叉树
第六章树测验
图
7.1图的概念和抽象数据类型
7.2图的存储结构
7.3图的遍历
7.4最短路径
7.5最小生成树
第七章图测验
内排序（上）
8.1排序问题的基本概念
8.2插入排序和Shell排序
8.3选择排序和堆排序
8.4交换排序（冒泡排序、快速排序）
第八章内排序（上）测验
内排序（下）
8.5归并排序
8.6分配排序和索引排序
8.7排序算法的复杂度分析和总结
第八章内排序（下）测验
外排序
9.1文件组织
9.2外排序
第九章外排序测验
检索
10.1检索的概念
10.2基于线性表的检索
10.3集合的检索
10.4散列表的概念和散列函数
10.5散列冲突处理
10.6散列的实现及性能分析
第十章检索测验
索引
11.1静态索引
11.2倒排索引
11.3B树
11.4B+树
11.5位索引技术
11.6红黑树
第十一章索引测验
高级数据结构（上）
12.1多维数组
12.2广义表
12.3存储管理
第十二章高级数据结构（上）测验
高级数据结构（下）
12.4Trie树
12.5AVL树
12.6伸展树
第十二章高级数据结构（下）测验
1.1课程介绍
1.2问题求解
1.3数据结构与抽象数据类型
1.4算法特性及分类
1.5算法效率与度量
1.6补充面向对象简介（选修）
1.7补充类的特殊成员（选修）
1.8补充模版函数与模版类（选修）
1.9补充输入输出流（选修）
第一章概论测验
线性表
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.4KMP算法
第四章字符串测验
二叉树（上）
5.1二叉树的基本概念
5.2二叉树的性质与抽象数据类型
5.3二叉树的遍历
5.4二叉树的存储结构
第五章二叉树（上）测验
二叉树（下）
5.5二叉搜索树
5.6堆与优先队列
5.7Huffman树及其应用
第五章二叉树（下）测验
树
6.1树的定义
6.2树与二叉树的等价转换
6.3树的抽象数据结构及树的遍历
6.4树的链式存储结构
6.5树的父指针表示法及其在并查集中的应用
6.6树的顺序存储和K叉树
第六章树测验
图
7.1图的概念和抽象数据类型
7.2图的存储结构
7.3图的遍历
7.4最短路径
7.5最小生成树
第七章图测验
内排序（上）
8.1排序问题的基本概念
8.2插入排序和Shell排序
8.3选择排序和堆排序
8.4交换排序（冒泡排序、快速排序）
第八章内排序（上）测验
内排序（下）
8.5归并排序
8.6分配排序和索引排序
8.7排序算法的复杂度分析和总结
第八章内排序（下）测验
外排序
9.1文件组织
9.2外排序
第九章外排序测验
检索
10.1检索的概念
10.2基于线性表的检索
10.3集合的检索
10.4散列表的概念和散列函数
10.5散列冲突处理
10.6散列的实现及性能分析
第十章检索测验
索引
11.1静态索引
11.2倒排索引
11.3B树
11.4B+树
11.5位索引技术
11.6红黑树
第十一章索引测验
高级数据结构（上）
12.1多维数组
12.2广义表
12.3存储管理
第十二章高级数据结构（上）测验
高级数据结构（下）
12.4Trie树
12.5AVL树
12.6伸展树
第十二章高级数据结构（下）测验