数据结构课件第八章查找.ppt

哈希查找算法实现 用线性探测再散列法处理冲突实现查找过程：同前删除：只能作标记，不能真正删除插入：遇到空位置或有删除标记的位置就可以插入算法描述：用外链表处理冲突算法第69页,共73页，星期六，2024年，5月7.5应用举例

例7．11画出对长度为10的有序表进行二分查找的判定树，并求其等概率时查找成功的平均查找长度。10个有序整数的序列为(10，20，30，40，50，60，70，80，90，100)。对应的二分查找的判定树如图7.12所示。判定树共四层，第一层表示比较一次可查到的结点有一个，第二层表示比较两次可到的结点有两个，第三层表示比较三次可查到的结点有四个，第四层表示比较四次可查到的结点有三个。计算等概率时查找成功的平均查找长度为(1+2+2+3+3+3+3+4+4+4)／10＝29／10。第70页,共73页，星期六，2024年，5月图7.12图7.13第71页,共73页，星期六，2024年，5月?例7.12已知一长度为12的关键字序列(Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec)，(1)试按表中元素的次序建立一棵二叉排序树，画出此二叉排序树，并求在等概率情况下查找成功的平均查找长度。(2)对上面的二叉排序树进行中序遍历，获得一有序表，求在等概率情况下对此有序表进行二分查找时查找成功的平均查找长度。此题中的关键字是字符串，比较关键字需按英文字母在ASCII码表中的编码大小进行比较。以此原则建立的二叉排序树如图7.13所示。计算等概率情况下查找成功的平均查找长度，将查找每个记录需要比较关键字的次数相加除以记录个数即得，为(1+2+2+3+3+3+4+4+4+5+5+6)／12＝42／12。第72页,共73页，星期六，2024年，5月对上面的二叉排序树进行中序遍历，获得的有序表为(Apr，Aug，Dec，Feb，Jan，Jul，Jun，Mar，May，Nov，Oct，Sep)，对此有序表进行二分查找时，求在等概率情况下查找成功的平均查找长度，其方法与上题中描述的方法一样，为(1+2+2+3+3+3+3+4+4+4+4+4)／12=37／12。第73页,共73页，星期六，2024年，5月例如，由结点关键字序列（62,15,68,46,65,12,57,79,35）构造二叉排序树的过程为：从空二叉树开始，依次将每个结点插入到二叉排序树中插入，在插入每个结点时都是从根结点开始有哪些信誉好的足球投注网站插入位置，找到插入位置后，将新结点作为叶子结点插入，经过9次的查找和插入操作，建成由这9个结点组成的二叉排序树。创建二叉排序树的算法如下：Bin_Sort_Tree_Node*bt_bulid(Bin_Sort_Treea,intn){//在数组a的a[1]~a[n]单元中存放着将要构成二叉排序树的n个结点内容第37页,共73页，星期六，2024年，5月bt=NULL;for(i=1;i=n;i++){p=(Bin_Sort_Tree_Node*)malloc(sizeof(Bin_Sort_Tree_Node));p-key=a[i].key;p-otheritem=a[i].otheritem;;p-lchile=NULL;p-rchile=NULL;bt_insert1(bt,p);}return(bt);}第38页,共73页，星期六，2024年，5月7.3.4二叉排序树的删除在一棵二叉树上，删除其中某个结点将隔断其祖先和子孙的关系，因此在二叉树的抽象数据类型的定义中只有删除一棵子树的基本操作，而没有删除一个结点的基本操作。而对二叉查找树而言，由于它表示的是动态查找表，因此可以并有必要进行删除一个结点的操作。第39页,共73页，星期六，2024年，5月下面分四种情况讨论一下如何确保从二叉树中删除一个结点后，不会影响二叉排序树的性质：（1）若要删除的结点为叶子结点，可以直接进行删除。（2）若要删除结点有右子树，但无左子树，可用其右子树的根结点取代要删除结点的位置。（3）若要删除结点有左子树，但无右子树，可用其左子树的根结点取代要删除结点的位