数据结构知识点总结课件.ppt

第一章 概论,理解和掌握 数据和数据结构的基本概念 数据的逻辑结构和物理结构 算法的定义和质量要求 算法的渐进时间复杂度分析,需要掌握的知识点 数据与数据结构的基本概念 数据元素是数据处理的基本单位，数据项是数据处理的最小单位。 数据结构是数据对象中元素之间的关系的表示。 数据类型是数据结构的使用方式。 基本数据类型是计算机中已经实现了的数据结构。,数据的逻辑结构和物理结构 逻辑结构分为线性结构和非线性结构。 非线性结构又分为集合结构、层次结构和图结构。物理结构分为顺序结构、链接结构、索引结构和散列结构。 逻辑结构与数据内容、物理安排、元素个数无关。区分线性或非线性结构的依据在于直接前驱和直接后继的数目。,算法复杂度分析 大O表示法：时间渐进复杂度。 并列程序段中各段时间复杂度的迭加规则。 嵌套程序段中各段时间复杂度的相乘规则。,第二章 线性表,理解和掌握线性表类型定义线性表顺序表示 单链表的基本概念 循环链表 双向链表,需要掌握的知识点 线性表的定义与四个特点 长度与位序的概念。线性表的顺序表示。 存储类型结构。随机访问方法。 线性表构造、插入、删除、合并算法及时间复杂度。 单链表的基本概念 单链表是线性表的链接存储表示。 不能随机访问, 只能顺序访问。 存储空间可以不断扩充。 元素的物理顺序与逻辑顺序可不同。 链表的插入与删除仅改变指针值。 有序单链表插入与删除算法。 有序单链表建立算法及性能分析。,循环链表 链表最后一个结点的链接指针指示表头结点。只要知道任一结点地址就能遍历其他所有结点。 若操作仅在链表两头, 可仅给出链尾指针, 它的下一结点即链头 。 对于需要循环操作的线性表, 可用循环链表存储，例如链式队列的实现。 循环单链表的插入与删除算法。,双向链表有两个链接指针：前驱和后继。 链表中同时存在两个链：一个按前驱方向，一个按后继方向。 在前驱方向和后继方向遍历, 时间复杂性都是O(1)。 在双向链表中两个方向的搜索算法。 在双向链表中插入新结点的算法。 在双向链表中删除一个结点的算法。,第三章 栈与队列,理解和掌握 栈与队列的结构与特点 循环队列的结构与特点,需要掌握的知识点 栈和队列的结构与特点 栈与队列都是限制存取点的线性表。 栈与队列都只能顺序存取。 栈是先进后出, 队列是先进先出。 顺序存储表示有“满”的问题。 链表存储表示可以扩充，不存在“满”的问题。 它们都有“空”的情形。,循环队列的结构与特点 其存储表示是顺序的环形结构。 队尾指针指示实际队尾的前一位置。 队头指针指示实际队头位置。 判断循环队列队空与队满的算法。 循环队列：将一个新元素进队的算法。 循环队列：从队列退出元素的算法。 循环链表表示队列时的进队列和出队列的算法。,第四章：串掌握串的定义、长度、子串、空串、空格串和位置等概念串的表示，串与线性表的区别。串的定长顺序存储表示、堆分配存储表示、块链存储表示的存储结构及特点。串的连接、求子串、串的复制、插入等算法。,第五章 数组与广义表,理解和掌握 一维数组和二维数组的概念 数组和顺序表的异同 特殊矩阵的压缩存储,需要掌握的知识点 一维数组和二维数组的概念一维数组是相同类型元素的集合二维数组是数组元素为一维数组的一维数组 二维数组不是线性结构，有最多二个直接前驱和二个直接后继。 一维有序数组插入新元素的算法 一维数组各元素逆置的算法,数组与顺序表的异同 顺序表是线性表的顺序存储表示。其逻辑顺序与物理顺序一致。 一维数组中非零元素可以不连续存放, 顺序表中非零元素必须连续存放。 数组与顺序表可以随机存取和顺序存取。 顺序表的存储可以借助一维数组。,特殊矩阵的压缩存储 对称矩阵的下三角压缩存储时的地址转换公式。 一维、二维数组元素地址的计算。 按行存储计算 按列存储计算 求一般矩阵各行元素之和的算法 求一般矩阵转置的算法,下三角矩阵,B a00 a10 a11 a20 a21 a22 a30 a31 a32 an-1n-1,0 1 2 3 4 5 6 7 8 n(n+1)/2-1,若 i j, 数组元素Aij在数组B中的存放位置为 1 + 2 + + i + j = (i + 1)* i / 2 + j若 i j，Aij = Aji = 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)。 树的先根、后根遍历过程与算法。,T1 T2 T3,A,F,H,T1 T2 T3,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条边时有e2e个非零元素。 邻接表是图的链接存储, 适用于稀疏图，e条边时有e2e个边链结点。 邻接矩阵的矩阵元素个数与顶点数n有关, 与边数无关; 其非零元素个数与边数e有关。 无向图的邻接矩阵是对称的; 有向图的邻接矩阵不一定是对称的。,图的遍历 图的深度优先搜索DFS。 图的广度优先搜索BFS。 图的DFS生成树的高度通常比其BFS 生成树的高度要高。普里姆和克鲁斯卡尔最小生成树方法 非连通图或非强连通图遍历后得到的通常是一个生成森林。,深度优先搜索DFS ( Depth First Search ),深度优先搜索的示例,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 ( Breadth First Search ),广度优先搜索的示例,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 搜索成功时无序表与有序表的ASL ASL = (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,散列 散列函数：除留余数法。 解决冲突的闭散列法（线性探查）。 解决冲突的开散列法。 除留余数法注意除数的选择：质数。 除留余数法优于其他散列函数。 开散列法优于闭散列法。 闭散列情形不能真正做表项的物理删除, 否则会中断其他表项的查找。,闭散列法 线性探查的探查序列 搜索成功的平均探查次数 搜索不成功的平均探查次数 探查序列 H0 = Hash(key) Hi = (H0 + i) % m, i = 1,2, m-1 搜索成功的平均探查次数 = 每个已有表项找到它的比较次数的平均值 搜索不成功的平均探查次数 = 散列函数可能算出的散列地址上插入新表项时找到空位的比较次数的平均值,线性探查法容易产生“堆积” 闭散列法 1, 开散列法 可大于 1 平均搜索长度取决于装填因子 平均搜索长度与装填因子之间关系,