数据结构与算法.pptx

《数据结构与算法.pptx》由会员分享，可在线阅读，更多相关《数据结构与算法.pptx（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1页2023/2/14 23:15本章内容本章内容 1.1 1.1 算法算法 1.2 1.2 数据结构基本概念数据结构基本概念 1.5 1.5 线性链表线性链表 1.6 1.6 树与二叉树树与二叉树 1 1.7.7 查找技术查找技术 1.3 1.3 线性表及其顺序存储结构线性表及其顺序存储结构 1.4 1.4 栈和栈和队列队列 1.8 1.8 排序技术排序技术第1页/共62页第2页2023/2/14 23:151.1 算法算法1.1.1 算法的基本概念算法的基本概念 1.算法的基本特征算法的基本特征 算法是指解决问题方案的准确而完整的描述。即用来完算法是指解决问题方案的准确而完整的描述。即用

2、来完成某个特定任务的正确的、有限步骤序列。成某个特定任务的正确的、有限步骤序列。第2页/共62页第3页2023/2/14 23:15例题：例题：算法的有穷性是指算法的有穷性是指A)算法程序的运行时间是有限的算法程序的运行时间是有限的B)算法程序所处理的数据量是有限的算法程序所处理的数据量是有限的C)算法程序的长度是有限的算法程序的长度是有限的D)算法只能被有限的用户使用算法只能被有限的用户使用下列叙述正确的是下列叙述正确的是A)算法的执行效率与数据的存储结构有关算法的执行效率与数据的存储结构有关B)算法的空间复杂度是指算法程序中指令（或语句）的算法的空间复杂度是指算法程序中指令（或语句）的条数

3、条数C)算法的有穷性是指算法必须能在执行有限个步骤之后算法的有穷性是指算法必须能在执行有限个步骤之后终止终止D)以上三种说法都不对以上三种说法都不对第3页/共62页第4页2023/2/14 23:15一个算法由两个基本要素组成：一个算法由两个基本要素组成：1)对数据对象的运算和操作对数据对象的运算和操作 包括以下四类：包括以下四类：算术运算算术运算逻辑运算逻辑运算关系运算关系运算数据传输数据传输 2)算法的控制结构算法的控制结构算法中各操作之间的执行顺序称为算法的控制结构。算法中各操作之间的执行顺序称为算法的控制结构。描述算法的工具包括自然语言描述、程序设计语言描述、描述算法的工具包括自然语言

4、描述、程序设计语言描述、流程图描述等。流程图描述等。一个算法一般可以用顺序、选择、循环三种基本结构组一个算法一般可以用顺序、选择、循环三种基本结构组合而成。合而成。2.算法的基本要素算法的基本要素第4页/共62页第5页2023/2/14 23:153.算法设计基本方法算法设计基本方法n 列举法列举法n 归纳法归纳法n 递推递推n 递归递归n 减半递推技术减半递推技术n 回溯法回溯法第5页/共62页第6页2023/2/14 23:15算法的复杂度包括时间复杂度和空间复杂度。算法的复杂度包括时间复杂度和空间复杂度。1 1）算法的时间复杂度：算法的时间复杂度：是指执行算法所需要的计算工作量。是指执行

5、算法所需要的计算工作量。2 2）算法的空间复杂度：算法的空间复杂度：是指执行算法所需要的存储空间。是指执行算法所需要的存储空间。1.1.2 算法复杂度算法复杂度 第6页/共62页第7页2023/2/14 23:15 算法的时间复杂度算法的时间复杂度 一般把程序运行时一般把程序运行时语句的执行次数语句的执行次数作为估算程序执行时间作为估算程序执行时间的量度。的量度。例：例：估算以下函数的时间复杂度。估算以下函数的时间复杂度。Dim Dim a(5)As Integer a(5)As IntegerConst n=5Const n=5k=0 k=0 执行执行 1 次次 for i=1 To n S

6、tep 1 for i=1 To n Step 1 执行执行 n 次次 if a(i)a(k)Then k=i if a(i)0)个数据元素的有限集合。它满足以下两个数据元素的有限集合。它满足以下两个条件：个条件：有且仅有一个特定的称为根的元素；有且仅有一个特定的称为根的元素；其余元素分为（其余元素分为（）个互不相交的有限集）个互不相交的有限集合合1、2、，其中每个集合又都是一棵树并、，其中每个集合又都是一棵树并称其为根的称其为根的子树子树。树形结构是一类非常重要的树形结构是一类非常重要的非线性结构，适合于描述数据元非线性结构，适合于描述数据元素之间的层次关系素之间的层次关系。1.6.1 树的

