数据结构课件第九章

《数据结构课件第九章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、查找和排序是数据处理系统中最重要的两个操作；其次是插入、删除操作；讨论查找、排序，不可避免要涉及文件、记录、关键字等概念。文件——查找表，是由同一类型的数据元素(记录)构成的集合记录——构成文件的数据元素，是文件中可存取的数据的基本单位字段——数据项，数据的最小单位关键字——某个可以用来标识记录的数据项主关键字——某个可以用来唯一标识记录的数据项次关键字——可以用来识别若干记录的数据项第九章查找D01曲守宁数据库004S01王永燕数据结构003L01潘玉奇程序设计002S01严蔚敏数据结构001………………………课程号

2、课程名教师课程类别课程安排表文件记录数据项主关键字次关键字对文件经常进行的操作有:1)查询某个“特定”的数据元素是否存在4)对数据元素进行排序2)插入某个数据元素3)删除某个数据元素查找算法排序算法不管何种操作，都遵循一个重要的性质:都是对主关键字操作9.1静态查找9.1.1顺序查找从表最后一个记录开始，逐个向前进行记录关键字和给定值的比较，相等，查找成功；不等，比较下一个记录；思想:直至第一个记录，若均不等，则查找不成功。12...n-2n-1nTomAnnieJohnRoseJack查找John比较2次查找Jack

3、比较n-1次若查找不存在比较n次9.1.2有序表的查找表中数据元素按照主关键字顺序排列。折半查找斐波那契查找插值查找5，13，19，21，37，56，64，75，80，88，92折半查找5，13，19，21，37，56，64，75，80，88，92lowhighmid=(low+high)/2查找211234567891011midmid=6high=mid–1=5highmid=3midlow=mid+1=4lowmid=4mid找到查找85lowhighmid=6midlow=mid+1=7lowmid=9midl

4、ow=mid+1=10lowmid=10midhigh=mid–1=9highhigh

5、树。1385231837查询操作:1385231837如何查找元素5?555查找成功！1385231837如何查找元素9?999查询+插入操作:查找不成功，执行插入。同一序列，不同二叉排序树的查找性能差别很大。例，{45,24,53,12,37,93}452453123793122437455393O(n)O(logn+1)为了实现二叉排序树的平均查找长度和logn等数量级，需要对二叉排序树进行“平衡化”处理，即构造平衡二叉树。9.2.2平衡二叉树——AVL树Adelson—Velskii—Landis平衡二叉树或者是

6、一棵空树，或者是具有下列性质的二叉树:其左子树和右子树的深度之差的绝对值不超过1；其左子树和右子树都是平衡二叉树；平衡二叉树首先是一棵二叉排序树；例,ABCDABCDEFGABCDEFABCDFGE结点的平衡因子:该结点的左子树的深度减去右子树的深度。由于平衡二叉树要求左右子树深度之差的绝对值不大于1，故结点的平衡因子只可能为-1、0、1。4524531293例，0100-1可以证明平衡二叉树的深度与logn同数量级。如何在二叉排序树的构造过程中实现平衡化从而得到平衡二叉树？例，序列{1324379053}13024-

7、1037-2-10左旋，以失去平衡结点的儿子结点为基准。37241300090-10-1053-20-210先右旋，以失去平衡结点的儿子结点为基准。再左旋，以失去平衡结点的儿子结点为基准。53905390370-1000平衡！平衡二叉树调整规则:RR型:新结点加入到右子树的右子树中。1调整规则:左旋，以失去平衡的结点的儿子结点为基准，整棵子树向左下方旋转。ABBLBRAL-10-2-1BAALBLBR00LL型:新结点加入到左子树的左子树中。11021调整规则:右旋，以失去平衡的结点的儿子结点为基准，整棵子树向右下方旋

8、转。ABBLBRARBABRARBL00RL型:新结点加入到右子树的左子树中。1调整规则:ABBRALCCLCR-100-211先右旋，以失去平衡的结点的儿子结点为基准，构造成RR型。后左旋。ACCLALBCRBR-2-1-1CBCLALACRBR0-10LR型:新结点加入到左子树的右子树中。1调整规则:ABBLARCCLCR先左