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

《c++与数据结构课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十四章查找和排序本章课件制作：吴虎统第三部分数据结构基础本章内容查找排序14.1查找1.查找的基本概念查找：在数据元素集合(查找表)中查找关键字与给定值相等的数据元素。关键字：数据元素中的一个或多个数据项值，它可以惟一标识一个数据元素。平均查找长度(ASL)：式中，n为查找表的长度；pi为查找第i个元素的概率，在等概率情况下pi等于1/n；Ci为找到第i个元素时的比较次数2.顺序查找基本思想：用给定值依次与线性表中每个元素的关键字进行比较。如果某个元素的关键字与给定值相同，则查找成

2、功；如果找遍全表也没有发现满足条件的元素，则查找失败。要求：查找表必须采用线性表。实现一：顺序表类中实现顺序查找的成员函数实现二：单链表类中实现顺序查找的成员函数顺序查找的平均查找长度评价：在用顺序查找方法完成查找时，每进行一次成功查找需要的平均比较次数约为表长度的一半，因此，它的效率较低。适用于在查找表较小的情况下进行查找。3.二分查找要求：查找表必须采用线性表；必须以顺序方式存储线性表；线性表中所有数据元素必须按照关键字有序排列基本思想：将给定值与处于顺序表“中间位置”上的元素的

3、关键字进行比较，若相等则查找成功，若给定值大于关键字则在表的后半部分继续进行二分查找，否则在表的前半部分继续进行二分查找。如此进行下去直至找到满足条件的元素，或当前查找区为空，此时查找失败。演示：例子：二分查找函数模板及其测试程序优点：查找效率高平均查找长度缺点：查找前要将表中元素按关键字有序排列只适用于线性表的顺序存储。适用于那种一经建立就很少改动而又经常需要查找的线性表。4.分块查找要求：查找表必须采用线性表；待查找的线性表分成若干块。在每一块内，元素的存放是任意的，但在块与块之间元素的存放

4、是有序的，即前一块中任意一个元素的关键字值都必须小于（或大于）后一块中所有元素的关键字值；建立一个索引表，索引表中的每个索引项对应于一块。一个索引项至少应含有两部分信息：一是对应块中最大的关键字值；二是指向对应块中第一个元素的指针基本思想：首先在索引表中查找，确定出要查找的元素应该在哪一块中；然后在已确定的那一块内进行顺序查找。演示：优点：块内元素是任意存放的，插入或删除运算不会造成元素的大量移动。缺点：增加了存放索引表的辅助空间及初始时对线性表分块排序的运算大量的插入和删除运算可能会导

5、致各块中元素的数目很不均匀，这会降低查找速度平均查找长度：将长度为n的线性表均匀地划分成ｂ块，每块中有ｓ个结点，即ｂ＝ｎ／ｓ。假定对表中每个元素的查找概率相等，则查找某一块的概率为１／ｂ，查找块中某个结点的概率为１／ｓ□索引表使用顺序查找：□索引表使用二分查找：5.二叉排序树查找二叉排序树的定义：二叉排序树或者是一棵空二叉树，或者是具有以下性质的二叉树：1、若它的左子树非空，则左子树上所有结点的值均小于根结点的值；2、若它的右子树非空，则右子树上所有结点的值均不小于根结点的值；3、左、右子树

6、本身又各是一棵二叉排序树。插入操作：若二叉排序树为空，则新结点为二叉排序树的根结点；否则将新结点的关键字值和根结点的关键字值进行比较，若小于根结点的值，则将新结点插入到左子树中去，否则，插入到右子树中去。此插入过程是递归进行的。设有整数序列{47,23,56,15,26,89},将其中的值依次插入二叉排序树568947231526删除操作：一个结点被删除后，必须保证余下的结点仍然构成一棵二叉排序树。下面分两种情况讨论：情况一：被删除的结点至少有一棵空子树方法：使被删结点的那棵非空子树的根成

7、为其双亲结点的相应子女50302510153533375362605553625550301015353337情况二：被删除的结点有两棵非空的子树方法一：找到被删除结点在中序遍历序列中的直接后继结点（它一定在被删除结点的右子树中），用此后继结点的值取代被删除结点的值，然后删除此后继结点，由于被删除的后继结点的左子树一定是空子树，所以删除后继结点的过程同情况一。方法二：用被删除结点在中序遍历序列中的直接前驱结点（该结点的右子树也一定为空）代替被删除的结点，然后删除这个前驱结点。5030101535

8、3337536255533010153533376255373010153533536255后继结点前驱结点将结点50删除中序遍历：5030101535333753625510153033353750535562查找操作：对二叉排序树进行中序遍历可以得到一个数据元素由小到大的有序序列。构造二叉排序树的过程即为对无序序列进行排序的过程。查找思路：当二叉排序树不为空时，将给定值与根结点的值进行比较，若相等则查找成功。如果给定值小于根结点的值，则在根结点的左子树中继续查找，否则在根结点的右子树中