《数据结构主要学习内容.ppt》由会员分享，可在线阅读，更多相关《数据结构主要学习内容.ppt（26页珍藏版）》请在三一文库上搜索。
1、2019年2月23日6时31分,Design By Chen Anlong,1,数据结构与算法,主讲人：陈安龙 电子科技大学信息与软件工程学院,2019年2月23日6时31分,Design By Chen Anlong,2,第1章 绪论 第2章 线性表 第3章 树 第4章 图 第6章 查找 第7章 排序,主要内容,2019年2月23日6时31分,Design By Chen Anlong,3,第1章 绪论,本章主要学习内容 什么是数据 数据元素 数据对象 数据结构 逻辑结构 存储结构 数据类型、抽象数据类型 算法的定义、算法的特性、算法的时空代价,2019年2月23日6时31分,Design
2、By Chen Anlong,4,本章要求,掌握数据结构的主要研究内容 掌握数据结构的含义 对数据的逻辑结构和存储结构有一个初步的认识 理解算法的时间复杂度和空间复杂度 理解数据结构和数据类型的关系 掌握算法的特性和度量算法优劣的标准。,2019年2月23日6时31分,Design By Chen Anlong,5,本章重点内容,数据结构的抽象数据类型定义 数据结构的含义 顺序存储 链式存储 线性结构 非线性结构,2019年2月23日6时31分,Design By Chen Anlong,6,本章难点,抽象数据类型 算法的时间复杂度 空间复杂度,2019年2月23日6时31分,Design B
3、y Chen Anlong,7,第2章 线性表,本章主要学习内容 线性表的特点、基本运算、线性表的顺序存储、线性表的链式存储 顺序表的静态分配和动态分配； 链式存储的单向链表、单向循环链表、双向链表、双向循环链表 受限的线性表栈和队列定义 栈的入栈，出栈，取栈顶元素操作，栈的两种存储结构：顺序栈和链栈。 队列的入队，出队等基本操作，循环队列，链队列的表示，实现及特点。 递归的概念，特点及递归算法的设计 数组的按行和按列的存储方式，两种存储方式下数组元素存储地址的计算方法，稀疏矩阵的概念及三元组及十字链表的压缩存储方式，稀疏矩阵的转置，相乘等基本操作。,2019年2月23日6时31分,Desig
4、n By Chen Anlong,8,本章要求,理解线形表的4类基本操作类型 掌握线性表的两种存储表示及其实现 掌握顺序表和链表的一些常见操作 理解顺序表和链表在存储及实现上的异同 理解双向链表，循环链表，双向循环链表和静态链表的存储特征及用途。 掌握栈和队列定义，特征及基本操作，掌握这两种线性结构的应用场合，理解假溢出的概念， 掌握循环队列的入队，出队，判满，判空等基本操作， 理解递归的含义及递归算法设计的思想。 掌握数组的地址计算方法 掌握稀疏矩阵的概念及稀疏矩阵的两种存储方法 理解稀疏矩阵的相关计算方法。,2019年2月23日6时31分,Design By Chen Anlong,9,本
5、章重点,顺序表和链表的C语言表示的数据结构，以及对应结构插入，删除，查询等常见操作。 栈和队列的定义，栈的入栈，出栈操作，队列及链队列的的入队，出队操作，循环队列的判空，判满。 数组的两种存储方式，稀疏矩阵的概念及表示方法。,2019年2月23日6时31分,Design By Chen Anlong,10,本章难点,顺序表和链表的存储和在此两种存储映像上的基本操作 双向循环链表和静态链表的插入与删除 一元多项式的加法和乘法运算。 栈和队列的基本操作，递归算法的设计。 稀疏矩阵的三元组和十字链表的表示方式及实现算法，如快速矩阵转置。,2019年2月23日6时31分,Design By Chen
6、Anlong,11,第3章 树,本章主要学习内容 树的定义和基本术语 二叉树的定义及性质，满二叉树和完全二叉树的概念及特征，二叉树的顺序存储和链式存储 二叉树的前序，中序和后序遍历方法，线索二叉树的构建，线索二叉树中的节点插入与删除 树和森林的三种存储表示方法及其遍历操作，二叉树，树及森林间的相互转换 二叉排序树，二叉平衡树，B-树，键树，四叉树，2-3树的基本概念及相应的查找方法，节点增删方法 二叉树及树的典型应用表达式求值，哈夫曼树的构建和哈夫曼编码 堆的构建和堆排序方法,2019年2月23日6时31分,Design By Chen Anlong,12,本章要求,掌握二叉树，树，森林的基本
7、概念 理解满二叉树和完全二叉树的概念和特征。 掌握树的遍历以及之间的相互转换 掌握二叉树的基本性质 掌握线索二叉树的构建以及在线索二叉树上的基本操作 掌握二叉排序树，二叉平衡树，B-树，2-3树的基本操作 掌握哈夫曼树的构建，哈夫曼编码，堆排序方法,2019年2月23日6时31分,Design By Chen Anlong,13,本章重点,二叉树，树，森林的基本概念和遍历操作 二叉树，树及森林相互间的转换 线索二叉树的构建，线索二叉树中节点的删除， 二叉排序树，二叉平衡树，B-树，2-3树的基本操作，哈夫曼树的定义和建立,2019年2月23日6时31分,Design By Chen Anlon
8、g,14,本章难点,二叉树，树，森林的各种遍历 线索二叉树的构建 线索二叉树中节点的删除 含左子树和右子树的二叉排序树节点删除方法 二叉平衡树的4种调整方法 堆的调整 哈夫曼编码,2019年2月23日6时31分,Design By Chen Anlong,15,第4章 图,本章主要学习内容 图的基本概念和基本术语 图的存储结构，图的遍历 图的基本操作和存储方法邻接矩阵、关联矩阵、邻接表、逆邻接表、十字链表 图的遍历方法深度优先和宽度优先， 图的生成树和最小生成树 最小生成树的两种构建方法普里姆和克鲁斯卡尔。 最短路径、关键路径 最短路径的求取方法迪杰斯特拉和弗洛伊德方法， 有向无环图的拓扑排序
9、和关键路径求取。,2019年2月23日6时31分,Design By Chen Anlong,16,本章要求,掌握图的基本概念和术语 图的存储结构邻接矩阵和邻接表 图基本操作深度优先和广度优先遍历 最小生成树、结点间的最短路径 图的拓扑排序以及关键路径。 理解图的层次遍历，图的连通分支及图的基本应用。,2019年2月23日6时31分,Design By Chen Anlong,17,本章重点,图的邻接矩阵和邻接表的存储表示 图的深度优先和广度优先遍历 图的最小生成树及其求取方法 图中两结点间及所有结点间的最短路径求取 有向无环图的拓扑排序 关键路径的求取方法。,2019年2月23日6时31分,
10、Design By Chen Anlong,18,本章难点,图的基本操作和存储方法邻接矩阵、关联矩阵、邻接表、逆邻接表、十字链表 图的生成树和最小生成树 最小生成树的两种构建方法普里姆和克鲁斯卡尔。 最短路径、关键路径 最短路径的求取方法迪杰斯特拉和弗洛伊德方法,2019年2月23日6时31分,Design By Chen Anlong,19,第6章 查找,本章主要学习内容 查找的基本概念和术语 顺序查找 折半查找 索引查找的方法。 哈希表的基本概念 哈希函数构造方法及冲突处理策略 哈希表的查找，删除等操作方法。,2019年2月23日6时31分,Design By Chen Anlong,20
11、,本章要求,掌握顺序查找，折半查找，索引查找以及哈希表的查找方法 掌握哈希函数的基本构造方法 掌握解决地址冲突的基本策略。 理解各查找算法的时间复杂度和空间复杂度。,2019年2月23日6时31分,Design By Chen Anlong,21,本章重点,顺序表的顺序查找 有序表的折半查找 哈希表的查找 哈希函数的构造和地址冲突解决办法。,2019年2月23日6时31分,Design By Chen Anlong,22,本章难点,折半查找 哈希查找,2019年2月23日6时31分,Design By Chen Anlong,23,第7章 排序,本章主要学习内容 排序的基本概念 排序算法及复杂
12、度分析 插入排序，快速排序，选择排序，堆排序 归并排序和基数排序,2019年2月23日6时31分,Design By Chen Anlong,24,本章要求,掌握直接插入排序 掌握折半插入排序 掌握希尔排序等插入排序算法 掌握冒泡排序和快速排序，归并排序和基数排序算法 了解各种排序算法的稳定性和时空性能分析 了解外部排序的基本思想和过程。,2019年2月23日6时31分,Design By Chen Anlong,25,本章重点,直接插入排序 折半插入排序 希尔排序 冒泡排序 快速排序 归并排序和基数排序等排序算法。,2019年2月23日6时31分,Design By Chen Anlong,26,本章难点,希尔排序 快速排序 堆排序 归并排序算法 排序算法分析。,