《软件基础串讲》PPT课件.ppt

《《软件基础串讲》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《软件基础串讲》PPT课件.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机软件基础计算机软件基础计算机软件基础计算机软件基础重点知识串讲重点知识串讲1 树与二叉树树与二叉树 一、树与二叉树概念一、树与二叉树概念 1 1树树t树（树（treetree）是一种简单的）是一种简单的非线性结构。在树这种数据非线性结构。在树这种数据结构中，所有数据元素之间结构中，所有数据元素之间的关系具有明显的层次特性。的关系具有明显的层次特性。左图表示了一棵一般的树。左图表示了一棵一般的树。由图可以看出，在用图形表由图可以看出，在用图形表示树这种数据结构时，很像示树这种数据结构时，很像自然界中的树，只不过是一自然界中的树，只不过是一棵倒长的树，因此，这种数棵倒长的树，因此，这种数据结

2、构就用据结构就用“树树”来命名。来命名。一般的树一般的树2t在现实世界中，能用树这种在现实世界中，能用树这种数据结构表示的例子有很多。数据结构表示的例子有很多。例如，图中的树表示了学校例如，图中的树表示了学校行政关系结构；由于树具有行政关系结构；由于树具有明显的层次关系，因此，树明显的层次关系，因此，树与二叉树都可以用树这种数与二叉树都可以用树这种数据结构来描述。在所有的层据结构来描述。在所有的层次关系中，人们最熟悉的是次关系中，人们最熟悉的是血缘关系，按血缘关系可以血缘关系，按血缘关系可以很直观地理解树结构中各数很直观地理解树结构中各数据元素结点之间的关系，因据元素结点之间的关系，因此，在描

3、述树结构时，也经此，在描述树结构时，也经常使用血缘关系中的一些术常使用血缘关系中的一些术语。语。学校行政层次结构树学校行政层次结构树3t树：是一个或多个结点的有穷集合树：是一个或多个结点的有穷集合T T，且满足以下条件：且满足以下条件：1 1、有且仅有一个指定的称作树根、有且仅有一个指定的称作树根的结点；的结点；2 2、除根以外的其余结点被分成、除根以外的其余结点被分成m m个不相交的集合，这些集合的每一个又个不相交的集合，这些集合的每一个又都是树，并且称为根的子树。都是树，并且称为根的子树。42 2树的一些术语树的一些术语t结点的度：结点结点的度：结点N N的子树数称为结点的度。的子树数称为

4、结点的度。t树的度：树树的度：树T T中各结点的度的最大值称的树中各结点的度的最大值称的树T T的度。的度。t叶子：树中度为叶子：树中度为0 0的结点称为叶子（终端结点）。的结点称为叶子（终端结点）。t分枝结点：树中度不为分枝结点：树中度不为0 0的结点称为分枝结点（非终端结点）的结点称为分枝结点（非终端结点）。t双亲和孩子：若树中结点双亲和孩子：若树中结点P P的一棵子树的根是结点的一棵子树的根是结点C C，则我，则我们称们称P P是是C C的双亲或父母，反之称的双亲或父母，反之称C C是是P P的孩子。的孩子。t结点的层数：树的层数为结点的层数：树的层数为1 1，其余任一结点的层数等于它的

5、，其余任一结点的层数等于它的双亲的层数加双亲的层数加1.1.t树的深度：树中各结点的层数的最大值称为树的深度：树中各结点的层数的最大值称为T T的深度（高度）的深度（高度）。53 3二叉树二叉树1 1）二叉树概念）二叉树概念t二叉树（二叉树（bintreebintree）是一种很有用的非线性结构。）是一种很有用的非线性结构。二叉树不同于前面介绍的树结构，但它与树结构二叉树不同于前面介绍的树结构，但它与树结构可以相互转换，二叉树的存储结构及其算法都较可以相互转换，二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。为简单，因此二叉树显得特别重要。t二叉树是二叉树是n n（n n 0 0）

6、个结点的有限集合，它或者是）个结点的有限集合，它或者是空集（空集（n n=0=0），或者由一个根结点及两棵互不相交），或者由一个根结点及两棵互不相交的、分别称这个根的左子树和右子树的二叉树组的、分别称这个根的左子树和右子树的二叉树组成。成。t二叉树不是树的特殊情形，与度数为二叉树不是树的特殊情形，与度数为2 2的有序树不的有序树不同。同。6t二叉树具有以下两个特点：二叉树具有以下两个特点：（1 1）非空二叉树只有一个根结点；）非空二叉树只有一个根结点；（2 2）每一个结点最多有两棵子树，且分）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。别称为该结点的左子树与右子树。t由以上特点

7、可以看出，在二叉树中，每由以上特点可以看出，在二叉树中，每一个结点的度最大为一个结点的度最大为2 2，即所有子树，即所有子树（左子树或右子树）也均为二叉树，而（左子树或右子树）也均为二叉树，而树结构中的每一个结点的度可以是任意树结构中的每一个结点的度可以是任意的。另外，二叉树中的每一个结点的子的。另外，二叉树中的每一个结点的子树被明显地分为左子树与右子树。在二树被明显地分为左子树与右子树。在二叉树中，一个结点可以只有左子树而没叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树，也没子树。当一个结点既没有左子树，也没

