《数据结构》电子教案.ppt

《《数据结构》电子教案.ppt》由会员分享，可在线阅读，更多相关《《数据结构》电子教案.ppt（59页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、开放教育本科计算机科学与技术专业数据结构电子教案第一章 概论n理解和掌握u 数据和数据结构的基本概念u 数据的逻辑结构和物理结构u 算法的定义和质量要求u 算法的渐进时间复杂度分析n需要掌握的知识点 数据与数据结构的基本概念 数据元素是数据处理的基本单位，数据项是数据处理的最小单位。 数据结构是数据对象中元素之间的关系的表示。 数据类型是数据结构的使用方式。 基本数据类型是计算机中已经实现了的数据结构。 数据的逻辑结构和物理结构 逻辑结构分为线性结构和非线性结构。 非线性结构又分为集合结构、层次结构和图结构。物理结构分为顺序结构、链接结构、索引结构和散列结构。 逻辑结构与数据内容、物理安排、元

2、素个数无关。区分线性或非线性结构的依据在于直接前驱和直接后继的数目。 算法复杂度分析 大O表示法：时间渐进复杂度。 并列程序段中各段时间复杂度的迭加规则。 嵌套程序段中各段时间复杂度的相乘规则。第二章 数组n理解和掌握u 一维数组和二维数组的概念u 数组和顺序表的异同u 特殊矩阵的压缩存储n需要掌握的知识点 一维数组和二维数组的概念u一维数组是相同类型元素的集合u二维数组是数组元素为一维数组的一维数组u 二维数组不是线性结构，有最多二个直接前驱和二个直接后继。 一维有序数组插入新元素的算法 一维数组各元素逆置的算法 数组与顺序表的异同u 顺序表是线性表的顺序存储表示。其逻辑顺序与物理顺序一致。

3、u 一维数组中非零元素可以不连续存放, 顺序表中非零元素必须连续存放。u 数组与顺序表可以随机存取和顺序存取。u 顺序表的存储可以借助一维数组。 特殊矩阵的压缩存储u 对称矩阵的下三角压缩存储时的地址转换公式。u 一维、二维数组元素地址的计算。v 按行存储计算v 按列存储计算 求一般矩阵各行元素之和的算法 求一般矩阵转置的算法11121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa下三角矩阵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若

4、 i j, 数组元素Aij在数组B中的存放位置为 1 + 2 + + i + j = (i + 1)* i / 2 + j若 i j，Aij = Aji = j *(j +1) / 2 + i第三章 链接表n理解和掌握u 单链表的基本概念u 循环链表u 双向链表n需要掌握的知识点 单链表的基本概念u 单链表是线性表的链接存储表示。u 不能随机访问, 只能顺序访问。u 存储空间可以不断扩充。u 元素的物理顺序与逻辑顺序可不同。u 链表的插入与删除仅改变指针值。 有序单链表插入与删除算法。 有序单链表建立算法及性能分析。 循环链表u 链表最后一个结点的链接指针指示表头结点。只要知道任一结点地址就能

5、遍历其他所有结点。u 若操作仅在链表两头, 可仅给出链尾指针, 它的下一结点即链头 。 对于需要循环操作的线性表, 可用循环链表存储，例如链式队列的实现。 循环单链表的插入与删除算法。 双向链表u有两个链接指针：前驱和后继。u 链表中同时存在两个链：一个按前驱方向，一个按后继方向。u 在前驱方向和后继方向遍历, 时间复杂性都是O(1)。 在双向链表中两个方向的搜索算法。 在双向链表中插入新结点的算法。 在双向链表中删除一个结点的算法。第四章 栈与队列n理解和掌握u 栈与队列的结构与特点u 循环队列的结构与特点 n需要掌握的知识点 栈和队列的结构与特点u 栈与队列都是限制存取点的线性表。u 栈与

