课程概述

数据结构与算法课程是计算机大类相关专业的的一门重要专业基础课，它的核心位置毋庸置疑，既是操作系统、软件工程、数据库概论、编译技术等课程的基础，同时也是从事计算机相关工作必须掌握的专业基础素养。本课程旨在讲解实用的数据结构与算法，包括线性表、栈和队列、树和二叉树、图等基本数据结构；AVL树、红黑树、Merkle树、Trie树等复杂数据结构；以及检索和排序等重要操作算法。点明数据结构应用的多个领域以及课程间的关联。例如Linux中用到的双循环链表数据结构，编译原理中的表达式计算、区块链中用到的Merkle树、人工智能词汇切分中用到的Trie树，让大家感受数据结构的博大精深和无限魅力。

通过本课程的学习，使学习者能够针对具体问题选择合适的数据结构，以合理地组织数据、有效地存储和处理数据，以锻炼数据抽象能力；使学习者能够将数据结构和应用付诸编程实践，正确地设计、编制高效算法，并对算法进行分析和评价，以锻炼良好的程序设计开发技能；使学习者能够应用工程知识和专业背景知识分析复杂工程问题，进行复杂程序设计的训练，解决工程实践问题，以锻炼学习者的工程实践能力；

本课程在每章开头视频，通过两个关键词进行章节主要内容概览。课程视频侧重理论和实践紧密结合，按照基本结构操作－算法讲解与实现－数据结构基本应用－应用扩展实践的路线讲解，不但锻炼你的抽象思维能力，更侧重动手实践能力的培养，注重基本数据结构的算法设计与实现以及它们的应用场景，在高度抽象和高度具体之间搭起一座桥梁。200多个视频片段有助于你自主地碎片化学习；CodeByCode视频直接在开发环境中讲解代码，使你“所见即所得”，减少起步的挫败感、增加自信；课后作业讲解视频进一步提升你的算法设计和动手能力。

本课程采用张瑞霞、张敬伟编写的21世纪高等学校规划教材《数据结构与算法》（清华大学出版社）。适合高等院校计算机相关专业的本科生学习，也适合高职院校计算机相关专业的学生学习，算法采用C语言描述，要求学习者具有C语言程序设计基础即可。

证书要求

本课程的学习环节包括章节测试、编程练习、课程讨论和期末测试等四部分组成，其成绩比例分别占25%，30%，5%和40%。


预备知识

计算机基础和C语言

授课大纲

第1章 绪论

1.0绪论导学

1.1为什么学习数据结构

1.2抽象数据类型

1.3数据结构

1.4算法与算法效率

1.5算法分析

第2章 线性表

2.0线性表导学

2.1线性表的概念

2.2顺序表的建立和判空

2.3顺序表的插入和删除

2.4顺序表的查找定位

 2.5单链表的建立与判空

2.6单链表的查找

2.7单链表的插入

2.8单链表的删除

2.9单循环链表

2.10双链表和双循环链表

2.11线性表的应用：一元多项式的表示和运算

2.12线性表的应用：Josephus问题

2.13 动态链接库

2.14 linux内核链表

第3章 栈与队列

3.0栈和队列导学

3.1栈和队列的概念

3.2顺序栈

3.3链栈

3.4栈的应用：进制转换

3.5栈的应用：括号匹配

3.6栈的应用：栈与递归

3.7栈的应用：迷宫

3.8栈的应用：表达式求值

3.9循环队列

3.10链队列

3.11队列的应用：迷宫

3.12队列的应用：农夫过河

3.13双端队列

 第4章 二叉树

4.0二叉树导学

4.1二叉树的概念  

4.2二叉树的数学性质  

4.3二叉树的深度优先遍历

4.4二叉树的广度优先遍历

4.5二叉树的重构

4.6二叉树的交叉遍历

4.7 二叉树的顺序存储

 4.8二叉树的链式存储

4.9二叉树的建立和遍历（递归算法）

4.10二叉树的建立和遍历（非递归算法）

4.11二叉树的其他操作

4.12线索二叉树

4.13二叉树的应用：哈夫曼树与哈夫曼编码

4.14树和森林

第5章 搜索树

5.0搜索树导学

5.1二分查找判定树

5.2二叉排序树的基本概念

5.3二叉排序树的查找

5.4二叉排序树的插入

5.5二叉排序树的删除

5.6平衡二叉树的概念

5.7平衡二叉树的实例

5.8平衡二叉树的四种调整和两个基本操作

5.9AVL的插入操作

5.10AVL的删除操作

第6章 图

6.0图导学

6.1图的基本概念和抽象数据类型定义

6.2图的存储表示  

6.3图的遍历    

6.4 Prim算法

6.5 Kruskal算法 

6.6 Dijkstra算法

6.7拓扑排序

6.8关键路径

6.9六度空间问题

6.10中国邮递员问题

第7章字典

7.0字典导学

7.1字典的基本概念

7.2跳跃链表的基本概念

7.3跳跃链表的建立和查找

7.4跳跃链表的插入和删除

7.5散列表的基本概念

7.6散列函数和冲突

7.7散列表的建立、查找和删除

7.8Merkle树的基本概念

7.8Merkle树的建立和查找比较

 第8章 排序

8.0排序导学

8.1 排序的基本概念

8.2插入排序 （直接插入、二分插入和shell排序）

8.3选择排序 (直接选择和堆排序)

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

8.5基数排序

8.6归并排序

8.7排序算法的比较

 第9章 字符串

9.0字符串导学

9.1字符串的基本知识

9.2朴素的模式匹配算法

9.3KMP算法


参考资料

[1]张瑞霞、张敬伟 编著. 数据结构与算法[M]. 北京：清华大学出版社，2018.

[2]张瑞霞、唐麟 编著. 数据结构与算法实验教程. 北京：清华大学出版社，2018.

[3]张乃孝、陈光、孙猛 编著. 算法与数据结构：C语言描述(第3版)[M]. 北京：高等教育出版社，2016.

[4]邓俊辉 编著.数据结构（C++语言版）(第3版)[M]. 北京：清华大学出版社，2016.