8、有右子树时，该结点即是叶子结点。图有右子树时，该结点即是叶子结点。图是一棵深度为是一棵深度为4 4的二叉树。的二叉树。t五种形态：空，根，左，右，左右五种形态：空，根，左，右，左右72 2）二叉树的基本性质二叉树的基本性质t性质性质1 1：在二叉树的第在二叉树的第k k层上，最多有层上，最多有2 2k k11个结点。个结点。根据二叉树的特点，这个性质是显然的。根据二叉树的特点，这个性质是显然的。t性质性质2 2：深度为：深度为k k的二叉树最多有的二叉树最多有2 2k k11个结点。个结点。深度为深度为k k的二叉树是指二叉树共有的二叉树是指二叉树共有k k层。根据性质层。根据性质1 1，只要

9、将第，只要将第1 1层到第层到第k k层上的最大的结点数相加，层上的最大的结点数相加，就可以得到整个二叉树中结点数的最大值，即就可以得到整个二叉树中结点数的最大值，即t性质性质3 3：在任意一棵二叉树中，度为在任意一棵二叉树中，度为0 0的结点（即的结点（即叶子结点）总是比度为叶子结点）总是比度为2 2的结点多一个，即的结点多一个，即 n0=n2+1 n0=n2+1t性质性质4 4：具有：具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 int int（log2nlog2n）+1+1 8t满二叉树：满二叉树：满二叉树是一棵深度为满二叉树是一棵深度为k，结点数为，结点数为2K-1

10、的二叉树。的二叉树。t完全二叉树：完全二叉树：完全二叉树是满二叉树在最下层自右向完全二叉树是满二叉树在最下层自右向左去除部分结点；左去除部分结点；93 3）二叉树的存贮表示：）二叉树的存贮表示：t顺序存贮：顺序存贮：二叉树的顺序存储结构就是把二叉树的二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单所有结点按照层次顺序存储到连续的存储单元中。（存储前先将其画成完全二叉树）元中。（存储前先将其画成完全二叉树）t链表表示：链表表示：lchildlchild，datadata，rchlid rchlid 104 4）遍历：）遍历：根据访问结点的次序不同可得三种遍历：根据访问结点

11、的次序不同可得三种遍历：先序遍历（前序遍历或先根遍历），中序遍先序遍历（前序遍历或先根遍历），中序遍历（或中根遍历）、后序遍历（或后根遍历）历（或中根遍历）、后序遍历（或后根遍历）。t前序：根前序：根左左右右t中序：左中序：左根根右右t后序：左后序：左右右根根115 5）树的二叉树表示）树的二叉树表示 转换方法：转换方法：兄弟相连，保留长子的连线。兄弟相连，保留长子的连线。12查找查找一、概念一、概念t查找：就是确定一个已给的数据是否出现在某个数查找：就是确定一个已给的数据是否出现在某个数据表中。据表中。t域（字段）：组成记录的每个数据项。域（字段）：组成记录的每个数据项。t关键字：通常记录中

12、总存在某个或某组数据项，它关键字：通常记录中总存在某个或某组数据项，它们的值能唯一标识一个记录，这个（组）数据项称为们的值能唯一标识一个记录，这个（组）数据项称为关键字。关键字。t平均查找长度平均查找长度ASLASL：衡量查找算法效率优劣的标准，是：衡量查找算法效率优劣的标准，是在查找过程中对关键字需要执行的平均比较次数。在查找过程中对关键字需要执行的平均比较次数。13二、查找方法二、查找方法t线性表查找的方法：线性表查找的方法：顺序查找：逐个查找，顺序查找：逐个查找，ASL=ASL=（n+1n+1）/2/2；二分查找：取中点二分查找：取中点intint（n/2n/2）比较，若小）比较，若小就

13、比左区间，大就比右区间。用二叉判定树就比左区间，大就比右区间。用二叉判定树表示。表示。ASL=ASL=（每层结点数（每层结点数*层数）层数）/N./N.14t二叉排序树（二叉排序树（BSTBST），（二叉查找树）。定义是：），（二叉查找树）。定义是：二叉排序树是空树或者满足如下性质的二叉树：二叉排序树是空树或者满足如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根若它的左子树非空，则左子树上所有结点的值均小于根结点的值；结点的值；若它的右子树非空，则右子树上所有结点的值均大于根若它的右子树非空，则右子树上所有结点的值均大于根结点的值；结点的值；左、右子树本身又是一棵二叉排序树。

14、左、右子树本身又是一棵二叉排序树。t二叉排序树的插入、建立、删除的算法平均时间性能是：二叉排序树的插入、建立、删除的算法平均时间性能是：O O（nlog2nnlog2n）。）。t二叉排序树的删除操作可分三种情况进行处理：二叉排序树的删除操作可分三种情况进行处理：*P *P是叶子，则直接删除是叶子，则直接删除*P*P，即将，即将*P*P的双亲的双亲*parent*parent中指中指向向*P*P的指针域置空即可。的指针域置空即可。*P *P只有一个孩子只有一个孩子*child*child，此时只需将，此时只需将*child*child和和*p*p的双亲的双亲直接连接就可删去直接连接就可删去*p.

