《数据结构与算法》PPT课件 于红 大连理工大学

 
课件内容： 
绪论 
掌握数据结构与算法概念，理解数据的逻辑结构与物理结构的相互关系，掌握算法概念及计算复杂度的概念，基本的算法分析方法。能够分析基本的循环结构、递归调用程序的算法复杂度。 
1.1 什么是数据结构 
1.2 算法设计与分析 
绪论单元测验 
绪论单元作业 
线性表 
掌握线性表结构的逻辑结构、存储结构、操作的定义；掌握栈、队列结构的定义，基于顺序存储结构实现栈与队列；了解字符串操作的定义和相关操作，掌握字符串的简单匹配算法和KMP算法逻辑。能够实现线性表的线性存储和链式存储及相关操作，应用栈与队列求解具体问题，用代码实现字符串的匹配操作。 
2.1 线性表及其顺序存储 
2.2 链表 
2.3 栈的基本概念与存储 
2.4 栈的应用 
2.5 队列 
2.6 字符串匹配 
2.7 字符串的模式匹配——KMP算法 
线性表单元测验 
线性表单元作业 
二叉树 
掌握二叉树的逻辑结构、存储结构、二叉树的广度优先、深度优先遍历操作；掌握特殊二叉树的定义、实现及应用；掌握树、森林的定义以及与二叉树的转换。编码实现二叉树的链式存储及各种遍历操作；编码实现二叉搜索树的的插入、删除和查找操作，对平衡二叉搜索树进行正确旋转，分析查找效率；编码实现堆结构及堆的插入、删除操作；设计具体文件中字符的Huffman编码；编码实现由先序（或后序）、中序序列创建二叉树。 
3.1 二叉树的概念与性质 
3.2 二叉树的存储 
3.3 二叉树的遍历（一） 
3.4 二叉树的遍历（二） 
3.5 二叉搜索树 
3.6 堆与优先队列 
3.7 Huffman树及其应用 
二叉树单元测验 
二叉树单元作业 
图 
4.1 图的基本概念4.2 图的存储4.3 图的遍历4.4 最小生成树4.5 最短路径4.6 关键路径图单元测验图单元作业 
掌握图结构的定义、存储实现及遍历操作；掌握最小生成树定义和生成算法、最短路径计算方法逻辑及实现、关键路径的定义及求解算法。 
编码实现图的顺序存储及各种遍历操作；编码实现确定最小生成树的Prim算法、Kruskal算法，编码实现单源最短路径Dijkstra算法和Floyd算法，并能分析算法的时间复杂度。应用相关算法设计具体问题的解决方案。 
查找 
掌握基于线性结构的顺序、二分法查找方法、散列查找方法和基于动态结构的查找方法。编码实现顺序查找和二分法查找方法，并能分析算法的时间复杂度；基于不同的解决冲突的方法，实现对数据的散列存储，并能分析查找成功和不成功的时间复杂度。能够实现在2-3树结构上的插入和删除。 
5.1 顺序查找 
5.2 二分法查找 
5.3 动态查找（一） 
5.4 动态查找（二） 
5.5 动态查找（三） 
5.6 散列查找（一） 
5.7 散列查找（二） 
查找单元测验 
查找单元作业 
排序 
掌握插入排序、交换排序、选择排序和归并排序算法思想；掌握基数排序算法思想。编码实现插入排序、交换排序、选择排序和归并排序；分析各排序方法时间性能和空间性能，能够根据实际问题选择恰当的排序算法。 
6.1 排序的基本概念 
6.2 插入排序（一） 
6.3 插入排序（二） 
6.4 交换排序——冒泡排序 
6.5 交换排序——快速排序 
6.6 选择排序 
6.7 归并排序 
6.8 基数排序 
排序单元测试 
排序单元作业