数据结构知识点总结.ppt

第一章概论 理解和掌握数据和数据结构的基本概念数据的逻辑结构和物理结构算法的定义和质量要求算法的渐进时间复杂度分析 需要掌握的知识点数据与数据结构的基本概念数据元素是数据处理的基本单位 数据项是数据处理的最小单位 数据结构是数据对象中元素之间的关系的表示 数据类型是数据结构的使用方式 基本数据类型是计算机中已经实现了的数据结构 数据的逻辑结构和物理结构逻辑结构分为线性结构和非线性结构 非线性结构又分为集合结构 层次结构和图结构 物理结构分为顺序结构 链接结构 索引结构和散列结构 逻辑结构与数据内容 物理安排 元素个数无关 区分线性或非线性结构的依据在于直接前驱和直接后继的数目 算法复杂度分析大O表示法 时间渐进复杂度 并列程序段中各段时间复杂度的迭加规则 嵌套程序段中各段时间复杂度的相乘规则 第二章线性表 理解和掌握线性表类型定义线性表顺序表示单链表的基本概念循环链表双向链表 需要掌握的知识点线性表的定义与四个特点长度与位序的概念 线性表的顺序表示 存储类型结构 随机访问方法 线性表构造 插入 删除 合并算法及时间复杂度 单链表的基本概念单链表是线性表的链接存储表示 不能随机访问 只能顺序访问 存储空间可以不断扩充 元素的物理顺序与逻辑顺序可不同 链表的插入与删除仅改变指针值 有序单链表插入与删除算法 有序单链表建立算法及性能分析 循环链表链表最后一个结点的链接指针指示表头结点 只要知道任一结点地址就能遍历其他所有结点 若操作仅在链表两头 可仅给出链尾指针 它的下一结点即链头 对于需要循环操作的线性表 可用循环链表存储 例如链式队列的实现 循环单链表的插入与删除算法 双向链表有两个链接指针 前驱和后继 链表中同时存在两个链 一个按前驱方向 一个按后继方向 在前驱方向和后继方向遍历 时间复杂性都是O 1 在双向链表中两个方向的搜索算法 在双向链表中插入新结点的算法 在双向链表中删除一个结点的算法 第三章栈与队列 理解和掌握栈与队列的结构与特点循环队列的结构与特点 需要掌握的知识点栈和队列的结构与特点栈与队列都是限制存取点的线性表 栈与队列都只能顺序存取 栈是先进后出 队列是先进先出 顺序存储表示有 满 的问题 链表存储表示可以扩充 不存在 满 的问题 它们都有 空 的情形 循环队列的结构与特点其存储表示是顺序的环形结构 队尾指针指示实际队尾的前一位置 队头指针指示实际队头位置 判断循环队列队空与队满的算法 循环队列 将一个新元素进队的算法 循环队列 从队列退出元素的算法 循环链表表示队列时的进队列和出队列的算法 第四章 串掌握串的定义 长度 子串 空串 空格串和位置等概念串的表示 串与线性表的区别 串的定长顺序存储表示 堆分配存储表示 块链存储表示的存储结构及特点 串的连接 求子串 串的复制 插入等算法 第五章数组与广义表 理解和掌握一维数组和二维数组的概念数组和顺序表的异同特殊矩阵的压缩存储 需要掌握的知识点一维数组和二维数组的概念一维数组是相同类型元素的集合二维数组是数组元素为一维数组的一维数组二维数组不是线性结构 有最多二个直接前驱和二个直接后继 一维有序数组插入新元素的算法一维数组各元素逆置的算法 数组与顺序表的异同顺序表是线性表的顺序存储表示 其逻辑顺序与物理顺序一致 一维数组中非零元素可以不连续存放 顺序表中非零元素必须连续存放 数组与顺序表可以随机存取和顺序存取 顺序表的存储可以借助一维数组 特殊矩阵的压缩存储对称矩阵的下三角压缩存储时的地址转换公式 一维 二维数组元素地址的计算 按行存储计算按列存储计算求一般矩阵各行元素之和的算法求一般矩阵转置的算法 下三角矩阵 Ba00a10a11a20a21a22a30a31a32 an 1n 1 012345678n n 1 2 1 若i j 数组元素A i j 在数组B中的存放位置为1 2 i j i 1 i 2 j若i j A i j A j i j j 1 2 i 广义表部分 理解和掌握广义表构成 原子与子表概念表头与表尾概念 表的长度与深度求表头与表尾的方法 存储结构表头表尾分析法和子表分析法递归与递归算法递归算法的编制 需要掌握的知识点递归与递归算法递归的定义可用递归过程解决 递归数据结构 链表 树等 可用递归算法求解 递归算法包含两部分 基本项和归纳项 递归与递推的关系 单向递归与尾递归 递归算法的编制二叉树前序遍历的算法 二叉树后序遍历的算法 二叉树中序遍历的算法 二叉树中交换根结点的左 右子树的算法 完全二叉树用前序遍历实现顺序存储表示与二叉链表表示相互转换的算法 第六章树 二叉树与森林 理解和掌握二叉树的定义与性质二叉树的三种遍历及线索树的存储表示树 森林与二叉树的转换与遍历霍夫曼树与霍夫曼编码 需要掌握的知识点二叉树的定义与性质二叉树的定义是递归的 二叉树各层最大结点数2i i 0 1 二叉树高度为h时的最大结点数n 2h 1 1 完全二叉树有n个结点时的高度h log2 n 1 1 完全二叉树结点i的双亲 i 1 2 左子女2i 1 右子女2i 2 二叉树的三种遍历二叉树的前序遍历方法 二叉树的中序遍历方法 二叉树的后序遍历方法 二叉树的前序序列与中序序列唯一确定二叉树的方法 二叉树的后序序列与中序序列唯一确定二叉树的方法 二叉树的后序序列与前序序列只能确定一个结点的二叉树 树的存储表示树的左子女 右兄弟表示 图示 树的左子女 右兄弟表示中根没有右兄弟 森林的左子女 右兄弟表示中有n个非叶结点 右指针为空的结点有n 1个 k叉树各层最大结点个数 高度为h时的最大结点个数 kh 1 1 k 1 树的先根 后根遍历过程与算法 T1T2T3 A F H T1T2T3 A B C D G I J E K F B C D E G H I K J A B C E D H I K J F G 3棵树的森林 各棵树的二叉树表示 森林的二叉树表示 霍夫曼树与霍夫曼编码霍夫曼树的构造方法 霍夫曼编码的构造方法 霍夫曼树带权路径长度 霍夫曼编码长度 的计算 构造霍夫曼树时权大的离根最近 权小的离根最远 根的权值相同时 新构造出来的树的根一般位于右边 但若用 堆 存储各树的根结点 则要看它们在堆中调整的结果来定哪一个做左子树 6 12 8 2 4 2 4 6 12 8 6 例 12 8 2 6 4 2 4 6 12 8 6 2 4 6 12 8 6 12 20 12 2 4 6 12 8 6 12 20 32 第七章图 理解和掌握图的基本概念图的存储表示图的遍历最小生成树拓扑排序 需要掌握的知识点图的基本概念顶点的度 完全图 生成树 无向图顶点度的和等于边数的2倍 有向图顶点的度等于入度 出度 无向连通图最大边数n n 1 2 最少边数n 1 生成树 有向强连通图最大边数n n 1 最少边数n 特例 n 1时最少边数0 图的存储表示邻接矩阵是图的顺序存储 适用于稠密图 e条边时有e 2e个非零元素 邻接表是图的链接存储 适用于稀疏图 e条边时有e 2e个边链结点 邻接矩阵的矩阵元素个数与顶点数n有关 与边数无关 其非零元素个数与边数e有关 无向图的邻接矩阵是对称的 有向图的邻接矩阵不一定是对称的 图的遍历图的深度优先搜索DFS 图的广度优先搜索BFS 图的DFS生成树的高度通常比其BFS生成树的高度要高 普里姆和克鲁斯卡尔最小生成树方法非连通图或非强连通图遍历后得到的通常是一个生成森林 深度优先搜索DFS DepthFirstSearch 深度优先搜索的示例 A C D E G B F I H A C D E G B F I H 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 前进 回退 深度优先搜索过程深度优先生成树 广度优先搜索BFS BreadthFirstSearch 广度优先搜索的示例 A C D E G B F I H A C D E G B F H 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 广度优先搜索过程广度优先生成树 I 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 Vi Vj Cost 0 5 10 05 2 3 12 05 23 1 6 14 05 23 16 1 2 16 05 1236 3 6 18 舍去 3 4 22 05 12346 4 6 24 舍去 5 4 25 123456 最小生成树Kruskal算法构造生成树的方法 拓扑排序拓扑排序的过程 拓扑排序的时间代价为O n e 拓扑排序的结果可能不唯一 当各边权值不同时 构造的最小生成树是唯一的 当各边权值有相同的 构造的最小生成树可能不唯一 C0 C1 C2 C3 C4 C5 拓扑排序的过程 a 有向无环图 C2 C5 C1 C0 C3 b 输出顶点C4 C1 C2 C5 C3 c 输出顶点C0 C4 C0 C2 C5 C1 C3 d 输出顶点C3 C1 C2 C5 e 输出顶点C2 C5 C1 f 输出顶点C1 C5 g 输出顶点C5 拓扑有序序列C4 C0 C3 C2 C1 C5 满足图中所有前驱和后继关系 对于本来没有这种关系的顶点 如C4和C2 也排出先后次序 h 拓扑排序完成 第九章查找 理解和掌握顺序搜索 折半搜索 索引搜索二叉判定树二叉排序树AVL树哈希表 需要掌握的知识点顺序搜索顺序搜索的过程顺序搜索的平均搜索长度ASL搜索成功时无序表与有序表的ASLASL n 1 2搜索不成功时无序表的ASL n 1搜索不成功时有序表的ASL 有序表的折半搜索折半搜索的过程折半搜索的平均搜索长度搜索成功时的平均搜索长度ASL元素的最大比较次数为 log2 n 1 在区间 low high 中取中点 low high 2 二叉搜索树二叉搜索树的搜索过程及性能分析 等概率情形下 二叉搜索树的搜索成功的平均搜索长度计算 n个结点的不同二叉搜索树个数计算 平均搜索长度达到最小的二叉搜索树即为最优二叉搜索树 最优二叉搜索树中权大的结点离根近 权小的结点离根远 二叉搜索树的搜索算法 AVL树AVL树的搜索过程及性能分析与二叉搜索树相同 AVL树的插入过程 从根开始寻找插入位置 新结点作为叶结点插入 从插入位置向上回溯找发生不平衡结点 确定参加旋转结点 旋转类型 左单旋 右单旋 先左后右双旋 先右后左双旋 16 16 例 输入关键码序列为 16 3 7 11 9 26 18 14 15 插入和调整过程如下 0 3 16 3 1 0 7 0 1 2 左右双旋 7 3 16 0 0 0 7 3 11 0 1 1 7 3 16 16 11 9 0 1 2 右单旋 3 7 16 9 0 0 0 1 3 7 11 26 9 16 11 0 1 1 2 2 18 18 0 3 16 3 1 0 16 0 2 右左双旋 7 3 9 0 0 0 18 26 11 1 7 3 26 16 11 9 1 左单旋 9 7 16 14 0 0 1 7 11 26 26 9 1 1 11 15 18 2 3 18 16 2 左右双旋 7 3 0 0 0 11 7 14 9 1 16 15 0 1 11 26 26 14 1 2 9 从空树开始的建树过程 第十章内部排序 理解和掌握直接插入排序希尔排序快速排序直接选择排序归并排序 需要掌握的知识点直接插入排序直接插入排序的算法 直接插入排序的实例 这是稳定的排序算法 当初始排列已有序时速度提高最快 最好时数据比较n 1次 移动0次 最坏时数据比较n n 1 2次 移动n 1次 希尔排序 缩小增量排序 希尔排序的实例 不要算法 希尔排序是不稳定的排序方法gap取法 Shell提出取gap n 2 gap gap 2 直到gap 1 对特定的待排序对象序列 可以准确地估算比较次数和移动次数 当n很大时 平均比较次数和平均移动次数大约在n1 25到1 6n1 25的范围内 希尔排序的过程 快速排序 分区排序 快速排序的算法 快速排序的实例 快速排序是不稳定的排序方法 就平均计算时间而言 快速排序是所有内排序方法中最好的一个 每趟等分排序区间 计算时间O nlog2n 当初始排列已经有序时 速度最慢 数据比较达n n 1 2次 p i i i i p i i p i 直接选择排序直接选择排序的算法 直接选择排序的实例 直接选择排序是不稳定的排序方法 数据比较次数不受初始排列影响 n n 1 2 数据移动次数受初始排列影响 最好0次 最坏3 n 1 次 归并排序归并排序的实例 不要算法 归并排序是稳定的排序方法 归并趟数 log2 n 1 n是待排序数据对象个数 每趟数据比较次数受初始排列影响 最好 有序 n 2 最坏 n 1 数据移动次数不受初始排列影响 O nlog2n 次 表之间传送 第十章索引与散列 理解和掌握B树散列 需要掌握的知识点B树m阶B树是平衡m路搜索树 m阶B树所有失败结点在同一层 故平衡m路搜索树不一定是m阶B树 m阶B树的非失败结点最多包含m 1个关键码 最少 m 2 1个关键码 m阶B树高度不超过 含失败结点 h log m 2 n 1 2 1 散列散列函数 除留余数法 解决冲突的闭散列法 线性探查 解决冲突的开散列法 除留余数法注意除数的选择 质数 除留余数法优于其他散列函数