数据结构主要学习内容-课件.ppt

1、Design By Chen Anlong1数据结构与算法主讲人：陈安龙主讲人：陈安龙电子科技大学信息与软件工程学院电子科技大学信息与软件工程学院Design By Chen Anlong2n第第1章章 绪论绪论n第第2章章 线性表线性表n第第3章章 树树n第第4章章 图图n第第6章章 查找查找n第第7章章 排序排序主要内容主要内容Design By Chen Anlong3第第1章章 绪论绪论本章主要学习内容本章主要学习内容n 什么是数据什么是数据n 数据元素数据元素n 数据对象数据对象n 数据结构数据结构n 逻辑结构逻辑结构n 存储结构存储结构n 数据类型、抽象数据类型数据类型、抽象数据类

2、型 算法的定义、算法的特性、算法的时空代价算法的定义、算法的特性、算法的时空代价Design By Chen Anlong4本章要求本章要求n掌握数据结构的主要研究内容n掌握数据结构的含义n对数据的逻辑结构和存储结构有一个初步的认识n理解算法的时间复杂度和空间复杂度n理解数据结构和数据类型的关系n掌握算法的特性和度量算法优劣的标准。Design By Chen Anlong5本章重点内容本章重点内容n数据结构的抽象数据类型定义n数据结构的含义n顺序存储n链式存储n线性结构n非线性结构Design By Chen Anlong6本章难点本章难点n抽象数据类型n算法的时间复杂度n空间复杂度Desi

3、gn By Chen Anlong7第第2章章 线性表线性表本章主要学习内容本章主要学习内容n线性表的特点、基本运算、线性表的顺序存储、线性表的链式存储n顺序表的静态分配和动态分配；n链式存储的单向链表、单向循环链表、双向链表、双向循环链表n受限的线性表栈和队列定义n栈的入栈，出栈，取栈顶元素操作，栈的两种存储结构：顺序栈和链栈。n队列的入队，出队等基本操作，循环队列，链队列的表示，实现及特点。n递归的概念，特点及递归算法的设计数组的按行和按列的存储方式，两种存储方式下数组元素存储地址的计算方法，稀疏矩阵的概念及三元组及十字链表的压缩存储方式，稀疏矩阵的转置，相乘等基本操作。Design By

4、 Chen Anlong8本章要求本章要求n理解线形表的4类基本操作类型n掌握线性表的两种存储表示及其实现n掌握顺序表和链表的一些常见操作n理解顺序表和链表在存储及实现上的异同n理解双向链表，循环链表，双向循环链表和静态链表的存储特征及用途。n掌握栈和队列定义，特征及基本操作，掌握这两种线性结构的应用场合，理解假溢出的概念，n掌握循环队列的入队，出队，判满，判空等基本操作，n理解递归的含义及递归算法设计的思想。n掌握数组的地址计算方法n掌握稀疏矩阵的概念及稀疏矩阵的两种存储方法n理解稀疏矩阵的相关计算方法。Design By Chen Anlong9本章重点本章重点n顺序表和链表的C语言表示的

5、数据结构，以及对应结构插入，删除，查询等常见操作。n栈和队列的定义，栈的入栈，出栈操作，队列及链队列的的入队，出队操作，循环队列的判空，判满。n数组的两种存储方式，稀疏矩阵的概念及表示方法。Design By Chen Anlong10本章难点本章难点n顺序表和链表的存储和在此两种存储映像上的基本操作n双向循环链表和静态链表的插入与删除n一元多项式的加法和乘法运算。n栈和队列的基本操作，递归算法的设计。n稀疏矩阵的三元组和十字链表的表示方式及实现算法，如快速矩阵转置。Design By Chen Anlong11第第3章章 树树本章主要学习内容本章主要学习内容n树的定义和基本术语n二叉树的定义

6、及性质，满二叉树和完全二叉树的概念及特征，二叉树的顺序存储和链式存储n二叉树的前序，中序和后序遍历方法，线索二叉树的构建，线索二叉树中的节点插入与删除n树和森林的三种存储表示方法及其遍历操作，二叉树，树及森林间的相互转换n二叉排序树，二叉平衡树，B-树，键树，四叉树，2-3树的基本概念及相应的查找方法，节点增删方法n二叉树及树的典型应用表达式求值，哈夫曼树的构建和哈夫曼编码堆的构建和堆排序方法 Design By Chen Anlong12本章要求本章要求n掌握二叉树，树，森林的基本概念n理解满二叉树和完全二叉树的概念和特征。n掌握树的遍历以及之间的相互转换n掌握二叉树的基本性质n掌握线索二叉

