大数据结构与算法设计实训教案设计

1、数据结构与算法设计实训教案授课教师职称开课单位课程名称数据结构与算法设计实训课程代 码课程性质必修2公共 基础课学科基础课专业课实践性环节2其它选修口选修口课程学时3232课程学 分2 2学时分配理论学时（0 0）实践学时（3232 ）优选专业软件工程教学班学年学期20152015 学年第 2 2 学期授课方式多媒体+ +实验考核方 式考试2考查口教材名称数据结构课程设计作者刘燕君 等 出版社及 出版时间机械工业出版社，20142014扌曰疋参考书数据结构（C+C+版）作者王红梅 等出版社及 出版时间清华大学出版社，20112011数据结构项目实训戴文华 等人民邮电出 版社，20122012教

2、案编写时间20152015 年 3 3 月1早节 名称第一早数据结构概论教学 时数1 1授课 方式课堂讲授教学 目的 及要求1.理解数据结构的定义，并掌握数据结构研究的内容2.理解数据的存储结构使用的4 种基本存储方法3.掌握时间复杂度的计算方法教学 重点 与难点正确理解算法的有穷性和可行性的含义，掌握空间复杂度的计算方法讨论练习作业1.求解百钱买百鸡问题P3，实验题目 1.4.1教学 手段多媒体+课后练习参考 资料1. 刘燕君，等.数据结构课程设计（C+语言描述）M.机械工业出版社，2014.2. 王红梅，等.数据结构（C+版） M.清华大学出版社，2011.3. 戴文华，等.数据结构项目实

3、训M.人民邮电出版社，2012.具体 内容1.学习目的10mi ns2.数据结构定义及研究内容15mi ns3.数据结构存储方式10mi ns4.空间复杂度的计算10mi ns2早节名称第一早类和类模板编程教学 时数1 1授课 方式课堂讲授+实训教学 目的 及要求1.熟悉类模板的设计2.熟悉动态分配内存的方法3.掌握多文件编程和基本调试方法教学 重点 与难点1.熟悉模板2.熟悉动态分配内存的使用方法讨论练习作业1.约瑟夫环游戏程序P10,实验题目 2.2.1 ,2. 折线程序 P14，实验题目 2.3.1教学 手段多媒体+课堂练习+课后练习参考 资料1. 刘燕君，等.数据结构课程设计（C+语言

4、描述）M.机械工业出版社，2014.2. 王红梅，等.数据结构（C+版） M.清华大学出版社，2011.3. 戴文华，等.数据结构项目实训M.人民邮电出版社，2012.具体 内容1.模板函数专门化和模板重载10mi ns2.类模板5mi ns3.在类中使用动态分配内存5mi ns4.课堂练习，难点提示25mi ns3早节名称第三早线性表训练教学 时数4 4授课 方式课堂讲授+实训教学 目的 及要求1.理解线性表的顺序存储结构和链式存储结构的异冋2.掌握顺序表上实现的各种基本运算的算法3.掌握单链表上实现的各种基本运算的算法教学 重点 与难点1.理解线性表的顺序存储结构优缺点2.理解线性表的链式

5、存储结构优缺点3.掌握线性表的基本运算的算法4.难点是循环链表讨论练习作业1.一元多项式的加法运算P28，实验题目 3.3.1 ,2.改进的约瑟夫环游戏实现P34，实验题目 3.4.1教学 手段多媒体+课堂练习+课后练习参考 资料1. 刘燕君，等.数据结构课程设计（C+语言描述）M.机械工业出版社，2014.2. 王红梅，等.数据结构（C+版） M.清华大学出版社，2011.3. 戴文华，等.数据结构项目实训M.人民邮电出版社，2012.具体 内容1.复习线性表顺序存储结构特性及基本运算10mi ns2.复习线性表链式存储结构特性及基本运算15mi ns3.通过学生信息表建立的例子，讲解链表的

6、建立过程20mi ns4.课堂练习，难点提示135mi ns4早节名称第四早栈和队列训练教学 时数4 4授课 方式课堂讲授+实训教学 目的 及要求1.熟悉顺序栈、链栈、循环队列、链队列的存储结构2.熟练掌握顺序栈、链栈、循环队列、链队列的基本运算3.掌握通过栈或队列解决实际应用问题的方法教学 重点 与难点1.理解栈和队列的特性2.熟练掌握栈和队列的基本运算，在解决实际应用问题中灵活使用栈和队列讨论练习作业1.八皇后问题完整的算法实现P49，实验题目 4412.模拟后缀表达式的计算过程实现P 54 ,实验题目 4.5.1教学 手段多媒体+课堂练习+课后练习参考 资料1. 刘燕君，等.数据结构课程

7、设计（C+语言描述）M.机械工业出版社，2014.2. 王红梅，等.数据结构（C+版） M.清华大学出版社，2011.3. 戴文华，等.数据结构项目实训M.人民邮电出版社，2012.具体 内容1.栈的特性和基本操作10mins2.通过类模板 Stack 的例子说明类模板专门化和使用方法20mins3.队列的特性和基本操作10mins4.课堂练习，难点提示140mins5早节名称第五早树和二叉树训练教学 时数4 4授课 方式课堂讲授+实训教学 目的 及要求1.熟悉二叉树的定义、性质2.熟练掌握二叉树的存储结构3.熟练掌握二叉树的遍历4.了解最优二叉树的特性5.掌握建立最优二叉树和哈夫曼编码的方法