7、基本概念树的基本概念第44页/共62页第45页2023/2/14 23:15树的常用术语树的常用术语 双亲双亲、子女子女、边边：若结点：若结点y是结点是结点x的一棵子树的根，则的一棵子树的根，则x称做称做y的的“双亲双亲”y称做称做x的的“子女子女”；有序对；有序对 称做从称做从x到到y的的“边边”。兄弟兄弟：具有同一双亲的结点：具有同一双亲的结点。路径路径、路径长度路径长度：若树中存在着一个结点的序列：若树中存在着一个结点的序列12j，使使ki是是ki+1（1ij）的双亲，则称该结点序列为从）的双亲，则称该结点序列为从k1到到kj的一条路径；的一条路径；路径长度等于路径长度等于j-1，它是该

8、路径所经过的边的数目，它是该路径所经过的边的数目。结点的层数结点的层数：根结点层数为：根结点层数为1，其余结点层数等于其双亲结点层数，其余结点层数等于其双亲结点层数加加1。树的深度（高度）树的深度（高度）：即树中层数最大的结点的层数：即树中层数最大的结点的层数。结点的度数结点的度数、树的度数树的度数：一个结点子女的个数称为该结点的：一个结点子女的个数称为该结点的“度度数数”。树中度数最大的结点的度数叫做树中度数最大的结点的度数叫做“树的度数树的度数”。树叶树叶、分支结点分支结点：度数为：度数为0的结点叫做的结点叫做“树叶树叶”；度数大于；度数大于0的结的结点叫做点叫做“分支结点分支结点”或或“

9、内结点内结点”。第45页/共62页第46页2023/2/14 23:15树的常用术语举例树的常用术语举例 是的是的双亲双亲，是的，是的子女子女，是从到的是从到的边边。、互为、互为兄弟兄弟，而和不是兄弟，而和不是兄弟 。ADINADIN是从结点到结点的一条是从结点到结点的一条路径路径，其，其长度长度为为 。层数层数为为 的结点有，的结点有，层数层数为的结点有、为的结点有、。树的深度树的深度为为 。、的、的度数度数分别为、；分别为、；树的度数树的度数为为 。、都是、都是树叶树叶，其余结点都是，其余结点都是分支结点分支结点 。森 林第46页/共62页第47页2023/2/14 23:151.6.2

10、二叉树及其基本性质二叉树及其基本性质 二叉树二叉树是是n（n0）个结点的有限集合。它或者是空集）个结点的有限集合。它或者是空集（n0），或者由一个根结点及两棵互不相交的、分别称为），或者由一个根结点及两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。这个根的左子树和右子树的二叉树组成。1.什么是什么是二叉二叉树树 二叉树五种基本形态二叉树五种基本形态 二叉树最多有两个子树，且子树有左、右之分，而树的二叉树最多有两个子树，且子树有左、右之分，而树的子树不分左右。子树不分左右。二叉树可以是空，而树不能为空。二叉树可以是空，而树不能为空。树和二叉树的差别树和二叉树的差别第47页/共62页第

11、48页2023/2/14 23:15二叉树的性质二叉树的性质性质性质 二叉树第二叉树第 i i 层上的结点数目最多为层上的结点数目最多为2 2k-1k-1（K K1 1）。）。性质性质 深度为深度为m m的二叉树至多有的二叉树至多有2 2m m-1-1个结点（个结点（k k）。）。性质性质 在任意一棵二叉树中，度数为在任意一棵二叉树中，度数为0 0的结点的个数总比度为的结点的个数总比度为2 2的结点的结点多一个。多一个。2.二叉树的性质二叉树的性质3.两种特殊的二叉树：满二叉树与完全二叉树两种特殊的二叉树：满二叉树与完全二叉树满二叉树满二叉树 完全二叉树完全二叉树第48页/共62页第49页20