7、树的构建以及在线索二叉树上的基本操作n掌握二叉排序树，二叉平衡树，B-树，2-3树的基本操作n掌握哈夫曼树的构建，哈夫曼编码，堆排序方法Design By Chen Anlong13本章重点本章重点n二叉树，树，森林的基本概念和遍历操作n二叉树，树及森林相互间的转换n线索二叉树的构建，线索二叉树中节点的删除，n二叉排序树，二叉平衡树，B-树，2-3树的基本操作，哈夫曼树的定义和建立Design By Chen Anlong14本章难点本章难点n二叉树，树，森林的各种遍历n线索二叉树的构建n线索二叉树中节点的删除n含左子树和右子树的二叉排序树节点删除方法n二叉平衡树的4种调整方法n堆的调整n哈夫

8、曼编码 Design By Chen Anlong15第第4章章 图图本章主要学习内容本章主要学习内容n图的基本概念和基本术语n图的存储结构，图的遍历n图的基本操作和存储方法邻接矩阵、关联矩阵、邻接表、逆邻接表、十字链表n图的遍历方法深度优先和宽度优先，n图的生成树和最小生成树n最小生成树的两种构建方法普里姆和克鲁斯卡尔。n最短路径、关键路径n最短路径的求取方法迪杰斯特拉和弗洛伊德方法，有向无环图的拓扑排序和关键路径求取。Design By Chen Anlong16本章要求本章要求n掌握图的基本概念和术语n图的存储结构邻接矩阵和邻接表n图基本操作深度优先和广度优先遍历n最小生成树、结点间的最

9、短路径n图的拓扑排序以及关键路径。n理解图的层次遍历，图的连通分支及图的基本应用。Design By Chen Anlong17本章重点本章重点n图的邻接矩阵和邻接表的存储表示n图的深度优先和广度优先遍历n图的最小生成树及其求取方法n图中两结点间及所有结点间的最短路径求取n有向无环图的拓扑排序n关键路径的求取方法。Design By Chen Anlong18本章难点本章难点n图的基本操作和存储方法邻接矩阵、关联矩阵、邻接表、逆邻接表、十字链表n图的生成树和最小生成树n最小生成树的两种构建方法普里姆和克鲁斯卡尔。n最短路径、关键路径n最短路径的求取方法迪杰斯特拉和弗洛伊德方法Design By

10、 Chen Anlong19第第6章章 查找查找本章主要学习内容本章主要学习内容n查找的基本概念和术语n顺序查找n折半查找n索引查找的方法。n哈希表的基本概念n哈希函数构造方法及冲突处理策略哈希表的查找，删除等操作方法。Design By Chen Anlong20本章要求本章要求n掌握顺序查找，折半查找，索引查找以及哈希表的查找方法n掌握哈希函数的基本构造方法n掌握解决地址冲突的基本策略。n理解各查找算法的时间复杂度和空间复杂度。Design By Chen Anlong21本章重点本章重点n顺序表的顺序查找n有序表的折半查找n哈希表的查找n哈希函数的构造和地址冲突解决办法。Design B

11、y Chen Anlong22本章难点本章难点n折半查找n哈希查找Design By Chen Anlong23第第7章章 排序排序本章主要学习内容本章主要学习内容n排序的基本概念n排序算法及复杂度分析n插入排序，快速排序，选择排序，堆排序归并排序和基数排序Design By Chen Anlong24本章要求本章要求n掌握直接插入排序n掌握折半插入排序n掌握希尔排序等插入排序算法n掌握冒泡排序和快速排序，归并排序和基数排序算法n了解各种排序算法的稳定性和时空性能分析n了解外部排序的基本思想和过程。Design By Chen Anlong25本章重点本章重点n直接插入排序n折半插入排序n希尔排序n冒泡排序n快速排序n归并排序和基数排序等排序算法。Design By Chen Anlong26本章难点本章难点n希尔排序n快速排序n堆排序n归并排序算法n排序算法分析。