8、教学 重点 与难点1.编写实现二叉树的各种运算的算法2.解决与树或二叉树相关的应用问题3.理解线索化二叉树讨论练习作业1.查找结点并显示该结点的层次和路径P116，实验题目 7.2.12.哈夫曼编码算法设计及实现P125，实验题目 7.4.1教学 手段多媒体+课堂练习+课后练习参考 资料1. 刘燕君，等.数据结构课程设计（C+语言描述）M.机械工业出版社，2014.2. 王红梅，等.数据结构（C+版） M.清华大学出版社，2011.3. 戴文华，等.数据结构项目实训M.人民邮电出版社，2012.具体 内容1.复习树和二叉树的定义和性质10mi ns2.复习二叉树的存储结构和遍历20mi ns3

9、.复习哈夫曼编码过程10mi ns4.课堂练习，难点提示140mi ns6早节名称第六早图结构训练教学 时数4 4授课 方式课堂讲授+实训教学 目的 及要求1.掌握图的邻接矩阵和邻接表两种基本的存储方式2.掌握图在两种存储结构上实现的两种遍历算法3.掌握求最小生成树算法思想4.掌握求最短路径算法思想5.掌握拓扑排序算法思想教学 重点 与难点1.掌握图的邻接矩阵和邻接表两种存储方式及对应的遍历算法2.掌握求最小生成树、求最短路径以及拓扑排序算法的基本思想及时间性能讨论练习作业1.无向网络的最小生成树的普利姆算法实现P135，实验题目 8.2.12.交通咨询系统设计与实现P138，实验题目 8.3

10、.1教学 手段多媒体+课堂练习+课后练习参考 资料1. 刘燕君，等.数据结构课程设计（C+语言描述）M.机械工业出版社，2014.2. 王红梅，等.数据结构（C+版） M.清华大学出版社，2011.3. 戴文华，等.数据结构项目实训M.人民邮电出版社，2012.具体 内容1.复习图的基本术语5mi ns2.复习图的存储表示方式5mi ns3.复习图的基本运算，包括深度优先搜索法、广度优先搜索法、生成最小生成树法和产生最短路径法30mi ns4.课堂练习，难点提示140mi ns7早节名称第七早排序算法训练教学 时数4 4授课 方式课堂讲授+实训教学 目的 及要求1.掌握有关内部排序的一些常用方

11、法，包括插入排序、交换排序、选择排序和归并排序2.熟悉内部排序的基本思想、排序过程、算法实现、时间和空间性能分析3.熟悉不同排序算法的差异教学 重点 与难点1.掌握希尔排序算法2.掌握快速排序算法3.熟练掌握堆排序算法讨论练习作业1.堆排序算法设计及实现P159，实验题目 9.3.12.学生成绩处理系统P161 ,实验题目 9.4.1教学 手段多媒体+课堂练习+课后练习参考 资料1. 刘燕君，等.数据结构课程设计（C+语言描述）M.机械工业出版社，2014.2. 王红梅，等.数据结构（C+版） M.清华大学出版社，2011.3. 戴文华，等.数据结构项目实训M.人民邮电出版社，2012.具体

12、内容1.复习排序的基本概念5mi ns2.复习经典的排序算法30mi ns3.比较几种排序算法的时间复杂度、稳定性、辅助空间、对记录存储方式的要求和排序方法的选取10mi ns4.课堂练习，难点提示135mi ns8早节名称第八早查找算法训练教学 时数2 2授课 方式课堂讲授+实训教学 目的 及要求1.熟悉各种查找算法，并能熟练应用2.掌握顺序查找、二分查找、二叉查找树上的查找，以及散列表上的查找的基本思想和 算法实现3.熟悉查找算法的评价方法教学 重点 与难点1.掌握线性表和二叉排序树的查找方法2.难点是解决散列表冲突的方法3.掌握查找方法所需的存储结构讨论练习作业1.航班信息的查询与检索

13、P177，实验题目 10.3.1教学 手段多媒体+课堂练习+课后练习参考 资料1. 刘燕君，等.数据结构课程设计（C+语言描述）M.机械工业出版社，2014.2. 王红梅，等.数据结构（C+版） M.清华大学出版社，2011.3. 戴文华，等.数据结构项目实训M.人民邮电出版社，2012.具体 内容1.复习顺序表查找算法10mins2.复习二叉排序树上的查找算法15mi ns3.复习散列表查找算法15mins4.课堂练习，难点提示50mins9早节名称第九早分治算法训练教学 时数4 4授课 方式课堂讲授+实训教学 目的 及要求1.掌握分治算法的基本原理2.利用分治策略编程解决输油管道、循环赛日

14、程表、邮局选址和集合划分问题教学 重点 与难点掌握分治算法的设计思想，通过实际问题来应用分治设计算法讨论练习作业1.输油管道问题2.循环赛日程表3.邮局选址4.集合划分教学 手段多媒体+课堂练习+课后练习参考 资料1. （美）克林伯格，等算法设计M.清华大学出版社，2007.2. Thomas H.Cormen，等.算法导论M.机械工业出版社出版（第二版），2006.具体 内容1.复习分治算法框架10mi ns2.分析典型二分法30mi ns3.课堂练习，难点提示140mi ns10早节名称第十早回溯算法训练教学 时数4 4授课 方式课堂讲授+实训教学 目的 及要求1.掌握回溯算法的基本原理2.利用回溯策略编程解决桥本分数式、马的遍历、素数环和排列树的回溯搜索问题教学 重点 与难点掌握回溯算法的设计思想，通过实际问题来应用回