12、23/2/14 23:15性质性质4 4 具有具有n n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 loglog2 2n n 性质性质5 5 若对一棵有若对一棵有n n个结点的完全二叉树，按自顶向下、同层由左到个结点的完全二叉树，按自顶向下、同层由左到右顺序依次为其每个结点从右顺序依次为其每个结点从1 1开始编号，则对编号为开始编号，则对编号为 k k的结点的结点 （1 1k kn n）则有：）则有：若若 k=1k=1，则该结点是根结点。若，则该结点是根结点。若 k1k1，则，则 k ki i 双亲结点的编号为双亲结点的编号为INT(k/2)INT(k/2)若若 2k2kn n，则

13、该结点左子女结点的编号是，则该结点左子女结点的编号是2k2k，否则，否则 该结点无左该结点无左子女。子女。若若 2k+12k+1n n，则该结点右子女结点的编号为，则该结点右子女结点的编号为2k+12k+1，否则该结点无，否则该结点无右子女。右子女。（二叉树中的结点数（二叉树中的结点数n=12n=12）第49页/共62页第50页2023/2/14 23:151.6.3 二叉树的存储结构二叉树的存储结构 对完全二叉树，利用性质对完全二叉树，利用性质5，将其所有结点按编号顺序依次，将其所有结点按编号顺序依次存储在一维数组里。存储在一维数组里。对一般二叉树，需要加上一些并不存在的对一般二叉树，需要加

14、上一些并不存在的“虚结点虚结点”，转，转换为完全二叉树的形式。换为完全二叉树的形式。1.顺序存储结构顺序存储结构 第50页/共62页第51页2023/2/14 23:15二叉树的存储结构二叉树的存储结构 链接存储时结点的结构链接存储时结点的结构第51页/共62页第52页2023/2/14 23:151.6.4 二叉树的遍历二叉树的遍历先序遍历先序遍历 访问根结点，先序遍历左子树，先序遍历右子树。访问根结点，先序遍历左子树，先序遍历右子树。中序遍历中序遍历 中序遍历左子树，访问根结点，中序遍历右子树。中序遍历左子树，访问根结点，中序遍历右子树。后序遍历后序遍历 后序遍历左子树，后序遍历右子树，访

15、问根结点。后序遍历左子树，后序遍历右子树，访问根结点。层次遍历层次遍历 按层数由小到大、同一层从左到右顺序依次访问二按层数由小到大、同一层从左到右顺序依次访问二叉树的各个结点叉树的各个结点。先序访问序列先序访问序列：ABDGECF中序访问序列中序访问序列：DGBEAFC后序访问序列后序访问序列：GDEBFCA层次访问序列层次访问序列：ABCDEFG 举例：举例：第52页/共62页第53页2023/2/14 23:15例题：例题：某二叉树中度为2的结点有18个，则该二叉树中有_个叶结点。某二叉树中度为2的结点有n个，则该二叉树中有_个叶结点。在树型结构中，树根结点没有_。在深度为5的满二叉树中，

16、叶子结点的个数为 A)32 B)31 C)16 D)15若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是 A)bdgcefha B)gdbecfha C)bdgaechf D)gdbehfca具有3个结点的二叉树有 A)2种形态 B)4种形态 C)7种形态 D)5种形态 第53页/共62页第54页2023/2/14 23:151.7 查找技术查找技术1.7.1 顺序查找顺序查找基本方法：基本方法：从线性表的第一个元素开始，依次将从线性表的第一个元素开始，依次将线性表中的元素与被查找元素进行比较。若相等，线性表中的元素与被查找元素进

17、行比较。若相等，则查找成功；如果找遍全表也没有发现满足条件的则查找成功；如果找遍全表也没有发现满足条件的元素，则查找失败。元素，则查找失败。要求：要求：查找表必须采用线性表。查找表必须采用线性表。第54页/共62页第55页2023/2/14 23:15在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为 A)63 B)64 C)6 D)7例题：例题：第55页/共62页第56页2023/2/14 23:151.7.2 二分查找二分查找 二分查找的必要条件：二分查找的必要条件：1)必须是以必须是以顺序方式顺序方式存储的线性表存储的线性表；2)线性表中所有数据元素必须线性表中所有数据元

