教学计划
本课程采用线上线下混合式教育模式进行,由于当前仍然属于建设期,因此资源将持续更新,恕不额外进行通告。本课程采用多种形式展开教学,主要包含如下几种模式。
教学内容:
理论教学章节按照教学周进行设计,总共包括17周,其中1-16周为理实一体化教学,第17周为综合习题选讲。本课程将全面介绍几种最重要的结构,包括线性表、堆栈、队列、树和图等的基本概念、基本原理和基本操作,同时也将介绍查询和排序这两种重要的复杂操作。在每一讲后面将给出建议的理论课程学时。
课堂互动:
教学过程中的即时测验,主要为理论客观题,包括单选题、多选题和判断题。课堂互动也提供有答案版和无答案版,其中有答案版本提供答案解析,为保证教学公平性,有答案版,将在学期末进行开放。
课程项目:
课程相关的完整项目案例,每个项目都将提供教学版(分步骤介绍)、学生版(分步骤介绍,但删去部分代码)。课程项目将持续进行增加和更新。
扩展知识:
数据结构相关的知识点,这部分内容将持续进行增加和更新。
教学周
课程内容
在线资源
作业及资料
1
09.18
《数据结构》课程导学
(1课时)
1. 课程基本信息
2. 课程组织形式
3. 课程作业与考核
4. 学习建议
第01讲 什么是数据结构?
(1课时)
1. 什么是数据结构?
2. 数据结构的基本概念
3. 数据结构的三要素
第02讲 什么是算法?
(2课时)
1. 算法的基本概念?
2. 算法的时间复杂度
3. 算法的空间复杂度
4. 数据结构求解问题的过程
5. 最大子列和问题
习题及实践:
[课堂互动01] 什么是数据结构
[课堂互动02] 什么是算法
[项目001] C/C++ 开发环境的安装和配置
[项目002] 晒一晒N的阶乘
[项目003] 多项式的时间复杂度
[项目004] 最大子列问题(建设中)
[可视化] 算法可视化展示 (cs.usfca)
2
09.25
第03讲 线性表的基本概念
(1课时)
1. 问题导入
2. 线性表的定义
3. 线性表的抽象数据类型
第04讲 线性表的顺序表示
(3课时)
1. 顺序表的定义
2. 顺序表的基本操作
习题及实践:
[课堂互动03] 线性表的基本概念
[课堂互动04] 线性表的顺序表示
[项目005] 顺序表的综合应用
3
国庆放假(9月29日-10月6日)
4
10.09
第05讲 线性表的链式表示
(4课时)
1. 线性表的链式表示
2. 单链表
3. 双向链表
4. 循环链表
5. 广义表和多重链表
习题及实践:
[课堂互动05] 线性表的链式表示
[项目006] 链表的综合应用
5
10.16
第06讲 线性表的应用及案例分析
(2课时)
1. 数列求和
2. 线性表元素的区间删除
3. 求链表倒数第n个元素
4. 线性表的合并
5. 有序表的合并
6. 一元多项式的运算
第07讲 数组和特殊矩阵
(2课时)
1. 数组的基本概念
2. 数组顺序存储实现
3. 特殊矩阵的压缩存储
习题及实践:
[课堂互动07] 数组和特殊矩阵
[项目007] 多项式加法运算(建设中)
[项目008] 迷宫问题(建设中)
专题:
数组地址转换 [video]
6
10.23
第08讲 堆栈
(2课时)
1. 堆栈的基本概念
2. 堆栈的顺序存储实现
3. 堆栈的链式存储实现
第09讲 队列
(2课时)
1. 队列的基本概念
2. 循环队列
3. 链队列
习题及实践:
[课堂互动08] 堆栈
[课堂互动09] 队列
[项目009] 栈和队列的综合应用
7
10.30
第10讲 串
(2课时)
1. 串的基本概念
2. BF匹配算法
3. KMP匹配算法
第11讲 树的基本概念(一)
(2课时)
1. 树的基本概念
2. 树的存储结构
3. 二叉树的基本概念
4. 二叉树的性质
习题及实践:
[课堂互动10] 串
[课堂互动11] 树的基本概念
8
11.06
第11讲 树的基本概念(二)
(2课时)
5. 二叉树的存储结构
6. 森林与二叉树的转换
习题及实践:
[课堂互动11] 树的基本概念
8
期中考试(第1-10讲)(2课时)
9
11.13
第12讲 树的遍历(一)
(2课时)
1. 二叉树的遍历
第12讲 树的遍历(二)
(2课时)
2. 二叉树遍历的相关性质
3. 二叉树遍历的应用
习题及实践:
[课堂互动12] 树的遍历
[项目010] 树的综合应用
10
11.20
第12讲 树的遍历(三)
(2课时)
4. 树和森林的遍历
5. 线索二叉树
第13讲 哈夫曼树及其应用
(2课时)
1. 树的路径长度
2. 哈夫曼算法和哈夫曼树
3. 哈夫曼编码
树的综合应用选讲
(0课时)
习题及实践:
[课堂互动12] 树的遍历
[课堂互动13] 哈夫曼树及其应用
11
运动会
12
12.04
第14讲 图的基本概念
(2课时)
1. 图的基本概念
2. 图的存储结构(邻接矩阵、邻接表、十字链表、邻接多重表)
3. 图的基本操作
第15讲 图的遍历
(2课时)
1. 图的遍历简介
2. 广度优先搜索
3. 深度优先搜索
习题及实践:
[课堂互动14] 图的基本概念
[课堂互动15] 图的遍历
13
12.11
第16讲 图的应用
(4课时)
1. 最小生成树(Prim算法、Kruskal算法)
2. 最短路径(Dijkstra算法、Flody算法)
3. 拓扑排序(AOV网)
4. 关键路径(AOE网)
习题及实践:
[课堂互动16] 图的应用
[项目011] 图的综合应用
[项目012] 六道空间理论(建设中)
14
12.18
第17讲 线性表的查找
(2课时)
1. 查找的基本概念
2. 顺序查找
3. 折半查找
4. 分块查找
第18讲 散列表
(2课时)
1. 哈希表
2. 哈希函数的构造
3. 处理冲突的方法
4. 基于哈希表的查找及其性能分析
习题及实践:
[课堂互动17] 线性表的查找
[课堂互动18] 散列表
15
12.25
第19讲 树表的查找
(4课时)
1. 二叉排序树
2. 平衡二叉树
3. 红黑树
4. B树和B+树
习题及实践:
[课堂互动19] 树表的查找
[项目013] 查找的综合应用
16
01.01
第20讲 内部排序(一)
(4课时)
1. 排序的基本概念
2. 插入排序(直接插入排序、折半插入排序、希尔排序)
3. 交换排序(冒泡排序、快速排序)
4. 选择排序(简单选择排序、堆排序)
习题及实践:
[课堂互动20] 内部排序
[项目014] 排序的综合应用
17
01.08
第20讲 内部排序(二)
(2课时)
5. 归并排序和基数排序
6. 各种内部排序算法的对比
第21讲 外部排序
(0课时-自学)
1. 外部排序的基本方法
2. 多路平衡归并的实现
3. 置换-选择排序
4. 最佳归并树
期末习题选讲
(2课时)
习题及实践:
[项目015] 银行排队问题(建设中)
[项目016] 畅通工程问题(建设中)
18
期末考试