页数：24页文件大小：105.3 KB来源： 数据结构ppt课件
本课件为课程知识点总结，按章节顺序梳理各章核心概念与算法要点：数据结构的基本概念与算法分析准则，线性表、堆栈与队列的定义及应用，数组与字符串，树、二叉树与线索二叉树，图的存储、遍历与典型应用，以及各类排序与查找算法的性能特点。
第一章绪论与算法分析数据结构的基本概念：•数据•数据元素•数据逻辑结构线性结构树型结构图型结构•数据存储结构：顺序存储和链接存储ADL算法描述语言
第一章绪论与算法分析评估算法的五条准则：正确性时间复杂性基本运算（关键操作）简单算法的时间效率分析（基本运算次数）大O等表示法占用空间（指令、数据和环境栈空间）可读性坚固性(健壮性)
第二章线性表线性表的定义：线性结构运算：查找、插入、删除、构造线性表、遍历等存储结构：顺序存储——一维数组链接存储——单链表两种存储结构及其相应算法的比较
第二章堆栈和队列堆栈是一种操作受限制的线性表push和pop操作只和栈顶有关顺序和链接两种存储结构堆栈的特性：后进先出堆栈的状态堆栈空：top =-1堆栈满：top = MaxStackSize-1
堆栈的应用算术表达式求值数制转换括号匹配堆栈与递归二叉树的遍历（先根、中根、后根）树和森林的遍历（先根、后根）图的深度优先搜索
队列队列是一种操作受限制的线性表操作只和队头、队尾有关队列的特性：先进先出顺序和链接两种存储结构队列的状态队列空：count=0队列满：count=MaxQSize
队列的应用二叉树的层次遍历树和森林的层次遍历图的广度优先搜索单源无权最短路径问题
第三章数组高维数组按照行（列）优先顺序转换为一维数组；特殊矩阵的压缩存储对角矩阵上（下）三角矩阵对称矩阵稀疏矩阵（三元组，十字链表）
第四章树基本概念结点根结点叶子结点分支结点从根到结点的路径孩子结点、双亲结点、兄弟结点、祖先结点、子孙结点结点的度树的度结点的层数树的高（深）度
二叉树及线索二叉树二叉树的定义及其性质满二叉树和完全二叉树的定义和性质二叉树的存储（顺序存储和链式存储）二叉树的实现搜索父结点、搜索特定域值的结点、删除子树、二叉树的创建与复制二叉树的先根、中根、后根及层次遍历（递归和非递归算法）
线索二叉树线索二叉树的定义与结构线索二叉树的基本操作•搜索中序线索二叉树中根序列的最后一个结点•搜索中序线索二叉树中根序列的第一个结点•搜索某结点的中根前趋结点•搜索某结点的中根后继
树和森林树和森林的定义树、森林与二叉树的转换树、森林的左孩子右兄弟表示法树的基本操作•搜索大儿子结点•搜索下一个兄弟结点•搜索父结点•查找结点•删除子树
树和森林的遍历•先根、后根遍历（递归与非递归算法）•层次遍历树的应用哈夫曼树和哈夫曼编码
第六章图基本概念图有向图无向图邻接点度入度出度子图母图支撑子图路径路径长度简单路径简单回路加权图连通图连通分量强连通图强连通分量最小支撑树
存储结构邻接矩阵邻接表两种存储方式的比较图的遍历深度优先遍历算法（递归和非递归算法）广度优先遍历算法
图的应用拓扑排序关键路径最短路径单源最短路径（无权最短路径、正权最短路径）顶点对间最短路径最小支撑树Prim算法Kruskar算法
第七章排序排序的基本概念•排序的基本概念•关键词、初始关键词排列•关键词比较次数、记录移动次数•稳定性•附加存储插入排序•用实例表明直接插入排序、折半插入排序和希尔排序的过程•直接插入排序和折半插入排序的算法
•排序的性能分析•当待排序的关键词序列已经基本有序时，用直接插入排序最快交换排序•用实例表明冒泡排序和快速排序的过程•冒泡排序的算法•快速排序的算法•算法时间复杂度的分析方法•快速排序是一个递归的排序法，当待排序关键词序列已经基本有序时，快速排序显著变慢
选择排序•用实例表明直接选择排序、堆排序的过程•直接选择排序和堆排序的算法•两种选择排序的性能分析•用直接选择排序在一个待排序区间中选出最大的数据时，与区间后一个数据对调，这导致方法不稳定
二路合并排序•用实例表明二路合并排序的过程•二路合并排序的算法•二路合并排序算法的性能分析•合并排序可以递归执行•合并排序需要较多的附加存储•合并排序对待排序关键词的初始排列不敏感，故排序速度较稳定
第八章查找无序表的顺序查找算法及分析有序表的查找顺序查找算法及分析对半（折半，二分）查找对半查找算法及其分析对半查找二叉判定树斐波那契查找、插值查找的思想
二叉查找树二叉查找树的定义二叉查找树的建立、查找、插入、删除结点过程高度平衡树的定义高度平衡树的建立、查找、插入结点、平衡调整过程B树、B+树的定义B树的结点插入、删除过程
杂凑杂凑表相关定义杂凑函数•抽取法•压缩法•除法杂凑函数•乘法杂凑函数处理冲突•拉链法•线性探查•双重杂凑
谢谢大家！
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}