《数据结构》PPT课件 商丘工学院 马玉芳

 
课件内容： 
绪论（4学时） 
理解数据结构的基本概念；了解数据的逻辑结构、数据的存储结构和数据操作；了解抽象数据类型与数据结构的关系；了解算法、算法描述、算法设计目标和算法分析方法；掌握算法的时间复杂度和空间复杂度的分析方法。重点：数据结构基本概念，算法的复杂度分析方法。难点：算法的复杂度分析方法。 
1.1数据结构的定义 
1.2算法描述 
1.3算法分析 
线性表（8学时） 
理解线性表的逻辑结构和基本操作；掌握线性表抽象数据类型的描述方法；掌握线性表的顺序存储结构和实现方法；掌握线性表的链式存储结构及其特点；掌握实现单链表、循环单链表、双链表、循环双链表基本操作的设计方法。重点：线性表的顺序存储结构和实现方法，线性表的链式存储结构和实现方法。难点：链表的基本操作。 
2.1线性表及其逻辑结构 
2.2顺序表 
2.2.1顺序表及基本运算 
2.2.2顺序表的应用 
2.3链表 
2.3.1链表与单链表 
2.3.2单链表的基本运算 
2.3.3单链表的应用 
栈和队列（6学时） 
掌握栈和队列的特点，并能在相应的应用问题中正确选用。熟练掌握栈的顺序栈和链栈的进栈出栈算法，特别应注意栈满和栈空的条件。熟练掌握循环队列和链队列的进队出队算法，特别是循环队列中队头与队尾指针的变化情况。了解计算表达式的方法和算法思路。重点：栈和队列的存储结构及相关算法的设计方法。难点：栈和队列的具体应用。 
3.1栈 
3.1.1栈的概念 
3.1.2顺序栈 
3.1.3链栈 
3.1.4栈的应用 
3.2队列 
3.2.1队列的概念 
3.2.2顺序队列 
3.2.3链队列 
串、数组和广义表（4学时） 
理解串的概念和串的基本操作，熟悉串的顺序存储结构和链式存储结构，掌握串的定义和基本操作的实现方法，理解串的模式匹配算法；理解一维数组和二维数组的存储结构；熟悉三角矩阵等特殊矩阵的压缩存储方法；理解广义表的概念；了解广义表表示的存储结构和操作实现。重点：串的模式匹配算法，特殊矩阵的压缩存储方法。难点：串的模式匹配算法，特殊矩阵的压缩存储方法。 
4.1串 
4.1.1串的概念和顺序存储结构 
4.1.2串的链式存储 
4.1.3串的模式匹配-BF算法 
4.1.4串的模式匹配-KMP算法（一） 
4.1.5串的模式匹配-KMP算法（二） 
4.1.6串的模式匹配-KMP算法（三） 
4.2数组 
4.2.1数组 
4.2.2稀疏矩阵 
4.3广义表 
树和二叉树（10学时） 
理解树的定义、术语、表示方法、遍历规则和多种存储结构，掌握采用树的孩子兄弟链表存储树并实现树的遍历、插入、删除等操作；理解二叉树的定义、性质、遍历规则和存储结构，掌握采用二叉链表或三叉链表存储结构存储二叉树的特点，掌握二叉树的遍历、构造、插入、删除等操作算法，比较二叉树遍历的递归算法与非递归算法的特点；理解线索二叉树概念，熟悉其存储结构，了解中序线索二叉树的遍历、线索化、求后继结点、插入等基本操作算法；理解Huffman编码在数据压缩中的作用，掌握Huffman算法、构造Huffman树。重点：树的定义和术语，二叉树的性质、遍历规则和存储结构，线索二叉树的线索化，Huffman树的概念，构造Huffman树，Huffman编码。难点：二叉树的遍历算法，Huffman算法实现构造Huffman树。 
5.1树的概念 
5.2树的运算和存储结构 
5.3二叉树的概念 
5.4二叉树的存储结构 
5.5二叉树的遍历 
5.6二叉树的构造 
5.7线索二叉树 
5.8哈夫曼树 
图（8学时） 
理解图的基本概念和术语；掌握图的邻接矩阵和邻接表存储结构；掌握图的深度优先遍历和广度优先遍历算法；理解最小生成树的概念；掌握两种构造图的最小生成树算法：Prim和Kruskal算法；理解最短路径问题的概念；熟悉求单源最短路径的Dijkstra算法；了解求所有最短路径的Floyd算法。重点：图的邻接矩阵和邻接表存储结构，图的遍历算法，Prim和Kruskal算法，Dijkstra算法。难点：Prim和Kruskal算法，Dijkstra算法。 
6.1图的定义 
6.2 图的存储结构 
6.2.1邻接矩阵 
6.2.2邻接表 
6.3 图的遍历 
6.3.1深度优先遍历 
6.3.2广度优先遍历 
6.4 生成树和最小生成树 
6.4.1生成树和最小生成树概念 
6.4.2普里姆算法 
6.4.3克鲁斯卡尔算法 
6.5最短路径 
查找（4学时） 
了解查找的基本概念；掌握查找算法效率的分析方法；理解常见的静态查找算法和动态查找算法；熟练掌握散列表的构造方法、处理冲突的方法，深刻理散列表与其他结构的表的实质性的差别。重点：常见的查找算法及效率的分析方法。难点：动态查找算法。 
7.1 查找的基本概念 
7.2 线性表的查找 
7.3 二叉树查找 
7.3.1二叉排序树 
7.3.2平衡二叉树 
7.4 哈希表 
7.4.1哈希表的概念 
7.4.2哈希函数的构造方法 
7.4.3哈希冲突的解决方法 
内排序（4学时） 
理解排序的基本概念和排序算法效率的分析方法；掌握常见的内排序算法；比较各内排序算法的特点、算法设计思想和适用的存储结构，了解各排序算法的时间效率和空间效率。重点：内排算法的设计思想。难点：内排序算法设计思想。 
8.1 排序的基本概念 
8.2 插入排序 
8.2.1插入排序–直接插入排序 
8.2.2插入排序–希尔排序 
8.3 交换排序 
8.3.1交换排序–冒泡排序 
8.3.2交换排序-快速排序 
8.4 选择排序 
8.4.1选择排序-简单排序 
8.4.2 选择排序–堆排序 
8.5 归并排序 
8.6基数排序