18、素必须有序排列有序排列。基本方法：基本方法：将给定值与处于顺序表将给定值与处于顺序表“中间位置中间位置”上的元素进行比较，若相等则查找成功，若给定值上的元素进行比较，若相等则查找成功，若给定值大于中间位置上的元素则在表的后半部分继续进行大于中间位置上的元素则在表的后半部分继续进行二分查找，否则在表的前半部分继续进行二分查找。二分查找，否则在表的前半部分继续进行二分查找。如此进行下去直至找到满足条件的元素，或当前查如此进行下去直至找到满足条件的元素，或当前查找区为空，此时查找失败。找区为空，此时查找失败。第56页/共62页第57页2023/2/14 23:15第57页/共62页第58页2023/

19、2/14 23:151.8 排序技术排序技术1.冒泡排序：冒泡排序：设待排序的元素序列为设待排序的元素序列为S=e0,e1,en-1，要求按升，要求按升序排列。序排列。基本思想：基本思想：从待排序记录集的一端（这里假定为低端）对相邻的两个从待排序记录集的一端（这里假定为低端）对相邻的两个元素（元素（e0和和e1，e1和和e2，en-2和和en-1）依次比较它们的）依次比较它们的排序码，若不符合排序的顺序要求，就将相应的两个元素排序码，若不符合排序的顺序要求，就将相应的两个元素互换，此过程称为一趟冒泡排序，最多经过互换，此过程称为一趟冒泡排序，最多经过n-1趟冒泡排序，趟冒泡排序，排序工作即可完

20、成。排序工作即可完成。每趟排序的结果是将待排序记录集中排序码最大的元素交每趟排序的结果是将待排序记录集中排序码最大的元素交换到待排序记录集最后一个元素的位置。假设在一趟冒泡换到待排序记录集最后一个元素的位置。假设在一趟冒泡排序时，从排序时，从ej+1以后没有发生元素的互换，则说明以后没有发生元素的互换，则说明ej+1以后以后的元素是已经排好序的，下面只需要在的元素是已经排好序的，下面只需要在e0到到ej范围内进行范围内进行新一趟的冒泡排序，即待排序记录集是从新一趟的冒泡排序，即待排序记录集是从e0到到ej，下一趟，下一趟只需从只需从e0到到ej范围内进行。范围内进行。第58页/共62页第59页

21、2023/2/14 23:15例题：例题：排序是程序设计中的一种重要操作，常见的排序方法有插入排排序是程序设计中的一种重要操作，常见的排序方法有插入排序、序、_排序和选择排序排序和选择排序对长度为对长度为n的线性表排序，最坏的情况下，比较次数不是的线性表排序，最坏的情况下，比较次数不是n(n-1)/2的排序方法是的排序方法是 A)快速排序快速排序 B)冒泡排序冒泡排序 C)直接插入排序直接插入排序 D)堆堆排序排序假设线性表长度为假设线性表长度为n，则在最坏的情况下，冒泡排序需要的比较，则在最坏的情况下，冒泡排序需要的比较次数为次数为 A)log2n B)n2 C)O(n1.5)D)n(n-1

22、)/2说明：最常见的排序有插入排序（简单插入、希尔排序）、交换排说明：最常见的排序有插入排序（简单插入、希尔排序）、交换排序（冒泡排序、快速排序）和选择排序（简单选择、堆排序）序（冒泡排序、快速排序）和选择排序（简单选择、堆排序）。假设线性表的长度为假设线性表的长度为n，则在最坏的情况下：，则在最坏的情况下：冒泡排序需要比较的次数为：冒泡排序需要比较的次数为：n(n-1)/2插入排序需要比较的次数为：插入排序需要比较的次数为：n(n-1)/2希尔插入排序需要比较的次数为：希尔插入排序需要比较的次数为：O(n1.5)堆排序需要比较的次数为：堆排序需要比较的次数为：O(nlog2n)第59页/共62页第60页2023/2/14 23:15查找：对长度为n的无序表，不论是顺序表还是链表都只能顺序查找。平均比较次数为n/2次；在最坏情况下的比较次数为n次。对长度为n的有序顺序表，采用二分查找，在最坏情况下的比较次数为O(nlog2n)次。第60页/共62页2023/2/14 23:15第61页第61页/共62页第1章 数据结构与算法第62页2023/2/14 23:15感谢您的观看。第62页/共62页