6、队列都只能顺序存取。u 栈是先进后出, 队列是先进先出。 u 顺序存储表示有“满”的问题。u 链表存储表示可以扩充，不存在“满”的问题。u 它们都有“空”的情形。 循环队列的结构与特点u 其存储表示是顺序的环形结构。u 队头指针指示实际队头的前一位置。u 队尾指针指示实际队尾位置。 判断循环队列队空与队满的算法。 循环队列：将一个新元素进队的算法。 循环队列：从队列退出元素的算法。 循环链表表示队列时的进队列和出队列的算法。第五章 递归与广义表n理解和掌握u 递归与递归算法u 递归算法的编制n需要掌握的知识点 递归与递归算法u 递归的定义可用递归过程解决。u 递归数据结构（链表、树等）可用递归

7、算法求解。u 递归算法包含两部分：基本项和归纳项。u 递归与递推的关系。u 单向递归与尾递归。 递归算法的编制 二叉树前序遍历的算法。 二叉树后序遍历的算法。 二叉树中序遍历的算法。 二叉树中交换根结点的左、右子树的算法。 完全二叉树用前序遍历实现顺序存储表示与二叉链表表示相互转换的算法。第六章 树与森林n理解和掌握u 二叉树的定义与性质u 二叉树的三种遍历u 树的存储表示u 霍夫曼树与霍夫曼编码u 堆 n需要掌握的知识点 二叉树的定义与性质u 二叉树的定义是递归的。u 二叉树各层最大结点数2i ( i = 0,1,u 二叉树高度为h时的最大结点数n = 2h+1 - -1。u 完全二叉树有n

8、个结点时的高度h : log2(n+1) - -1 。 u 完全二叉树结点i的双亲 (i- -1)/2 、左子女 2i+1、右子女 2i+2。 二叉树的三种遍历u 二叉树的前序遍历方法。u 二叉树的中序遍历方法。u 二叉树的后序遍历方法。u 二叉树的前序序列与中序序列唯一确定二叉树的方法。u 二叉树的后序序列与中序序列唯一确定二叉树的方法。u 二叉树的后序序列与前序序列只能确定一个结点的二叉树。 树的存储表示u 树的左子女/右兄弟表示（图示）。u 树的左子女/右兄弟表示中根没有右兄弟。u 森林的左子女/右兄弟表示中有n个非叶结点, 右指针为空的结点有n+1 个。u k叉树各层最大结点个数、高度

9、为h时的最大结点个数(kh+1- -1)/(k- -1)。u 树的先根、后根遍历过程与算法。T1 T2 T3AFHT1 T2 T3ABC DGIJEKFBCDEGHIKJABCEDHIKJFG3 棵树的森林各棵树的二叉树表示森林的二叉树表示 霍夫曼树与霍夫曼编码u 霍夫曼树的构造方法。u 霍夫曼编码的构造方法。u 霍夫曼树带权路径长度（霍夫曼编码长度）的计算。 构造霍夫曼树时权大的离根最近，权小的离根最远。 根的权值相同时，新构造出来的树的根一般位于右边。但若用“堆”存储各树的根结点，则要看它们在堆中调整的结果来定哪一个做左子树。6128242461286*：2461286*2461286*1

10、2*2012*2461286*12*2032 堆u 堆的定义：顺序存储的关键码集合。u 堆的插入与删除。 形成堆时用到的向下调整算法。 堆插入时用到的向上调整算法。 堆的插入与删除算法。第七章 集合与搜索n理解和掌握u 顺序搜索u 折半搜索u 二叉搜索树u AVL树 n需要掌握的知识点 顺序搜索u 顺序搜索的过程u 顺序搜索的平均搜索长度ASL 搜索成功时无序表与有序表的ASL ASL = (n+1)/2 搜索不成功时无序表的ASL = n+1 搜索不成功时有序表的ASL n1iin1n1ASL 有序表的折半搜索u 折半搜索的过程u 折半搜索的平均搜索长度 搜索成功时的平均搜索长度ASL 元素

11、的最大比较次数为 log2(n+1) 在区间low, high中取中点 (low + high) / 2 n1i2n1ii1ilogn1Cn1ASL 二叉搜索树u 二叉搜索树的搜索过程及性能分析。u 等概率情形下，二叉搜索树的搜索成功的平均搜索长度计算。u n个结点的不同二叉搜索树个数计算。u 平均搜索长度达到最小的二叉搜索树即为最优二叉搜索树。u 最优二叉搜索树中权大的结点离根近，权小的结点离根远。 二叉搜索树的搜索算法。 AVL树u AVL树的搜索过程及性能分析与二叉搜索树相同。u AVL树的插入过程：v 从根开始寻找插入位置。v 新结点作为叶结点插入。v 从插入位置向上回溯找发生不平衡结

12、点，确定参加旋转结点。v 旋转类型：左单旋、右单旋、先左后右双旋、先右后左双旋。1616例，输入关键码序列为 16, 3, 7, 11, 9, 26, 18, 14, 15 ，插入和调整过程如下。3163316311316161193169311269161118183163167391826117326161199716147112626911151831816731171491615112626149从空树开始的建树过程从空树开始的建树过程第八章 图n理解和掌握u 图的基本概念u 图的存储表示u 图的遍历u 最小生成树u 拓扑排序 n需要掌握的知识点 图的基本概念u 顶点的度、完全图、生成

13、树。u 无向图顶点度的和等于边数的2倍。u 有向图顶点的度等于入度+出度。u 无向连通图最大边数n(n- -1)/2, 最少边数n- -1（生成树）。u 有向强连通图最大边数n(n- -1), 最少边数n, (特例, n=1时最少边数0) 。 图的存储表示u 邻接矩阵是图的顺序存储, 适用于稠密图，e条边时有e2e个非零元素。u 邻接表是图的链接存储, 适用于稀疏图，e条边时有e2e个边链结点。u 邻接矩阵的矩阵元素个数与顶点数n有关, 与边数无关; 其非零元素个数与边数e有关。u 无向图的邻接矩阵是对称的; 有向图的邻接矩阵不一定是对称的。 图的遍历u 图的深度优先搜索DFS。u 图的广度优

14、先搜索BFS。 图的DFS生成树的高度通常比其BFS 生成树的高度要高。 非连通图或非强连通图遍历后得到的通常是一个生成森林。深度优先搜索n深度优先搜索的示例ACDEGBFIHACDEGBFIH123456789123456789前进回退深度优先搜索过程 深度优先生成树广度优先搜索n广度优先搜索的示例ACDEGBFIHACDEGBFH123456789123456789广度优先搜索过程 广度优先生成树I5046132281025142422161812舍去(12346)（4 , 6 , 24 ） 舍去 拓扑排序u 拓扑排序的过程。u 拓扑排序的时间代价为O(n+e)。u 拓扑排序的结果可能不唯

15、一。当各边权值不同时, 构造的最小生成树 是唯一的; 当各边权值有相同的, 构造的最小生成 树可能不唯一。C0C1C2C3C4C5拓扑排序的过程(a) 有向无环图C2C5C1C0C3(b) 输出顶点C4C1C2C5C3(c) 输出顶点C0C4C0C2C5C1C3(d) 输出顶点C3C1C2C5(e) 输出顶点C2C5C1(f) 输出顶点C1C5(g) 输出顶点C5拓扑有序序列。满足图中所有前驱和后继关系, 对于本来没有这种关系的顶点, 如和也排出先后次序。(h) 拓扑排序完成第九章 排序n理解和掌握u 直接插入排序u 希尔排序u 快速排序u 直接选择排序u 归并排序 n需要掌握的知识点 直接插

16、入排序u 直接插入排序的算法。u 直接插入排序的实例。 这是稳定的排序算法。 当初始排列已有序时速度提高最快。 最好时数据比较 n- -1次, 移动 0 次。 最坏时数据比较 n(n- -1)/2 次, 移动n- -1次。 希尔排序 （缩小增量排序）u 希尔排序的实例（不要算法） 希尔排序是不稳定的排序方法 gap取法: Shell 提出取gap = n/2 ，gap = gap/2 ，直到gap = 1。 对特定的待排序对象序列，可以准确地估算比较次数和移动次数。 当 n 很大时，平均比较次数和平均移动次数大约在 n1.25 到 1.6n1.25 的范围内。 i (0) (1) (2) (3

17、) (4) (5) gap 初初始始 21 25 49 25* 16 08 1 21 25* 3 25 16 49 08 21 16 08 25* 25 49 i (0) (1) (2) (3) (4) (5) gap 2 21 08 25 2 16 25* 49 08 16 21 25* 25 49 3 08 16 21 25* 25 49 1 08 16 21 25* 25 49 快速排序 （分区排序）u 快速排序的算法。u 快速排序的实例。 快速排序是不稳定的排序方法。 就平均计算时间而言, 快速排序是所有内排序方法中最好的一个,每趟等分排序区间, 计算时间 O(nlog2n) 。 当初

18、始排列已经有序时, 速度最慢,数据比较达 n(n- -1)/2 次。 i = 1 (0) (1) (2) (3) (4) (5) pivot 初初始始 21 25 49 25* 16 08 21 p i i i i 循循环环4 21 16 49 25* 25 08 25 16 p i i循循环环5 21 16 08 25* 25 49 49 08 p i 出出循循环环 08 16 21 25* 25 49 21 08 直接选择排序u 直接选择排序的算法。u 直接选择排序的实例。 直接选择排序是不稳定的排序方法。 数据比较次数不受初始排列影响 = n(n- -1)/2。 数据移动次数受初始排列影

19、响, 最好 0 次，最坏 3(n- -1) 次。 归并排序u 归并排序的实例（不要算法）。 归并排序是稳定的排序方法。 归并趟数 = log2(n+1) , n 是待排序数据对象个数。 每趟数据比较次数受初始排列影响, 最好（有序） n/2, 最坏 = n- -1。 数据移动次数不受初始排列影响, O(nlog2n) 次（表之间传送）。 第十章 索引与散列n理解和掌握u B 树u 散列 n需要掌握的知识点 B 树u m阶B树是平衡m路搜索树。u m阶B树所有失败结点在同一层。故平衡m路搜索树不一定是m阶B树。u m阶B树的非失败结点最多包含 m- -1 个关键码, 最少 m/2 - -1 个关

20、键码。u m阶B树高度不超过(含失败结点)： h log m / 2 ( (n+1)/2 )+1 散列u 散列函数：除留余数法。u 解决冲突的闭散列法（线性探查）。u 解决冲突的开散列法。 除留余数法注意除数的选择：质数。 除留余数法优于其他散列函数。 开散列法优于闭散列法。 闭散列情形不能真正做表项的物理删除, 否则会中断其他表项的查找。 闭散列法u 线性探查的探查序列u 搜索成功的平均探查次数u 搜索不成功的平均探查次数 探查序列 H0 = Hash(key) Hi = (H0 + i) % m, i = 1,2, m-1 搜索成功的平均探查次数 = 每个已有表项找到它的比较次数的平均值 搜索不成功的平均探查次数 = 散列函数可能算出的散列地址上插入新表项时找到空位的比较次数的平均值 线性探查法容易产生“堆积” 闭散列法 1, 开散列法 可大于 1 平均搜索长度取决于装填因子 平均搜索长度与装填因子之间关系 处理冲突 平均搜索长度 ASL 的方法 搜索成功 Sn 搜索不成功 (登入新记录) Un 线性探查法 )(