15、*p.*p *p有两个孩子，则先将有两个孩子，则先将*p*p结点的中序后继结点的数据到结点的中序后继结点的数据到*p*p，删除中序后继结点。，删除中序后继结点。15t散列技术：将结点按其关键字的散列地址存散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。储到散列表的过程称为散列。t哈希查找：哈希查找：t哈希函数：能把关键字映射成记录存贮地址哈希函数：能把关键字映射成记录存贮地址的函数。的函数。t哈希表：假定数组哈希表：假定数组HT0m-1HT0m-1为存贮记录为存贮记录的地址空间，哈希函数的地址空间，哈希函数H H以每个记录的关键以每个记录的关键字值字值K K作为输入，产生一个落

16、在作为输入，产生一个落在0m-10m-1内的整数内的整数H H（K K），并以它作为），并以它作为K K所标识的记所标识的记录在表录在表HTHT中的地址或索引号，这样产生的记中的地址或索引号，这样产生的记录表录表H H（K K）叫做哈希表。）叫做哈希表。16t构造哈希函数的方法：构造哈希函数的方法：平方取中法：平方取中法：hash=hash=intint（x2x2）%100%100）除余法：表长为除余法：表长为m m，hash=hash=x%mx%m相乘取整法：相乘取整法：hash=hash=intint（m*m*（x*A-x*A-intint（x*Ax*A）；A=0.618A=0.618随机

17、数法：随机数法：hash=randomhash=random（x x）。）。17t处理冲突的方法：处理冲突的方法：开放定址法：开放定址法：一般形式为一般形式为hi=hi=（h h（keykey）+di+di）%m1im-1%m1im-1，开放定址法要求散列表，开放定址法要求散列表的装填因子的装填因子1.1.拉链法：拉链法：是将所有关键字为同义词的结点链接在同一个是将所有关键字为同义词的结点链接在同一个单链表中。单链表中。拉链法的优点：拉链法的优点：拉链法处理冲突简单，且无堆积现象；拉链法处理冲突简单，且无堆积现象；链表上的结点空间是动态申请的适于无法确定表长的情链表上的结点空间是动态申请的适于

18、无法确定表长的情况；况；拉链法中拉链法中可以大于可以大于1 1，结点较大时其指针域可忽略，因，结点较大时其指针域可忽略，因此节省空间；此节省空间；拉链法构造的散列表删除结点易实现。拉链法构造的散列表删除结点易实现。拉链法也有缺点：当结点规模较小时，用拉链法中的指拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。针域也要占用额外空间，还是开放定址法省空间。18排序排序t排序是使文件中的记录按关键字递增（或递排序是使文件中的记录按关键字递增（或递减）次序排列起来。减）次序排列起来。基本操作：比较关键字大小；改变指向记录基本操作：比较关键字大小；改变指向记录

19、的指针或移动记录。的指针或移动记录。存储结构：顺序结构、链表结构、索引结构。存储结构：顺序结构、链表结构、索引结构。排序过程中不涉及数据的内、外存交换则称排序过程中不涉及数据的内、外存交换则称之为之为“内部排序内部排序”（内排序），反之，若存（内排序），反之，若存在数据的内外存交换，则称之为外排序。在数据的内外存交换，则称之为外排序。19t内部排序内部排序方法方法可分为：插入排序、选择排序、可分为：插入排序、选择排序、交换排序。交换排序。t评价排序算法好坏的标准主要有两条：执行评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程时间和所需的辅助空间，另外算法的复杂程度也

20、是要考虑的一个因素。度也是要考虑的一个因素。t插入排序：插入排序：直接插入排序：直接插入排序：逐个向前插入到合适位逐个向前插入到合适位置。置。t直接插入排序的时间复杂度为直接插入排序的时间复杂度为O O（n2n2），），比较次数为（比较次数为（n+2n+2）（）（n-1n-1）/2/2；移动次数为（移动次数为（n+4n+4）（）（n-1n-1）/2/2；20t交换排序：交换排序：冒泡排序：自下向上确定最轻的一个，后自冒泡排序：自下向上确定最轻的一个，后自上向下确定最重的一个。上向下确定最重的一个。冒泡排序时间复杂度为冒泡排序时间复杂度为O（n2），），比较次数为比较次数为n（n-1）/2；移动次数为移动次数为3n（n-1）/2；快速排序：快速排序：以第一个元素为参考基准，设以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，定、动两个指针，发生交换后指针交换位置，直到指针重合。重复直到排序完成。直到指针重合。重复直到排序完成。快速排序时间复杂度为快速排序时间复杂度为O（nlog2n），），比较次数为比较次数为n（n-1）/2；21t选择排序：选择排序：直接选择排序：选择最小的放在比较区前。直接选择排序：选择最小的放在比较区前。直接选择排序时间复杂度为直接选择排序时间复杂度为O（n2）。）。比较次数为比较次数为n（n-1）/2；22