教案数据结构.docx
《教案数据结构.docx》由会员分享，可在线阅读，更多相关《教案数据结构.docx（26页珍藏版）》请在冰点文库上搜索。
教案数据结构
XX职业技术学院
——学年第二学期
教案
学科：
数据结构/嵌入式应用算法基础
系部：
电子与信息技术系
教研室：
计算机教研室
授课班级：
11软件工程/11嵌入式应用；
任课教师：
江门职业技术学院教案
授课时间
第1周
授课地点
实训B208
课程类型
理论课
授课题目
概述
授课班级
教学目的
与
教学要求
1什么是数据结构
2基本概念和术语
3算法和算法分析
重点与难点
算法分析
教学方法
手段（教具）
讲授法
主要内容
基本概念和术语
参考资料
精品课程网站:
课后作业与
思考题
P121.1;1.2
教学后记
教学过程
时间分配
1.1什么是数据结构
举例说明数据结构课程要解决的问题
数据结构课程的创建
数据结构课程所处的地位
1.2基本概念和术语
基本概念和术语：
数据、数据元素、数据对象、数据结构等
数据结构的分类
数据结构的二元组表示
抽象数据类型的概念和三元组表示
1.3算法和算法分析
算法的概念和5个重要特性
算法设计的4个要求
算法效率的度量：
时间复杂度
江门职业技术学院教案
授课时间
第2周；第3周
授课地点
课程类型
理论课
授课题目
线性表
授课班级
教学目的
与
教学要求
熟练线性表的基本特征和基本运算
重点与难点
线性表的插入与删除
教学方法
手段（教具）
讲授法
主要内容
数组的基本特点及寻址方式
线性数据结构的基本特征和基本运算
参考资料
精品课程网站:
课后作业与
思考题
P372.4;2.5;2.6;2.7
教学后记
教学过程
时间分配
2.1线性表的类型定义
●线性表的定义和相关术语
●线性表的抽象数据类型定义
●举例
2.2线性表的顺序表示和实现
●线性表的顺序表示方式
●线性表的动态分配顺序存储结构
●线性表顺序表示方式下的操作：
InitList_Sq
ListInsert_Sq
ListDelete_Sq
LocateElem_Sq
MergeList_Sq
结合第一章内容，分析上述算法的时间复杂度
江门职业技术学院教案
授课时间
第3周
授课地点
课程类型
理论课
授课题目
线性表
授课班级
教学目的
与
教学要求
熟练掌握以下内容:
单链表的结构特点、基本运算并能设计简单算法
循环链表的结构特点、基本运算并能设计简单算法
重点与难点
双链表插入、删除运算的算法
利用链接结构的特点设计有效算法，解决与链表结构相关的应用问题
教学方法
手段（教具）
讲授法
主要内容
单链表的结点形式、组织方法和特点
单链表的基本运算和相应的算法
循环链表的组织方法和基本运算算法
顺序表与链表比较，各自的优、缺点
链表的应用
参考资料
精品课程网站:
课后作业与
思考题
P372.4;2.5;2.6;2.7
教学后记
教学过程
时间分配
链表基本结构结构讨论
静态链表：
定义及示意图
动态链表：
详细介绍链表的相关知识，链表的类型说明及示意图。
带头结点的链表结构示意图
单链表上运算的实现：
初始化链表
（思考题）链表不带头结点时的初始化算法。
求链表长度
按序号取元素结点（算法流程图）
按值查询元素（算法流程图）
插入（示意图）
删除（示意图）
链表的构造（算法的基本框架，.尾插法建立链表的算法，.头插法建立链表的算法）
链表结构的应用：
列举若干求解实例
5.4其它链表结构：
单循环、带尾指针的单循环链表，双链表、双循环链表结构讨论，运算实现的变化讨论。
江门职业技术学院教案
授课时间
第4周
授课地点
课程类型
理论课
授课题目
堆栈和队列
授课班级
教学目的
与
教学要求
掌握堆栈的有关操作;
理解队列的定义、特性和运算；理解队列的顺序存储实现及其性能分析；理解循环队列的背景和实现方法。
重点与难点
堆栈的应用
教学方法
手段（教具）
讲授法
主要内容
栈的定义和运算；栈的C描述、顺序存储结构及运算实现；栈在表达式求解中的作用。
队列的定义和运算；队列的C描述、顺序存储结构以及运算实现
参考资料
精品课程网站:
课后作业与
思考题
P58
3.1;3.2;3.3
教学后记
教学过程
时间分配
3.1.1栈的定义和运算
栈的定义及相关概念，栈的示意图
栈的特征
栈的基本运算和C描述（注意几个关键问题的细节讨论）：
（1）初始化栈
（2）判断栈是否为空
（3）取栈顶元素值
（4）入栈
（5）出栈
（6）判断栈是否为满
初始化的讨论，函数返回值的方法，错误信息类型的引入，私有和公用属性的讨论。
3.1.2顺序栈
栈的顺序存储结构
顺序栈，示意图
顺序栈上运算的实现（结合示意图分析算法思想，然后写出算法）
3.1.3栈的应用
举出若干应用实例，说明栈在软件设计中的广泛应用。
栈的基本应用实例：
表达式的计算，从软件技术的发展到表达式的计算的介绍，表达式计算方法的讨论（以示意图表现计算过程）。
3.1.2队列的定义和运算
队列
队列的特性
队列示意图
队尾，队头，入队和出队
队列的基本运算和C++描述：
（1）初始化队列
（2）判队列是否为空
（3）取队头元素
（4）入队
（5）出队
（6）判队列是否为满
基本讨论与栈类似。
3.2顺序队列和循环队列
队列的顺序存储结构
顺序队列，示意图
由顺序队列中运算的实现可能出现“假溢出”，引入循环队列（示意图）。
提出问题：
对循环队列，如何判断队列的满和空的状态？
解决方法：
设置一个入队（出队）标志；或者少用一个元素空间。
循环队列中运算的实现（结合示意图讲解）。
江门职业技术学院教案
授课时间
第5周
授课地点
教C504
教D502
课程类型
理论课
授课题目
串
授课班级
07软件工程；
07信息管理
教学目的
与
教学要求
理理解串的相关概念，串的基本和常用运算的定义，理解串的两种顺序存储方式，能实现有关运算。
重点与难点
串的两种顺序存储方式，实现有关运算。
教学方法
手段（教具）
讲授法
主要内容
串的概念、运算、存储结构及运算的实现。
参考资料
精品课程网站:
课后作业与
思考题
P76
4.1;4.2;4.3;4.4
教学后记
教学过程
时间分配
串的定义
串名，串值，串的长度，空串，子串（举例说明）
串的基本运算：
（1）赋值
（2）求长度
（3）连接
（4）求子串
（5）串比较（比较是否相等，比较大小）
串的常用运算：
（6）插入
（7）删除
串的存储：
顺序串，链串（结点大小的概念，示意图）
举例说明链串运算的实现。
江门职业技术学院教案
授课时间
第6，7，8周
授课地点
教C504
教D502
课程类型
理论课
授课题目
树和二叉树
授课班级
07软件工程；
07信息管理
教学目的
与
教学要求
理解树和二叉树的定义及相关术语；理解二叉树的五个性质及相关概念；理解二叉树的两种存储结构的形式、描述及特点，理解二叉树的遍历运算，并能综合应用理解树和森林的存储结构及其描述，树（森林）与二叉树的相互转换，树（森林）的遍历算法；理解树模型在软件设计中的作用；理解哈夫曼树的有关概念、应用及构造。
重点与难点
有关树和二叉树的算法。
教学方法
手段（教具）
讲授法
主要内容
树和二叉树的概念，二叉树的性质和存储方法，二叉树的三种遍历算法和线索化概念及算法，树的存储，二叉树与树（森林）的相互转换，哈夫曼树。
参考资料
精品课程网站:
课后作业与
思考题
P146
6.1;6.2;6.3;6.4;6.5;6.7;6.8;6.18;6.22
教学后记
教学过程
时间分配
7.1树的定义和运算
举出若干现实生活和软件设计中的树形结构的实例，引入树的概念。
树，根，子树
几种常见的表示树结构的形式：
（1）图形表示法
（2）嵌套集合表示法
（3）凹入表表示法
（4）广义表表示法
与树有关的概念：
结点的度，叶子结点（终结点），分支结点（非终结点，内部结点），树的度；
孩子结点，双亲结点（父结点），兄弟结点，祖先结点和后代结点；
层次，树的高度（深度）；
有序树，无序树，森林。
树（森林）的基本运算：
（1）初始化树
（2）插入子树
（3）插入兄弟结点
（4）查询根结点
（5）查询父结点
（6）查询孩子结点
（7）查询兄弟结点
由树和森林的存储结构引入二叉树。
7.2二叉树的定义、性质和存储
二叉树的定义，左、右子树，示意图
举例说明树和二叉树的区别
二叉树的五种基本形态
二叉树的性质：
（较简单直观的性质，可以不给出证明。
）
性质1：
在二叉树的第i层上的结点数≤2i-1（i>0）。
性质2：
深度为k的二叉树的结点数≤2k-1（k>0）。
性质3：
对任一棵非空的二叉树T，如果其叶子数为n0，度为2的结点数为n2，则有下面的关系式成立：
n0=n2+1。
（证明）
满二叉树，完全二叉树的定义
性质4：
有n个结点的完全二叉树（n>0）的深度为
+1。
性质5：
在编号的完全二叉树中，各结点的编号之间的关系为：
编号为i的结点如果存在左孩子，则其编号为2i，如果存在右孩子，则其编号为2i+1，如果存在父结点，则其编号为
。
（提出并讲解一个与二叉树的性质）相关的例题。
二叉树的存储结构：
·顺序存储结构
按完全二叉树的编号次序进行，示意图，缺点：
空间的浪费，引入动态链表结构。
·二叉链表存储结构
二叉链表，相关描述，示意图。
7.3二叉树的遍历
基本遍历方法讨论：
先序遍历，中序遍历，后序遍历。
详细讲解几种算法的思想。
遍历算法的求解过程，举出实例：
·对给定二叉树，分别写出它的先序、中序和后序序列。
（结合示意图分步讲解）
·已知二叉树的先（后）序和中序序列，试构造出相应的二叉树。
（求解过程示意图）
遍历算法的实现：
·先序遍历算法
·中序遍历算法
·后序遍历算法
为加深学生对递归形式的遍历算法的理解，举例说明遍历算法的执行过程（遍历过程示意图）。
二叉树遍历算法的应用：
二叉树遍历算法的简单应用：
对二叉树遍历算法适当修改，便可得到许多问题的求解算法。
二叉树遍历算法思想的应用：
法形式较繁杂的递归算法的编写、阅读及证明。
江门职业技术学院教案
授课时间
第9，10周
授课地点
教C504
教D502
课程类型
理论课
授课题目
图
授课班级
07软件工程；
07信息管理
教学目的
与
教学要求
理解图的相关概念、图的存储结构；熟练掌握图的两种遍历算法（深度优先搜索遍历和广度优先搜索遍历），并能灵活应用；熟练掌握两种求解最小生成树的算法（Prim算法和Kruskal算法）；熟练掌握拓扑排序算法和关键路径算法，并能灵活应用；熟练掌握两种最短路径算法（Dijkstra算法和Floyd算法），并能灵活应用。
重点与难点
图的两种遍历算法以及各应用问题的求解算法。
教学方法
手段（教具）
讲授法
主要内容
图的相关概念、存储结构、图的遍历、最小生成树、拓扑排序和关键路径、最短路径。
参考资料
精品课程网站:
课后作业与
思考题
P191
7.1;7.3;7.4;7.5;7.6;7.7;7.9;7.10
教学后记
教学过程
时间分配
8.1图结构的定义、相关术语和运算
结合示意图讲解：
图
顶点，弧/边
无向图，有向图，带权图（网络）
无向完全图，有向完全图，子图
邻接，邻接点，度，入度，出度
路径，简单路径，回路（环），简单回路
（无向）连通图，连通分量，强连通图
（无向）树，有向树。
图的基本运算
8.2图的存储结构
邻接矩阵：
无向图、有向图及带权图的邻接矩阵，示意图
简单介绍采用邻接矩阵时基本运算的算法思想。
由邻接矩阵存在的不足引入邻接表。
邻接表：
无向图、有向图及带权图的邻接表，有向图的逆邻接表，示意图
简单介绍采用邻接表时基本运算的算法思想。
8.3图的遍历
1．深度优先搜索遍历
基本遍历算法的描述
深度优先搜索遍历（dfs）算法描述，示意图
执行过程，顶点访问序列，深度遍历生成树
深度优先搜索遍历算法：
详细讲述算法思想，给出算法的实现。
深度遍历算法的应用：
举例讨论。
2．广度优先搜索遍历
广度优先搜索遍历算法描述
广度优先搜索遍历（bfs）算法描述，示意图
执行过程，顶点访问序列，广度遍历生成树
广度遍历算法：
详细讲述算法思想，给出算法的实现。
广度遍历算法应用实例
8.4最小生成树
从现实中的问题引入最小生成树。
最小生成树的定义，如何构造最小生成树？
分别介绍两种算法。
1．Prim算法
Prim算法的求解思想
求解实例，示意图
算法的实现
2．Kruskal算法
Kruskal算法的求解思想
求解实例，示意图
算法的实现。
8.5拓扑排序
有向无环图的应用：
两个问题：
拓扑排序、关键路径。
工程，子工程（活动），活动之间的制约关系
工程问题：
工程能否顺利进行？
用图（AOV网）来表示工程，判断工程能否顺利进行等价于判断AOV网中是否存在有向回路。
如何判断AOV网中是否存在有向回路？
——拓扑排序。
拓扑排序、拓扑序列的概念
拓扑排序的方法步骤，举实例说明，示意图。
拓扑排序算法及实现。
8.6最短路径
1．从单个顶点到其余各顶点之间的最短路径：
Dijkstra算法
用Dijkstra算法求解从单个顶点到其余各顶点之间的最短路径的求解方法，举实例说明求解过程，结合示意图讲解。
讨论Dijkstra算法的实现，给出算法描述。
2．各顶点之间的最短路径：
FLOYD算法
算法思想，求解实例分析，算法描述，算法分析
江门职业技术学院教案
授课时间
第11周
授课地点
课程类型
理论课
授课题目
查找
授课班级
教学目的
与
教学要求
理解查找的相关概念，理解简单顺序查找、二分查找、分块有序表的查找算法的算法及性能分析；理解二叉排序树的定义、特性和查找算法，二叉排序树的构造、插入结点的算法和删除结点的实现方法；
重点与难点
二分查找，二叉排序树的构造，
教学方法
手段（教具）
讲授法
主要内容
查找的相关概念，顺序表中的顺序查找、有序表上的二分查找、分块有序表上的查找；二叉排序树构造、及查找运算；
参考资料
精品课程网站:
课后作业与
思考题
P221
8.2;8.3;8.4;8.5
教学后记
教学过程
时间分配
.1查找运算的定义和相关概念
查找，查找表
关键字（键），主关键字，次关键字
查找算法的时间性能，查找长度
9.2顺序表的查找
顺序表查找的问题描述
1．简单顺序查找
简单顺序查找的算法思想，算法的实现（算法中设置监视哨的技巧）
算法在查找成功时的平均查找长度、失败时的查找长度。
由简单顺序查找的查找长度引入更快的查找方法——二分查找。
2．有序表的二分查找
有序表，二分查找（折半查找）
二分查找的算法思想，以示意图举实例说明查找过程。
二分查找算法的实现：
二分查找的递归算法，算法分析
二分查找的判定树及其构造
3．索引顺序表的查找
分块有序表，索引表
在索引顺序表中进行查找分两步：
首先要通过在索引表中查找以确定元素所在的块，然后在所确定的块中进行查找。
每一步可以采用的查找方法。
简述索引顺序表的查找的时间性能。
9.3二叉排序树二树表的查找
通过分析顺序类表查找的静态特性对维护表的制约，引入树表的查找。
二叉排序树的定义、特性
二叉排序树的查找方法、算法描述。
二叉排序树的运算：
插入结点与构造二叉排序树
江门职业技术学院教案
授课时间
第12，13周
授课地点
课程类型
理论课
授课题目
排序
授课班级
教学目的
与
教学要求
直接插入排序、Shell排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序等。
重点与难点
快速排序、堆排序、归并排序
教学方法
手段（教具）
讲授法、启发法
主要内容
理解排序的相关概念；理解直接插入排序、Shell排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序等算法的基本思想、算法、时间复杂度和空间占用情况，并能根据具体问题选择合适的算法。
参考资料
精品课程网站:
课后作业与
思考题
P247
9.3;9.7;9.8
教学后记
教学过程
时间分配
10.1排序运算的定义和相关概念
排序的定义
排序的分类：
·增排序和减排序
·内部排序和外部排序
·稳定排序和不稳定排序
·插入排序、交换排序、选择排序、归并排序和基数排序
排序算法的分析指标：
时间性能分析，比较元素、移动或交换元素的平均次数。
空间性能分析，排序过程中所占用的辅助空间。
10.2插入排序
插入排序算法的基本思想
1．直接插入排序
直接插入排序的基本思想
举例说明直接插入排序算法的执行过程。
直接插入排序算法的实现。
算法分析：
稳定性、空间性能、时间性能。
2．希尔排序
希尔排序的基本思想
举例说明希尔排序算法的执行过程。
希尔排序算法的实现。
算法分析：
稳定性、空间性能、时间性能。
10.3交换排序
交换排序的基本思想
1．冒泡排序
冒泡排序的基本思想
举例说明冒泡排序算法的执行过程。
冒泡排序算法的实现。
算法分析：
稳定性、空间性能、时间性能。
冒泡排序算法的时间复杂度依赖于待排序序列的初始特性，改善的冒泡排序算法，双向冒泡排序。
2．快速排序
快速排序算法是对冒泡排序算法的改进。
快速排序的基本思想
举例说明快速排序算法的执行过程。
快速排序算法的实现。
算法分析：
稳定性、空间性能、时间性能（理想情况、最坏情况、一般情况）。
划分算法及其应用。
10.4选择排序
选择排序的基本思想
1．直接选择排序
直接选择排序的基本思想
举例说明直接选择排序算法的执行过程。
直接选择排序算法的实现。
算法分析：
稳定性、空间性能、时间性能。
改进直接选择排序算法的时间性能，引入堆排序。
2．堆排序
堆的定义，堆顶，大根堆，小根堆
堆的完全二叉树描述示意图
堆的筛选极其算法的实现
堆排序及建堆的方法，
举例说明堆排序算法的执行过程。
堆排序算法的实现。
算法分析：
稳定性、空间性
升级会员 