c++与数据结构ppt课件.ppt

,第十四章 查找和排序,本章课件制作：吴虎统,第三部分 数据结构基础,本章内容, 查找 排序,14.1 查找,1. 查找的基本概念, 查找：在数据元素集合(查找表)中查找关键字与给定值相等的数据元素。 关键字：数据元素中的一个或多个数据项值，它可以惟一标识一个数据元素。 平均查找长度(ASL)：,式中，n为查找表的长度；pi为查找第i个元素的概率，在等概率情况下pi等于1/n； Ci为找到第i个元素时的比较次数,2. 顺序查找, 基本思想：用给定值依次与线性表中每个元素的关键字进行比较。如果某个元素的关键字与给定值相同，则查找成功；如果找遍全表也没有发现满足条件的元素，则查找失败。, 要求： 查找表必须采用线性表。, 实现一：顺序表类中实现顺序查找的成员函数, 实现二：单链表类中实现顺序查找的成员函数, 顺序查找的平均查找长度, 评价：在用顺序查找方法完成查找时，每进行一次成功查找需要的平均比较次数约为表长度的一半，因此，它的效率较低。适用于在查找表较小的情况下进行查找。,3. 二分查找,要求： 查找表必须采用线性表；必须以顺序方式存储线性表；线性表中所有数据元素必须按照关键字有序排列, 基本思想：将给定值与处于顺序表“中间位置”上的元素的关键字进行比较，若相等则查找成功，若给定值大于关键字则在表的后半部分继续进行二分查找，否则在表的前半部分继续进行二分查找。如此进行下去直至找到满足条件的元素，或当前查找区为空，此时查找失败。,演示：,例子：二分查找函数模板及其测试程序,优点： 查找效率高平均查找长度,缺点： 查找前要将表中元素按关键字有序排列只适用于线性表的顺序存储。适用于那种一经建立就很少改动而又经常需要查找的线性表。,4. 分块查找,要求： 查找表必须采用线性表；待查找的线性表分成若干块。在每一块内，元素的存放是任意的，但在块与块之间元素的存放是有序的，即前一块中任意一个元素的关键字值都必须小于（或大于）后一块中所有元素的关键字值；建立一个索引表，索引表中的每个索引项对应于一块。一个索引项至少应含有两部分信息：一是对应块中最大的关键字值；二是指向对应块中第一个元素的指针, 基本思想：首先在索引表中查找，确定出要查找的元素应该在哪一块中；然后在已确定的那一块内进行顺序查找。, 演示：, 优点：块内元素是任意存放的，插入或删除运算不会造成元素的大量移动。, 缺点：增加了存放索引表的辅助空间及初始时对线性表分块排序的运算大量的插入和删除运算可能会导致各块中元素的数目很不均匀，这会降低查找速度, 平均查找长度：将长度为n的线性表均匀地划分成块，每块中有个结点，即。假定对表中每个元素的查找概率相等，则查找某一块的概率为，查找块中某个结点的概率为, 索引表使用顺序查找：, 索引表使用二分查找：,5. 二叉排序树查找, 二叉排序树的定义：二叉排序树或者是一棵空二叉树，或者是具有以下性质的二叉树：1、若它的左子树非空，则左子树上所有结点的值均小于根结点的值；2、若它的右子树非空，则右子树上所有结点的值均不小于根结点的值；3、左、右子树本身又各是一棵二叉排序树。, 插入操作：,若二叉排序树为空，则新结点为二叉排序树的根结点；否则将新结点的关键字值和根结点的关键字值进行比较，若小于根结点的值，则将新结点插入到左子树中去，否则，插入到右子树中去。此插入过程是递归进行的。, 设有整数序列47,23,56,15,26,89,将其中的值依次插入二叉排序树,56,89,47,23,15,26, 删除操作：,一个结点被删除后，必须保证余下的结点仍然构成一棵二叉排序树。下面分两种情况讨论：,情况一：被删除的结点至少有一棵空子树,方法：使被删结点的那棵非空子树的根成为其双亲结点的相应子女,情况二：被删除的结点有两棵非空的子树,方法一：找到被删除结点在中序遍历序列中的直接后继结点（它一定在被删除结点的右子树中），用此后继结点的值取代被删除结点的值，然后删除此后继结点，由于被删除的后继结点的左子树一定是空子树，所以删除后继结点的过程同情况一。,方法二：用被删除结点在中序遍历序列中的直接前驱结点（该结点的右子树也一定为空）代替被删除的结点，然后删除这个前驱结点。,后继结点,前驱结点, 将结点50删除, 中序遍历：,10,15,30,33,35,37,50,53,55,62, 查找操作：,对二叉排序树进行中序遍历可以得到一个数据元素由小到大的有序序列。构造二叉排序树的过程即为对无序序列进行排序的过程。,查找思路：,当二叉排序树不为空时，将给定值与根结点的值进行比较，若相等则查找成功。如果给定值小于根结点的值，则在根结点的左子树中继续查找，否则在根结点的右子树中继续查找。当待查找的二叉排序树为空时，查找失败。,平均查找长度：,在二叉排序树中查找成功时走过的是一条从根结点到所寻找结点的一条路径，因此，二叉排序树查找的平均查找长度取决于二叉排序树的深度。, 二叉排序树的蜕变：,二叉排序树是动态生成的，它的形态与各结点插入二叉排序树时的先后顺序有关。当把一组有序值依次插入到一棵二叉排序树时，生成的二叉排序树将蜕变成一棵单支树。例如，由整数序列15,23,26,47,56,89 生成的二叉排序树就是一棵单支树。在单支树中查找时，平均查找长度与顺序查找相同。,6. 哈希查找, 哈希存储(哈希表)：,以数据元素的关键字k为自变量，通过一定的函数关系h(称为哈希函数或散列函数)计算出对应的函数值h(k)，把这个值解释为数据元素的存储地址并把数据元素存储到相应的存储单元内。h(k)称为哈希地址。, 冲突：,若有两个不同的关键字ki和kj，即ki kj(i j)。但h(ki)=h(kj)，这种情况称为冲突。如上例的关键字85和49，其对应的哈希地址都为1，即产生冲突。,例：设有一组关键字值85,72,49,58,15,70,90,38，哈希函数h(k) = k mod 12。则对应的哈希地址为1,0,1,10,3,10,6,2, 采用哈希技术要解决的两个主要问题：,构造一个好的哈希函数，使出现冲突的机会尽可能少些；,设计一个有效的解决冲突的办法, 哈希函数的构造方法,构造哈希函数要考虑以下几点,1) 哈希函数的定义域必须包括要存储的数据元素的全部关键字; 而如果散列表允许有 m 个地址，则哈希函数的值域必须在 0 到 m-1 之间,2)由哈希函数计算出的地址应均匀分布在散列地址空间内,3)哈希函数应该是简单的，能在较短时间内计算出结果,直接定位法,取关键字的某个线性函数作为哈希函数，即h(k)=ak+b。其中，k为关键字，a、b为常数。,常用哈希函数,数学分析法,当关键字的位数比存储区域地址码的位数多时，可以取关键字中位值分布比较均匀的若干位作为哈希函数的值。这种方法适合于所有关键字为已知的情况。,除留余数法,选择一个适当的正整数p (p通常选为不大于哈希表长度 m 的最大素数），用p去除关键字，取其余数作为哈希地址，即h(k)=k%p (pm)。, 解决冲突的方法：开放地址法和链地址法,开放地址法,当冲突发生时形成一个地址序列，按序列顺序逐个检查各地址单元，直至找到一个未被占用的单元为止，将发生冲突的数据元素存入该地址单元中。,线性探查序列,平方探查序列,设哈希表的长度是m，发生冲突的地址是d,d+1, d+2, , m-1, 0, 1, , d-1,(d+12)%m, (d-12)%m, (d+22)%m, (d-22)%m, ,例1,线性探查法建立哈希表,设哈希表的长度11，哈希函数是h(k) = k % 11，将整数序列54,77,94,89,14,45,76存入哈希表。按平方探查法处理冲突,例2,0,1,2,3,4,5,6,7,8,9,10,54,77,94,89,54 % 11 = 10,77 % 11 = 0,94 % 11 = 6,89 % 11 = 1,14 % 11 = 3,45 % 11 = 1 (冲突),76 % 11 = 10 (冲突),14,45,76,链地址法,将哈希地址相同的数据元素存储到同一个单链表中，哈希表中的每个存储单元中不再存放数据元素而是存放相应单链表的头指针,14.2 排序,1. 排序的基本概念, 排序：将文件中的记录按排序码非递减(或非递增)的顺序重新排列, 排序码：数据元素中的一个或多个数据项。排序码可以是关键字，也可以是其他若干数据项的组合。, 排序算法的稳定性：如果在待排序的元素序列中，存在着多个排序码相同的元素，按照某种排序算法排序后，这些元素的相对位置仍保持不变，则称该排序算法是稳定的，否则就是不稳定的。,2. 插入排序, 基本思想：把元素ei(0in) 依次插入到由S中前i个元素组成的已经排好序的序列e0, e1, ,ei-1的适当位置上，插入后S的前i+1个元素仍为有序。, 直接插入排序：,以顺序查找的办法找到要插入的元素在已排好序的元素序列中应处的位置。所有元素分成2个集合：已排序记录集和待排序记录集。初始时，已排序记录集只有一个元素，即e0，待排序记录集是所有剩余元素。然后每次从待排序记录集中选取一个元素，使用顺序查找的方法，找到其在已排序记录集中的位置，将其插入到该位置，直到待排序记录集为空。, 例：,待排序记录为50,20,75,34,40,34,40,75,20,50, 直接插入排序的函数示例：, 算法分析：,直接插入排序的平均时间复杂度是O(n2),直接插入排序是稳定的排序算法,对于一个长度较短、接近有序的序列，直接插入排序是十分有效的,在插入ei时，e0, e1, , ei-1是一个有序序列，所以可以用二分查找法寻找ei的插入位置，从而减少比较次数。二分插入排序是稳定的排序算法，其平均时间复杂度仍是O(n2), 二分插入排序：,3. 选择排序, 基本思想：把元素ei(0in) 依次插入到由S中前i个元素组成的已经排好序的序列e0, e1, ,ei-1的适当位置上，插入后S的前i+1个元素仍为有序。,在初始时，已排好序的元素序列为空，待排序的元素序列中包括了需要排序的所有元素, 直接选择排序：,基本思想：用逐个比较的办法从待排序的元素序列中选出最小的元素。依次对i=0, 1, 2, ,n-2分别执行如下的选择和交换步骤：在元素序列ei, ei+1, , en-1中选择出最小的元素ek；当ki时，交换ei与ek的值。经上述n-1次的选择和交换后，排序工作即已完成。,直接选择排序函数模板：,直接选择排序算法是不稳定算法，其平均时间复杂度为O(n2), 演示：, 树形选择排序：,基本思想：首先对n个待排序元素的排序码两两进行比较，得到 个比较的优胜者（排序码较小者），然后对这些优胜者再进行两两比较，如此反复，直至选出排序码最小的元素。在下一步选择排序码为次小的元素时，只需把树当中与已选出元素对应的叶结点的值设置为最大（），并从该叶结点开始和其兄弟结点进行比较，修改从该叶结点到根结点路径上各结点的值，即可选出排序码次小的元素。,算法的时间复杂度O(nlog2n)，该算法是稳定的。, 堆排序：,基本思想：首先，用需要排序的元素的排序码构造一个堆（称为建堆），这样就可以找到排序码最小的元素，将其取出；然后，用剩下的排序码继续建堆。如此反复进行直至全部元素有序。,堆是一棵完全二叉树，其中每个分支结点的值均小于或等于左、右子女的值。位于堆顶位置的结点（即完全二叉树的根结点）的值是最小的。,堆排序的关键步骤有两个：一是建立初始堆；二是在取出堆顶后把剩余的结点调整为堆。,首先，把所有元素的排序码组织到一棵完全二叉树中。然后从完全二叉树中结点编号排在最后的那个分支结点km( )开始，逐步地把以km、km-1、km-2为根的子树建成堆，最后，当以k0（k0是完全二叉树的根结点）为根的完全二叉树也是堆时，整个建堆过程也就完成了。,建立初始堆：,考虑以ki为根的子树，设ki的左、右子树均已是堆。为将该子树也调整为堆，只需将ki与其左子女k2i+1和右子女k2i+2进行比较。如果kik2i+1且kik2i+2，则以ki为根的子树已经是堆。否则，将ki与其最小的那个子结点（不妨设为k2i+1）交换位置。交换后，在以ki为根的子树中，除了与其交换位置的子树外，其余部分均满足堆的定义，而以k2i+1（其值由于与ki交换已发生了变化）为根的子树的左、右子树原来已经是堆，这样可使用前述过程将以k2i+1为根的子树调整为堆。如此递推下去，即可完成建堆工作。,建立初始堆示例：,无需交换,取出堆顶后将剩余结点调整为堆：,堆建成后，从堆顶取走值最小的结点，然后将最后一个结点kn-1提升到根结点的位置上，得到一棵新的完全二叉树。虽然这棵二叉树可能不是堆，但其左、右子树都是堆。因此，当把此二叉树调整为堆时，只需从根结点开始自上而下地进行调整即可。,具体示例见教材图14.10,子树调整为堆的模板函数：,演示, 算法分析：,堆排序算法的时间复杂度为O(nlog2n),堆排序算法是不稳定的,如果需要排序的元素数目较少一般并不提倡使用堆排序算法，但如果元素数目较多，堆排序算法还是很有效的, 冒泡排序：,设待排序的元素序列为S=e0, e1, , en-1，要求按升序排列,基本思想：从待排序记录集的一端（这里假定为低端）对相邻的两个元素（e0和e1，e1和e2，en-2和en-1）依次比较它们的排序码，若不符合排序的顺序要求，就将相应的两个元素互换，此过程称为一趟冒泡排序，最多经过n-1趟冒泡排序，排序工作即可完成。,每趟排序的结果是将待排序记录集中排序码最大的元素交换到待排序记录集最后一个元素的位置。假设在一趟冒泡排序时，从ej+1以后没有发生元素的互换，则说明ej+1以后的元素是已经排好序的，下面只需要在e0到ej范围内进行新一趟的冒泡排序，即待排序记录集是从e0到ej，下一趟只需从e0到ej范围内进行。,第一趟排序结束,第二趟排序结束,冒泡排序函数模板：, 算法分析：,最好情况下的时间复杂度为O(n)。若待排序元素序列已经有序，则排序工作经一趟处理就可结束。此时，对元素排序码的比较次数为最小值n-1，且没有元素的互换。,最坏情况下的时间复杂度为O(n2)。若待排序元素序列为逆序，则需要进行n-1趟冒泡。每趟要进行n-i-1次排序码的比较和n-i-1次元素的互换,冒泡排序算法是稳定的, 快速排序：,基本思想：从待排序的个元素中任取一个元素，以该元素为基准，用交换的方法将剩下的元素分成两组。第组中各元素的排序码均小于或等于基准元素的排序码；第组中各元素的排序码均大于基准元素的排序码。把基准元素放到两组元素之间（这也是基准元素在最后排好序的元素序列中的最终位置）。以上过程称为一趟快速排序（或一次划分）。,对划分出的两组元素重复上述过程，直到所有元素都排列到最终位置为止。,71,38,15,78,基准,61,45,33,69,40,52,一趟排序结束,实现快速排序的函数模板：, 算法分析：,最坏的时间复杂度为O(n2)，最好的时间复杂度为O(nlog2n)。平均时间复杂度也是O(nlog2n)，具体分析 见教材,目前基于比较的排序算法中速度最快的，快速排序算法是不稳定的,C+标准库中的函数模板采用的是快速排序算法,